From bc8b9b23ca3f33e738d85c4734bd35dfe63e9ac4 Mon Sep 17 00:00:00 2001 From: Aliaksandr Valialkin Date: Thu, 9 Mar 2017 12:29:45 +0200 Subject: [PATCH] strconv: optimize formatting for small decimal ints MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 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 Run-TryBot: Robert Griesemer TryBot-Result: Gobot Gobot --- src/strconv/itoa.go | 25 +++++++++++++++++++++++++ src/strconv/itoa_test.go | 31 +++++++++++++++++++++++++++---- 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 -- 2.48.1