7 ms·

Just keep in mind that stdio is really slow, even its fast paths. For example, here's a trivial sscanf() rewrite for a log parsing case that achieves 300x spee

Just keep in mind that stdio is really slow, even its fast paths. For example, here's a trivial sscanf() rewrite for a log parsing case that achieves 300x speed-up - https://gist.github.com/apankrat/20776d68d1d97bca12576a6e204b2f74 https://gist.github.com/apankrat/20776d68d1d97bca12576a6e204... - and that's with a completely unoptimized code.

AceJohnny2 6y ago
so the follow-up question (not necessarily to you but to the crowd) is: why is stdio so slow?
- why_only_15 6y ago
  Wonder why... Maybe because of compatibility concerns?
- kstenerud 6y ago
  Because it's an abstraction on top of an abstraction on top of an abstraction. You need to leak parts of the lower layers to higher levels in order to get the speed back (and allow zero-copy). There are probably some non-leaky optimizations that can be done as well, although that's been going on for decades. Another biggie is floating point. Converting binary floating point to decimal floating point and vice versa is VERY VERY VERY SLOW, difficult to get right, and difficult to predict results. Unfortunately, ieee754 decimal float just isn't getting any adoption, so we're stuck doing these costly conversions every time we deal with text formats or big float implementations. Actually, scanf and printf are just in general slow because of their general nature. They need to handle a TON of options and get really bloated and complicated as a result.
  - 77pt77 6y ago
    > Another biggie is floating point. Converting binary floating point to decimal floating point and vice versa is VERY VERY VERY SLOW, difficult to get right Never forget the cluster bug in PHP because the developers decided they needed to reinvent the wheel[1]. [1] https://www.exploringbinary.com/php-hangs-on-numeric-value-2-2250738585072011e-308/ https://www.exploringbinary.com/php-hangs-on-numeric-value-2...
    - ars 6y ago
      Can you explain what you mean? Because I read the bug report and it seems to be some intricacy about loading variables into a register solved by using volatile. Meaning it's a complicated implementation detail of the CPU, and does not seem to be because they reinvented the wheel. Plus is there some standardized library they should have been using?
    - hyperman1 6y ago
      Java had a variant of that bug too: https://www.exploringbinary.com/java-hangs-when-converting-2-2250738585072012e-308/ https://www.exploringbinary.com/java-hangs-when-converting-2... It sits in a loop flip-flopping between 2 representations, each time deciding the other one is better. This turned into a DOS, as some web servers used floating point when decoding time zones from the http request header. So if your server has e.g. 20 http acceptor threads, someone could send 20 requests with an insane time zone, each sending 1 thread in an infinite loop.
      - deleted 6y ago
        [deleted]
  - thethirdone 6y ago
    > Another biggie is floating point. Converting binary floating point to decimal floating point and vice versa is VERY VERY VERY SLOW, difficult to get right, and difficult to predict results. I haven't read deeply into IEEE 754-2008 for decimal floating points, but it seems like it should be pretty fast (relative to system calls) to convert binary to decimal because 10 has a factor of 2. > Unfortunately, ieee754 decimal float just isn't getting any adoption, so we're stuck doing these costly conversions every time we deal with text formats or big float implementations. Is there any reason big float implementations should use decimal rather than binary? It seems like it is very straightforward to make a binary big float, and do operations on it. In fact, IEEE 754-2008 specifies interchange formats for all binary floats of bit lengths >= 128 where length is a multiple of 32.
    - saagarjha 6y ago
      > it seems like it should be pretty fast (relative to system calls) to convert binary to decimal because 10 has a factor of 2 I don’t see how this would matter?
      - thethirdone 6y ago
        Any binary float is exactly representable in a decimal float with enough digits. This is not true in the other direction. for example 1/5th or 0.2 is 0.001100110011... in binary. So a simple solution for binary to decimal is to express it as a larger decimal float than you intend to show and then crop off digits if it doesn't fit in your destination format.
    - kstenerud 6y ago
      > haven't read deeply into IEEE 754-2008 for decimal floating points, but it seems like it should be pretty fast (relative to system calls) to convert binary to decimal because 10 has a factor of 2. It could be fast, but legacy has doomed us all to a "canonical" conversion of sorts, where any other conversion algorithm will likely yield off-by-a-tiny-amount differences in the binary format (like 1.200000000031 instead of 1.2). There are in fact fairly simple conversions that can be done, but they yield results that are incompatible with printf. > Is there any reason big float implementations should use decimal rather than binary? At the end of the day, we work in decimal. So every binary result we calculate has to be converted to its decimal approximation (the meaning of which is subject to convention). Rounding is also an issue, because you want to keep your number of significant digits within reason to avoid false precision errors. Doing all of this in a different base that can't be 1:1 converted adds a whole slew of bug opportunities and corner cases.
  - asveikau 6y ago
    I think you are over counting abstractions. printf copies to a buffer and eventually calls write(2). On Windows there is an additional layer: CRT implements unix-style integer file descriptors (io.h) before calling WriteFile.
    - kstenerud 6y ago
      It's usually printf() -> fwrite() -> write() -> syscall. You need the fwrite (or something equivalent) in there for buffering and concurrency, otherwise multithreaded printfs would stomp on each other.
      - saagarjha 6y ago
        Usually you go through vfprintf, which is the “most generic” function, and that will grab the file’s lock.
  - haberman 6y ago
    > Converting binary floating point to decimal floating point and vice versa is VERY VERY VERY SLOW The fastest dtoa() algorithms are on the order of 50ns or less: https://erthink.github.io/dtoa-benchmark/#results https://erthink.github.io/dtoa-benchmark/#results There are probably a lot of implementations lagging behind the state of the art though...
    - dathinab 6y ago
      The problem is if it's still behaving exactly the same for certain edge cases. I don't know about stdio, but in Java there are a bunch of float operations in the standardlibrary which can be easily implemented much faster and simpler, but then misbehave in that one edge cases most people don't care about.
      - klodolph 6y ago
        > The problem is if it's still behaving exactly the same for certain edge cases. It is behaving correctly for all edge cases. That’s the benchmark you compare floating-point to decimal conversion—your algorithm is no good if it doesn’t handle all cases. The start of the art back in the 1990s the algorithm used in dtoa, written by David M. Gay and included in Netlib, taken from a paper by Steele (I think). Since then, people have chipped away at the problem, making it faster. A few new algorithms have appeared, including Grisu and Ryu. Something you’ll see in these algorithms is some “fast path” which uses ordinary double arithmetic, and then logic to detect when this gives the wrong answer and fall back to some slower path. The slower path may use arbitrary precision arithmetic or something else (Ryu avoids bignums!). These new algorithms generally hit the slow path very infrequently, which is why you sometimes see benchmarks with numbers picked to trigger the slow path. The algorithms have associated papers proving their correctness for all inputs. You are free to read them. https://www.cs.tufts.edu/~nr/cs257/archive/florian-loitsch/printf.pdf https://www.cs.tufts.edu/~nr/cs257/archive/florian-loitsch/p... https://dl.acm.org/doi/10.1145/3192366.3192369 https://dl.acm.org/doi/10.1145/3192366.3192369
