9 ms·

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,

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.

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.