11 ms·

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

by johnfn 6y ago

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.

CGamesPlay 6y ago
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.
- BenFrantzDale 6y ago
  All of the C++ algorithms list complexity guarantees, I believe. This saga stunned me to learn that C doesn’t seem to do this.
  - tedunangst 6y ago
    Are there complexity guarantees for std::istream::operator>>?
    - rtpg 6y ago
      In the standard there's things like "exactly N operations", but not seeing stuff for `istream`. There's like... an explanation of how things should work and I imagine you can derive complexity from it, but I think `istream` is a bit special since you're talking about this wrapper for (potentially) an arbitrary input source. [0]: https://eel.is/c++draft/alg.move#15 https://eel.is/c++draft/alg.move#15 [1]: https://eel.is/c++draft/input.streams#istream.extractors-7 https://eel.is/c++draft/input.streams#istream.extractors-7
    - mkl 6y ago
      No, or at least not in general, because you can overload it for your custom types with whatever terrible implementation you like.
      - loeg 6y ago
        This is true in essentially the same way for C's FILE, which is the point I think Ted is insinuating.
  - 0xcde4c3db 6y ago
    It's easy to forget that the original C standards were largely codifying existing practice during an era when using gets() [1] was existing practice. The world wasn't quite ready for Ada, I guess. Best-laid plans of mice and men etc. etc.. Also, keep an eye out for "amortized" complexity. This does have a legitimately rigorous definition, but for latency-bound paths it can practically amount to "O(whatever), except for the particular invocations that are far, far worse under unspecified conditions". [1] https://www.man7.org/linux/man-pages/man3/gets.3.html#BUGS https://www.man7.org/linux/man-pages/man3/gets.3.html#BUGS
    - lostcolony 6y ago
      ...I fully plan to use "O(whatever)". Not sure for what. But, yes. (naive) Quicksort's amortized complexity being O(nlogn), but its O(n^2) on already sorted data, is all I ever needed to learn to take away that lesson. When sorting already sorted data is worse than sorting randomized data, it's a quick realization that "amortized cost" = "read the fine print".
      - nyanpasu64 6y ago
        Quicksort as O(n log n) is not amortized complexity, but average runtime for random data.
        lostcolony 6y ago
        Fair point; I'm confusing my terminology. Analogy and realization still holds.
        virgilp 6y ago
        Also, already sorted data.. in reverse order. If it's already sorted in the right order, quicksort takes linear time. This is an important difference - data you use might indeed often be appropriately sorted, but in practice will seldom be sorted in reverse order.
  - TheOtherHobbes 6y ago
    That's because C is just a wrapper for machine code on a cheap PDP-11, and cheap PDP-11s didn't have enough RAM to do complexity.
- fastball 6y ago
  Listing time complexity up top is my favorite thing about the Redis docs. https://redis.io/commands/ https://redis.io/commands/
- est31 6y ago
  The cppreference page linked by the blog post has been changed since: https://en.cppreference.com/w/cpp/io/c/fscanf#Notes https://en.cppreference.com/w/cpp/io/c/fscanf#Notes > Note that some implementations of sscanf involve a call to strlen, which makes their runtime linear on the length of the entire string. This means that if sscanf is called in a loop to repeatedly parse values from the front of a string, your code might run in quadratic time
  - TeMPOraL 6y ago
    Good. I'm so happy they put it there. It's a little thing, but such little things - documenting corner cases - can have great benefits. I have a bad memory for all but most frequently used standard library calls, so I regularly end up refreshing my memory from cppreference.com, and I tend to instinctively scan any notes/remarks sections, as there's often critical information there. So now I can be sure I'll be reminded of this the next time I need to use scanf family.
- yread 6y ago
  How would it help you knowing that it's O(n)? It needs to read all the characters of the float. Problem is that it's needlessly reading characters even after the float
- formerly_proven 6y ago
  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.
  - dominicl 6y ago
    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-common/sscanf.c;h=75daedd2aebe392e7f0d9e5d8816c1524b28f6ec;hb=HEAD#l34 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/strops.c;h=6208518cdd861b770787c3f64cbfa3b6b9fb9afd;hb=HEAD#l41 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 :-)
    - JdeBP 6y ago
      See https://news.ycombinator.com/item?id=26298300 https://news.ycombinator.com/item?id=26298300 . The alternative implementation technique that already exists in some C implementations is not to use nonce FILE objects at all.