- saagarjha 6y ago
  They’re exceptionally complicated. No, really, take a look at the source to glibc’s vfprintf-internal.c (http://sourceware.org/git/?p=glibc.git;a=blob;f=stdio-common/vfprintf-internal.c http://sourceware.org/git/?p=glibc.git;a=blob;f=stdio-common...) or vfcanf-internal.c (http://sourceware.org/git/?p=glibc.git;a=blob;f=stdio-common/vfscanf-internal.c http://sourceware.org/git/?p=glibc.git;a=blob;f=stdio-common...) sometime. all the * (scanf|printf) functions are funneled through that, which means right off the bat you’re converting your string to a FILE * abstraction and marshaling all your arguments through a va_args. Then you get to the actual function itself, which needs to deal with locales and buffering and locking and positional arguments and multiple bases and memory allocation and rounding floating point and a huge amount of complexity that you might not even be aware of. And then there’s the somewhat awkward signature itself, which means it is all but required to do extra work to conform to the standard.
- geocar 6y ago
  Because it's doing something else. Saying stdio is slow isn't the same thing as saying "they should just do what these other guys are doing" -- they can't do that without breaking everyone who uses stdio, and a lot of people use stdio because being slow isn't a problem they need to solve. Meanwhile, when being slow is a problem you need to solve, just because there are undoubtedly some quick wins in just about every stdio implementation doesn't mean there would be much value chasing them. Let's say for every 20% improvement in stdio you can find there, you could get a 20x improvement in your application some other way. And there are a lot of other ways: More formatting and IO libraries than you can shake a stick at, so it's easy to think about the things you're paying for by using stdio that you don't need and simply find something else that doesn't have those things. Some examples: - Compatibility: stdio offers a lot of options for no better reason than it's always offered them. This creates a certain amount of bloat and slowdown that can't be removed without breaking some other application that expects this behaviour. - Edge cases: More on that point, stdio is expected to handle a lot of situations to handle the application might never get into, but they have to test for anyway. Other libraries don't. - Locking: FILE* needs to be locked for concurrent access to get things like the file position or to update the buffer. Many implementations have an _unlocked() implementation of stdio operations that skip the lock, but the only way to know if they're safe is to know there's no part of the application (or a library) that could be using that stream in another thread. It also nearly doubled the number of API calls stdio offers. - Tuneables with bad defaults: Most people don't ever use setvbuf because choosing a good value is hard. Pick a value too big, and you'll see massive delays with data coming out, and too small and you waste time on syscalls. If people do use this, they choose something like line buffering (usually for logfiles) which means you're doing a syscall per line. - Impedance mismatch: fwrite() might look* like write() but it doesn't look anything like writev() or sendmmsg(); Similarly fread() versus recvmmsg() or readv(). stdio would need a bunch of new API calls (like the _unlocked() calls) just to keep up. - Abstraction in implementation: stdio probably uses malloc which is also slow, but taking an allocator as an argument would require a whole new API. Meanwhile, it is trivial to stack-allocate a buffer for writing your log-line and flush it out with a single write(). There are others. I like to say that writing fast software is 99% doing only what you need to, and being good at writing fast software requires being brutally narrow about that "need".
kyllo 6y ago
Is this generally the case across all major C standard library implementations or are some of them much faster than others?
- apankrat 6y ago
  Oh, I'm sure it's implementation-specific.
asveikau 6y ago
> For example, here's a trivial sscanf() rewrite "sscanf rewrite" implies you wrote a general purpose replacement. This just parses a fixed format. That is not an sscanf rewrite. The way you phrased it sounds like they could drop it into an existing libc and do better.
- apankrat 6y ago
  Don't get carried away with misquoting or you end up with a strawman. It's "sscanf() rewrite for a log parsing case", not "sscanf rewrite".
  - zerr 6y ago
    I also understood it as ((sscanf() rewrite) for a log parsing case) :)
    - rat9988 6y ago
      I understood it the same way until I saw his limited implementation, and then revised my understanding. It seems pretty obvious to me that he isn't writing a sscanf clone.
  - zoomablemind 6y ago
    There are other word choices than 'rewrite' that describe that implementation without confusing the context. For example, "log parsing without using sscanf()", or "sscanf()-like parsing using fixed formats". Saves the need to lookup the actual code in disbelief.
  - ChrisLomont 6y ago
    It's not misquoting. It's poorly chosen words that were misleading. I too thought you meant you either replaced sscanf with a faster equivalent or used sscanf to beat something else. Instead write "I replaced sscanf with single use code", but then the speed improvement is not that interesting.
    - 6y ago
