Repository: segmentio/encoding
Pull request #50 (2020-09-17 10:12:41)

Faster string encoding
This PR adds a fast path for strings that don't require escaping.

```
name           old time/op    new time/op    delta
CodeEncoder-4    2.33ms ± 2%    2.12ms ± 0%   -9.05%  (p=0.000 n=7+8)

name           old speed      new speed      delta
CodeEncoder-4   834MB/s ± 2%   917MB/s ± 0%   +9.93%  (p=0.000 n=7+8)
```

`encodeString` does a pass over the string to determine if it can copy it straight into the output buffer. A [SWAR](https://en.wikipedia.org/wiki/SWAR) technique derived from https://graphics.stanford.edu/~seander/bithacks.html#HasLessInWord is used to check 8 bytes at a time:

```
SimpleString4KB-4            3.91GB/s ± 0%
SimpleString4KBEscapeHTML-4  3.07GB/s ± 0%
SimpleString1-4               217MB/s ± 0%
SimpleString1EscapeHTML-4     195MB/s ± 0%
SimpleString7-4               683MB/s ± 0%
SimpleString7EscapeHTML-4     510MB/s ± 0%
```

I get 3-4GB/s which is not bad for a pass free of SIMD instructions.

I threw in an improvement to struct encoding too (https://github.com/segmentio/encoding/pull/50/commits/933a4e3ab3eec8b63166f0d7db8dcc6954553bf5) which accounts for 1-2% of the gains.

chriso: Current standings:

```
name                 old speed     new speed      delta
Marshal/string#01-4  397MB/s ± 0%   477MB/s ± 0%   +20.29%  (p=0.008 n=5+5)
Marshal/string#02-4  392MB/s ± 1%   503MB/s ± 1%   +28.20%  (p=0.002 n=6+6)
Marshal/string#03-4  399MB/s ± 1%   507MB/s ± 0%   +27.11%  (p=0.008 n=5+5)
Marshal/string#04-4  403MB/s ± 0%   506MB/s ± 1%   +25.57%  (p=0.002 n=6+6)
Marshal/string#05-4  404MB/s ± 2%   508MB/s ± 1%   +25.89%  (p=0.002 n=6+6)
Marshal/string#06-4  392MB/s ± 3%   486MB/s ± 0%   +24.12%  (p=0.002 n=6+6)
Marshal/string#07-4  497MB/s ± 1%   508MB/s ± 1%    +2.14%  (p=0.004 n=6+5)
Marshal/string#08-4  498MB/s ± 0%   505MB/s ± 1%    +1.57%  (p=0.004 n=5+6)
Marshal/string#09-4  222MB/s ± 7%   227MB/s ± 1%      ~     (p=1.000 n=6+6)
Marshal/string#10-4  134MB/s ± 0%   134MB/s ± 0%      ~     (p=0.105 n=4+6)
Marshal/string#11-4  134MB/s ± 1%   134MB/s ± 0%      ~     (p=0.132 n=6+6)
Marshal/string#12-4  134MB/s ± 0%   134MB/s ± 0%      ~     (p=0.952 n=5+5)
Marshal/string#13-4  355MB/s ± 1%   352MB/s ± 1%      ~     (p=0.132 n=6+6)
Marshal/string#14-4  205MB/s ± 6%   208MB/s ± 0%      ~     (p=0.931 n=6+5)
Marshal/string#15-4  208MB/s ± 1%   208MB/s ± 0%      ~     (p=0.690 n=5+5)
Marshal/string#16-4  358MB/s ± 1%   354MB/s ± 0%    -1.11%  (p=0.004 n=6+5)
Marshal/string#17-4  477MB/s ± 1%   370MB/s ± 0%   -22.50%  (p=0.004 n=6+5)
Marshal/string#18-4  589MB/s ± 0%   495MB/s ± 0%   -15.90%  (p=0.008 n=5+5)
Marshal/string#19-4  605MB/s ± 0%  1055MB/s ± 1%   +74.25%  (p=0.004 n=5+6)
Marshal/string#20-4  781MB/s ± 0%  2511MB/s ± 1%  +221.29%  (p=0.004 n=5+6)
Marshal/string#21-4  842MB/s ± 0%  3059MB/s ± 0%  +263.46%  (p=0.004 n=6+5)
```

You'll see a win when the whole string, or the prefix (52246e59bf9ac39111c1eaf8f6d87f37edccdfa3), doesn't need escaping — the larger the prefix, the bigger the speedup. You could refactor it to copy chunks rather than characters (repeatedly call `EscapeIndex` to find the end of the chunk), and have a circuit breaker for strings with lots of escaping (where you'd fallback to a char loop).

I've disabled the optimization for short strings (< 8 chars). The only case where you'll still see a minor hit is cases like [these](https://github.com/segmentio/encoding/blob/00e544d8f30ff569bcc117a868cc046941af8ff4/json/json_test.go#L154-L155). 

Patch:
diff --git a/json/codec.go b/json/codec.go
index cf7216d..371da3f 100644
--- a/json/codec.go
+++ b/json/codec.go
@@ -675,18 +675,21 @@ func appendStructFields(fields []structField, t reflect.Type, offset uintptr, se
 	}
 
 	for i := range fields {
-		fields[i].json = encodeString(fields[i].name, 0)
-		fields[i].html = encodeString(fields[i].name, EscapeHTML)
+		name := fields[i].name
+		fields[i].json = encodeKeyFragment(name, 0)
+		fields[i].html = encodeKeyFragment(name, EscapeHTML)
 	}
 
 	sort.Slice(fields, func(i, j int) bool { return fields[i].index < fields[j].index })
 	return fields
 }
 
-func encodeString(s string, flags AppendFlags) string {
-	b := make([]byte, 0, len(s)+2)
+func encodeKeyFragment(s string, flags AppendFlags) string {
+	b := make([]byte, 1, len(s)+4)
+	b[0] = ','
 	e := encoder{flags: flags}
 	b, _ = e.encodeString(b, unsafe.Pointer(&s))
+	b = append(b, ':')
 	return *(*string)(unsafe.Pointer(&b))
 }
 
diff --git a/json/encode.go b/json/encode.go
index eb001c8..d0b0b3c 100644
--- a/json/encode.go
+++ b/json/encode.go
@@ -130,12 +130,21 @@ func (e encoder) encodeNumber(b []byte, p unsafe.Pointer) ([]byte, error) {
 
 func (e encoder) encodeString(b []byte, p unsafe.Pointer) ([]byte, error) {
 	s := *(*string)(p)
+	if len(s) == 0 {
+		return append(b, `""`...), nil
+	}
 	i := 0
 	j := 0
 	escapeHTML := (e.flags & EscapeHTML) != 0
 
 	b = append(b, '"')
 
+	if len(s) >= 8 {
+		if j = escapeIndex(s, escapeHTML); j < 0 {
+			return append(append(b, s...), '"'), nil
+		}
+	}
+
 	for j < len(s) {
 		c := s[j]
 
@@ -532,6 +541,8 @@ func (e encoder) encodeStruct(b []byte, p unsafe.Pointer, st *structType) ([]byt
 	var n int
 	b = append(b, '{')
 
+	escapeHTML := (e.flags & EscapeHTML) != 0
+
 	for i := range st.fields {
 		f := &st.fields[i]
 		v := unsafe.Pointer(uintptr(p) + f.offset)
@@ -540,7 +551,7 @@ func (e encoder) encodeStruct(b []byte, p unsafe.Pointer, st *structType) ([]byt
 			continue
 		}
 
-		if (e.flags & EscapeHTML) != 0 {
+		if escapeHTML {
 			k = f.html
 		} else {
 			k = f.json
@@ -549,12 +560,11 @@ func (e encoder) encodeStruct(b []byte, p unsafe.Pointer, st *structType) ([]byt
 		lengthBeforeKey := len(b)
 
 		if n != 0 {
-			b = append(b, ',')
+			b = append(b, k...)
+		} else {
+			b = append(b, k[1:]...)
 		}
 
-		b = append(b, k...)
-		b = append(b, ':')
-
 		if b, err = f.codec.encode(e, b, v); err != nil {
 			if err == (rollback{}) {
 				b = b[:lengthBeforeKey]
diff --git a/json/string.go b/json/string.go
new file mode 100644
index 0000000..ae7f57b
--- /dev/null
+++ b/json/string.go
@@ -0,0 +1,71 @@
+package json
+
+import (
+	"math/bits"
+	"reflect"
+	"unsafe"
+)
+
+const (
+	lsb = 0x0101010101010101
+	msb = 0x8080808080808080
+)
+
+// escapeIndex finds the index of the first char in `s` that requires escaping.
+// A char requires escaping if it's outside of the range of [0x20, 0x7F] or if
+// it includes a double quote or backslash. If the escapeHTML mode is enabled,
+// the chars <, > and & also require escaping. If no chars in `s` require
+// escaping, the return value is -1.
+func escapeIndex(s string, escapeHTML bool) int {
+	chunks := stringToUint64(s)
+	for _, n := range chunks {
+		// combine masks before checking for the MSB of each byte. We include
+		// `n` in the mask to check whether any of the *input* byte MSBs were
+		// set (i.e. the byte was outside the ASCII range).
+		mask := n | below(n, 0x20) | contains(n, '"') | contains(n, '\\')
+		if escapeHTML {
+			mask |= contains(n, '<') | contains(n, '>') | contains(n, '&')
+		}
+		if (mask & msb) != 0 {
+			return bits.TrailingZeros64(mask&msb) / 8
+		}
+	}
+
+	for i := len(chunks) * 8; i < len(s); i++ {
+		c := s[i]
+		if c < 0x20 || c > 0x7f || c == '"' || c == '\\' || (escapeHTML && (c == '<' || c == '>' || c == '&')) {
+			return i
+		}
+	}
+
+	return -1
+}
+
+// below return a mask that can be used to determine if any of the bytes
+// in `n` are below `b`. If a byte's MSB is set in the mask then that byte was
+// below `b`. The result is only valid if `b`, and each byte in `n`, is below
+// 0x80.
+func below(n uint64, b byte) uint64 {
+	return n - expand(b)
+}
+
+// contains returns a mask that can be used to determine if any of the
+// bytes in `n` are equal to `b`. If a byte's MSB is set in the mask then
+// that byte is equal to `b`. The result is only valid if `b`, and each
+// byte in `n`, is below 0x80.
+func contains(n uint64, b byte) uint64 {
+	return (n ^ expand(b)) - lsb
+}
+
+// expand puts the specified byte into each of the 8 bytes of a uint64.
+func expand(b byte) uint64 {
+	return lsb * uint64(b)
+}
+
+func stringToUint64(s string) []uint64 {
+	return *(*[]uint64)(unsafe.Pointer(&reflect.SliceHeader{
+		Data: ((*reflect.StringHeader)(unsafe.Pointer(&s))).Data,
+		Len:  len(s) / 8,
+		Cap:  len(s) / 8,
+	}))
+}


Test patch:
diff --git a/json/string_test.go b/json/string_test.go
new file mode 100644
index 0000000..84ac70b
--- /dev/null
+++ b/json/string_test.go
@@ -0,0 +1,38 @@
+package json
+
+import (
+	"strings"
+	"testing"
+)
+
+func BenchmarkEscapeIndex4KB(b *testing.B) {
+	benchmarkEscapeIndex(b, strings.Repeat("!foobar!", 512), false)
+}
+
+func BenchmarkEscapeIndex4KBEscapeHTML(b *testing.B) {
+	benchmarkEscapeIndex(b, strings.Repeat("!foobar!", 512), true)
+}
+
+func BenchmarkEscapeIndex1(b *testing.B) {
+	benchmarkEscapeIndex(b, "1", false)
+}
+
+func BenchmarkEscapeIndex1EscapeHTML(b *testing.B) {
+	benchmarkEscapeIndex(b, "1", true)
+}
+
+func BenchmarkEscapeIndex7(b *testing.B) {
+	benchmarkEscapeIndex(b, "1234567", false)
+}
+
+func BenchmarkEscapeIndex7EscapeHTML(b *testing.B) {
+	benchmarkEscapeIndex(b, "1234567", true)
+}
+
+func benchmarkEscapeIndex(b *testing.B, s string, escapeHTML bool) {
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		escapeIndex(s, escapeHTML)
+	}
+	b.SetBytes(int64(len(s)))
+}