Number Parsing at a Gigabyte per Second
lemire.me
lemire.me
Also this discussion of algorithms for the inverse problem, converting floats to strings. [1]
While Ryu and Ulf work is indeed cited for the reverse, i do not see any acknowledgement for his work on the string to float version.... despite really close similitude.
I suppose sometimes it is too obvious...
No doubt you're right that it would be more efficient to store the binary representation natively, especially assuming portability isn't an issue, and especially if a zero-copy solution were used, but many real-world systems have to cope with data formats that aren't the most efficient. Huge amounts of data are shipped as XML and JSON.
Both representations should lend themselves to compression.
True.
> it's hard to make a point that they occupy less storage
No, like I said, it would occupy less storage for sparse data. That's true even with separator characters (2 bytes as against 4). Doubtless there are much better solutions for representing sparse data that aren't human readable. A simple (index, value) dictionary, say.
> it can represent infinitely large numbers
Right, there's no upper bound beyond the limitations of the systems, although again a non-human-readable bignum format could do this more efficiently.
Now that I think about it, Excel spreadsheets, Json, XML,textfiles are all mayor contributors to sometimes very flawed ascii-based workloads that should have a complementary binary backing.
My $400 consumer motherboard has a 10Gb network card, and my SSD reads at over 50Gb/s. Anything that brings IO closer to those speeds is welcome.
https://lemire.me/blog/2020/03/10/fast-float-parsing-in-prac...
He followed up in a comment: "RapidJSON has at least two fast-parsing mode. The fast mode, which I think is what you refer to, is indeed quite fast, but it can be off by one ULP, so it is not standard compliant."
The Github README for this new project says, "The fast_float library provides a performance similar to that of the fast_double_parser library."
https://github.com/fastfloat/fast_float
However, the benchmarks show a significant improvement relative to those in the fast_double_parser README:
https://github.com/lemire/fast_double_parser
I tried to run the benchmarks, but my CMake is apparently too old, and Homebrew barfed all over the living room rug when I tried to update it.
That highlights the complexity of benchmarking in general and the importance of comparing within the same benchmark. I haven't looked at this in a while but I thought some of the newer JSON parsers were standards compliant (maybe not?).
Anyway, that other blog post answers my question as it looks like the big insight is that you use the fast approach (that everyone uses) when you can, and fall back to slow if you really have to. From that blog link:
"The full idea requires a whole blog post to explain, but the gist of it is that we can attempt to compute the answer, optimistically using a fast algorithm, and fall back on something else (like the standard library) as needed. It turns out that for the kind of numbers we find in JSON documents, we can parse 99% of them using a simple approach. All we have to do is correctly detect the error cases and bail out."
Again, I swear I've seen this in one of the other JSON parsers but maybe I'm misremembering. And again, good for them for breaking it out into a header library for others to use.