I/O library 6x faster than fmt, 10x faster than stdio.h and iostream
github.com
github.com
* What is the core implementation idea behind this library? Why is it supposedly so much faster than stdio and fmt? There doesn't seem to be much explanation in the readme. The only thing I can see is "Locale support optional" and "Zero copy IO" but these are mixing up formatted and unformatted interfaces - it is supposed to be faster at both? Does the "zero copy IO" mean that it's unbuffered (as another comment here mentioned, that usually makes things slower not faster)?
* What does the API look like? There's no documentation whatsoever - the "documentation" heading in the readme just refers to "./doxygen/html/index.html" which doesn't exist in the repo; I can't even see a Doxyfile. Just a brief example in the readme showing reading and writing would be nice!
* What exactly is it faster at? Reading or writing? Formatted or unformatted IO? If formatted, is it just the formatting that's faster (e.g. is there also a comparison against fputs)? The benchmarks section has no detail of what code was compared except a mention of the examples/ directory, but that contains dozens of subdirectories, most of which each have multiple files in them. I find it quite implausible that it's 6x faster at formatting than fmt, and benchmarks are notoriously hard, so combined with the extreme lack of clarity I find it hard to take these claims seriously.
Indeed.
> I can't really see how it could be optimised to gain 6x speed up.
Performance claims appear to not even be based on I/O but only on two formatting microbenchmarks and are severely misleading https://news.ycombinator.com/item?id=23311726
Source: have spent a fair amount of time working on speeding up human-readable log output, the performance of which tends to be dominated by formatting.
[1] https://www.reddit.com/r/cpp/comments/dc5t1n/reply_to_herb_s...
[2] https://www.reddit.com/r/cpp_questions/comments/efuemt/c_wit...
[3] https://www.reddit.com/r/cpp_questions/comments/f7zgat/why_d...
A great many of these libraries are also, unfortunately, “newbie traps” (faster is better, right?)
/* typically 16 to 32 times
stat.st_blksize or BUFSIZ
is good */
int new_size = 16 * 4096;
setvbuf(fp, NULL, _IOFBF, new_size);Source: mailing list discussion with one of the Sun devs.
The reason it is slow is because it is "thread safe". 99% of the time, you don't really want that (especially in cases where you know how big the string will be at the end of everything).
StringBuilder should be preferred for pretty much everything.
The JVM's Escape analysis isn't perfect.
I once wrote my own JSON parser in Java. Mostly because I couldn't abide by how hard serialization was with the popular libs. I just wanted JSON to HashMap and back.
Then I got nutty trying to hyperoptimize it. Stuff like resizing methods so that JIT inlining could work.
At the time Boon was the benchmark leader. Its trick was preallocating a huge buffer per parse (and as well as taking shortcuts with the spec, accepting invalid JSON). Which I deemed wasteful. I had an HTTP server and I wanted each client connection to be lighter vs heavier. And for some reason I was committed to "stream processing" (incremental pull parser).
I could never match Boon's performance. Close. But never quite catching it. Which offended me in some way. More simple should always win, right?
Some time later I forced myself to crawl out of the rabbit hole. I backed out all my goofy optimizations. Opting for the most simple implementation I could conceive. Given my use case, my parser was more than good enough.
It's fun to tinker now and again. If only to relearn the "don't preoptimize" lesson.
1. ospan, performance claims seem to be based on, doesn't do any bound checks, so you can easily get buffer overflow.
2. fast_io generates a whopping 50kB of static data just to format an integer.
So if these benchmark results are correct (I was not able to verify because the author hasn't provided the benchmark source):
> format_int 7867424 ns 7866027 ns 89 items_per_second=127.129M/s
> fast_io_ospan_res 6871917 ns 6870708 ns 102 items_per_second=145.545M/s
fast_io gives 15% perf improvement by replacing a safe format_int API from https://github.com/fmtlib/fmt with a similar but unsafe one + 50kB of extra data. Adding safety will likely bring perf down which the last line seems to confirm:
> fast_io_concat 7967591 ns 7966162 ns 88 items_per_second=125.531M/s
This shows that fast_io is slightly slower than the equivalent {fmt} code. Again this is from the fast_io's benchmark results that I hasn't been able to reproduce.
50kB may not seem like much but for comparison, after a recent binary size optimization, the whole {fmt} library is around 57kB when compiled with `-Os -flto`: http://www.zverovich.net/2020/05/21/reducing-library-size.ht...
The floating-point benchmark results are even less meaningful. They appear to be based on a benchmark that I wrote to test the worst case Grisu (https://www.cs.tufts.edu/~nr/cs257/archive/florian-loitsch/p...) performance on unrealistic random data with maximum digit count. fast_io compares it to Ryu (https://dl.acm.org/doi/pdf/10.1145/3192366.3192369) where maximum digit count is actually the best case and the performance degrades as the number of digits goes down. A meaningful thing to do would be to use Milo Yip's benchmark instead: https://github.com/miloyip/dtoa-benchmark
Including video: https://www.youtube.com/watch?v=avyIFLuFUQs
1. It now constructs unnecessary `std::string` penalizing `format_int`:
value+=fmt::format_int(i).str().size();
2. The input is consecutive numbers which makes branches well predicted which is not realistic but beneficial for fast_io integer formatter which has a lot of branches.
The precomputed table you can find in include/fast_io_core_impl/integers/jiaendu/table_gen.h
Author appears to be doing the equivalent in the other benchmark:
value+=fast_io::to<std::string>(i).size();
Maybe you could argue that in both cases it would be better not to measure time spent creating and destroying strings, but I don't see how the two benchmarks are not comparable.
For example, here's a trivial sscanf() rewrite for a log parsing case that achieves 300x speed-up - https://gist.github.com/apankrat/20776d68d1d97bca12576a6e204... - and that's with a completely unoptimized code.
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.
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...
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?
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.
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.
I don’t see how this would matter?
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.
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.
I would argue that the issue here is not the binary -> decimal conversion. People expect when they write "1.2" they get that exact value, but that is not representable with binary floats. So the weird value you get is the closest value that is representable.
I definitely agree that there aren't good options to make a round trip fast and intuitive.
> 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 also is 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.
If you are keeping track of significant digits, you can definitely work in binary and render the binary value to the significant decimal digits. In particular for scientific work, if you cannot handle the issues with binary floating point, you probably are not handling uncertainty well enough. The corner cases you would hit would already have been bugs, but you just wouldn't have noticed.
One particular setup I am a fan of is keeping track of an upper and lower bound for all of your numbers which allows your computations to introduce a small amount of error , but you will still have objectively true statements when converting back to decimal to read.
For example "1.2" would be converted to the range "1.001-1.010" in binary with 4 significant figs which when converted back would be the range "1.125-1.25". Its not perfect, but it steps around a lot of typical floating point problems.
What? No.
I have spent much of my life working with floating point numbers and never ever had to resort to anything decimal for serious purposes (that is, except for some occasional printing of a number for debugging).
Do you realize that many entire fields of scientific computing (i.e., computer vision, fluid mechanics, solid mechanics, signal processing, numerical partial differential equations, computational chemistry, climate modeling, and dozens of other things) couldn't care less whether the inner representation of floating point numbers is decimal or binary? If binary can be made just a little faster, so be it.
In that regard your argument is a little like saying kids test question such as "Jennifer has 3 apples and gives one to Bob and Terry, how many does she have left" isn't decimal because the calculation is written in English rather than as a "number sentence" (as schools call them). But clearly the kids are still thinking about those numbers as decimal even if the question is not phrased as a mathematical equation.
Whereas some other cultures used base-12 or base-60 (https://en.wikipedia.org/wiki/Sexagesimal) which, incidentally, are also believed to originate from finger counting much like base-10 was.
I believe the Romans also thought about things in decimal despite their numerals being logarithmic. However their numerals do follow the decimal orders of magnitude.
The reason being is because decimal is the base system people learn when growing up. It's also widely speculated that one of the origins of decimal is around the number of digits (it's not an accident I've chosen that ambiguous term) on our hands: 10 fingers and thumbs. You might mentally map that to number line when trying to assess the distance between numbers or visualise formula but ultimately these would be mental models you generate on top of decimal rather than in place of.
They are integers with a fixed point, which is an entirely different domain.
edit: you've now edited your post to repeat a lot of what I put above. Though I doubt intentional (probably a race condition of us both posting at the same time). Anyhow, I'll keep what I posted as it's still relevant.
It is true that in home shopping lists there aren’t prices. I was thinking more about company ones (like parts).
Because they are more real than base 10 rationals. Math is either calculating with exact numbers (without any floating point nor overflow, or bigrat. ie symbolic), or inexact approximations (floating point types). Nothing is decimal, but those folks counting with their fingers, or financial folks who cannot afford to work with exact numbers. Decimal is just to minimize errors on the decimal representation side, nobody else does decimal. It's either binary or exact.
The problem isn’t to find a decimal representation, it’s to find one that round-trips and, among those, the ‘best’ one, and do that fast.
With best, people typically mean that the IEEE float closest to ⅒ prints as “0.1”, the one closest to 42/100 as “0.42”, etc. In general, you want to produce all “0.x”, “0.xx”, “0.xxx”, etc. until you run out of IEEE numbers in (0,1).
It took surprisingly long for _any_ implementation to get there (I think it was Steele, around 1980, published in 1990)
http://www.ryanjuckett.com/programming/printing-floating-poi... has a good introduction to the problem, insofar as I am qualified to judge that.
But doing it correctly shouldn't be too slow. Some rough psuedo-code for what I would do without looking at any references:
- convert the binary float one higher and lower than the given binary float.
- find the point at which they diverge
- Generate the given value rounded to that digit + 1
If you actually start putting your pseudocode into real code you’ll see how quickly it can go wrong, if you want to correctly convert all inputs. For example, once you get past 10^22, you can no longer do a simple division or multiplication to get the leading digit, because 10^22 cannot be represented as a double. For numbers 10^22 or below, you can just use ordinary division or multiplication and rely on the fact that this will be rounded correctly.
It’s a fun exercise to write an exact converter that works in the range -10^22..+10^22, though. It doesn’t require much code.
The Ryu paper outlines the process as follows:
* Extract e and m from the float, and normalize the next-smallest and next-largest numbers to handle subnormal and largest/smallest mantissa for a given exponent cases.
* Convert the adjusted mantissas to base-10 mantissas by multiplying by a power of 2, or by multiplying by a power of 1/5.
* Print out all of the common prefix of the smallest and largest values.
Except it turns out that doing the last two steps naively is actually quite slow: you need bignum support to do step 2 correctly, and bignum div/mod to do step 3 correctly.
What Ryu does to speed it up is it uses a lookup table to work out a bound on the prefix size to skip several iterations of "find the common prefix", proves that everything can be done with just 128-bit (for doubles)/64-bit (for floats) math, and then precomputes the necessary multiplications of 2^a/5^b via a lookup table.
I don't doubt that my naive solution would be slow relative (probably at least x4) to an ideal one, but I think it would be fast relative to system calls.
My naive implementation would not use a bignum for step two. I would just use a use a integer with size large enough to fit maximum mantissa * 5^log_2(maximum mantissa) which can be rounded up to a number with 4 x the number of bits as the binary mantissa (1 for maximum mantissa and 3 for the multiplication with 5). So a 128 bit number is definitely enough for a 32 bit float.
And with that you can still use a normal modulus and divide for step 3.
> What Ryu does to speed it up is it uses a lookup table to work out a bound on the prefix size to skip several iterations of "find the common prefix", proves that everything can be done with just 128-bit (for doubles)/64-bit (for floats) math, and then precomputes the necessary multiplications of 2^a/5^b via a lookup table.
It definitely seems like there are some optimizations that I had not considered. I will probably give a close look into the algorithm at some point.
It does also seem like the given algorithm roughly follows my psuedo-code though. My psuedo-code lumped your steps 1 and 2 into step 1 and then would include an extra digit rather than stop at the common prefix.
This means my algorithm would show 1.2 for the float closest to 1.2 (0x3F99999A) whereas that algorithm would show 1. Its possible (and probable) I am misunderstanding your simplification of step 3 from the Ryu paper.
It should be mantissa * 5^O(maximum binary exponent), not O(log mantissa).
On Windows there is an additional layer: CRT implements unix-style integer file descriptors (io.h) before calling WriteFile.
The fastest dtoa() algorithms are on the order of 50ns or less: https://erthink.github.io/dtoa-benchmark/#results
There are probably a lot of implementations lagging behind the state of the art though...
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.
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/p...
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".
It's so much easier, and the gains are so much bigger to just change the application, and given people's dependency on stdio is usually quite low, that's what most people do.
Yes, once a particular programmer knows about the problem, they can solve it pretty quickly by switching to faster and narrower functions. But this is happening one programmer at a time. Practically everyone is still learning the wrong default, and switching away only after they've noticed they've been burned by it, and scientific programmers at least are being burned by enough other things that there's no guarantee that they'll ever notice this detail, even if they're generally very competent. (We're initially trained to not worry much about this sort of constant factor, after all.)
The lowest-hanging fruit I see is in the compiler enhancement domain. They already e.g. inspect printf-family format strings, redirect the containing function call to fputs/memcpy when the string contains no format placeholders, and when there are format placeholders a warning is printed when the number of additional arguments does not match the number of format placeholders. If we could count on snprintf(buf, bufsize, "count: %d", k) being compiled down to little more than a 7- or 8-byte memcpy followed by a call to a dedicated integer-to-string function, I think the associated gain would be far more than "0.01%".
I think this is a much deeper problem than stdio.
Your logic is incorrect. A typical REST API might make millions of float<->string conversions in one request. Making it twice as fast might mean shaving many milliseconds from your median response time, which is a huge deal.
Indeed! Writing freestanding C while usiing Linux system calls directly was a great experience. I had to rewrite a lot of functionality but everything was explicit and there was no need to worry about old C library stuff like FILE pointers, I/O buffers or thread-local errno.
Even the glibc system call stubs can be a lot more complex than they seem. Many of them have a lot of hidden functionality, something to do with system call cancellation. The kernel's own nolibc.h provides a much better way to make system calls:
https://github.com/torvalds/linux/blob/master/tools/include/...
"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.
It's "sscanf() rewrite for a log parsing case", not "sscanf rewrite".
For example, "log parsing without using sscanf()", or "sscanf()-like parsing using fixed formats".
Saves the need to lookup the actual code in disbelief.
Instead write "I replaced sscanf with single use code", but then the speed improvement is not that interesting.
I was writing part of a codebase where I couldn't use the heap, so all standard libraries were not on the cards, and I ended up just using write(2, "hello\n", 6) to send the data direct to the kernel, and found the experience remarkably simple and unpainful.
Syscalls are extremely expensive and dominant the execution time unless you are writing large chunks of data all at once. Which is precisely why stdio.h exists, because it only occasionally flushes the buffer with write(). This can be observed when you get a segfault, often it seems like your print statements did not execute. One can use fflush() to force stdio.h to flush the buffer.
write() on the otherhand, always writes the data, well, at least to the file buffer cache. fsync() is required to ensure that the data is on disk, though I've seen systems lie about that too.
Virtually all SSDs lie about this to a certain extent. They'll indicate a write is complete when it's in their cache. The cache is RAM; as long as the power stays on, the write will appear to have succeeded to readers, but if the power goes goes off before the drive flushes the cache, the write will disappear. The exception is high end enterprise drives, which come with a capacitor that stores enough power to flush the cache to persistent storage in the event of power loss.
You can create a workqueue where each item is a copy of the argument list and a const char* of the format string. Then your program will only take a microsecond or two to print (depending on the argument length) on the critical path.
Unless you are formatting a really large message.
klodolph made some handwavey claim about synchronization overhead that are clearly false. It doesn't even make sense to me since the device being printed to will need some sort of synchronization and syscall.
Both you and klodlph are also making handwavey claims about formatting speed in Linux.
You both need to measure before you argue. I find it extremely rude to argue from a position of ignorance as both of you are doing.
"Well gee, I dunno but you're probably wrong". It's so asinine.
Even for floating point numbers, you’ll hit the fast path with fairly high regularity. My measurements put it at around 80ns for a double, on my system, most of the time.
Benchmark: https://github.com/expnkx/fast_io/tree/master/benchmarks/001... Binary Size: https://bitbucket.org/ejsvifq_mabmip/fast_io/src/master/benc...