strconv: optimize formatting for small decimal ints

Avoid memory allocations by returning pre-calculated strings
for decimal ints in the range 0..99.

Benchmark results:

name              old time/op    new time/op    delta
FormatInt-4         2.45µs ± 1%    2.40µs ± 1%    -1.86%  (p=0.000 n=8+9)
AppendInt-4         1.67µs ± 1%    1.65µs ± 0%    -0.92%  (p=0.000 n=10+10)
FormatUint-4         676ns ± 3%     669ns ± 1%      ~     (p=0.146 n=10+10)
AppendUint-4         467ns ± 2%     474ns ± 0%    +1.58%  (p=0.000 n=10+10)
FormatIntSmall-4    29.6ns ± 2%     3.3ns ± 0%   -88.98%  (p=0.000 n=10+9)
AppendIntSmall-4    16.0ns ± 1%     8.5ns ± 0%   -46.98%  (p=0.000 n=10+9)

name              old alloc/op   new alloc/op   delta
FormatInt-4           576B ± 0%      576B ± 0%      ~     (all equal)
AppendInt-4          0.00B          0.00B           ~     (all equal)
FormatUint-4          224B ± 0%      224B ± 0%      ~     (all equal)
AppendUint-4         0.00B          0.00B           ~     (all equal)
FormatIntSmall-4     2.00B ± 0%     0.00B       -100.00%  (p=0.000 n=10+10)
AppendIntSmall-4     0.00B          0.00B           ~     (all equal)

name              old allocs/op  new allocs/op  delta
FormatInt-4           37.0 ± 0%      35.0 ± 0%    -5.41%  (p=0.000 n=10+10)
AppendInt-4           0.00           0.00           ~     (all equal)
FormatUint-4          6.00 ± 0%      6.00 ± 0%      ~     (all equal)
AppendUint-4          0.00           0.00           ~     (all equal)
FormatIntSmall-4      1.00 ± 0%      0.00       -100.00%  (p=0.000 n=10+10)
AppendIntSmall-4      0.00           0.00           ~     (all equal)

Fixes #19445

Change-Id: Ib1f8922f2e0b13743c847ee9e703d1dab77f705c
Reviewed-on: https://go-review.googlesource.com/37963
Reviewed-by: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

2 files changed, 52 insertions, 4 deletions

diff --git a/src/strconv/itoa.go b/src/strconv/itoa.go
index d0b4258d76..2a21185a6b 100644
--- a/src/strconv/itoa.go
+++ b/src/strconv/itoa.go
@@ -8,6 +8,9 @@ package strconv
 // for 2 <= base <= 36. The result uses the lower-case letters 'a' to 'z'
 // for digit values >= 10.
 func FormatUint(i uint64, base int) string {
+	if i < uint64(len(smallints)) && base == 10 {
+		return smallints[i]
+	}
 	_, s := formatBits(nil, i, base, false, false)
 	return s
 }
