Bugs happen to everyone, all the time - correctness bugs and performance bugs.
On the other hand - if you write parsing code and completely ignore the cost of functions, then, well, you sort of had it coming.
It Can Happen to You
211–220 of 419 posts
Re: It Can Happen to You
#212Earlier quoted context omitted.
For me the moral of the story is do not use (whatever)scanf() for anything other than toy programs. In most cases implementing your own tokenizer (for both of these cases of reading numbers that involves str(c)spn() to get length of candidate token and then strtosomething()) is significantly easier than reasoning about what scanf() really does (even ignoring accidentally quadratic implementation details) and whether…
Can you ELICSUndergraduate. Tokenizing is normally for if you're writing a compiler of DSL right?
Yes. But any data format you read, particularly any plaintext data format you read, is essentially interpreting or compiling a DSL. On a typical job, people are writing compilers much more often than they think!
Re: It Can Happen to You
#213Earlier quoted context omitted.
Don't roll your own parser? How the hell would you get anything done? Unless you don't count regular expressions or something, I can't imagine somehow avoiding problems requiring parsers, especially on any unix-based system.
There are a lot of tasks that only need to work with existing, commonplace file formats with existing high-quality parsers (e.g., JSON, XML, sqlite, ...).
SQLite I can grant you, but I'm starting to get a bit worried about certain XML parser popular in C/C++ land. Might do a swing at it with a profiler later today.
Re: It Can Happen to You
#214The moral of the story, as far as I'm concerned: do NOT parse strings in C! Use a library, prefferably in a higher-level language. C string handling is a mess of viciously surprising APIs, juggling those particular footguns is almost certainly not your least bad option.
I've taken it a step further (or three). I'm building a whole computer on the principle[1] (one possible way of looking at it) of avoiding parsing as far as possible. https://github.com/akkartik/mu Mu takes the dwm[2] principle of avoid-config-files/modify-sources-to-reconfigure to the limit. The idea is that there are at any given time only 3 languages in the computer: 1. A self-hosted notation for a subset of 32-bi…
Hi, level 1 and 2 looks really cool, but I may not understand the point of only having these languages “running” on a computer? Both 2 and 3 are interpreted and the interpreter is the area you want to minimize?
What about a program written in 3 that can compile to either 1 or 2? Why would it hurt anything to have a different language somehow made possible to run here?
Re: It Can Happen to You
#215The reward system of my brain wants me to write clever code to solve the "core" problem. The remaining 80-99.999% (depending on the environment) of the code - authentication & authorization, logging, parsing, I/O, ensuring that the program is "well behaved" - all that is perceived as "boring", "boilerplate", "glue code", which results in churning out code that is not thought through.
So yes, that code probably contains some bugs from the "stupid if you think about it for a second" category.
Re: It Can Happen to You
#216Earlier quoted context omitted.
For me the moral of the story is do not use (whatever)scanf() for anything other than toy programs. In most cases implementing your own tokenizer (for both of these cases of reading numbers that involves str(c)spn() to get length of candidate token and then strtosomething()) is significantly easier than reasoning about what scanf() really does (even ignoring accidentally quadratic implementation details) and whether…
Can you ELICSUndergraduate. Tokenizing is normally for if you're writing a compiler of DSL right?
It is a general term for the process of breaking a string into "tokens" which have a sort of meaning. Definitely a common task in compilers, but not limited to it.
Re: It Can Happen to You
#217Earlier quoted context omitted.
> 203 is enough to make almost every line of code questionable. The result of this is that looking at a simple 3 line C program and being asked whether the program terminates is undecidable without knowing which compiler was used. This is hyperbole to the point of being nonsensical. > Null dereference for example is undefined behavior, and could cause a termination or not, depending on the implementation, even if it…
> If your C code has UB, it is wrong. This goes against the sheer notion of UB. If some code was wrong, the standard would say it is not allowed and it would result in a compile error, or at least a runtime error. As it is, the language standards choose to leave it open almost as if to concede that the standard can’t cover every base. UB isn’t wrong, almost by definition. It’s just implementation specific, and that’s…
I always though that code with UB is wrong, and UB allows implementation to deal with it on its own way (it is allowed to ignore it, stop program, corrupt memory, delete hard drive contents...).
So if your code has UB then it is wrong, one thing not specified in standard is exact consequences of that.
(yes, in some hacks one may rely on UB behaving in some way in some circumstances - it will be hack)
Re: It Can Happen to You
#218I didn’t follow the original story or comments about GTA, but based on the description in this article, I wouldn’t be surprised that this sort of problem could happen to any coder of any experience level and I wouldn’t give them any grief, but I would be surprised that the problem would be live in production for a very long time without ever having been profiled. Surely seeing JSON parsing taking more than 70% of the…
You'd be surprised. In the companies I worked for so far, it's usually my radar that bleeped over ridiculously inefficient code that was present for years in the codebase. That is, some developers would be aware something is off with performance, but they didn't bother to do anything about it. Hell, sometimes even management would know users complain about performance, but the feedback didn't percolate down to developers.
Sure, I get priorities and "good enough". But really, about half of the order-of-magnitude wins in performance I achieved were on things you could find and fix in few hours if you bothered to look. The other half tends to be unfortunate architectural decisions that may take a few days to fix, so I get why those don't get done.
Re: It Can Happen to You
#219This just makes me think that null-terminated strings are the bad gift that keeps on giving. If we were to design an OS, language, or standard library in 2021 (or even 1999) we probably wouldn't use them, but we're stuck with this relic of a former era.
The thing is, they are even worse for performance than string implementations that store the length.. that extra few bits of memory is much cheaper than checking the size of a string everywhere. For example, copying a string with known length.
Also, c++’s strings even do some clever hacking where they store the text itself for shorter strings in the pointer, barring a pointer lookup. And this is possible only because abstraction.
Re: It Can Happen to You
#220Earlier quoted context omitted.
> assuming the map doesn't need resizing This isn't a big difficulty; it's still amortized O(1). > and there isn't a hash collision This is a real difficulty, unless you allow map resizing. Luckily, we do. > but it's generally not true in respect to the key length. OK, but in most cases the key length is constant, making anything that depends on the key length O(1) by definition.
I'm guessing GP means the complexity guarantee sidesteps the complexity of the hashing function. It probably doesn't matter all that much in typical case - I'm guessing 80-90% of hash map use is with very short strings.
Short strings, long strings; they're going to use the same key length. Calculating the key may take longer for the long string, if you're basing the hash on the contents of the string[1], but the key won't end up being a different size. The md5 of a 3-byte string is 16 bytes and the md5 of a 40GB string is also 16 bytes.
[1] Not typical. e.g. Java takes the hash key of an object to be its address in memory, which doesn't require looking at the contents.