From f43e012084c4edd381d21c9988638535696775ea Mon Sep 17 00:00:00 2001
From: =?utf8?q?R=C3=A9my=20Oudompheng?= <remyoudompheng@gmail.com>
Date: Fri, 23 Oct 2020 22:23:21 +0200
Subject: [PATCH] strconv: make Eisel-Lemire handle long mantissas
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

In many cases, it is not necessary to parse long
decimal mantissas entirely to produce the correctly
rounded floating-point number. It is enough to parse
the short, rounded lower and upper bounds and in most cases
they round to the same floating point number because uint64
can hold 19 digits.

Previously this case was handled by the extFloat code path
(Grisu3 algorithm).

name                      old time/op  new time/op  delta
Atof64Big-4               1.07µs ± 2%  0.11µs ± 2%  -89.61%  (p=0.000 n=10+9)
Atof64RandomLongFloats-4  8.03µs ± 2%  0.14µs ± 7%  -98.24%  (p=0.000 n=10+10)
Atof32RandomLong-4         760ns ± 1%   156ns ± 0%  -79.46%  (p=0.000 n=10+8)

Benchmarks versus extFloat:

name                      old time/op  new time/op  delta
Atof64Big-4                121ns ± 3%   111ns ± 2%   -7.93%  (p=0.000 n=10+9)
Atof64RandomLongFloats-4   144ns ± 1%   142ns ± 7%     ~     (p=0.167 n=10+10)
Atof32RandomLong-4         129ns ± 1%   156ns ± 0%  +21.12%  (p=0.000 n=10+8)

Change-Id: Id734b8c11e74b49a444fda67ee72870ae9422e60
Reviewed-on: https://go-review.googlesource.com/c/go/+/264677
Trust: Emmanuel Odeke <emmanuel@orijtech.com>
Trust: Russ Cox <rsc@golang.org>
Run-TryBot: Emmanuel Odeke <emmanuel@orijtech.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Nigel Tao <nigeltao@golang.org>
---
 src/strconv/atof.go      | 44 +++++++++++++++++++++++++++++++---------
 src/strconv/atof_test.go | 33 ++++++++++++++++++++++++++++--
 2 files changed, 65 insertions(+), 12 deletions(-)

diff --git a/src/strconv/atof.go b/src/strconv/atof.go
index c0385170cb..9010a66ca8 100644
--- a/src/strconv/atof.go
+++ b/src/strconv/atof.go
@@ -576,14 +576,26 @@ func atof32(s string) (f float32, n int, err error) {
 		return float32(f), n, err
 	}
 
-	if optimize && !trunc {
+	if optimize {
 		// Try pure floating-point arithmetic conversion, and if that fails,
 		// the Eisel-Lemire algorithm.
-		if f, ok := atof32exact(mantissa, exp, neg); ok {
-			return f, n, nil
+		if !trunc {
+			if f, ok := atof32exact(mantissa, exp, neg); ok {
+				return f, n, nil
+			}
 		}
-		if f, ok := eiselLemire32(mantissa, exp, neg); ok {
-			return f, n, nil
+		f, ok := eiselLemire32(mantissa, exp, neg)
+		if ok {
+			if !trunc {
+				return f, n, nil
+			}
+			// Even if the mantissa was truncated, we may
+			// have found the correct result. Confirm by
+			// converting the upper mantissa bound.
+			fUp, ok := eiselLemire32(mantissa+1, exp, neg)
+			if ok && f == fUp {
+				return f, n, nil
+			}
 		}
 	}
 
@@ -615,14 +627,26 @@ func atof64(s string) (f float64, n int, err error) {
 		return f, n, err
 	}
 
-	if optimize && !trunc {
+	if optimize {
 		// Try pure floating-point arithmetic conversion, and if that fails,
 		// the Eisel-Lemire algorithm.
-		if f, ok := atof64exact(mantissa, exp, neg); ok {
-			return f, n, nil
+		if !trunc {
+			if f, ok := atof64exact(mantissa, exp, neg); ok {
+				return f, n, nil
+			}
 		}
-		if f, ok := eiselLemire64(mantissa, exp, neg); ok {
-			return f, n, nil
+		f, ok := eiselLemire64(mantissa, exp, neg)
+		if ok {
+			if !trunc {
+				return f, n, nil
+			}
+			// Even if the mantissa was truncated, we may
+			// have found the correct result. Confirm by
+			// converting the upper mantissa bound.
+			fUp, ok := eiselLemire64(mantissa+1, exp, neg)
+			if ok && f == fUp {
+				return f, n, nil
+			}
 		}
 	}
 
diff --git a/src/strconv/atof_test.go b/src/strconv/atof_test.go
index 25ec1a9a51..5a6fec8d3b 100644
--- a/src/strconv/atof_test.go
+++ b/src/strconv/atof_test.go
@@ -674,6 +674,23 @@ func BenchmarkAtof64RandomFloats(b *testing.B) {
 	}
 }
 
+func BenchmarkAtof64RandomLongFloats(b *testing.B) {
+	initAtof()
+	samples := make([]string, len(atofRandomTests))
+	for i, t := range atofRandomTests {
+		samples[i] = FormatFloat(t.x, 'g', 20, 64)
+	}
+	b.ResetTimer()
+	idx := 0
+	for i := 0; i < b.N; i++ {
+		ParseFloat(samples[idx], 64)
+		idx++
+		if idx == len(samples) {
+			idx = 0
+		}
+	}
+}
+
 func BenchmarkAtof32Decimal(b *testing.B) {
 	for i := 0; i < b.N; i++ {
 		ParseFloat("33909", 32)
@@ -692,10 +709,9 @@ func BenchmarkAtof32FloatExp(b *testing.B) {
 	}
 }
 
-var float32strings [4096]string
-
 func BenchmarkAtof32Random(b *testing.B) {
 	n := uint32(997)
+	var float32strings [4096]string
 	for i := range float32strings {
 		n = (99991*n + 42) % (0xff << 23)
 		float32strings[i] = FormatFloat(float64(math.Float32frombits(n)), 'g', -1, 32)
@@ -705,3 +721,16 @@ func BenchmarkAtof32Random(b *testing.B) {
 		ParseFloat(float32strings[i%4096], 32)
 	}
 }
+
+func BenchmarkAtof32RandomLong(b *testing.B) {
+	n := uint32(997)
+	var float32strings [4096]string
+	for i := range float32strings {
+		n = (99991*n + 42) % (0xff << 23)
+		float32strings[i] = FormatFloat(float64(math.Float32frombits(n)), 'g', 20, 32)
+	}
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		ParseFloat(float32strings[i%4096], 32)
+	}
+}
-- 
2.48.1