Repository: CloudyKit/jet
Pull request #201 (2022-12-08 20:09:03)

eval: resolveIndex speedup
Depends on #200

This improves the performance of resolveIndex calls by bringing back the structure cache access that was removed in commit https://github.com/CloudyKit/jet/commit/be876debf33e1e830c07cba38d2a592b0a7b2807 and by modifying the function's signature to receive either a reflect.Value or a string argument, depending on what the call sites already have. This brings down allocations for the most common execution paths back to zero.

Benchmarks shows that the hot path for executing templates involve allocations made when executing a {{ .Field }} action when the current context is a structure. This is one of the most fundamental building blocks for templates, and thus deserves a closer inspection on how to make performant.

Going over the history of this package, up to version 3.0.0, benchmarks showed this code path to have zero allocations, and further digging shows that commit https://github.com/CloudyKit/jet/commit/be876debf33e1e830c07cba38d2a592b0a7b2807 rewrote the resolveIndex function in such a way that it dropped support for a package-level cache of parsed structures, which avoided these allocations for commonly used structures.

This commit brings back access to that cache for the common case, while retaining the previous behavior of using the FieldByName() call (which causes one allocation).

Additionally, after analyzing the call sites for resolveIndex, it's clear that in many of them, the representation of the index to be resolved is already stored in a string variable and for the common case of structure fields, it ends up doing a roundtrip to a reflect.Value before being extracted again as a string, causing another unnecessary allocation.

Thus this commit also modifies the signature of the resolveIndex function to take either a reflect.Value or a string, depending on what is available on each call site without having to perform a conversion for the common cases, and handling the uncommon cases (when conversion is actually necessary) in a special way.

The net result is that execution of templates which consist only of field accesses become allocation-free, offering an alternative to write very memory efficient templates, even when they contain large numbers of accesses or items.

Following is a representative sample of benchmarks before and after the change:

```
name                      old time/op    new time/op    delta
RangeSimple-4               21.9µs ± 1%    15.1µs ± 2%   -31.07% (p=0.000 n=10+10)
RangeSimpleSet-4            31.6µs ± 1%    24.2µs ± 2%   -23.49% (p=0.000 n=10+10)
CustomRanger-4               346ns ± 1%     210ns ± 2%   -39.36% (p=0.000 n=10+10)
FieldAccess-4                414ns ±11%     290ns ±10%   -29.91% (p=0.000 n=10+10)

name                      old alloc/op   new alloc/op   delta
RangeSimple-4               1.21kB ± 0%    0.06kB ± 0%   -95.37% (p=0.000 n=9+10)
RangeSimpleSet-4            1.63kB ± 0%    0.48kB ± 0%   -70.61% (p=0.000 n=10+10)
CustomRanger-4               24.0B ± 0%      0.0B       -100.00% (p=0.000 n=10+10)
FieldAccess-4                24.0B ± 0%      0.0B       -100.00% (p=0.000 n=10+10)

name                      old allocs/op  new allocs/op  delta
RangeSimple-4                 98.0 ± 0%       2.0 ± 0%   -97.96% (p=0.000 n=10+10)
RangeSimpleSet-4               101 ± 0%         5 ± 0%   -95.05% (p=0.000 n=10+10)
CustomRanger-4                2.00 ± 0%      0.00       -100.00% (p=0.000 n=10+10)
FieldAccess-4                 2.00 ± 0%      0.00       -100.00% (p=0.000 n=10+10)
```