nchase 6y ago
this adds some helpful perspective. thanks!

AceJohnny2 6y ago

so the follow-up question (not necessarily to you but to the crowd) is: why is stdio so slow?

why_only_15 6y ago
Wonder why... Maybe because of compatibility concerns?
kstenerud 6y ago
Because it's an abstraction on top of an abstraction on top of an abstraction. You need to leak parts of the lower layers to higher levels in order to get the speed back (and allow zero-copy). There are probably some non-leaky optimizations that can be done as well, although that's been going on for decades. Another biggie is floating point. Converting binary floating point to decimal floating point and vice versa is VERY VERY VERY SLOW, difficult to get right, and difficult to predict results. Unfortunately, ieee754 decimal float just isn't getting any adoption, so we're stuck doing these costly conversions every time we deal with text formats or big float implementations. Actually, scanf and printf are just in general slow because of their general nature. They need to handle a TON of options and get really bloated and complicated as a result.
- 77pt77 6y ago
  > Another biggie is floating point. Converting binary floating point to decimal floating point and vice versa is VERY VERY VERY SLOW, difficult to get right Never forget the cluster bug in PHP because the developers decided they needed to reinvent the wheel[1]. [1] https://www.exploringbinary.com/php-hangs-on-numeric-value-2-2250738585072011e-308/ https://www.exploringbinary.com/php-hangs-on-numeric-value-2...
  - ars 6y ago
    Can you explain what you mean? Because I read the bug report and it seems to be some intricacy about loading variables into a register solved by using volatile. Meaning it's a complicated implementation detail of the CPU, and does not seem to be because they reinvented the wheel. Plus is there some standardized library they should have been using?
  - hyperman1 6y ago
    Java had a variant of that bug too: https://www.exploringbinary.com/java-hangs-when-converting-2-2250738585072012e-308/ https://www.exploringbinary.com/java-hangs-when-converting-2... It sits in a loop flip-flopping between 2 representations, each time deciding the other one is better. This turned into a DOS, as some web servers used floating point when decoding time zones from the http request header. So if your server has e.g. 20 http acceptor threads, someone could send 20 requests with an insane time zone, each sending 1 thread in an infinite loop.
    - deleted 6y ago
      [deleted]
