Repository: alecthomas/kong
Pull request #79 (2020-05-15 21:17:10)

fix performance issue in interpolation
I ran across an issue where having a large number of variables to interpolate can significantly slow down `kong.New()`.  In my case I had around 5,000 variables and it took about five seconds to run my program with `--help`.

The problem is in `kong.interpolate()`. Because it calls `Vars.CloneWith()` for each field, its complexity is roughly O(n<sup>2</sup>).

This PR updates `kong.interpolateValue()` so that `Vars.CloneWith()` is not called in most cases. It will only be called if `value.Tag.Vars` is populated or if interpolation modified value.Enum of value.Default.

It also updates `Vars.CloneWith()` to preallocate the output map.

I added benchmarks to show the performance improvement.  I'm happy for them to be removed before merging if you don't want to keep them around. Their primary purpose is just to show the change in this PR.

This is what benchstat shows on my laptop:

```
name                     old time/op    new time/op    delta
_interpolateValue-8        3.26ms ± 5%    0.00ms ± 1%  -99.96%  (p=0.000 n=10+10)
Kong_interpolate/5-8       12.5µs ± 4%     6.8µs ± 8%  -45.32%  (p=0.000 n=10+9)
Kong_interpolate/500-8     72.5ms ± 2%     0.5ms ± 4%  -99.35%  (p=0.000 n=9+10)
Kong_interpolate/5000-8     7.69s ± 6%     0.01s ± 7%  -99.93%  (p=0.000 n=10+9)

name                     old alloc/op   new alloc/op   delta
_interpolateValue-8        2.57MB ± 0%    0.00MB ± 0%  -99.98%  (p=0.000 n=10+10)
Kong_interpolate/5-8       8.77kB ± 0%    4.01kB ± 0%  -54.23%  (p=0.000 n=10+10)
Kong_interpolate/500-8     84.7MB ± 0%     0.3MB ± 0%  -99.65%  (p=0.000 n=10+10)
Kong_interpolate/5000-8    6.46GB ± 0%    0.00GB ± 0%  -99.96%  (p=0.000 n=10+9)

name                     old allocs/op  new allocs/op  delta
_interpolateValue-8           517 ± 0%         3 ± 0%  -99.42%  (p=0.000 n=8+10)
Kong_interpolate/5-8         71.0 ± 0%      43.0 ± 0%  -39.44%  (p=0.000 n=10+10)
Kong_interpolate/500-8      29.7k ± 0%      2.5k ± 0%  -91.52%  (p=0.000 n=10+10)
Kong_interpolate/5000-8      975k ± 0%       25k ± 0%  -97.41%  (p=0.000 n=9+9)
```


WillAbides: While I was writing up the PR, I realized I could further reduce the instances where `Vars.CloneWith()` is called from interpolate vars.  Now instead of every time enum or default is updated, it requires help to have a variable to interpolate as well.

