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 time would have made it onto someone’s radar?
It Can Happen to You
41–50 of 419 posts
Re: It Can Happen to You
#42"it will open a 97 MB binary STL file in about 165 milliseconds flat, on a 2013 Macbook Pro. This is blinding fast." This actually sounds incredibly slow, that's nearly 1/5th of an entire second. What can it possibly be doing? :) In case anyone else was wondering, I followed the link and clicked the description and this is actually based on the time to the first frame being rendered - not just the time to load the fi…
How can loading a file be infinitely fast? There is latency to receive the first byte from loading the file.
Re: It Can Happen to You
#43The 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.
There's also an entire book on using lex and yacc.
Re: It Can Happen to You
#44It would be nice if it were more common for standard library functions to include algorithmic complexity as part of the standard documentation. Absent that, of course we can potentially read the source code and find out, but I think for the most part we tend to operate based on an informed assumption about what we imagine the algorithmic complexity of a given operation would be. Inevitably, sometimes the assumption i…
Keeping track of algorithmic complexity would be nice as a language and/or static analysis feature. If you wanted to be exact or do it for a language with complex metaprogramming I assume it would be a nightmare to implement. Absent those complications and especially if you always reduced it to O(1), O(n), O(log(n)), etc it might not even be that difficult given the potential advantages.
The difficulty here is "define n". And I don't mean that facetiously. You have a string parsing lib. It is, for reasons, quadratic over the number of strings parsed, and linear per string.
This is overall n^3, but that's meaningless because there actually isn't just one n. So, more m^2 * n. That means you can't reduce it to anything, because you want to keep both components. (Because, say, you know it will only ever be called with a single string).
But then, in the next app, this gets called and reinitialized once per file. And the routine handling files, for reasons beyond our ken, is (n lg n). We're now at k * log(k) * m^2 * n.
And so, over any sufficiently long call chain, "what is n" is the overriding question - string length, number of strings, number of files? Not "how complex is the algorithm", because you want to optimize for what's relevant to your use case.
Re: It Can Happen to You
#45I 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 don't find it that surprising because there's a huge lack of awareness in the industry when it comes to profiling tools. Quite often I've seen people trying to speed up programs without once profiling to see where the problem is. More than once I've seen the supposed solution (usually caching or distributing in my line of work) actually slow things down. At times it can be almost impossible to get permission to "waste" time on performance profiling because it's not fixing bugs or adding features.
I kind of expected more from game developers, but I doubt the guys shaving micro second off tight game loops are the same ones writing the asset loading code.
Devs should follow carpentry rules for this: measure twice, cut once.
Re: It Can Happen to You
#46"it will open a 97 MB binary STL file in about 165 milliseconds flat, on a 2013 Macbook Pro. This is blinding fast." This actually sounds incredibly slow, that's nearly 1/5th of an entire second. What can it possibly be doing? :) In case anyone else was wondering, I followed the link and clicked the description and this is actually based on the time to the first frame being rendered - not just the time to load the fi…
From my experience creating loaders for 3D formats (FBX, glTF, LWO) it's not loading the file that takes a long time, it's parsing the data in the file and converting it to a suitable format for rendering in OpenGL. In practice, most people use the terms "parsing" and "loading" interchangeably, or "loading" means "reading + parsing file".
There can be a lot of processing involved (looking at you FBX) or less (glTF, probably STL) but there's still going to be at least decompressing the binary data and copying it into buffers then uploading those to the GPU. So, without knowing how STL binary is specified, parsing 97mb in 165ms seems reasonable.
Re: It Can Happen to You
#47Blog 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…
Hey, Matt, neat to see you here and congrats on making the front page!
Recognize you from the Formlabs forums & conferences.
Love that notion of professional empathy underscoring your message in the blog post.
Re: It Can Happen to You
#48Re: It Can Happen to You
#49Earlier quoted context omitted.
And now your memory usage will grow eye-wateringly large. Instead, convert the algorithm to be iterative or at least tail-recursive and it will be faster than both the naive and memoized versions!
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).
Re: It Can Happen to You
#50Given 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.