encoding/json: index names for the struct decoder

In the common case, structs have a handful of fields and most inputs
match struct field names exactly.

The previous code would do a linear search over the fields, stopping at
the first exact match, and otherwise using the first case insensitive
match.

This is unfortunate, because it means that for the common case, we'd do
a linear search with bytes.Equal. Even for structs with only two or
three fields, that is pretty wasteful.

Worse even, up until the exact match was found via the linear search,
all previous fields would run their equalFold functions, which aren't
cheap even in the simple case.

Instead, cache a map along with the field list that indexes the fields
by their name. This way, a case sensitive field search doesn't involve a
linear search, nor does it involve any equalFold func calls.

This patch should also slightly speed up cases where there's a case
insensitive match but not a case sensitive one, as then we'd avoid
calling bytes.Equal on all the fields. Though that's not a common case,
and there are no benchmarks for it.

name           old time/op    new time/op    delta
CodeDecoder-8    11.0ms ± 0%    10.6ms ± 1%  -4.42%  (p=0.000 n=9+10)

name           old speed      new speed      delta
CodeDecoder-8   176MB/s ± 0%   184MB/s ± 1%  +4.62%  (p=0.000 n=9+10)

name           old alloc/op   new alloc/op   delta
CodeDecoder-8    2.28MB ± 0%    2.28MB ± 0%    ~     (p=0.725 n=10+10)

name           old allocs/op  new allocs/op  delta
CodeDecoder-8     76.9k ± 0%     76.9k ± 0%    ~     (all equal)

Updates #28923.

Change-Id: I9929c1f06c76505e5b96914199315dbdaae5dc76
Reviewed-on: https://go-review.googlesource.com/c/go/+/172918
Run-TryBot: Daniel Martí <mvdan@mvdan.cc>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

1 files changed, 13 insertions, 10 deletions

diff --git a/src/encoding/json/decode.go b/src/encoding/json/decode.go
index 3c40eb9cef..3ca3d7803e 100644
--- a/src/encoding/json/decode.go
+++ b/src/encoding/json/decode.go
@@ -8,7 +8,6 @@
 package json
 
 import (
-	"bytes"
 	"encoding"
 	"encoding/base64"
 	"fmt"
@@ -691,7 +690,7 @@ func (d *decodeState) object(v reflect.Value) error {
 		return nil
 	}
 
-	var fields []field
+	var fields structFields
 
 	// Check type of target:
 	//   struct or
@@ -761,14 +760,18 @@ func (d *decodeState) object(v reflect.Value) error {
 			subv = mapElem
 		} else {
 			var f *field
-			for i := range fields {
-				ff := &fields[i]
-				if bytes.Equal(ff.nameBytes, key) {
-					f = ff
-					break
-				}
-				if f == nil && ff.equalFold(ff.nameBytes, key) {
-					f = ff
+			if i, ok := fields.nameIndex[string(key)]; ok {
+				// Found an exact name match.
+				f = &fields.list[i]
+			} else {
+				// Fall back to the expensive case-insensitive
+				// linear search.
+				for i := range fields.list {
+					ff := &fields.list[i]
+					if ff.equalFold(ff.nameBytes, key) {
+						f = ff
+						break
+					}
 				}
 			}
 			if f != nil {