Patch:
diff --git a/interpolate.go b/interpolate.go
index 9de1ff7..8c6f742 100644
--- a/interpolate.go
+++ b/interpolate.go
@@ -8,9 +8,18 @@ import (
 var interpolationRegex = regexp.MustCompile(`((?:\${([[:alpha:]_][[:word:]]*))(?:=([^}]+))?})|(\$)|([^$]+)`)
 
 // Interpolate variables from vars into s for substrings in the form ${var} or ${var=default}.
-func interpolate(s string, vars map[string]string) (string, error) {
+func interpolate(s string, vars Vars, updatedVars map[string]string) (string, error) {
 	out := ""
 	matches := interpolationRegex.FindAllStringSubmatch(s, -1)
+	if len(matches) == 0 {
+		return s, nil
+	}
+	for key, val := range updatedVars {
+		if vars[key] != val {
+			vars = vars.CloneWith(updatedVars)
+			break
+		}
+	}
 	for _, match := range matches {
 		if name := match[2]; name != "" {
 			value, ok := vars[name]
diff --git a/kong.go b/kong.go
index 3a61567..a17a2f0 100644
--- a/kong.go
+++ b/kong.go
@@ -128,7 +128,7 @@ func (k *Kong) interpolate(node *Node) (err error) {
 		switch node := node.(type) {
 		case *Node:
 			vars := stack.push(node.Vars())
-			node.Help, err = interpolate(node.Help, vars)
+			node.Help, err = interpolate(node.Help, vars, nil)
 			if err != nil {
 				return fmt.Errorf("help for %s: %s", node.Path(), err)
 			}
@@ -144,18 +144,20 @@ func (k *Kong) interpolate(node *Node) (err error) {
 }
 
 func (k *Kong) interpolateValue(value *Value, vars Vars) (err error) {
-	vars = vars.CloneWith(value.Tag.Vars)
-	if value.Default, err = interpolate(value.Default, vars); err != nil {
+	if len(value.Tag.Vars) > 0 {
+		vars = vars.CloneWith(value.Tag.Vars)
+	}
+	if value.Default, err = interpolate(value.Default, vars, nil); err != nil {
 		return fmt.Errorf("default value for %s: %s", value.Summary(), err)
 	}
-	if value.Enum, err = interpolate(value.Enum, vars); err != nil {
+	if value.Enum, err = interpolate(value.Enum, vars, nil); err != nil {
 		return fmt.Errorf("enum value for %s: %s", value.Summary(), err)
 	}
-	vars = vars.CloneWith(map[string]string{
+	value.Help, err = interpolate(value.Help, vars, map[string]string{
 		"default": value.Default,
 		"enum":    value.Enum,
 	})
-	if value.Help, err = interpolate(value.Help, vars); err != nil {
+	if err != nil {
 		return fmt.Errorf("help for %s: %s", value.Summary(), err)
 	}
 	return nil
@@ -342,7 +344,7 @@ func (k *Kong) FatalIfErrorf(err error, args ...interface{}) {
 func (k *Kong) LoadConfig(path string) (Resolver, error) {
 	var err error
 	path = ExpandPath(path)
-	path, err = interpolate(path, k.vars)
+	path, err = interpolate(path, k.vars, nil)
 	if err != nil {
 		return nil, err
 	}
diff --git a/options.go b/options.go
index 714bbcb..681dfb9 100644
--- a/options.go
+++ b/options.go
@@ -35,7 +35,7 @@ func (v Vars) Apply(k *Kong) error {
 
 // CloneWith clones the current Vars and merges "vars" onto the clone.
 func (v Vars) CloneWith(vars Vars) Vars {
-	out := Vars{}
+	out := make(Vars, len(v)+len(vars))
 	for key, value := range v {
 		out[key] = value
 	}


Test patch:
diff --git a/benchmark_test.go b/benchmark_test.go
new file mode 100644
index 0000000..0fd2469
--- /dev/null
+++ b/benchmark_test.go
@@ -0,0 +1,79 @@
+package kong
+
+import (
+	"fmt"
+	"strconv"
+	"testing"
+
+	"github.com/stretchr/testify/require"
+)
+
+func BenchmarkKong_interpolate(b *testing.B) {
+	prepareKong := func(t testing.TB, count int) *Kong {
+		t.Helper()
+		k := &Kong{
+			vars:     make(Vars, count),
+			registry: NewRegistry().RegisterDefaults(),
+		}
+		for i := 0; i < count; i++ {
+			helpVar := fmt.Sprintf("help_param%d", i)
+			k.vars[helpVar] = strconv.Itoa(i)
+		}
+		grammar := &struct {
+			Param0 string `help:"${help_param0}"`
+		}{}
+		model, err := build(k, grammar)
+		require.NoError(t, err)
+		for i := 0; i < count; i++ {
+			model.Node.Flags = append(model.Node.Flags, &Flag{
+				Value: &Value{
+					Help: fmt.Sprintf("${help_param%d}", i),
+					Tag:  newEmptyTag(),
+				},
+			})
+		}
+		k.Model = model
+		return k
+	}
+
+	for _, count := range []int{5, 500, 5000} {
+		count := count
+		b.Run(strconv.Itoa(count), func(b *testing.B) {
+			var err error
+			k := prepareKong(b, count)
+			for i := 0; i < b.N; i++ {
+				err = k.interpolate(k.Model.Node)
+			}
+			require.NoError(b, err)
+			b.ReportAllocs()
+		})
+	}
+}
+
+func Benchmark_interpolateValue(b *testing.B) {
+	varsLen := 10000
+	k := &Kong{
+		vars:     make(Vars, 10000),
+		registry: NewRegistry().RegisterDefaults(),
+	}
+	for i := 0; i < varsLen; i++ {
+		helpVar := fmt.Sprintf("help_param%d", i)
+		k.vars[helpVar] = strconv.Itoa(i)
+	}
+	grammar := struct {
+		Param9999 string `kong:"cmd,help=${help_param9999}"`
+	}{}
+	model, err := build(k, &grammar)
+	if err != nil {
+		b.FailNow()
+	}
+	k.Model = model
+	flag := k.Model.Flags[0]
+	for i := 0; i < b.N; i++ {
+		err = k.interpolateValue(flag.Value, k.vars)
+		if err != nil {
+			b.FailNow()
+		}
+	}
+	b.ReportAllocs()
+}
diff --git a/interpolate_test.go b/interpolate_test.go
index a2c9df1..38d9266 100644
--- a/interpolate_test.go
+++ b/interpolate_test.go
@@ -10,7 +10,10 @@ func TestInterpolate(t *testing.T) {
 	vars := map[string]string{
 		"age": "35",
 	}
-	actual, err := interpolate("${name=Bobby Brown} is ${age} years old", vars)
+	updatedVars := map[string]string{
+		"height": "180",
+	}
+	actual, err := interpolate("${name=Bobby Brown} is ${age} years old and ${height} cm tall", vars, updatedVars)
 	require.NoError(t, err)
-	require.Equal(t, `Bobby Brown is 35 years old`, actual)
+	require.Equal(t, `Bobby Brown is 35 years old and 180 cm tall`, actual)
 }