diff options
| author | Martin Möhrmann <moehrmann@google.com> | 2018-05-01 11:39:17 +0200 |
|---|---|---|
| committer | Brad Fitzpatrick <bradfitz@golang.org> | 2018-05-01 15:48:15 +0000 |
| commit | d29ec40e19fa0548292bb0bf2a4fb88920838877 (patch) | |
| tree | db7d057db12d558982bada34e28c15cb55946a6c /src/strconv | |
| parent | f8ef6ed24a65ef50cb81510a5720abf406c90642 (diff) | |
| download | go-d29ec40e19fa0548292bb0bf2a4fb88920838877.tar.gz go-d29ec40e19fa0548292bb0bf2a4fb88920838877.zip | |
strconv: use bounded bits.TrailingZeros instead of shifts table
The strconv shifts table is 320 bytes (amd64) and is present in
many binaries since integer formatting is very common.
Instead of using a precalculated table with shift amounts
use a bounded bits.TrailingZeros to determine the shift amount
to format numbers in a base that is a power of 2.
amd64:
name old time/op new time/op delta
AppendUint 379ns ± 1% 286ns ± 2% -24.62% (p=0.000 n=20+19)
Change-Id: Ib94d9b033321b41e975868943c7fcd9428c5111e
Reviewed-on: https://go-review.googlesource.com/110478
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Diffstat (limited to 'src/strconv')
| -rw-r--r-- | src/strconv/itoa.go | 25 |
1 files changed, 13 insertions, 12 deletions
diff --git a/src/strconv/itoa.go b/src/strconv/itoa.go index 78527c8ae6..394716ccd7 100644 --- a/src/strconv/itoa.go +++ b/src/strconv/itoa.go @@ -4,6 +4,8 @@ package strconv +import "math/bits" + const fastSmalls = true // enable fast path for small integers // FormatUint returns the string representation of i in the given base, @@ -79,14 +81,6 @@ const host32bit = ^uint(0)>>32 == 0 const digits = "0123456789abcdefghijklmnopqrstuvwxyz" -var shifts = [len(digits) + 1]uint{ - 1 << 1: 1, - 1 << 2: 2, - 1 << 3: 3, - 1 << 4: 4, - 1 << 5: 5, -} - // formatBits computes the string representation of u in the given base. // If neg is set, u is treated as negative int64 value. If append_ is // set, the string is appended to dst and the resulting byte slice is @@ -158,14 +152,17 @@ func formatBits(dst []byte, u uint64, base int, neg, append_ bool) (d []byte, s a[i] = smallsString[is] } - } else if s := shifts[base]; s > 0 { - // base is power of 2: use shifts and masks instead of / and % + } else if isPowerOfTwo(base) { + // It is known that base is a power of two and + // 2 <= base <= len(digits). + // Use shifts and masks instead of / and %. + shift := uint(bits.TrailingZeros(uint(base))) & 31 b := uint64(base) - m := uint(base) - 1 // == 1<<s - 1 + m := uint(base) - 1 // == 1<<shift - 1 for u >= b { i-- a[i] = digits[uint(u)&m] - u >>= s + u >>= shift } // u < base i-- @@ -200,3 +197,7 @@ func formatBits(dst []byte, u uint64, base int, neg, append_ bool) (d []byte, s s = string(a[i:]) return } + +func isPowerOfTwo(x int) bool { + return x&(x-1) == 0 +} |