iab 6y ago
Amazing
ineedasername 6y ago
That's actually a very simple one. Just run a regex on "P != NP" to remove the "!" and you're good to go.
- ctoth 6y ago
  Seriously the most I have laughed in like 6 months. Which probably says a lot more about me than this joke. I know that jokes aren't really welcome on HN, and I generally really like this policy. But just had to mention this was just ... what I needed to read right now.
  - koalahedron 6y ago
    > I know that jokes aren't really welcome on HN IMO, while I really don't come to HN to find dial-a-joke, or joke-of-the-day, I think some humor is essential in modern life. Since we're talking about Matt Keeter, you will find he has a great sense of humor if you read his website or interact with him. Some of his jokes are ROTFL funny, but subtle.
    - koalahedron 6y ago
      Even greater is someone understanding my own sardonic sense of humor and putting it to good use. I did have a nice half round of golf today with my wife. What a beautiful day to spend with such a wonderful person! I'm out.
xconverge 6y ago
Agreed, also hey bud, hope you are doing well
- johnfn 6y ago
  Hey, there’s a username I recognize! Long time no see! Same to you :)
  - notretarded 6y ago
    You too
TeMPOraL 6y ago
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 Hypothesis tells me it's unlikely the library has this problem, but then again, so I thought about AAA videogames, and then GTA Online thing came out.
- acqq 6y ago
  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).
  - MaxBarraclough 6y ago
mfbx9da4 6y ago
actually lolled
bsldld 6y ago
> 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 owe me a keyboard!
nightmunnas 6y ago
I don't think I've laughed this much since the pandemic started, well done.
fanf2 6y ago
Well, https://twitter.com/stephentyrone/status/1366573121365565444 https://twitter.com/stephentyrone/status/1366573121365565444 >> So many years ago when I first took over the iOS string functions, I found that like 30% of boot time in debug builds was in strstr. << >> Needless to say, we did not fix that issue by writing a more efficient strstr. Removed the parser and then removed strstr from the environment where it had been in use =) <<
eru 6y ago
You joke, but there's actually lots of work going on into what techniques will definitely NOT be enough to settle P=NP. (I find it pretty exciting, that this kind of negative result is possible. Ain't mathematics wonderful?)
coolgeek 6y ago
I just got an infinite loop down to 8.6 seconds! And I'm not done yet!
specialist 6y ago
You kid. But truer things are said in jest. > ...Tomorrow, someone’s going to reduce the boot times of macOS by 90% by the same principle. My 2019 MacBook often pauses when I connect the charging cable. Sometimes it just seizes, requiring a hard bounce. Clearly there's a contended lock buried deep. Something non-obvious. I'm certain everything these days has dozens of hidden quadratics and contended locks. Which is one of the reasons I'm excited for stuff like structured concurrency (Java's Project Loom) and retoolings like systemd becoming the norm. Ages ago I worked on kitchen sink app that had a very finicky startup. Any breeze would break it. Much consternation by mgmt. Apparently if we only clapped louder, Tinkerbell would fly. I couldn't take it any more. LARPing as a bulldozer, I replumbed the innards, changing from something like initd to be more like systemd with some lazy loading for good measure. Voila! Back to GTA. The failure here is the product owner didn't specify a max load time, and then hold the team to it. Devs will mostly do the work that's expected of them. If load time wasn't measured (and managed), no one is going to bother with expunging sscanfs.
- dcolkitt 6y ago
  > My 2019 MacBook often pauses when I connect the charging cable. Sometimes it just seizes, requiring a hard bounce. Yesterday my MBP kernel panicked because my keyboard was low on battery and the bluetooth connection kept dropping. There's something weird with MacOS where peripherals seem to really not be well isolated from the core OS runtime.
  - raihansaputra 6y ago
    Oh peripherals on newer Macs are somehow very hit or miss. I have a very difficult time with external monitors, especially from sleep. My MBP 16" would just loop between initializing and failing to initialize, until I unplug, wait, and re-plug again. Or I have to press the `Extend` option instead of the `Mirror` option that I use. The older 2015 MBP would just connect fine.
stainforth 6y ago
Next Hacktober should offer a free t-shirt to anyone who goes out and issues a PR to a repo containing sscanf
randomswede 6y ago
P = NP for "P == 0" and/or "N == 1".

