8 ms·

Fast function to parse strings into double (binary64) floating-point values

73 points by vitaut 7y ago

eesmith 7y ago
More context at Daniel Lemire's blog post at https://lemire.me/blog/2020/03/10/fast-float-parsing-in-practice/ https://lemire.me/blog/2020/03/10/fast-float-parsing-in-prac... . It's about twice as fast as abseil or from_chars and nearly 10x faster than strtod.
abductee_hg 7y ago
bad. you should not do that at all.
- yellowapple 7y ago
  If you're writing a parser for any language which is expected to deal with floating point numbers, being able to parse those numbers is generally necessary.
scottlamb 7y ago
It has about 15 KB of data: 10KB in power_of_ten_components and 5KB in mantissa_128. [1] That's ~23% of the per-core L1 data cache on (eg) the recently announced APU chip. [2, 3] So before getting too excited about the microbenchmark numbers, I'd be careful to ensure the additional cache pressure doesn't slow down my program as a whole. edit: also, ~2.5KB of that is due to padding in power_of_ten_components. I wonder if it'd be better to split the uint64_t field into two uint32_ts to avoid this. [1] https://github.com/lemire/fast_double_parser/blob/master/include/fast_double_parser.h https://github.com/lemire/fast_double_parser/blob/master/inc... [2] https://news.ycombinator.com/item?id=22440894 https://news.ycombinator.com/item?id=22440894 [3] https://en.wikichip.org/wiki/amd/ryzen_embedded/r1606g https://en.wikichip.org/wiki/amd/ryzen_embedded/r1606g
- userbinator 7y ago
  Also, I know it's not always possible, but if your application is spending so much time parsing strings into numbers that this could make a difference, seriously consider whether the source of those strings could be changed to not emit strings, because unless it's something like user input, chances are they may already be doubles which can be used as-is.
  - thedance 7y ago
    HN is collectively schizophrenic on this topic. On the one hand, the comments say that nobody really needs anything fancier than JSON. On the other hand, other comments say that if JSON parsing shows up in your profiles, you should switch off JSON!
    - gameswithgo 7y ago
      that just reflects that actual engineers and not actual engineers frequent hn
    - userbinator 7y ago
      HN (and a lot of other places, really) has a large population of web or otherwise "web-heritage" developers, as well as those whose ventures into computing started beside/before the web. I suspect the JSON promotion comes mostly from the former group, while the latter, of which I am a member, laments it roughly as much as we did the "XML craze" of the late 90s and early 2000s.
      - cm2187 7y ago
        And a tiny minority I am proudly part of, who watches these debates about xml vs json or tabs vs whitespace with the same amusement than Mike Judge!
        xxs 7y ago
        C'mon spaces vs tab is a serious one and it makes sense... unlike xml, json shizz.
- kzrdude 7y ago
  A serious question is how can we make microbenchmarks that take this into account? Along the lines of measuring a speedup of an operation, in varying scenarios of cache pressure.
  - vbezhenar 7y ago
    I'm not sure about actual implementation, but one approach would be to copy this function 100 times and invoke those copies sequentially. Of course linker must not optimize it into one function, so that's why I'm not sure about actual implementation. May be naive approach would work or may be not.
plus 7y ago
> That is, given the string "1.0e10", it should return a 64-bit floating-point value equal to 10. Err, surely it should be equal to 10,000,000,000. Or more probably, they meant to write "1.0e1".
- vardump 7y ago
  Oh, you don't use base 10,000,000,000 yet?