Patch:
diff --git a/eval.go b/eval.go
index 6528c9c..42155e3 100644
--- a/eval.go
+++ b/eval.go
@@ -268,7 +268,7 @@ func (st *Runtime) executeSet(left Expression, right reflect.Value) {
 	lef := len(fields) - 1
 	for i := 0; i < lef; i++ {
 		var err error
-		value, err = resolveIndex(value, reflect.ValueOf(fields[i]))
+		value, err = resolveIndex(value, reflect.Value{}, fields[i])
 		if err != nil {
 			left.errorf("%v", err)
 		}
@@ -491,11 +491,12 @@ func (st *Runtime) executeList(list *ListNode) (returnValue reflect.Value) {
 				node.error(err)
 			}
 			if !ranger.ProvidesIndex() {
-				if len(node.Set.Left) > 1 {
+				if isSet && len(node.Set.Left) > 1 {
 					// two-vars assignment with ranger that doesn't provide an index
 					node.error(errors.New("two-var range over ranger that does not provide an index"))
+				} else if isSet {
+					keyVarSlot, valVarSlot = -1, 0
 				}
-				keyVarSlot, valVarSlot = -1, 0
 			}
 
 			indexValue, rangeValue, end := ranger.Range()
@@ -682,7 +683,7 @@ func (st *Runtime) evalPrimaryExpressionGroup(node Expression) reflect.Value {
 		base := st.evalPrimaryExpressionGroup(node.Base)
 		index := st.evalPrimaryExpressionGroup(node.Index)
 
-		resolved, err := resolveIndex(base, index)
+		resolved, err := resolveIndex(base, index, "")
 		if err != nil {
 			node.error(err)
 		}
@@ -751,7 +752,7 @@ func (st *Runtime) isSet(node Node) (ok bool) {
 		base := st.evalPrimaryExpressionGroup(node.Base)
 		index := st.evalPrimaryExpressionGroup(node.Index)
 
-		resolved, err := resolveIndex(base, index)
+		resolved, err := resolveIndex(base, index, "")
 		return err == nil && notNil(resolved)
 	case NodeIdentifier:
 		value, err := st.resolve(node.String())
@@ -761,7 +762,7 @@ func (st *Runtime) isSet(node Node) (ok bool) {
 		resolved := st.context
 		for i := 0; i < len(node.Ident); i++ {
 			var err error
-			resolved, err = resolveIndex(resolved, reflect.ValueOf(node.Ident[i]))
+			resolved, err = resolveIndex(resolved, reflect.Value{}, node.Ident[i])
 			if err != nil || !notNil(resolved) {
 				return false
 			}
@@ -1143,7 +1144,7 @@ func (st *Runtime) evalBaseExpressionGroup(node Node) reflect.Value {
 		node := node.(*FieldNode)
 		resolved := st.context
 		for i := 0; i < len(node.Ident); i++ {
-			field, err := resolveIndex(resolved, reflect.ValueOf(node.Ident[i]))
+			field, err := resolveIndex(resolved, reflect.Value{}, node.Ident[i])
 			if err != nil {
 				node.errorf("%v", err)
 			}
@@ -1225,7 +1226,7 @@ func (st *Runtime) evalChainNodeExpression(node *ChainNode) (reflect.Value, erro
 	resolved := st.evalPrimaryExpressionGroup(node.Node)
 
 	for i := 0; i < len(node.Field); i++ {
-		field, err := resolveIndex(resolved, reflect.ValueOf(node.Field[i]))
+		field, err := resolveIndex(resolved, reflect.Value{}, node.Field[i])
 		if err != nil {
 			return reflect.Value{}, err
 		}
@@ -1545,7 +1546,17 @@ func indirectEface(v reflect.Value) reflect.Value {
 }
 
 // mostly copied from text/template's evalField() (exec.go):
-func resolveIndex(v, index reflect.Value) (reflect.Value, error) {
+//
+// The index to use to access v can be specified in either index or indexAsStr.
+// Which parameter is filled depends on the call path up to when a particular
+// call to resolveIndex is made and whether that call site already has access
+// to a reflect.Value for the index or just a string identifier.
+//
+// While having both options makes the implementation of this function more
+// complex, it improves the memory allocation story for the most common
+// execution paths when executing a template, such as when accessing a field
+// element.
+func resolveIndex(v, index reflect.Value, indexAsStr string) (reflect.Value, error) {
 	if !v.IsValid() {
 		return reflect.Value{}, fmt.Errorf("there is no field or method '%s' in %s (%s)", index, v, getTypeString(v))
 	}
@@ -1557,14 +1568,35 @@ func resolveIndex(v, index reflect.Value) (reflect.Value, error) {
 		return reflect.Value{}, fmt.Errorf("nil pointer evaluating %s.%s", v.Type(), index)
 	}
 
+	// Handle the caller passing either index or indexAsStr.
+	indexIsStr := indexAsStr != ""
+	indexAsValue := func() reflect.Value { return index }
+	if indexIsStr {
+		// indexAsStr was specified, so make the indexAsValue function
+		// obtain the corresponding reflect.Value. This is only used in
+		// some code paths, and since it causes an allocation, a
+		// function is used instead of always extracting the
+		// reflect.Value.
+		indexAsValue = func() reflect.Value {
+			return reflect.ValueOf(indexAsStr)
+		}
+	} else {
+		// index was specified, so extract the string value if the index
+		// is in fact a string.
+		indexIsStr = index.Kind() == reflect.String
+		if indexIsStr {
+			indexAsStr = index.String()
+		}
+	}
+
 	// Unless it's an interface, need to get to a value of type *T to guarantee
 	// we see all methods of T and *T.
-	if index.Kind() == reflect.String {
+	if indexIsStr {
 		ptr := v
 		if ptr.Kind() != reflect.Interface && ptr.Kind() != reflect.Ptr && ptr.CanAddr() {
 			ptr = ptr.Addr()
 		}
-		if method := ptr.MethodByName(index.String()); method.IsValid() {
+		if method := ptr.MethodByName(indexAsStr); method.IsValid() {
 			return method, nil
 		}
 	}
@@ -1576,35 +1608,58 @@ func resolveIndex(v, index reflect.Value) (reflect.Value, error) {
 	//  - if v is (still) a pointer, indexing will fail but we check for nil to get a useful error
 	switch v.Kind() {
 	case reflect.Array, reflect.Slice, reflect.String:
-		x, err := indexArg(index, v.Len())
+		indexVal := indexAsValue()
+		x, err := indexArg(indexVal, v.Len())
 		if err != nil {
 			return reflect.Value{}, err
 		}
 		return indirectEface(v.Index(x)), nil
 	case reflect.Struct:
-		if index.Kind() != reflect.String {
-			return reflect.Value{}, fmt.Errorf("can't use %s (%s, not string) as field name in struct type %s", index, index.Type(), v.Type())
+		if !indexIsStr {
+			return reflect.Value{}, fmt.Errorf("can't use %s (%s, not string) as field name in struct type %s", index, indexAsValue().Type(), v.Type())
 		}
-		tField, ok := v.Type().FieldByName(index.String())
+		typ := v.Type()
+		key := indexAsStr
+
+		// Fast path: use the struct cache to avoid allocations.
+		cachedStructsMutex.RLock()
+		cache, ok := cachedStructsFieldIndex[typ]
+		cachedStructsMutex.RUnlock()
+		if !ok {
+			cachedStructsMutex.Lock()
+			if cache, ok = cachedStructsFieldIndex[typ]; !ok {
+				cache = make(map[string][]int)
+				buildCache(typ, cache, nil)
+				cachedStructsFieldIndex[typ] = cache
+			}
+			cachedStructsMutex.Unlock()
+		}
+		if id, ok := cache[key]; ok {
+			return v.FieldByIndex(id), nil
+		}
+
+		// Slow path: use reflect directly
+		tField, ok := typ.FieldByName(key)
 		if ok {
 			field := v.FieldByIndex(tField.Index)
 			if tField.PkgPath != "" { // field is unexported
-				return reflect.Value{}, fmt.Errorf("%s is an unexported field of struct type %s", index.String(), v.Type())
+				return reflect.Value{}, fmt.Errorf("%s is an unexported field of struct type %s", indexAsStr, v.Type())
 			}
 			return indirectEface(field), nil
 		}
-		return reflect.Value{}, fmt.Errorf("can't use %s as field name in struct type %s", index, v.Type())
+		return reflect.Value{}, fmt.Errorf("can't use %s as field name in struct type %s", indexAsStr, v.Type())
 	case reflect.Map:
 		// If it's a map, attempt to use the field name as a key.
-		if !index.Type().ConvertibleTo(v.Type().Key()) {
-			return reflect.Value{}, fmt.Errorf("can't use %s (%s) as key for map of type %s", index, index.Type(), v.Type())
+		indexVal := indexAsValue()
+		if !indexVal.Type().ConvertibleTo(v.Type().Key()) {
+			return reflect.Value{}, fmt.Errorf("can't use %s (%s) as key for map of type %s", indexAsStr, indexVal.Type(), v.Type())
 		}
-		index = index.Convert(v.Type().Key()) // noop in most cases, but not expensive
-		return indirectEface(v.MapIndex(index)), nil
+		index = indexVal.Convert(v.Type().Key()) // noop in most cases, but not expensive
+		return indirectEface(v.MapIndex(indexVal)), nil
 	case reflect.Ptr:
 		etyp := v.Type().Elem()
-		if etyp.Kind() == reflect.Struct && index.Kind() == reflect.String {
-			if _, ok := etyp.FieldByName(index.String()); !ok {
+		if etyp.Kind() == reflect.Struct && indexIsStr {
+			if _, ok := etyp.FieldByName(indexAsStr); !ok {
 				// If there's no such field, say "can't evaluate"
 				// instead of "nil pointer evaluating".
 				break
@@ -1614,7 +1669,7 @@ func resolveIndex(v, index reflect.Value) (reflect.Value, error) {
 			return reflect.Value{}, fmt.Errorf("nil pointer evaluating %s.%s", v.Type(), index)
 		}
 	}
-	return reflect.Value{}, fmt.Errorf("can't evaluate index %s (%s) in type %s", index, getTypeString(index), getTypeString(v))
+	return reflect.Value{}, fmt.Errorf("can't evaluate index %s (%s) in type %s", index, indexAsStr, getTypeString(v))
 }
 
 // from Go's text/template's funcs.go:
diff --git a/ranger.go b/ranger.go
index 23360c1..da52233 100644
--- a/ranger.go
+++ b/ranger.go
@@ -11,7 +11,15 @@ import (
 // Implementing this interface means the ranger will be used when it's
 // encountered on the right hand side of a range's "let" expression.
 type Ranger interface {
+	// Range calls should return a key, a value and a done bool to indicate
+	// whether there are more values to be generated.
+	//
+	// When the done flag is true, then the loop ends.
 	Range() (reflect.Value, reflect.Value, bool)
+
+	// ProvidesIndex should return true if keys are produced during Range()
+	// calls. This call should be idempotent across Range() calls (i.e.
+	// its return value must not change during an iteration).
 	ProvidesIndex() bool
 }
 


Test patch:
diff --git a/eval_test.go b/eval_test.go
index c00351e..c7f98b2 100644
--- a/eval_test.go
+++ b/eval_test.go
@@ -88,6 +88,7 @@ func init() {
 	JetTestingLoader.Set("rangeOverUsers", `{{range .}}{{.Name}}-{{.Email}}{{end}}`)
 	JetTestingLoader.Set("rangeOverUsers_Set", `{{range index,user:= . }}{{index}}{{user.Name}}-{{user.Email}}{{end}}`)
 	JetTestingLoader.Set("BenchNewBlock", "{{ block col(md=12,offset=0) }}\n<div class=\"col-md-{{md}} col-md-offset-{{offset}}\">{{ yield content }}</div>\n\t\t{{ end }}\n\t\t{{ block row(md=12) }}\n<div class=\"row {{md}}\">{{ yield content }}</div>\n\t\t{{ content }}\n<div class=\"col-md-1\"></div>\n<div class=\"col-md-1\"></div>\n<div class=\"col-md-1\"></div>\n\t\t{{ end }}\n\t\t{{ block header() }}\n<div class=\"header\">\n\t{{ yield row() content}}\n\t\t{{ yield col(md=6) content }}\n{{ yield content }}\n\t\t{{end}}\n\t{{end}}\n</div>\n\t\t{{content}}\n<h1>Hey</h1>\n\t\t{{ end }}")
+	JetTestingLoader.Set("BenchCustomRanger", "{{range .}}{{.Name}}{{end}}")
 }
 
 func RunJetTest(t *testing.T, variables VarMap, context interface{}, testName, testContent, testExpected string) {
@@ -684,6 +685,35 @@ func TestBuiltinCollectionFuncs(t *testing.T) {
 	RunJetTest(t, nil, nil, "array_builtin", `{{ m := array( "foo", "bar", "asd", 123)}}{{m}}`, "[foo bar asd 123]")
 }
 
+// customTestRanger satisfies the Ranger interface for custom tests.
+type customTestRanger struct {
+	providesIndex bool
+	data          []string
+	i             int
+}
+
+var _ Ranger = (*customTestRanger)(nil)
+
+func (ctr *customTestRanger) ProvidesIndex() bool {
+	return ctr.providesIndex
+}
+
+func (ctr *customTestRanger) Range() (k reflect.Value, v reflect.Value, done bool) {
+	if ctr.i >= len(ctr.data) {
+		// Reset ctr.i for the next test.
+		ctr.i = 0
+		done = true
+		return
+	}
+
+	if ctr.providesIndex {
+		k = reflect.ValueOf(ctr.i)
+	}
+	v = reflect.ValueOf(ctr.data[ctr.i])
+	ctr.i += 1
+	return
+}
+
 func TestRanger(t *testing.T) {
 	c := make(chan string)
 	go func() {
@@ -702,15 +732,28 @@ func TestRanger(t *testing.T) {
 	)
 	data.Set("s", []string{"asd", "foo", "bar"})
 	data.Set("c", c)
+	data.Set("ci", &customTestRanger{
+		providesIndex: true,
+		data:          []string{"asd", "foo", "bar"},
+	})
+	data.Set("cu", &customTestRanger{
+		providesIndex: false,
+		data:          []string{"asd", "foo", "bar"},
+	})
 	RunJetTest(t, data, nil, "slice_ranger", `{{ range s }}{{.}},{{ end }}`, "asd,foo,bar,")
-	RunJetTest(t, data, nil, "slice_ranger_value", `{{ range v := s }}{{v}},{{ end }}`, "0,1,2,")
-	RunJetTest(t, data, nil, "slice_ranger_value_context", `{{ range v := s }}{{.}},{{ end }}`, "asd,foo,bar,")
+	RunJetTest(t, data, nil, "slice_ranger_index", `{{ range k := s }}{{k}},{{ end }}`, "0,1,2,")
+	RunJetTest(t, data, nil, "slice_ranger_index_context", `{{ range k := s }}{{k}}:{{.}},{{ end }}`, "0:asd,1:foo,2:bar,")
 	RunJetTest(t, data, nil, "slice_ranger_index_value", `{{ range i, v := s }}{{i}}:{{v}},{{ end }}`, "0:asd,1:foo,2:bar,")
 	RunJetTest(t, data, nil, "map_ranger", `{{ range m }}{{.}},{{ end }}`, "123,")
 	RunJetTest(t, data, nil, "map_ranger_key_context", `{{ range k := m }}{{k}}:{{.}},{{ end }}`, "asd:123,")
 	RunJetTest(t, data, nil, "map_ranger_key_value", `{{ range k, v := m }}{{k}}:{{v}},{{ end }}`, "asd:123,")
 	RunJetTest(t, data, nil, "chan_ranger", `{{ range v := c }}{{v}}{{ end }}`, "0123456789")
 	RunJetTest(t, nil, nil, "ints_ranger", `{{ range i := ints(0, 10) }}{{ (i == 0 ? "" : ", ") + i }}{{ end }}`, "0, 1, 2, 3, 4, 5, 6, 7, 8, 9")
+	RunJetTest(t, data, nil, "custom_indexed_ranger", `{{ range ci }}{{.}},{{ end  }}`, "asd,foo,bar,")
+	RunJetTest(t, data, nil, "custom_indexed_ranger_key_context", `{{ range k := ci }}{{k}}:{{.}},{{ end  }}`, "0:asd,1:foo,2:bar,")
+	RunJetTest(t, data, nil, "custom_indexed_ranger_key_value", `{{ range k, v := ci }}{{k}}:{{v}},{{ end  }}`, "0:asd,1:foo,2:bar,")
+	RunJetTest(t, data, nil, "custom_unindexed_ranger", `{{ range cu }}{{.}},{{ end  }}`, "asd,foo,bar,")
+	RunJetTest(t, data, nil, "custom_unindexed_ranger_value", `{{ range v := cu }}{{v}},{{ end  }}`, "asd,foo,bar,")
 }
 
 func TestWhitespaceControl(t *testing.T) {
@@ -844,3 +887,86 @@ func BenchmarkJetFunc(b *testing.B) {
 		}
 	}
 }
+
+// customBenchRanger satisfies the Ranger interface for custom benchmarks.
+type customBenchRanger struct {
+	i, n int
+	key  reflect.Value
+	data reflect.Value
+}
+
+var _ Ranger = (*customBenchRanger)(nil)
+
+func (cbr *customBenchRanger) ProvidesIndex() bool {
+	return false
+}
+
+func (cbr *customBenchRanger) Range() (_ reflect.Value, v reflect.Value, done bool) {
+	if cbr.i >= cbr.n {
+		done = true
+		return
+	}
+
+	v = cbr.data
+	cbr.i += 1
+	return
+}
+
+// BenchmarkCustomRanger benchmarks the overhead in doing one iteration of
+// a custom ranger.
+func BenchmarkCustomRanger(b *testing.B) {
+	data := reflect.ValueOf(struct {
+		Name string
+	}{Name: "John Doe"})
+	execCtx := &customBenchRanger{data: data, n: b.N}
+
+	t, _ := JetTestingSet.GetTemplate("BenchCustomRanger")
+	b.ResetTimer()
+	err := t.Execute(ww, nil, execCtx)
+	if err != nil {
+		b.Error(err.Error())
+	}
+}
+
+// BenchmarkFieldAccess benchmarks executing a template that accesses fields
+// in the current context.
+//
+// This measures the overhead from adding one additional field access to a
+// template.
+func BenchmarkFieldAccess(b *testing.B) {
+	// This benchmark is disabled from normal execution due to being
+	// limited by the parsing performance of this package. When the
+	// benchmark len grows greater than about 100K, parsing performance is
+	// degraded and this benchmark takes a long time to setup.
+	//
+	// To test this, comment out the following line and run this specific
+	// benchmark with
+	//   go test -run Bench -bench BenchmarkFieldAcces -benchtime 0.02s
+	b.Skip("Can only run manually with -benchtime 0.02s")
+
+	const numFields = 3 // Must match the structure below.
+	tmplBuilder := new(strings.Builder)
+	for i := 0; i < b.N; i++ {
+		fmt.Fprintf(tmplBuilder, "{{ .Field%d }} ", i%numFields+1)
+	}
+
+	loader := NewInMemLoader()
+	loader.Set("BenchFields", tmplBuilder.String())
+	set := NewSet(loader, WithSafeWriter(nil))
+	testCtx := struct {
+		Field1 string
+		Field2 int
+		Field3 float64
+	}{
+		Field1: "secret",
+		Field2: 42,
+		Field3: 3.1415,
+	}
+	t, _ := set.GetTemplate("BenchFields")
+
+	b.ResetTimer()
+	err := t.Execute(ww, nil, testCtx)
+	if err != nil {
+		b.Error(err.Error())
+	}
+}