Floating-point number parsing with perfect accuracy at a gigabyte per second

Daniel Lemire
professor, Université du Québec (TÉLUQ)Montreal
blog: https://lemire.me
twitter: @lemire
GitHub: https://github.com/lemire/
work with Michael Eisel, Ivan Smirnov, Nigel Tao, R. Oudompheng, Carl Verret andothers!

How fast is your disk?

PCIe 4 disks: 5 GB/s reading speed (sequential)

2

Fact

Single-core processes are often CPU bound3How fast can you ingest data?
{ "type": "FeatureCollection","features": [[[[-65.613616999999977,43.420273000000009],[-65.619720000000029,43.418052999999986],[-65.625,43.421379000000059],[-65.636123999999882,43.449714999999969],[-65.633056999999951,43.474709000000132],[-65.611389000000031,43.513054000000068],[-65.605835000000013,43.516105999999979],[-65.598343,43.515830999999935],[-65.566101000000003,43.508331000000055],...

4

How fast can you parse numbers?
std::stringstream in(mystring);
while(in >> x) {sum += x;}
return sum;

50 MB/s (Linux, GCC -O3)
Source: https://lemire.me/blog/2019/10/26/how-expensive-is-it-to-parse-numbers-froma-string-in-c/5Some arithmetic

5 GB/s divided by 50 MB/s is 100.
Got 100 CPU cores?
Want to cause climate change all on your own?

6How to go faster?

Fewer instructions (simpler code)
Fewer branches

7How fast can you go?

AMD Rome (Zen 2). GNU GCC 10, -O3.
function bandwidth instructions ins/cycle
strtod (GCC 10) 200 MB/s 1100
3ours
1.1 GB/s 280
4.2
17-digit mantissa, random in [0,1].
8

Floats are easy

Standard in Java, Go, Python, Swift, JavaScript...
IEEE standard well supported on all recent systems
64-bit floats can represent all integers up to 253 exactly.

9Floats are hard
> 0.1 + 0.2 == 0.3
false

10

Generic rules regarding "exact" IEEE support

Always round to nearest floating-point number (*,+,/)
Resolve ties by rounding to nearest with an even decimal mantissa/significand.

11

Benefits

Predictable outcomes.
Debuggability.
Cross-language compatibility (same results).

12

Challenges

Machine A writes float x to string
Machine B reads string gets float x′
Machine C reads string gets float x′′
Do you have x = x′ and x = x′′ ?
13

What is the problem?
Need to go from(e.g., 123e5)
tow × 10q

m × 2p14

Example
0.1 → 7205759403792793 × 2−560.10000000000000000555

0.2 → 7205759403792794 × 2−55

0.2000000000000000111

0.3 → 5404319552844595 × 2−54

0.29999999999999998889776975

15

ProblemsStart with 32323232132321321111e124.
Lookup 10124 as a float (not exact)
Convert 32323232132321321111 to a float (not exact)
Compute (10124 ) × (32323232132321321111)
Approximation × Approximation = Even worse approximation!
16

Insight

You can always represent floats exactly (binary64) using at most 17 digits.
Never to this:3.141592653589793238462643383279502884197169399375105820974944592
3078164062862089986280348253421170679
17

credit: xkcd

18

We have 64-bit processors

So we can express all positive floats as12345678901234567E+/-123 .
Or w × 10q
where mantissa w < 1017
But 1017 fits in a 64-bit word!
19Factorization
10 = 5 × 220

Overall algorithm

Parse decimal mantissa to a 64-bit word!
Precompute 5q for all powers with up to 128-bit accuracy.
Multiply!
Figure out right power of two
Tricks:Deal with "subnormals"
Handle excessively large numbers (infinity)
Round-to-nearest, tie to even21Check whether we have 8 consecutive digitsbool is_made_of_eight_digits_fast(const char *chars) {uint64_t val;
memcpy(&val, chars, 8);
return (((val & 0xF0F0F0F0F0F0F0F0) |(((val + 0x0606060606060606) & 0xF0F0F0F0F0F0F0F0) >> 4))== 0x3333333333333333);}(Works with ASCII, harder if input is UTF-16 as in Java/C#)
22

Then construct the corresponding integer
Using only three multiplications (instead of 7):

uint32_t parse_eight_digits_unrolled(const char *chars) {uint64_t val;
memcpy(&val, chars, sizeof(uint64_t));val = (val & 0x0F0F0F0F0F0F0F0F) * 2561 >> 8;
val = (val & 0x00FF00FF00FF00FF) * 6553601 >> 16;
return (val & 0x0000FFFF0000FFFF) * 42949672960001 >> 32;}

23

Positive powers

Compute w × 5q where 5q is only approximate (128 bits)
99.99% of the time, you get provably accurate 55 bits

24

Negative powers

Compilers replace division by constants with multiply and shiftcredit: godbolt
Reading: Integer Division by Constants: Optimal Bounds, https://arxiv.org/abs/2012.12369
25

Negative powers

Precompute 2b /5q (reciprocal, 128-bit precision)
99.99% of the time, you get provably accurate results

26

What about tie to even?
Need absolutely exact mantissa computation, to infinite precision.
But only happens for small decimal powers (q ∈ [−4, 23]) where absolutely exact
results are practical.

27

What if you have more than 19 digits?

Truncate the mantissa to 19 digits, map to w.
Do the work for w × 10q
Do the work for (w + 1) × 10q
When get same results, you are done. (99% of the time)28

OverallWith 64-bit mantissa.
With 128-bit powers of five.
Can do exact computation 99.99% of the time.
Fast, cheap, accurate.
29

Full product?

64-bit × 64-bit → 128-bit product
GNU GCC: __uint128_t .
Microsoft Visual Studio: _umul128
ARM intrinsic: __umulh
Go: bits.Mul64
C#: Math.BigMul
30

Leading zeros

How many consecutive leading zeros in 64-bit word?
GNU GCC: __builtin_clzll
Microsoft Visual Studio: _BitScanReverse64
C++20: std::countl_zero
Go: bits.LeadingZeros64
C#: BitOperations.LeadingZeroCount31

https://github.com/lemire/fast_float
GNU GCC
LLVM clang
used by Apache Arrow, Yandex ClickHouse, Microsoft LightGBM

32

Go
Algorithm adapted to Go's standard library (ParseFloat) by Nigel Tao and others
Release notes (version 1.16): ParseFloat (...) improving performance by up to a factorof 2.
Perfect rounding.
Blog post by Tao: The Eisel-Lemire ParseNumberF64 Algorithm
33Rustfunction
speed
from_str (standard) 130 MB/s
lexical (popular lib.) 370 MB/s
fast-float
1200 MB/s
34

R

rcppfastfloat: https://github.com/eddelbuettel/rcppfastfloat
3x faster than standard library35

C#is 5x faster than standard library ( Double.Parse )https://github.com/CarlVerret/csFastFloat/
credit: Carl Verret, Egor Bogatov (Microsoft) and others
FastFloat.ParseDouble

36

Further reading

Daniel Lemire, Number Parsing at a Gigabyte per Second, Software: Practice andExperience (to appear) https://arxiv.org/abs/2101.11408
Blog: https://lemire.me/blog/37