robust float parsing in the standard library

[andrewrk]

Thanks to @tiehuis's work in #1958, #375 is closed and zig has basic float parsing in the standard library. But as he notes, there are the following deficiencies:

• it doesn't handle some edge cases
• error behavior is not zig-idiomatic
• handling the edge cases might require an allocator
• does not handle hex floats

I did a proof of concept of porting musl's float parsing code to implement f128 parsing in stage1. You can see this implementation in parse_f128.c. I believe that further porting this code to the Zig standard library would check all the above boxes.

This issue is the "deserialization" side of #1181. Note the goal stated in #1181 (comment):

I would like to propose that the default float printing and default float parsing in Zig should have roundtrip bit-for-bit value preservation for all values for all float types.

[mattsta]

jumping in randomly here: for battle-tested float parsing, also check out the sqlite and luajit input parsers and compare their tradeoffs and performance characteristics (both are implemented to be more instruction cache friendly than stdlib versions too):

• sqlite float parser: https://github.com/mackyle/sqlite/blob/ae5d3aa91a794f6f1486b3f453ec44c0aa4c086b/src/util.c#L375-L571
• luajit float parser: https://github.com/LuaJIT/LuaJIT/blob/b025b01c5b9d23f6218c7d72b7aafa3f1ab1e08a/src/lj_strscan.c#L15-L327

and as for roundtrip bit-for-bit value preservation (ignoring things like f16 having 2k "unique" NaNs (and same-meaning-different-bits just gets worse with larger binary lengths)), the best I end up with when running my systems in "super paranoid mode" is: parse string to native float/double/long double, convert native float back to string, string compare original string to see if match is exact.

But, now an entire new decision opens up: which reliable float pretty print algorithm will conversions be tested against?

• https://www.cs.indiana.edu/~dyb/pubs/FP-Printing-PLDI96.pdf
• http://kurtstephens.com/files/p372-steele.pdf
• https://cseweb.ucsd.edu/~lerner/papers/fp-printing-popl16.pdf
• https://www.cs.tufts.edu/~nr/cs257/archive/florian-loitsch/printf.pdf

[tiehuis]

It should be safe to assume that Ryu will be used. This currently is not in std (there is a bit more work to do regarding fixed precision modes) but I have an implementation of this here: https://github.com/tiehuis/zig-ryu that should be usable for testing.

[tiehuis]

An upstream string to f64 float parsing function was added to ryu recently: https://github.com/ulfjack/ryu/blob/master/ryu/s2d.c

[tiehuis]

Would suggest reading the paper Number Parsing at a Gigabyte per Second.

Example implementations in other languages:

• https://github.com/fastfloat/fast_float
• https://github.com/rust-lang/rust/tree/master/library/core/src/num/dec2flt
• Go
  • https://go.dev/src/strconv/atof.go
  • https://go.dev/src/strconv/decimal.go
  • https://go.dev/src/strconv/eisel_lemire.go

Other useful high-level reading:

• https://nigeltao.github.io/blog/2020/eisel-lemire.html
• https://nigeltao.github.io/blog/2020/parse-number-f64-simple.html

[tiehuis]

See https://github.com/tiehuis/zig-parsefloat for an implementation of the above method.