Live data from Hacker News

It Can Happen to You

mattkeeter.com

261–270 of 419 posts

Re: It Can Happen to You

#261
post #32

Loving 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.

I don't know if it is required to, but there doesn't really seem to be an upper bound to what glibc's scanf will eat for a %f (e.g. a gigabyte of zeroes followed by "1.5" will still be parsed as 1.5), so for that implementation there certainly isn't a trivial upper bound for the amount of input read and processed that is done for %f, like you would perhaps expect.

Yet another reason to not stringify floats. Just use hexfloats (but beware of C++ standard bugs involving >>) or binary.

Unfortunately "gigabytes of numerical data, but formatted as a text file" is commonplace. For some reason HDF5 is far less popular than it ought to be.

Re: It Can Happen to You

#262
post #27

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…

I love the format of this blog post. Perfect length. Perfect detail. You don't waste words. A good number of images.

I like this blog post but I also happen to quite like long forms like these, too: https://mango.pdf.zone/finding-former-australian-prime-minis... / https://apenwarr.ca/log/20201227

Re: It Can Happen to You

#263

Earlier quoted context omitted.

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.

I don't know if it is required to, but there doesn't really seem to be an upper bound to what glibc's scanf will eat for a %f (e.g. a gigabyte of zeroes followed by "1.5" will still be parsed as 1.5), so for that implementation there certainly isn't a trivial upper bound for the amount of input read and processed that is done for %f, like you would perhaps expect. Yet another reason to not stringify floats. Just use…

But why do strlen() at all? And why are all platforms (Linux, Windows, MacOS) seemingly doing that?

I think you're right that there is no upper bound but it shouldn't be necessary to do a full strlen() if you're instead scanning incremental. You could go char by char until the pattern '%f' is fullfilled and then return. That would solve the issue on it's root -- and who know how many programs would suddenly get faster...

So looking at glibc souces I've found the culprit in abstraction. Looks like a FILE* like stringbuffer object is created around the c-string: https://sourceware.org/git/?p=glibc.git;a=blob;f=stdio-commo...

And that abstraction does call something similiar to strlen() when initializing to know it's bounds here: https://sourceware.org/git/?p=glibc.git;a=blob;f=libio/strop...

I'm reading this source the first time, but I guess to not break anything one could introduce a new type of FILE* stringbuffer let's say in 'strops_incr.c' that is working incrementally reading one char at the time from the underlying string skipping the strlen()...

Would be awesome cool if GTA online would be loading faster under wine than on windows :-)

Re: It Can Happen to You

#264
post #32

Loving 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.

You're joking, but now I'm thinking about the XML we parse at work and the library we're using to do it. We parse a lot of it, but I've always had this vague feeling that it takes a bit too long (given the codebase is C++). The XML library we use is rather well-known, so if someone found a bug like this there, I'd suspect a general improvement of performance across the board in the entire industry. Efficient Market H…

It's possible. I've personally reduced the time spent for reading huge XML file on the startup of an application at least 10 times in the application I was in charge of, by avoiding the library dependence and writing a custom code. Having a lot of experience in such kinds of code and in the performance issues, it was quite a fast change with no negative effects.

The prehistory of that was simple: up to some point the amount of data stored was reasonably small. Then from some point on the amount of data grew significantly (a few orders of magnitude), and the startup times became very unpleasant.

There's a lot that is going on when loading huge XML files. As an example, don't forget all the possible Unicode conversions, all the possible allocations of the elements in the handling code, just to be discarded etc.

I don't suggest everybody doing it "just because" but if some specific use is known to have very specific assumptions and it is in the "hot path" and really dominates (profile first!) and it is known that only a small subset of all XML possibilities will ever be used it can be justified to avoid the heavy libraries. For example, in that specific case, I knew that the XML is practically always only read and written by the application, or by somebody who knew what he was doing, and not something that somebody random in some random form would regularly provide from the outside, and I knew that my change surely won't break anything for years to come, as I knew for sure that that part of application was not the "hot spot" of expected future changes.

So it was a win-win. Immensely faster application startup, which is something that improved everybody's work, while preserving the "readability" of that file for the infrequent manual editing or control (and easy diff).

