strconv: optimize ParseFloat with new refloat algorithm

[sugawarayuuta]

Floating point conversions are used in many places such as encoding/json. While the current Eisel-Lemire is efficient, you can actually use smaller lookup table and reduce execution time at the same time.
I implemented this algorithm in Go from start and now it's available through BSD-3-Clause license: https://github.com/sugawarayuuta/refloat

• Benchmarks

$ go test -bench "\d$" -benchmem -benchtime 1m
goos: linux
goarch: amd64
pkg: github.com/sugawarayuuta/refloat
cpu: Intel(R) Core(TM) i3-10110U CPU @ 2.10GHz
BenchmarkParseFloat64/strconv/bits-4            648877453              112.3 ns/op             0 B/op          0 allocs/op
BenchmarkParseFloat64/strconv/norm-4            729803588               95.37 ns/op            0 B/op          0 allocs/op
BenchmarkParseFloat64/refloat/bits-4            773428314               93.41 ns/op            0 B/op          0 allocs/op
BenchmarkParseFloat64/refloat/norm-4            1000000000              67.75 ns/op            0 B/op          0 allocs/op
BenchmarkParseFloat32/strconv/bits-4            894441672               82.30 ns/op            0 B/op          0 allocs/op
BenchmarkParseFloat32/strconv/norm-4            1000000000              67.97 ns/op            0 B/op          0 allocs/op
BenchmarkParseFloat32/refloat/bits-4            870175646               83.18 ns/op            3 B/op          0 allocs/op
BenchmarkParseFloat32/refloat/norm-4            1000000000              50.24 ns/op            0 B/op          0 allocs/op
PASS
ok      github.com/sugawarayuuta/refloat        612.972s

• Observation

We can see that it performs mostly better on normally distributed (norm) floats and bit-wise uniform floats (bits).
Benchmarks are done on multiple machines - they did produce results very similarly.
Especially normally distributed float64 has a significant change (~41%) which will fit in many real use-cases.

• Tests

passes parse-number-fxx-test-data, the standard libraries' tests and I'm doing active fuzz testing in addition comparing outputs to the current strconv. so far the only detected problem seems to be the issue 42436 which is a problem with strconv only.

• Notes

I actually used an external tool to generate polynomial approximations (Which is not distributed through the same license as the project itself). Do tell me if it can be a problem...

[ianlancetaylor]

Please add the output of golang.org/x/perf/cmd/benchstat comparing the benchmark output, run with -test.count=10, for both the current package and the package with your change. Thanks.

[sugawarayuuta]

Hi, thank you for commenting. I had to rerun the benchmark since I didn't specify -count 10 in the benchmark above, if you're OK with that. The left side is the standard library and the right side is my library.

                    │ ./strconv.txt │            ./refloat.txt            │
                    │    sec/op     │   sec/op     vs base                │
ParseFloat64/bits-4    104.85n ± 1%   92.11n ± 1%  -12.16% (p=0.000 n=10)
ParseFloat64/norm-4     95.04n ± 5%   68.89n ± 3%  -27.51% (p=0.000 n=10)
ParseFloat32/bits-4     80.86n ± 2%   84.44n ± 1%   +4.41% (p=0.000 n=10)
ParseFloat32/norm-4     65.97n ± 2%   48.88n ± 1%  -25.91% (p=0.000 n=10)
geomean                 85.39n        71.53n       -16.22%

                    │ ./strconv.txt │         ./refloat.txt          │
                    │     B/op      │    B/op     vs base            │
ParseFloat64/bits-4    0.000 ± 0%     0.000 ± 0%  ~ (p=1.000 n=10) ¹
ParseFloat64/norm-4    0.000 ± 0%     0.000 ± 0%  ~ (p=1.000 n=10) ¹
ParseFloat32/bits-4    0.000 ± 0%     3.000 ± 0%  ? (p=0.000 n=10)
ParseFloat32/norm-4    0.000 ± 0%     0.000 ± 0%  ~ (p=1.000 n=10) ¹
geomean                           ²               ?                ²
¹ all samples are equal
² summaries must be >0 to compute geomean

                    │ ./strconv.txt │            ./refloat.txt            │
                    │   allocs/op   │ allocs/op   vs base                 │
ParseFloat64/bits-4    0.000 ± 0%     0.000 ± 0%       ~ (p=1.000 n=10) ¹
ParseFloat64/norm-4    0.000 ± 0%     0.000 ± 0%       ~ (p=1.000 n=10) ¹
ParseFloat32/bits-4    0.000 ± 0%     0.000 ± 0%       ~ (p=1.000 n=10) ¹
ParseFloat32/norm-4    0.000 ± 0%     0.000 ± 0%       ~ (p=1.000 n=10) ¹
geomean                           ²               +0.00%                ²
¹ all samples are equal
² summaries must be >0 to compute geomean

[cherrymui]

@sugawarayuuta this is great! Thanks for sharing. It would be great if you send a change to optimize the strconv package. See https://go.dev/doc/contribute for how to contribute to Go, if you haven't seen it. Thanks!

[ianlancetaylor]

CC @griesemer

[sugawarayuuta]

Hi, kind of unfortunate. I tried to apply my parser to the strconv, and indeed it became faster. However after some hours of experimenting, It seemed that it's not the transformation (main algorithm) that's faster, but the reading part...
I'm sorry I didn't notice this issue, but since I confirmed only changing readFloat can speed up all of benchmarks in atof_test.go by considerable amount, can I send a change which covers the reading part? Should I edit this issue or create a new one? Thanks...

[odeke-em]

@sugawarayuuta nice work and thank you, please go ahead with firstly sending the change for readFloat, we appreciate it and look forward to interacting with you on your change! Later on, with enough time we can figure out how to completely transform your work for the whole of ParseFloat.

[gopherbot]

Change https://go.dev/cl/572235 mentions this issue: strconv: simplify and optimize the logic of readFloat