- thethirdone 6y ago
  > Another biggie is floating point. Converting binary floating point to decimal floating point and vice versa is VERY VERY VERY SLOW, difficult to get right, and difficult to predict results. I haven't read deeply into IEEE 754-2008 for decimal floating points, but it seems like it should be pretty fast (relative to system calls) to convert binary to decimal because 10 has a factor of 2. > Unfortunately, ieee754 decimal float just isn't getting any adoption, so we're stuck doing these costly conversions every time we deal with text formats or big float implementations. Is there any reason big float implementations should use decimal rather than binary? It seems like it is very straightforward to make a binary big float, and do operations on it. In fact, IEEE 754-2008 specifies interchange formats for all binary floats of bit lengths >= 128 where length is a multiple of 32.
  - saagarjha 6y ago
    > it seems like it should be pretty fast (relative to system calls) to convert binary to decimal because 10 has a factor of 2 I don’t see how this would matter?
    - thethirdone 6y ago
      Any binary float is exactly representable in a decimal float with enough digits. This is not true in the other direction. for example 1/5th or 0.2 is 0.001100110011... in binary. So a simple solution for binary to decimal is to express it as a larger decimal float than you intend to show and then crop off digits if it doesn't fit in your destination format.
  - kstenerud 6y ago
    > haven't read deeply into IEEE 754-2008 for decimal floating points, but it seems like it should be pretty fast (relative to system calls) to convert binary to decimal because 10 has a factor of 2. It could be fast, but legacy has doomed us all to a "canonical" conversion of sorts, where any other conversion algorithm will likely yield off-by-a-tiny-amount differences in the binary format (like 1.200000000031 instead of 1.2). There are in fact fairly simple conversions that can be done, but they yield results that are incompatible with printf. > Is there any reason big float implementations should use decimal rather than binary? At the end of the day, we work in decimal. So every binary result we calculate has to be converted to its decimal approximation (the meaning of which is subject to convention). Rounding is also an issue, because you want to keep your number of significant digits within reason to avoid false precision errors. Doing all of this in a different base that can't be 1:1 converted adds a whole slew of bug opportunities and corner cases.