Re: It Can Happen to You

#265
post #127

There's a bigger potential problem with the *scanf() functions than performance. They are inherently unsafe for reading numeric input. For example, if you do something like this: int n; sscanf("9999999999999999999999999", "%d", &n); the behavior is undefined. As the C standard says: > ... the result of the conversion is placed in the object pointed to by the first argument following the format argument that has not a…

> Remember that in C "undefined behavior" [...] means that a conforming implementation can do literally anything. In the worst case, it will do what what you expect until it fails at the most inconvenient possible moment. Actually, the worst case possibility is that your program will become Skynet, enslave humanity for 10000 years, collapse all stars in the universe into black holes, and significantly accelerate proc…

Programs don't need undefined behavior to do those things, you just need to wait a bit :)

Re: It Can Happen to You

#266
post #32

Loving 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.

You're joking, but now I'm thinking about the XML we parse at work and the library we're using to do it. We parse a lot of it, but I've always had this vague feeling that it takes a bit too long (given the codebase is C++). The XML library we use is rather well-known, so if someone found a bug like this there, I'd suspect a general improvement of performance across the board in the entire industry. Efficient Market H…

> it's unlikely the library has this problem

Any sufficiently-complex library code likely has plenty of problems, often unavoidably so (e.g. trade-offs between best performance and edge cases). Whether they have been found or not is a function of many, many factors.

> Efficient Market Hypothesis

I've lived long enough to be very sceptical about that sort of thing. Markets tend to be efficient in aggregate, maybe, but on the single case they can fail quite brutally. Look at how "dramatic" bugs are overlooked even in critical pieces of infrastructure like openssl, for years and years; maybe it happens less for openssl than most equivalent libraries, but it still happens.

Also, once the "market" for standards moves on, network effects make it very hard to have any meaningful competition. I mean, who writes XML parsers nowadays? Whichever XML lib was winning when JSON "happened" is now likely to stay in control of that particular segment; and the likelihood that top developers will keep reviewing it, falls off a cliff. Sprinkle a bit of cargo-cultism on top, and "efficient markets" become almost a cruel joke.

Re: It Can Happen to You

#267

Earlier quoted context omitted.

Calculating the key may take longer for the long string Right, that’s exactly what they are warning about. Not typical. e.g. Java takes the hash key of an object to be its address in memory No, that’s just the base implementation in Object (and arguably it was a bad idea). All useful “value type” classes will override it with a real hash of the content, including String. There are some cases in Java where you do want…

> All useful “value type” classes will override it with a real hash of the content Well, this is necessary for a lot of sensible things you'd want to do with non-numeric value types as hash keys... > including String ...except String is something of an intermediate case. There are loads of use cases where what you're really using is a set of constant strings, not variables that contain arbitrary character data. In th…

> Strings are immutable, so in theory it could easily be the case that any two equal Strings must share their machine address, even if you got them from user input.

Hey, and now you have two problems: String hashing and finding all strings which are equal to each other in memory

Re: It Can Happen to You

#268
I think these kind of things get caught in an organization with technically competent people that can give feedback to the product process. People who can understand from first principles how long something should last, and don't tolerate it lasting ten times as much.

Re: It Can Happen to You

#269

Earlier quoted context omitted.

> All useful “value type” classes will override it with a real hash of the content Well, this is necessary for a lot of sensible things you'd want to do with non-numeric value types as hash keys... > including String ...except String is something of an intermediate case. There are loads of use cases where what you're really using is a set of constant strings, not variables that contain arbitrary character data. In th…

> Strings are immutable, so in theory it could easily be the case that any two equal Strings must share their machine address, even if you got them from user input. Hey, and now you have two problems: String hashing and finding all strings which are equal to each other in memory

Well, no, the whole point of this discussion is that solving the second problem means the first problem never comes up.

And this isn't exactly some exotic approach; how often do you think people write Hashes in Ruby where the keys they use are all symbols? It's so common that there's dedicated syntax for it.

Re: It Can Happen to You

#270
post #32

Loving 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.

actually lolled
Post reply on HN