by johnfn 6y ago

CGamesPlay 6y ago

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.

BenFrantzDale 6y ago
All of the C++ algorithms list complexity guarantees, I believe. This saga stunned me to learn that C doesn’t seem to do this.
- tedunangst 6y ago
  Are there complexity guarantees for std::istream::operator>>?
  - rtpg 6y ago
    In the standard there's things like "exactly N operations", but not seeing stuff for `istream`. There's like... an explanation of how things should work and I imagine you can derive complexity from it, but I think `istream` is a bit special since you're talking about this wrapper for (potentially) an arbitrary input source. [0]: https://eel.is/c++draft/alg.move#15 https://eel.is/c++draft/alg.move#15 [1]: https://eel.is/c++draft/input.streams#istream.extractors-7 https://eel.is/c++draft/input.streams#istream.extractors-7
  - mkl 6y ago
    No, or at least not in general, because you can overload it for your custom types with whatever terrible implementation you like.
    - loeg 6y ago
      This is true in essentially the same way for C's FILE, which is the point I think Ted is insinuating.
- 0xcde4c3db 6y ago
  It's easy to forget that the original C standards were largely codifying existing practice during an era when using gets() [1] was existing practice. The world wasn't quite ready for Ada, I guess. Best-laid plans of mice and men etc. etc.. Also, keep an eye out for "amortized" complexity. This does have a legitimately rigorous definition, but for latency-bound paths it can practically amount to "O(whatever), except for the particular invocations that are far, far worse under unspecified conditions". [1] https://www.man7.org/linux/man-pages/man3/gets.3.html#BUGS https://www.man7.org/linux/man-pages/man3/gets.3.html#BUGS
  - lostcolony 6y ago
    ...I fully plan to use "O(whatever)". Not sure for what. But, yes. (naive) Quicksort's amortized complexity being O(nlogn), but its O(n^2) on already sorted data, is all I ever needed to learn to take away that lesson. When sorting already sorted data is worse than sorting randomized data, it's a quick realization that "amortized cost" = "read the fine print".
    - nyanpasu64 6y ago
      Quicksort as O(n log n) is not amortized complexity, but average runtime for random data.
      - lostcolony 6y ago
        Fair point; I'm confusing my terminology. Analogy and realization still holds.
        virgilp 6y ago
        Also, already sorted data.. in reverse order. If it's already sorted in the right order, quicksort takes linear time. This is an important difference - data you use might indeed often be appropriately sorted, but in practice will seldom be sorted in reverse order.
- TheOtherHobbes 6y ago
  That's because C is just a wrapper for machine code on a cheap PDP-11, and cheap PDP-11s didn't have enough RAM to do complexity.
fastball 6y ago
Listing time complexity up top is my favorite thing about the Redis docs. https://redis.io/commands/ https://redis.io/commands/
est31 6y ago
The cppreference page linked by the blog post has been changed since: https://en.cppreference.com/w/cpp/io/c/fscanf#Notes https://en.cppreference.com/w/cpp/io/c/fscanf#Notes > Note that some implementations of sscanf involve a call to strlen, which makes their runtime linear on the length of the entire string. This means that if sscanf is called in a loop to repeatedly parse values from the front of a string, your code might run in quadratic time
- TeMPOraL 6y ago
  Good. I'm so happy they put it there. It's a little thing, but such little things - documenting corner cases - can have great benefits. I have a bad memory for all but most frequently used standard library calls, so I regularly end up refreshing my memory from cppreference.com, and I tend to instinctively scan any notes/remarks sections, as there's often critical information there. So now I can be sure I'll be reminded of this the next time I need to use scanf family.
yread 6y ago
How would it help you knowing that it's O(n)? It needs to read all the characters of the float. Problem is that it's needlessly reading characters even after the float
formerly_proven 6y ago
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.
- dominicl 6y ago
  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-common/sscanf.c;h=75daedd2aebe392e7f0d9e5d8816c1524b28f6ec;hb=HEAD#l34 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/strops.c;h=6208518cdd861b770787c3f64cbfa3b6b9fb9afd;hb=HEAD#l41 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 :-)
  - JdeBP 6y ago
    See https://news.ycombinator.com/item?id=26298300 https://news.ycombinator.com/item?id=26298300 . The alternative implementation technique that already exists in some C implementations is not to use nonce FILE objects at all.

