Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

strconv: optimize ParseFloat with new refloat algorithm #66327

Open
sugawarayuuta opened this issue Mar 15, 2024 · 7 comments
Open

strconv: optimize ParseFloat with new refloat algorithm #66327

sugawarayuuta opened this issue Mar 15, 2024 · 7 comments
Labels
NeedsFix The path to resolution is known, but the work has not been done. Performance
Milestone
Unplanned

Comments

@sugawarayuuta
Copy link

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
Copy link
Contributor

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
Copy link
Author

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 cherrymui added this to the Unplanned milestone Mar 15, 2024
@cherrymui cherrymui added the NeedsFix The path to resolution is known, but the work has not been done. label Mar 15, 2024
@cherrymui
Copy link
Member

@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
Copy link
Contributor

CC @griesemer

@sugawarayuuta
Copy link
Author

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
Copy link
Member

@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
Copy link

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
NeedsFix The path to resolution is known, but the work has not been done. Performance
Projects
None yet
Milestone
Unplanned
Development

No branches or pull requests
5 participants
@ianlancetaylor @odeke-em @gopherbot @cherrymui @sugawarayuuta