Parsing floats in C++: benchmarking strtod vs. from_chars

https://lemire.me/blog/2020/09/10/parsing-floats-in-c-benchmarking-strtod-vs-from_chars/

by ibobev • 6 years ago

61 14 6 years ago

wolf550e• 6 years ago

I guess someone has an optimized function for this which is faster than the one that comes with the compiler.

Someone• 6 years ago

…that doesn’t handle some edge cases (NaNs, infinities, denormalized numbers), or doesn’t round trip what to_chars produces for some values.

Parsing floating point strings, always producing the IEEE float or double closest to the number given, is surprisingly hard.

titzer• 6 years ago

NaNs and infinities are not the hard cases.

The hard cases are big exponents and large numbers of decimal digits. In general, it requires arbitrarily large integers (OK, OK, up to the maximum size of a double ~2^1023) and long division on said large integers. Denormalized is a pain for sure.

Did this recently. https://github.com/titzer/virgil/blob/master/aeneas/src/vst/...

alfalfasprout2• 6 years ago

I'm trying to think about which use cases would really be bottlenecked by parsing floats and they basically fall into two categories:

1) You're writing a JSON/some other human-readable serialization library 2) You need to interact with some API that you can't change that sends floats over the wire as strings (a subset of which will fall into the case of (1)).

For something like currencies you'd need a custom parsing engine anyways since you'll typically represent monetary values as fixed-width integer multiples of the smallest unit (eg; cents or basis points) except for trading engines where proper accounting isn't required. In fact, a lookup table may even be faster if the valid values are bounded.

My guess is most of the things in (2) are going to be reading telemetry from embedded devices with firmware that simply won't be changed anymore and values are sent as text.

dundarious2• 6 years ago

Except for trading engines is pretty big exception :) A lot of exchanges still use FIX, which is a very simple text format.

SAI_Peregrinus2• 6 years ago

JSON doesn't use Javascript doubles. It uses a custom format that excludes NaNs and Infinities. It allows arbitrary precision values: "A number is a sequence of decimal digits with no superfluous leading zero. It may have a preceding minus sign (U+002D). It may have a fractional part prefixed by a decimal point (U+002E). It may have an exponent, prefixed by e (U+0065) or E (U+0045) and optionally + (U+002B) or – (U+002D). The digits are the code points U+0030 through U+0039. Numeric values that cannot be represented as sequences of digits (such as Infinity and NaN) are not permitted."—ECMA-404[1]

That means that not all JSON values can be represented as IEEE754 doubles (Javascript Numbers) and not all IEEE754 doubles can be represented as JSON values. It's a lossy conversion.

[1] https://www.ecma-international.org/publications/files/ECMA-S...

osolo• 6 years ago

For those interested in more information about performance was achieved, Stephan Lavavej gave a talk about this very subject during CppCon 2019 [1].

[1] https://www.youtube.com/watch?v=4P_kbF0EbZM

jeffbee• 6 years ago

FWIW there is also absl::from_chars, with some included benchmarks and results at the bottom of the benchmark code.

https://github.com/abseil/abseil-cpp/blob/master/absl/string...

ETA: I adapted the benchmark in the blog to use absl::from_chars and it's more than twice as fast as strtod.

SAI_Peregrinus2• 6 years ago

The first example is incomplete: it forgets to clear and then check errno and/or check the returned value to +-HUGE_VAL! That'd probably slow down the strtod version a bit more.

jwilk• 6 years ago

strtod() could also return 0 on underflow.

But to be fair, the C++17 example doesn't check for underflow or overflow either.

thangalin• 6 years ago

Performance in the opposite direction is also useful; the Ryū algorithm[0] is a fast float-to-string conversion that I've used recently to great effect[1]. Namely, to convert path information from glyphs into vector graphics for a minimal math-oriented Java-based TeX implementation[2]. The result is code that converts 1,000 simple formulas as strings into individual SVG documents in under 600 milliseconds on newish hardware.

[0] https://github.com/ulfjack/ryu/blob/master/README.md

[1] https://news.ycombinator.com/item?id=17633182

[2] https://github.com/DaveJarvis/JMathTeX/blob/master/README.md

SomeoneFromCA• 6 years ago

Locale should not be a big deal in most of the code, since majority of applications use "C" locale anyways.

Parsing floats in C++: benchmarking strtod vs. from_chars

Related Stories