iab 6y ago

Amazing

ineedasername 6y ago

That's actually a very simple one. Just run a regex on "P != NP" to remove the "!" and you're good to go.

ctoth 6y ago
Seriously the most I have laughed in like 6 months. Which probably says a lot more about me than this joke. I know that jokes aren't really welcome on HN, and I generally really like this policy. But just had to mention this was just ... what I needed to read right now.
- koalahedron 6y ago
  > I know that jokes aren't really welcome on HN IMO, while I really don't come to HN to find dial-a-joke, or joke-of-the-day, I think some humor is essential in modern life. Since we're talking about Matt Keeter, you will find he has a great sense of humor if you read his website or interact with him. Some of his jokes are ROTFL funny, but subtle.
  - koalahedron 6y ago
    Even greater is someone understanding my own sardonic sense of humor and putting it to good use. I did have a nice half round of golf today with my wife. What a beautiful day to spend with such a wonderful person! I'm out.

xconverge 6y ago

Agreed, also hey bud, hope you are doing well

johnfn 6y ago
Hey, there’s a username I recognize! Long time no see! Same to you :)
- notretarded 6y ago
  You too

TeMPOraL 6y ago

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 Hypothesis tells me it's unlikely the library has this problem, but then again, so I thought about AAA videogames, and then GTA Online thing came out.

acqq 6y ago
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).
- MaxBarraclough 6y ago

mfbx9da4 6y ago

actually lolled

bsldld 6y ago

> 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 owe me a keyboard!

nightmunnas 6y ago

I don't think I've laughed this much since the pandemic started, well done.

fanf2 6y ago

Well, https://twitter.com/stephentyrone/status/1366573121365565444 https://twitter.com/stephentyrone/status/1366573121365565444 >> So many years ago when I first took over the iOS string functions, I found that like 30% of boot time in debug builds was in strstr. << >> Needless to say, we did not fix that issue by writing a more efficient strstr. Removed the parser and then removed strstr from the environment where it had been in use =) <<

eru 6y ago

You joke, but there's actually lots of work going on into what techniques will definitely NOT be enough to settle P=NP. (I find it pretty exciting, that this kind of negative result is possible. Ain't mathematics wonderful?)

coolgeek 6y ago

I just got an infinite loop down to 8.6 seconds! And I'm not done yet!

specialist 6y ago

You kid. But truer things are said in jest. > ...Tomorrow, someone’s going to reduce the boot times of macOS by 90% by the same principle. My 2019 MacBook often pauses when I connect the charging cable. Sometimes it just seizes, requiring a hard bounce. Clearly there's a contended lock buried deep. Something non-obvious. I'm certain everything these days has dozens of hidden quadratics and contended locks. Which is one of the reasons I'm excited for stuff like structured concurrency (Java's Project Loom) and retoolings like systemd becoming the norm. Ages ago I worked on kitchen sink app that had a very finicky startup. Any breeze would break it. Much consternation by mgmt. Apparently if we only clapped louder, Tinkerbell would fly. I couldn't take it any more. LARPing as a bulldozer, I replumbed the innards, changing from something like initd to be more like systemd with some lazy loading for good measure. Voila! Back to GTA. The failure here is the product owner didn't specify a max load time, and then hold the team to it. Devs will mostly do the work that's expected of them. If load time wasn't measured (and managed), no one is going to bother with expunging sscanfs.

dcolkitt 6y ago
> My 2019 MacBook often pauses when I connect the charging cable. Sometimes it just seizes, requiring a hard bounce. Yesterday my MBP kernel panicked because my keyboard was low on battery and the bluetooth connection kept dropping. There's something weird with MacOS where peripherals seem to really not be well isolated from the core OS runtime.
- raihansaputra 6y ago
  Oh peripherals on newer Macs are somehow very hit or miss. I have a very difficult time with external monitors, especially from sleep. My MBP 16" would just loop between initializing and failing to initialize, until I unplug, wait, and re-plug again. Or I have to press the `Extend` option instead of the `Mirror` option that I use. The older 2015 MBP would just connect fine.

stainforth 6y ago

Next Hacktober should offer a free t-shirt to anyone who goes out and issues a PR to a repo containing sscanf

randomswede 6y ago

P = NP for "P == 0" and/or "N == 1".