@@ -16,6 +19,9 @@ func FormatUint(i uint64, base int) string {
 // for 2 <= base <= 36. The result uses the lower-case letters 'a' to 'z'
 // for digit values >= 10.
 func FormatInt(i int64, base int) string {
+	if 0 <= i && i < int64(len(smallints)) && base == 10 {
+		return smallints[i]
+	}
 	_, s := formatBits(nil, uint64(i), base, i < 0, false)
 	return s
 }
@@ -28,6 +34,9 @@ func Itoa(i int) string {
 // AppendInt appends the string form of the integer i,
 // as generated by FormatInt, to dst and returns the extended buffer.
 func AppendInt(dst []byte, i int64, base int) []byte {
+	if 0 <= i && i < int64(len(smallints)) && base == 10 {
+		return append(dst, smallints[i]...)
+	}
 	dst, _ = formatBits(dst, uint64(i), base, i < 0, true)
 	return dst
 }
@@ -35,6 +44,9 @@ func AppendInt(dst []byte, i int64, base int) []byte {
 // AppendUint appends the string form of the unsigned integer i,
 // as generated by FormatUint, to dst and returns the extended buffer.
 func AppendUint(dst []byte, i uint64, base int) []byte {
+	if i < uint64(len(smallints)) && base == 10 {
+		return append(dst, smallints[i]...)
+	}
 	dst, _ = formatBits(dst, i, base, false, true)
 	return dst
 }
@@ -43,6 +55,19 @@ const host32bit = ^uint(0)>>32 == 0
 
 const digits = "0123456789abcdefghijklmnopqrstuvwxyz"
 
+var smallints = [...]string{
+	"0", "1", "2", "3", "4", "5", "6", "7", "8", "9",
+	"10", "11", "12", "13", "14", "15", "16", "17", "18", "19",
+	"20", "21", "22", "23", "24", "25", "26", "27", "28", "29",
+	"30", "31", "32", "33", "34", "35", "36", "37", "38", "39",
+	"40", "41", "42", "43", "44", "45", "46", "47", "48", "49",
+	"50", "51", "52", "53", "54", "55", "56", "57", "58", "59",
+	"60", "61", "62", "63", "64", "65", "66", "67", "68", "69",
+	"70", "71", "72", "73", "74", "75", "76", "77", "78", "79",
+	"80", "81", "82", "83", "84", "85", "86", "87", "88", "89",
+	"90", "91", "92", "93", "94", "95", "96", "97", "98", "99",
+}
+
 var shifts = [len(digits) + 1]uint{
 	1 << 1: 1,
 	1 << 2: 2,
diff --git a/src/strconv/itoa_test.go b/src/strconv/itoa_test.go
index 48dc03e839..7823cf4673 100644
--- a/src/strconv/itoa_test.go
+++ b/src/strconv/itoa_test.go
@@ -129,7 +129,8 @@ func TestUitoa(t *testing.T) {
 func BenchmarkFormatInt(b *testing.B) {
 	for i := 0; i < b.N; i++ {
 		for _, test := range itob64tests {
-			FormatInt(test.in, test.base)
+			s := FormatInt(test.in, test.base)
+			BenchSink += len(s)
 		}
 	}
 }
@@ -138,7 +139,8 @@ func BenchmarkAppendInt(b *testing.B) {
 	dst := make([]byte, 0, 30)
 	for i := 0; i < b.N; i++ {
 		for _, test := range itob64tests {
-			AppendInt(dst, test.in, test.base)
+			dst = AppendInt(dst[:0], test.in, test.base)
+			BenchSink += len(dst)
 		}
 	}
 }
@@ -146,7 +148,8 @@ func BenchmarkAppendInt(b *testing.B) {
 func BenchmarkFormatUint(b *testing.B) {
 	for i := 0; i < b.N; i++ {
 		for _, test := range uitob64tests {
-			FormatUint(test.in, test.base)
+			s := FormatUint(test.in, test.base)
+			BenchSink += len(s)
 		}
 	}
 }
@@ -155,7 +158,27 @@ func BenchmarkAppendUint(b *testing.B) {
 	dst := make([]byte, 0, 30)
 	for i := 0; i < b.N; i++ {
 		for _, test := range uitob64tests {
-			AppendUint(dst, test.in, test.base)
+			dst = AppendUint(dst[:0], test.in, test.base)
+			BenchSink += len(dst)
 		}
 	}
 }
+
+func BenchmarkFormatIntSmall(b *testing.B) {
+	const smallInt = 42
+	for i := 0; i < b.N; i++ {
+		s := FormatInt(smallInt, 10)
+		BenchSink += len(s)
+	}
+}
+
+func BenchmarkAppendIntSmall(b *testing.B) {
+	dst := make([]byte, 0, 30)
+	const smallInt = 42
+	for i := 0; i < b.N; i++ {
+		dst = AppendInt(dst[:0], smallInt, 10)
+		BenchSink += len(dst)
+	}
+}
+
+var BenchSink int // make sure compiler cannot optimize away benchmarks