- asveikau 6y ago
  I think you are over counting abstractions. printf copies to a buffer and eventually calls write(2). On Windows there is an additional layer: CRT implements unix-style integer file descriptors (io.h) before calling WriteFile.
  - kstenerud 6y ago
    It's usually printf() -> fwrite() -> write() -> syscall. You need the fwrite (or something equivalent) in there for buffering and concurrency, otherwise multithreaded printfs would stomp on each other.
    - saagarjha 6y ago
      Usually you go through vfprintf, which is the “most generic” function, and that will grab the file’s lock.
- haberman 6y ago
  > Converting binary floating point to decimal floating point and vice versa is VERY VERY VERY SLOW The fastest dtoa() algorithms are on the order of 50ns or less: https://erthink.github.io/dtoa-benchmark/#results https://erthink.github.io/dtoa-benchmark/#results There are probably a lot of implementations lagging behind the state of the art though...
  - dathinab 6y ago
    The problem is if it's still behaving exactly the same for certain edge cases. I don't know about stdio, but in Java there are a bunch of float operations in the standardlibrary which can be easily implemented much faster and simpler, but then misbehave in that one edge cases most people don't care about.
    - klodolph 6y ago
      > The problem is if it's still behaving exactly the same for certain edge cases. It is behaving correctly for all edge cases. That’s the benchmark you compare floating-point to decimal conversion—your algorithm is no good if it doesn’t handle all cases. The start of the art back in the 1990s the algorithm used in dtoa, written by David M. Gay and included in Netlib, taken from a paper by Steele (I think). Since then, people have chipped away at the problem, making it faster. A few new algorithms have appeared, including Grisu and Ryu. Something you’ll see in these algorithms is some “fast path” which uses ordinary double arithmetic, and then logic to detect when this gives the wrong answer and fall back to some slower path. The slower path may use arbitrary precision arithmetic or something else (Ryu avoids bignums!). These new algorithms generally hit the slow path very infrequently, which is why you sometimes see benchmarks with numbers picked to trigger the slow path. The algorithms have associated papers proving their correctness for all inputs. You are free to read them. https://www.cs.tufts.edu/~nr/cs257/archive/florian-loitsch/printf.pdf https://www.cs.tufts.edu/~nr/cs257/archive/florian-loitsch/p... https://dl.acm.org/doi/10.1145/3192366.3192369 https://dl.acm.org/doi/10.1145/3192366.3192369
