Wouldn’t it be better to read the entire file into memory first? And then do the parsing in the next step? Would take more memory of course but if you’re trying to maximize performance.
It Can Happen to You
71–80 of 419 posts
Re: It Can Happen to You
#72Loving the progression here. Tomorrow, someone’s going to reduce the boot times of macOS by 90% by the same principle. A week from now, someone will prove P=NP because all the problems we thought were NP were just running strlen() on the whole input.
And maybe, in a decade or so, the man page for these functions will list their algorithmic complexity! That was the most interesting takeaway from this article, for me at least. I have only seen a one or two libraries that actually list this in their documentation.
Re: It Can Happen to You
#73Blog 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.
Hey RK! Thanks for the kind words – hopefully I'll see you again, once we're back to holding in-person events!
Re: It Can Happen to You
#74This 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.
Ok, let’s assume that 10mb json source was loaded into a not null-terminated opaque struct str_t {size_t; pchar;}. You have to parse a number from a position `i’ and you have (double parse_number(str_t)). Next obvious step?
Re: It Can Happen to You
#75Wouldn’t it be better to read the entire file into memory first? And then do the parsing in the next step? Would take more memory of course but if you’re trying to maximize performance.
Wouldn't matter at all, and the function in question is already operating on a string buffer. You might be able to get a minor boost by reading the file in parallel with parsing it, using async IO or threads, but it doesn't seem like the disk is actually the bottleneck here.
Re: It Can Happen to You
#76How many oss code bases using sscanf same way worth finding out? All of them can benefit from same speed gain.
Re: It Can Happen to You
#77Loving the progression here. Tomorrow, someone’s going to reduce the boot times of macOS by 90% by the same principle. A week from now, someone will prove P=NP because all the problems we thought were NP were just running strlen() on the whole input.
And maybe, in a decade or so, the man page for these functions will list their algorithmic complexity! That was the most interesting takeaway from this article, for me at least. I have only seen a one or two libraries that actually list this in their documentation.
All of the C++ algorithms list complexity guarantees, I believe. This saga stunned me to learn that C doesn’t seem to do this.
Re: It Can Happen to You
#78The 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 used to work for people that processed emails and loaded them into databases with perl scripts. One day someone asked me if I could help, because the script they were running on a batch of emails was inexplicably freezing or running out of memory, I forget the exact details.
There were maybe a few thousand or tens of thousands of emails, and so, I came to look at the issue with my usual attitude which is that if it isn't running instantly on a GHz computer of any kind, something must be horrifically wrong. Not to mention running out of memory.
It turned out that essentially every email was cc'ed to several thousand people; you know, the thread went to a whole company or something. The file size itself wasn't huge in the scheme of things, but our perl script (written by someone much more elevated that me, with a master's degree) read the whole file at once into memory, and expanded the headers to perl hashes, multiplying the size.
But there was no reason the whole thing had to be in memory. Only that people learn to program in CS 101 these days, I guess, as if memory is infinite, because gigabytes might as well be infinity, but if you multiply a certain moderate overhead times tens of thousands by tens of thousands, suddenly all your gigabytes are gone.
Another thing I remember, was when I was given a T-SQL report that typically ran on a few thousand documents, and was asked to run it on all of the millions on all our databases. It was hundreds or thousands of times too slow, but it was running a SQL statement in a procedural loop per document and it could be turned into a single statement.
So my experience has basically taught me that if something is within a factor of two of optimal, it's good enough, but an incredible amount of code, regardless of high or low level, is way worse than that.
But I've never gotten much pay or glory for fixing this sort of thing. Sometimes I daydream about being a high paid consultant who goes and turns three nested loops into two, or two into one.
Re: It Can Happen to You
#79Earlier quoted context omitted.
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…
It would be a huge step to simply follow the call tree and report the depth of nested loops for each branch. You could then check what N is at each level.
The trick is knowing where the nested loops are since they can be spread across functions.
I had a function that scaled as N^2, but it was creating a list of that size as well. Then it called a function to remove duplicates from that list. That function was N^2, which meant the whole thing was actually N^4. And now that I think of it, those loops were not nested... I rewrote the first part to no create duplicates and deleted the quadratic deduplication. Now its N^2, but it has to be.
Re: It Can Happen to You
#80"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.
Predict your access pattern and prefetch into RAM or DMA.