zozbot234 7y ago
Great hack, but in a broader sense this is silly. If parsing/pretty-printing floats from/to ASCII strings is a bottleneck you should be using hexfloats, as supported in the latest C/C++ standards and elsewhere. As a bonus, they will reliably evaluate to the same floating point number, eliminating an extra source of ambiguity and possible overhead.
- chadaustin 7y ago
  It can be a big chunk of the cost of parsing JSON.
  - gameswithgo 7y ago
    stop using json is the message
    - blacklion 7y ago
      I dream about day when all cryptoexchanges get this message. Not today :-(
- thedance 7y ago
  It's not silly at all. Replacing a lot of sprintf calls with Grisu and later Ryu made a huge difference in the production fleet at my last job. It wasn't by any means "the bottleneck" but it was costing real money. Most of the calls were in peripheral functions like debug logs, status page outputs, and whatnot. That said, I've never seen strtod showing up in my profiles, but I bet if I was profiling web browsers then I would see it.
  - MaxBarraclough 7y ago
    I was wondering if ctrl-f for 'Ryu' would match anything. Jeroen van der Zijp, developer of the lesser known FOX Toolkit, claims to have done better than the Ryu algorithm. From his changelist [0]: > New, faster, and often more accurate floating point to string conversion. No, this is not based on Ryu paper. New method reliably generates 16 digits, and does much better rounding. I believe this [1] is his implementation in C++. See also his paper [2]. (I believe it's not peer-reviewed, but it does appear in Google Scholar.) [0] http://www.fox-toolkit.org/ http://www.fox-toolkit.org/ [1] https://github.com/gogglesguy/fox/blob/77396c638c1c4e05/lib/fxprintf.cpp#L381 https://github.com/gogglesguy/fox/blob/77396c638c1c4e05/lib/... [2] http://www.fox-toolkit.org/ftp/fasthalffloatconversion.pdf http://www.fox-toolkit.org/ftp/fasthalffloatconversion.pdf
voldacar 7y ago
Is there a site out there that collects the absolute fastest ways of doing common low-level operations like this? For something as common as converting strings of digits to IEEE 754 floats/doubles, you would think we would already have the absolute fastest sequence of assembly instructions to do this. It's disconcerting thinking that the functions in the standard c/c++ library may not even be close to optimal. Very cool btw
- thedance 7y ago
  I can't think of a single thing in the C or C++ standard library that is state of the art. Often they are actually quite terrible. Some of them just can't be fixed because of ABI compatibility issues. That's why, just as an example, C++'s std::unordered_map is an embarrassment compared to all recent hash tables.
  - voldacar 7y ago
    That's so true and honestly it kind of gives me a pit in my stomach just thinking about all the C++ programs in particular that use STL and end up being so much slower than they could be. Hopefully Rust and Zig won't end up making this kind of mistake
    - KMnO4 7y ago
      I think Rust has an intrinsic advantage simply in its power. Standard libraries (and really most code) are written by humans. Giving those humans the confidence to implement complex data structures and algorithms without worrying about null pointers or memory leaks has ripping effects on performance. See C’s (“simple”) AVL tree vs Rust’s B-Tree[0]. [0]: http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performance-of-c-and-rust/ http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performa...
    - pjscott 7y ago
      The most egregious offenders here IMO are C++'s map and unordered_map. The spec constrains the possible implementations, and it's hard to implement them as anything better than a red-black tree or a badly-unoptimized hash table, respectively. And really the unordered one should be the default with the nice short name. It looks like Rust is doing well on this. HashMap (the one everybody uses) is essentially a clone of Google's heavily-optimized C++ hash table: https://abseil.io/blog/20180927-swisstables https://abseil.io/blog/20180927-swisstables ... and if you need the collection to be sorted, their BTreeMap has much lower overhead than the C++ std::map, plus a big prominent note in its documentation saying that HashMap is usually the one you want. I'm impressed. (Haven't looked at Zig yet.)
zone411 7y ago
Shouldn't std::from_chars be included in the benchmarks?
- deadmutex 7y ago
  Yeah, looking forward to it. Especially with latest version of MSVC, based on this post from the author: https://www.reddit.com/r/cpp/comments/92bkxp/how_to_efficiently_convert_a_string_to_an_int_in_c/e35b3r1/ https://www.reddit.com/r/cpp/comments/92bkxp/how_to_efficien...
roel_v 7y ago
Would having a mode that restricts the types of numbers it accepts (in my particular case: no scientific notation) speed it up significantly?
londons_explore 7y ago
I was expecting this to include fancy bit twiddling and simd assembly for parsing 8 decimal digits at once... But the reality is the core of the algorithm is still a while loop that looks at each digit one at a time and multiplies by 10 each time ...
alkonaut 7y ago
What's a scenario where you have a huge flow of floating point data as text? Assuming it's usually json, but in which case does that happen and you need to work around it (parse faster) rather than fix the underlying problem of having a huge stream of numbers as text?
- blacklion 7y ago
  If you could control both ends, yes. But sometimes you need to consume data produced by entities which you could not control. Examples? Crypto currency exchanges, for example. All of them use ugly, often terrible, JSON-based protocols, and some of them have non-trivial amount of trading to see JSON parsers as hot spots.

73 points by vitaut 7y ago

More context at Daniel Lemire's blog post at https://lemire.me/blog/2020/03/10/fast-float-parsing-in-practice/ https://lemire.me/blog/2020/03/10/fast-float-parsing-in-prac... . It's about twice as fast as abseil or from_chars and nearly 10x faster than strtod.

abductee_hg 7y ago

bad. you should not do that at all.

yellowapple 7y ago
If you're writing a parser for any language which is expected to deal with floating point numbers, being able to parse those numbers is generally necessary.

scottlamb 7y ago

It has about 15 KB of data: 10KB in power_of_ten_components and 5KB in mantissa_128. [1] That's ~23% of the per-core L1 data cache on (eg) the recently announced APU chip. [2, 3] So before getting too excited about the microbenchmark numbers, I'd be careful to ensure the additional cache pressure doesn't slow down my program as a whole. edit: also, ~2.5KB of that is due to padding in power_of_ten_components. I wonder if it'd be better to split the uint64_t field into two uint32_ts to avoid this. [1] https://github.com/lemire/fast_double_parser/blob/master/include/fast_double_parser.h https://github.com/lemire/fast_double_parser/blob/master/inc... [2] https://news.ycombinator.com/item?id=22440894 https://news.ycombinator.com/item?id=22440894 [3] https://en.wikichip.org/wiki/amd/ryzen_embedded/r1606g https://en.wikichip.org/wiki/amd/ryzen_embedded/r1606g

userbinator 7y ago
Also, I know it's not always possible, but if your application is spending so much time parsing strings into numbers that this could make a difference, seriously consider whether the source of those strings could be changed to not emit strings, because unless it's something like user input, chances are they may already be doubles which can be used as-is.
- thedance 7y ago
  HN is collectively schizophrenic on this topic. On the one hand, the comments say that nobody really needs anything fancier than JSON. On the other hand, other comments say that if JSON parsing shows up in your profiles, you should switch off JSON!
  - gameswithgo 7y ago
    that just reflects that actual engineers and not actual engineers frequent hn
  - userbinator 7y ago
    HN (and a lot of other places, really) has a large population of web or otherwise "web-heritage" developers, as well as those whose ventures into computing started beside/before the web. I suspect the JSON promotion comes mostly from the former group, while the latter, of which I am a member, laments it roughly as much as we did the "XML craze" of the late 90s and early 2000s.
    - cm2187 7y ago
      And a tiny minority I am proudly part of, who watches these debates about xml vs json or tabs vs whitespace with the same amusement than Mike Judge!
      - xxs 7y ago
        C'mon spaces vs tab is a serious one and it makes sense... unlike xml, json shizz.
kzrdude 7y ago
A serious question is how can we make microbenchmarks that take this into account? Along the lines of measuring a speedup of an operation, in varying scenarios of cache pressure.
- vbezhenar 7y ago
  I'm not sure about actual implementation, but one approach would be to copy this function 100 times and invoke those copies sequentially. Of course linker must not optimize it into one function, so that's why I'm not sure about actual implementation. May be naive approach would work or may be not.

plus 7y ago

> That is, given the string "1.0e10", it should return a 64-bit floating-point value equal to 10. Err, surely it should be equal to 10,000,000,000. Or more probably, they meant to write "1.0e1".

vardump 7y ago
Oh, you don't use base 10,000,000,000 yet?

zozbot234 7y ago

Great hack, but in a broader sense this is silly. If parsing/pretty-printing floats from/to ASCII strings is a bottleneck you should be using hexfloats, as supported in the latest C/C++ standards and elsewhere. As a bonus, they will reliably evaluate to the same floating point number, eliminating an extra source of ambiguity and possible overhead.

chadaustin 7y ago
It can be a big chunk of the cost of parsing JSON.
- gameswithgo 7y ago
  stop using json is the message
  - blacklion 7y ago
    I dream about day when all cryptoexchanges get this message. Not today :-(
thedance 7y ago
It's not silly at all. Replacing a lot of sprintf calls with Grisu and later Ryu made a huge difference in the production fleet at my last job. It wasn't by any means "the bottleneck" but it was costing real money. Most of the calls were in peripheral functions like debug logs, status page outputs, and whatnot. That said, I've never seen strtod showing up in my profiles, but I bet if I was profiling web browsers then I would see it.
- MaxBarraclough 7y ago
  I was wondering if ctrl-f for 'Ryu' would match anything. Jeroen van der Zijp, developer of the lesser known FOX Toolkit, claims to have done better than the Ryu algorithm. From his changelist [0]: > New, faster, and often more accurate floating point to string conversion. No, this is not based on Ryu paper. New method reliably generates 16 digits, and does much better rounding. I believe this [1] is his implementation in C++. See also his paper [2]. (I believe it's not peer-reviewed, but it does appear in Google Scholar.) [0] http://www.fox-toolkit.org/ http://www.fox-toolkit.org/ [1] https://github.com/gogglesguy/fox/blob/77396c638c1c4e05/lib/fxprintf.cpp#L381 https://github.com/gogglesguy/fox/blob/77396c638c1c4e05/lib/... [2] http://www.fox-toolkit.org/ftp/fasthalffloatconversion.pdf http://www.fox-toolkit.org/ftp/fasthalffloatconversion.pdf

voldacar 7y ago

Is there a site out there that collects the absolute fastest ways of doing common low-level operations like this? For something as common as converting strings of digits to IEEE 754 floats/doubles, you would think we would already have the absolute fastest sequence of assembly instructions to do this. It's disconcerting thinking that the functions in the standard c/c++ library may not even be close to optimal. Very cool btw

thedance 7y ago
I can't think of a single thing in the C or C++ standard library that is state of the art. Often they are actually quite terrible. Some of them just can't be fixed because of ABI compatibility issues. That's why, just as an example, C++'s std::unordered_map is an embarrassment compared to all recent hash tables.
- voldacar 7y ago
  That's so true and honestly it kind of gives me a pit in my stomach just thinking about all the C++ programs in particular that use STL and end up being so much slower than they could be. Hopefully Rust and Zig won't end up making this kind of mistake
  - KMnO4 7y ago
    I think Rust has an intrinsic advantage simply in its power. Standard libraries (and really most code) are written by humans. Giving those humans the confidence to implement complex data structures and algorithms without worrying about null pointers or memory leaks has ripping effects on performance. See C’s (“simple”) AVL tree vs Rust’s B-Tree[0]. [0]: http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performance-of-c-and-rust/ http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performa...
  - pjscott 7y ago
    The most egregious offenders here IMO are C++'s map and unordered_map. The spec constrains the possible implementations, and it's hard to implement them as anything better than a red-black tree or a badly-unoptimized hash table, respectively. And really the unordered one should be the default with the nice short name. It looks like Rust is doing well on this. HashMap (the one everybody uses) is essentially a clone of Google's heavily-optimized C++ hash table: https://abseil.io/blog/20180927-swisstables https://abseil.io/blog/20180927-swisstables ... and if you need the collection to be sorted, their BTreeMap has much lower overhead than the C++ std::map, plus a big prominent note in its documentation saying that HashMap is usually the one you want. I'm impressed. (Haven't looked at Zig yet.)

zone411 7y ago

Shouldn't std::from_chars be included in the benchmarks?

deadmutex 7y ago
Yeah, looking forward to it. Especially with latest version of MSVC, based on this post from the author: https://www.reddit.com/r/cpp/comments/92bkxp/how_to_efficiently_convert_a_string_to_an_int_in_c/e35b3r1/ https://www.reddit.com/r/cpp/comments/92bkxp/how_to_efficien...

roel_v 7y ago

Would having a mode that restricts the types of numbers it accepts (in my particular case: no scientific notation) speed it up significantly?

londons_explore 7y ago

I was expecting this to include fancy bit twiddling and simd assembly for parsing 8 decimal digits at once... But the reality is the core of the algorithm is still a while loop that looks at each digit one at a time and multiplies by 10 each time ...

alkonaut 7y ago

What's a scenario where you have a huge flow of floating point data as text? Assuming it's usually json, but in which case does that happen and you need to work around it (parse faster) rather than fix the underlying problem of having a huge stream of numbers as text?

blacklion 7y ago
If you could control both ends, yes. But sometimes you need to consume data produced by entities which you could not control. Examples? Crypto currency exchanges, for example. All of them use ugly, often terrible, JSON-based protocols, and some of them have non-trivial amount of trading to see JSON parsers as hot spots.