51–60 of 419 posts
Given everyone's interest in the topic, can I also share something I wrote under "accidentally quadratic"? I think people might enjoy reading it: https://news.ycombinator.com/item?id=26337913 It turns out that multi-pass algorithms in general can be quite susceptible to this issue, and it can be far from obvious in general.
Move things around or just use a cache... and instant 1000%+ speedup.
I've seen this too many times to count, often in apps and on sites that are in fairly heavy use.
The answer is often to scale up and pay for 10x more server capacity to handle the load, rather than spend some time optimizing the slow code paths.
Blog author here! Thanks to HN for warning me about sscanf at exactly the right time – within a day of me trying to load some ASCII STLs and noticing it was slow... Linked deep in the Twitter replies [1], there's an open glibc issue about this, dating back to 2014: https://sourceware.org/bugzilla/show_bug.cgi?id=17577 C doesn't have any requirements on the complexity of sscanf, so it might not be a bug per se, but it…
Pro tip: the classic recursive approach to implementing the Fibonacci sequence exhibits eye-wateringly poor performance.
Looped algorithms generally outperform recursive algorithms.
(They're just more general, you can always implement a loop based algorithm using gotos, but not the other way around)
I 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…
I maintain my original position that sscanf calculating the entire length of its input is absolutely ridiculous. Are *scanf difficult to use safely, not very robust, and somewhat baroque? Yes. Should sscanf("%f") be a correct (not performance-killing) way of reading floats? Also yes. (Though aside: the OP seems to be reading data from files, so they could have just used fscanf, which has correct performance already.)
Unfortunately, many libcs are guilty of this:
- glibc uses memchr (the trail is convoluted, but ends up at _IO_str_init_static_internal)
- freebsd libc (and thus also the apple and android libcs, as well as those of the other BSDs) use strlen
- uclibc and newlib are the same as freebsd (appear to be copied directly from it)
- Since the original bug was in GTA, which only runs on windows, I must presume msvcrt has the same problem
- musl has the correct behaviour, processing input in 128-byte chunks
- managarm doesn’t strlen but looks broken for unrelated reasons. (Assumes nul byte means eof.) Also has codebloat because of templates.
- serenityos tries to implement fscanf in terms of sscanf, not the other way around! Unfortunately that means it chomps a whole line of input at every call, so it doesn’t even work correctly. Horrifying.
- pdclib has ok performance, but with an interesting implementation: it duplicates code between sscanf and fscanf, though the heavyweight format parsing is shared.
- dietlibc and sortix have the sensible, simple implementation
I don't think anyone sensible would claim they would never have made this mistake. It's not even surprising that it made it to production. What is surprising is that it lead to a massive and easily-diagnosable slowdown that no one bothered to fix for several years.
I'd bet that some combination of "Oh, of course it's slow, it's json" and "I'm too important to work on microtransactions" accounts for a lot it.
By that point R* developers had moved on to other projects and the artists may have used a different workflow to validate things and never bothered booting up the "real" game to test things.
The expected code would do something closer to this:
len = strspn(s, "0123456789INFTYAEBCDXPinftyaebcdxp-+.");
That would be optimized to use a bitmap.
Earlier quoted context omitted.
Or use the closed-form solution.
The "closed-form solution" is slower than standard method. It just uses arbitrary-precision fractional arithmetic (square root, exponentiation, division) instead of arbitrary-precision integer arithmetic (exponentiation of a 2x2 integer matrix).