saagarjha 6y ago
They’re exceptionally complicated. No, really, take a look at the source to glibc’s vfprintf-internal.c (http://sourceware.org/git/?p=glibc.git;a=blob;f=stdio-common/vfprintf-internal.c http://sourceware.org/git/?p=glibc.git;a=blob;f=stdio-common...) or vfcanf-internal.c (http://sourceware.org/git/?p=glibc.git;a=blob;f=stdio-common/vfscanf-internal.c http://sourceware.org/git/?p=glibc.git;a=blob;f=stdio-common...) sometime. all the * (scanf|printf) functions are funneled through that, which means right off the bat you’re converting your string to a FILE * abstraction and marshaling all your arguments through a va_args. Then you get to the actual function itself, which needs to deal with locales and buffering and locking and positional arguments and multiple bases and memory allocation and rounding floating point and a huge amount of complexity that you might not even be aware of. And then there’s the somewhat awkward signature itself, which means it is all but required to do extra work to conform to the standard.
geocar 6y ago
Because it's doing something else. Saying stdio is slow isn't the same thing as saying "they should just do what these other guys are doing" -- they can't do that without breaking everyone who uses stdio, and a lot of people use stdio because being slow isn't a problem they need to solve. Meanwhile, when being slow is a problem you need to solve, just because there are undoubtedly some quick wins in just about every stdio implementation doesn't mean there would be much value chasing them. Let's say for every 20% improvement in stdio you can find there, you could get a 20x improvement in your application some other way. And there are a lot of other ways: More formatting and IO libraries than you can shake a stick at, so it's easy to think about the things you're paying for by using stdio that you don't need and simply find something else that doesn't have those things. Some examples: - Compatibility: stdio offers a lot of options for no better reason than it's always offered them. This creates a certain amount of bloat and slowdown that can't be removed without breaking some other application that expects this behaviour. - Edge cases: More on that point, stdio is expected to handle a lot of situations to handle the application might never get into, but they have to test for anyway. Other libraries don't. - Locking: FILE* needs to be locked for concurrent access to get things like the file position or to update the buffer. Many implementations have an _unlocked() implementation of stdio operations that skip the lock, but the only way to know if they're safe is to know there's no part of the application (or a library) that could be using that stream in another thread. It also nearly doubled the number of API calls stdio offers. - Tuneables with bad defaults: Most people don't ever use setvbuf because choosing a good value is hard. Pick a value too big, and you'll see massive delays with data coming out, and too small and you waste time on syscalls. If people do use this, they choose something like line buffering (usually for logfiles) which means you're doing a syscall per line. - Impedance mismatch: fwrite() might look* like write() but it doesn't look anything like writev() or sendmmsg(); Similarly fread() versus recvmmsg() or readv(). stdio would need a bunch of new API calls (like the _unlocked() calls) just to keep up. - Abstraction in implementation: stdio probably uses malloc which is also slow, but taking an allocator as an argument would require a whole new API. Meanwhile, it is trivial to stack-allocate a buffer for writing your log-line and flush it out with a single write(). There are others. I like to say that writing fast software is 99% doing only what you need to, and being good at writing fast software requires being brutally narrow about that "need".

kyllo 6y ago

Is this generally the case across all major C standard library implementations or are some of them much faster than others?

apankrat 6y ago
Oh, I'm sure it's implementation-specific.

asveikau 6y ago

> For example, here's a trivial sscanf() rewrite "sscanf rewrite" implies you wrote a general purpose replacement. This just parses a fixed format. That is not an sscanf rewrite. The way you phrased it sounds like they could drop it into an existing libc and do better.

apankrat 6y ago
Don't get carried away with misquoting or you end up with a strawman. It's "sscanf() rewrite for a log parsing case", not "sscanf rewrite".
- zerr 6y ago
  I also understood it as ((sscanf() rewrite) for a log parsing case) :)
  - rat9988 6y ago
    I understood it the same way until I saw his limited implementation, and then revised my understanding. It seems pretty obvious to me that he isn't writing a sscanf clone.
- zoomablemind 6y ago
  There are other word choices than 'rewrite' that describe that implementation without confusing the context. For example, "log parsing without using sscanf()", or "sscanf()-like parsing using fixed formats". Saves the need to lookup the actual code in disbelief.
- ChrisLomont 6y ago
  It's not misquoting. It's poorly chosen words that were misleading. I too thought you meant you either replaced sscanf with a faster equivalent or used sscanf to beat something else. Instead write "I replaced sscanf with single use code", but then the speed improvement is not that interesting.
  - 6y ago

nchase 6y ago

this adds some helpful perspective. thanks!