From a2eb53c571607bb0e64cb2996ca2bd402ad6e347 Mon Sep 17 00:00:00 2001 From: Nigel Tao Date: Fri, 9 Oct 2020 23:18:05 +1100 Subject: strconv: use the Eisel-Lemire ParseFloat algorithm MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Also fix BenchmarkAtof64Random* to initialize the test data when none of the TestAtof* tests are run. Passing "go test -test.count=5 -test.run=xxx -test.bench=Atof64" on to benchstat: name old time/op new time/op delta Atof64Decimal-4 47.9ns ± 0% 48.3ns ± 1% ~ (p=0.238 n=4+5) Atof64Float-4 58.3ns ± 3% 57.7ns ± 0% ~ (p=0.151 n=5+5) Atof64FloatExp-4 107ns ± 0% 71ns ± 1% -33.89% (p=0.016 n=4+5) Atof64Big-4 163ns ± 0% 166ns ± 2% ~ (p=0.159 n=4+5) Atof64RandomBits-4 299ns ± 1% 166ns ± 1% -44.41% (p=0.008 n=5+5) Atof64RandomFloats-4 188ns ± 1% 144ns ± 0% -23.03% (p=0.008 n=5+5) The canada.json file from github.com/miloyip/nativejson-benchmark is full of geospatial coordinates (i.e. numbers). With this program: src, _ := ioutil.ReadFile("canada.json") for i := 0; i < 5; i++ { now := time.Now() for j := 0; j < 10; j++ { dst := interface{}(nil) if err := json.Unmarshal(src, &dst); err != nil { log.Fatal(err) } } fmt.Println(time.Since(now)) } Median of the 5 printed numbers, lower is better. Before: 760.819549ms After: 702.651646ms Ratio: 1.08x The new detailedPowersOfTen table weighs in at 596 * 16 = 9536 bytes, but some of that weight gain can be clawed back, in a follow-up commit, that folds in the existing powersOfTen table in extfloat.go. RELNOTE=yes Change-Id: I3953110deaa1f5f6941e88e8417c4665b649ed80 Reviewed-on: https://go-review.googlesource.com/c/go/+/260858 Run-TryBot: Nigel Tao TryBot-Result: Go Bot Reviewed-by: Robert Griesemer Trust: Nigel Tao --- src/strconv/atof.go | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'src/strconv/atof.go') diff --git a/src/strconv/atof.go b/src/strconv/atof.go index 901f27afff..c0b9c1f1e0 100644 --- a/src/strconv/atof.go +++ b/src/strconv/atof.go @@ -624,10 +624,13 @@ func atof64(s string) (f float64, n int, err error) { } if optimize { - // Try pure floating-point arithmetic conversion. + // Try pure floating-point arithmetic conversion, and if that fails, + // the Eisel-Lemire algorithm. if !trunc { if f, ok := atof64exact(mantissa, exp, neg); ok { return f, n, nil + } else if f, ok = eiselLemire(mantissa, exp, neg); ok { + return f, n, nil } } // Try another fast path. -- cgit v1.2.1 From 7e01b3b3879593828b89f4ff4a04667a547b22d9 Mon Sep 17 00:00:00 2001 From: Nigel Tao Date: Fri, 23 Oct 2020 10:41:50 +1100 Subject: strconv: add eiselLemire32 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit This does for ParseFloat(etc, 32) what commit a2eb53c571 did for ParseFloat(etc, 64). name old time/op new time/op delta Atof32Decimal-4 48.3ns ± 4% 48.8ns ± 2% ~ (p=0.548 n=5+5) Atof32Float-4 56.2ns ± 5% 54.7ns ± 3% ~ (p=0.246 n=5+5) Atof32FloatExp-4 104ns ± 0% 76ns ± 2% -27.19% (p=0.008 n=5+5) Atof32Random-4 142ns ± 2% 109ns ± 1% -23.07% (p=0.008 n=5+5) Change-Id: I6ee5a2f2d791d4fe3028f1d40aca96400120fda0 Reviewed-on: https://go-review.googlesource.com/c/go/+/264517 Trust: Nigel Tao Trust: Robert Griesemer Reviewed-by: Robert Griesemer --- src/strconv/atof.go | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'src/strconv/atof.go') diff --git a/src/strconv/atof.go b/src/strconv/atof.go index c0b9c1f1e0..e61eeab1c3 100644 --- a/src/strconv/atof.go +++ b/src/strconv/atof.go @@ -581,6 +581,8 @@ func atof32(s string) (f float32, n int, err error) { if !trunc { if f, ok := atof32exact(mantissa, exp, neg); ok { return f, n, nil + } else if f, ok = eiselLemire32(mantissa, exp, neg); ok { + return f, n, nil } } // Try another fast path. @@ -629,7 +631,7 @@ func atof64(s string) (f float64, n int, err error) { if !trunc { if f, ok := atof64exact(mantissa, exp, neg); ok { return f, n, nil - } else if f, ok = eiselLemire(mantissa, exp, neg); ok { + } else if f, ok = eiselLemire64(mantissa, exp, neg); ok { return f, n, nil } } -- cgit v1.2.1