Repository: segmentio/encoding
Pull request #49 (2020-09-17 09:47:10)

Faster integer encoding
This PR adds faster versions of the `strconv.Append(U)Int` functions from the stdlib.

```
name           old time/op    new time/op    delta
CodeEncoder-4    2.51ms ± 1%    2.31ms ± 2%   -7.72%  (p=0.000 n=9+9)

name           old speed      new speed      delta
CodeEncoder-4   774MB/s ± 1%   838MB/s ± 2%   +8.37%  (p=0.000 n=9+9)
```

The algorithm is the same — the gains come from:
- inlining the append calls by moving [these](https://github.com/golang/go/blob/ed78c90a784f9703857c3303d871b973ee2f0102/src/strconv/itoa.go#L41-L43) [chunks](https://github.com/golang/go/blob/ed78c90a784f9703857c3303d871b973ee2f0102/src/strconv/itoa.go#L51-L53) of code into the [inner](https://github.com/golang/go/blob/ed78c90a784f9703857c3303d871b973ee2f0102/src/strconv/itoa.go#L44) function which already couldn't be inlined
- replacing the [lookup table of bytes](https://github.com/golang/go/blob/ed78c90a784f9703857c3303d871b973ee2f0102/src/strconv/itoa.go#L68) with a lookup table of `uint16`, and copying two bytes at a time rather than one
- removing unneeded functionality [such as](https://github.com/golang/go/blob/ed78c90a784f9703857c3303d871b973ee2f0102/src/strconv/itoa.go#L90-L92) supporting bases other than 10

```
name                  time/op
AppendIntStd1-4       5.93ns ± 0%
AppendIntStdMinI64-4  33.7ns ± 0%
```
```
name                  time/op
AppendInt1-4          3.47ns ± 1%
AppendIntMinI64-4     22.0ns ± 1%
```

I haven't ported across the `host32bit` [branch](https://github.com/golang/go/blob/ed78c90a784f9703857c3303d871b973ee2f0102/src/strconv/itoa.go#L109) and so the encoding of `(u)int64` values may take a hit on 32-bit systems.


Patch:
diff --git a/json/encode.go b/json/encode.go
index e6e1e29..eb001c8 100644
--- a/json/encode.go
+++ b/json/encode.go
@@ -27,47 +27,47 @@ func (e encoder) encodeBool(b []byte, p unsafe.Pointer) ([]byte, error) {
 }
 
 func (e encoder) encodeInt(b []byte, p unsafe.Pointer) ([]byte, error) {
-	return strconv.AppendInt(b, int64(*(*int)(p)), 10), nil
+	return appendInt(b, int64(*(*int)(p))), nil
 }
 
 func (e encoder) encodeInt8(b []byte, p unsafe.Pointer) ([]byte, error) {
-	return strconv.AppendInt(b, int64(*(*int8)(p)), 10), nil
+	return appendInt(b, int64(*(*int8)(p))), nil
 }
 
 func (e encoder) encodeInt16(b []byte, p unsafe.Pointer) ([]byte, error) {
-	return strconv.AppendInt(b, int64(*(*int16)(p)), 10), nil
+	return appendInt(b, int64(*(*int16)(p))), nil
 }
 
 func (e encoder) encodeInt32(b []byte, p unsafe.Pointer) ([]byte, error) {
-	return strconv.AppendInt(b, int64(*(*int32)(p)), 10), nil
+	return appendInt(b, int64(*(*int32)(p))), nil
 }
 
 func (e encoder) encodeInt64(b []byte, p unsafe.Pointer) ([]byte, error) {
-	return strconv.AppendInt(b, *(*int64)(p), 10), nil
+	return appendInt(b, *(*int64)(p)), nil
 }
 
 func (e encoder) encodeUint(b []byte, p unsafe.Pointer) ([]byte, error) {
-	return strconv.AppendUint(b, uint64(*(*uint)(p)), 10), nil
+	return appendUint(b, uint64(*(*uint)(p))), nil
 }
 
 func (e encoder) encodeUintptr(b []byte, p unsafe.Pointer) ([]byte, error) {
-	return strconv.AppendUint(b, uint64(*(*uintptr)(p)), 10), nil
+	return appendUint(b, uint64(*(*uintptr)(p))), nil
 }
 
 func (e encoder) encodeUint8(b []byte, p unsafe.Pointer) ([]byte, error) {
-	return strconv.AppendUint(b, uint64(*(*uint8)(p)), 10), nil
+	return appendUint(b, uint64(*(*uint8)(p))), nil
 }
 
 func (e encoder) encodeUint16(b []byte, p unsafe.Pointer) ([]byte, error) {
-	return strconv.AppendUint(b, uint64(*(*uint16)(p)), 10), nil
+	return appendUint(b, uint64(*(*uint16)(p))), nil
 }
 
 func (e encoder) encodeUint32(b []byte, p unsafe.Pointer) ([]byte, error) {
-	return strconv.AppendUint(b, uint64(*(*uint32)(p)), 10), nil
+	return appendUint(b, uint64(*(*uint32)(p))), nil
 }
 
 func (e encoder) encodeUint64(b []byte, p unsafe.Pointer) ([]byte, error) {
-	return strconv.AppendUint(b, *(*uint64)(p), 10), nil
+	return appendUint(b, *(*uint64)(p)), nil
 }
 
 func (e encoder) encodeFloat32(b []byte, p unsafe.Pointer) ([]byte, error) {
diff --git a/json/int.go b/json/int.go
new file mode 100644
index 0000000..b53149c
--- /dev/null
+++ b/json/int.go
@@ -0,0 +1,98 @@
+package json
+
+import (
+	"unsafe"
+)
+
+var endianness int
+
+func init() {
+	var b [2]byte
+	*(*uint16)(unsafe.Pointer(&b)) = uint16(0xABCD)
+
+	switch b[0] {
+	case 0xCD:
+		endianness = 0 // LE
+	case 0xAB:
+		endianness = 1 // BE
+	default:
+		panic("could not determine endianness")
+	}
+}
+
+// "00010203...96979899" cast to []uint16
+var intLELookup = [100]uint16{
+	0x3030, 0x3130, 0x3230, 0x3330, 0x3430, 0x3530, 0x3630, 0x3730, 0x3830, 0x3930,
+	0x3031, 0x3131, 0x3231, 0x3331, 0x3431, 0x3531, 0x3631, 0x3731, 0x3831, 0x3931,
+	0x3032, 0x3132, 0x3232, 0x3332, 0x3432, 0x3532, 0x3632, 0x3732, 0x3832, 0x3932,
+	0x3033, 0x3133, 0x3233, 0x3333, 0x3433, 0x3533, 0x3633, 0x3733, 0x3833, 0x3933,
+	0x3034, 0x3134, 0x3234, 0x3334, 0x3434, 0x3534, 0x3634, 0x3734, 0x3834, 0x3934,
+	0x3035, 0x3135, 0x3235, 0x3335, 0x3435, 0x3535, 0x3635, 0x3735, 0x3835, 0x3935,
+	0x3036, 0x3136, 0x3236, 0x3336, 0x3436, 0x3536, 0x3636, 0x3736, 0x3836, 0x3936,
+	0x3037, 0x3137, 0x3237, 0x3337, 0x3437, 0x3537, 0x3637, 0x3737, 0x3837, 0x3937,
+	0x3038, 0x3138, 0x3238, 0x3338, 0x3438, 0x3538, 0x3638, 0x3738, 0x3838, 0x3938,
+	0x3039, 0x3139, 0x3239, 0x3339, 0x3439, 0x3539, 0x3639, 0x3739, 0x3839, 0x3939,
+}
+
+var intBELookup = [100]uint16{
+	0x3030, 0x3031, 0x3032, 0x3033, 0x3034, 0x3035, 0x3036, 0x3037, 0x3038, 0x3039,
+	0x3130, 0x3131, 0x3132, 0x3133, 0x3134, 0x3135, 0x3136, 0x3137, 0x3138, 0x3139,
+	0x3230, 0x3231, 0x3232, 0x3233, 0x3234, 0x3235, 0x3236, 0x3237, 0x3238, 0x3239,
+	0x3330, 0x3331, 0x3332, 0x3333, 0x3334, 0x3335, 0x3336, 0x3337, 0x3338, 0x3339,
+	0x3430, 0x3431, 0x3432, 0x3433, 0x3434, 0x3435, 0x3436, 0x3437, 0x3438, 0x3439,
+	0x3530, 0x3531, 0x3532, 0x3533, 0x3534, 0x3535, 0x3536, 0x3537, 0x3538, 0x3539,
+	0x3630, 0x3631, 0x3632, 0x3633, 0x3634, 0x3635, 0x3636, 0x3637, 0x3638, 0x3639,
+	0x3730, 0x3731, 0x3732, 0x3733, 0x3734, 0x3735, 0x3736, 0x3737, 0x3738, 0x3739,
+	0x3830, 0x3831, 0x3832, 0x3833, 0x3834, 0x3835, 0x3836, 0x3837, 0x3838, 0x3839,
+	0x3930, 0x3931, 0x3932, 0x3933, 0x3934, 0x3935, 0x3936, 0x3937, 0x3938, 0x3939,
+}
+
+var intLookup = [2]*[100]uint16{&intLELookup, &intBELookup}
+
+func appendInt(b []byte, n int64) []byte {
+	return formatInteger(b, uint64(n), n < 0)
+}
+
+func appendUint(b []byte, n uint64) []byte {
+	return formatInteger(b, n, false)
+}
+
+func formatInteger(out []byte, n uint64, negative bool) []byte {
+	if !negative {
+		if n < 10 {
+			return append(out, byte(n+'0'))
+		} else if n < 100 {
+			u := intLELookup[n]
+			return append(out, byte(u), byte(u>>8))
+		}
+	} else {
+		n = -n
+	}
+
+	lookup := intLookup[endianness]
+
+	var b [22]byte
+	u := (*[11]uint16)(unsafe.Pointer(&b))
+	i := 11
+
+	for n >= 100 {
+		j := n % 100
+		n /= 100
+		i--
+		u[i] = lookup[j]
+	}
+
+	i--
+	u[i] = lookup[n]
+
+	i *= 2 // convert to byte index
+	if n < 10 {
+		i++ // remove leading zero
+	}
+	if negative {
+		i--
+		b[i] = '-'
+	}
+
+	return append(out, b[i:]...)
+}


Test patch:
diff --git a/json/int_test.go b/json/int_test.go
new file mode 100644
index 0000000..4611375
--- /dev/null
+++ b/json/int_test.go
@@ -0,0 +1,58 @@
+package json
+
+import (
+	"math"
+	"strconv"
+	"testing"
+)
+
+func TestAppendInt(t *testing.T) {
+	var ints []int64
+	for i := 0; i < 64; i++ {
+		u := uint64(1) << i
+		ints = append(ints, int64(u-1), int64(u), int64(u+1), -int64(u))
+	}
+
+	var std [20]byte
+	var our [20]byte
+
+	for _, i := range ints {
+		expected := strconv.AppendInt(std[:], i, 10)
+		actual := appendInt(our[:], i)
+		if string(expected) != string(actual) {
+			t.Fatalf("appendInt(%d) = %v, expected = %v", i, string(actual), string(expected))
+		}
+	}
+}
+
+func benchStd(b *testing.B, n int64) {
+	var buf [20]byte
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		strconv.AppendInt(buf[:0], n, 10)
+	}
+}
+
+func benchNew(b *testing.B, n int64) {
+	var buf [20]byte
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		appendInt(buf[:0], n)
+	}
+}
+
+func BenchmarkAppendIntStd1(b *testing.B) {
+	benchStd(b, 1)
+}
+
+func BenchmarkAppendInt1(b *testing.B) {
+	benchNew(b, 1)
+}
+
+func BenchmarkAppendIntStdMinI64(b *testing.B) {
+	benchStd(b, math.MinInt64)
+}
+
+func BenchmarkAppendIntMinI64(b *testing.B) {
+	benchNew(b, math.MinInt64)
+}