internal/compile: build index of local vars (#576)
This eliminates the linear scan over locals in the interpreter
when processing named arguments. This reduces the new benchmark
from 1081ns to 843ns (-22%).
(This was inspired by recent work in the Java-based implementation,
but findParams seemed to be a bigger hit in that case, possibly
because of the two extra levels of indirection involved in the
length comparison (hot path) of a Java array of Java strings,
versus Go where they are all in the same cache line.)
diff --git a/internal/compile/compile.go b/internal/compile/compile.go
index b257d70..bc38200 100644
--- a/internal/compile/compile.go
+++ b/internal/compile/compile.go
@@ -345,6 +345,8 @@
lntOnce sync.Once
lnt []pclinecol // decoded line number table
+
+ localsMap map[string]int
}
type pclinecol struct {
@@ -403,6 +405,24 @@
line, col int32
}
+// finish is called to populate derived fields of Funcode.
+func (fn *Funcode) finish() {
+ // (We could populate this map on first use,
+ // but the sync adds 33% to bench_calling_kwargs.)
+ fn.localsMap = make(map[string]int, len(fn.Locals))
+ for index, binding := range fn.Locals {
+ fn.localsMap[binding.Name] = index
+ }
+}
+
+// Local returns the index of the named local, or -1.
+func (fn *Funcode) Local(name string) int {
+ if i, ok := fn.localsMap[name]; ok {
+ return i
+ }
+ return -1
+}
+
// Position returns the source position for program counter pc.
func (fn *Funcode) Position(pc uint32) syntax.Position {
fn.lntOnce.Do(fn.decodeLNT)
@@ -680,6 +700,7 @@
fmt.Fprintf(os.Stderr, "end function(%s @ %s)\n", name, pos)
}
+ fcomp.fn.finish()
return fn
}
diff --git a/internal/compile/serial.go b/internal/compile/serial.go
index 0dbae47..6131322 100644
--- a/internal/compile/serial.go
+++ b/internal/compile/serial.go
@@ -380,7 +380,7 @@
numKwonlyParams := d.int()
hasVarargs := d.int() != 0
hasKwargs := d.int() != 0
- return &Funcode{
+ fn := &Funcode{
// Prog is filled in later.
Pos: id.Pos,
Name: id.Name,
@@ -396,4 +396,6 @@
HasVarargs: hasVarargs,
HasKwargs: hasKwargs,
}
+ fn.finish()
+ return fn
}
diff --git a/starlark/eval.go b/starlark/eval.go
index be3eb61..a4640e4 100644
--- a/starlark/eval.go
+++ b/starlark/eval.go
@@ -1491,10 +1491,9 @@
}
// Bind keyword arguments to parameters.
- paramIdents := fn.funcode.Locals[:nparams]
for _, pair := range kwargs {
k, v := pair[0].(String), pair[1]
- if i := findParam(paramIdents, string(k)); i >= 0 {
+ if i := fn.funcode.Local(string(k)); i >= 0 && i < nparams {
if locals[i] != nil {
return fmt.Errorf("function %s got multiple values for parameter %s", fn.Name(), k)
}
@@ -1515,6 +1514,8 @@
if n < nparams || fn.NumKwonlyParams() > 0 {
m := nparams - len(fn.defaults) // first default
+ paramIdents := fn.funcode.Locals[:nparams]
+
// Report errors for missing required arguments.
var missing []string
var i int
@@ -1544,15 +1545,6 @@
return nil
}
-func findParam(params []compile.Binding, name string) int {
- for i, param := range params {
- if param.Name == name {
- return i
- }
- }
- return -1
-}
-
// https://github.com/google/starlark-go/blob/master/doc/spec.md#string-interpolation
func interpolate(format string, x Value) (Value, error) {
buf := new(strings.Builder)
diff --git a/starlark/testdata/benchmark.star b/starlark/testdata/benchmark.star
index c448889..d41c000 100644
--- a/starlark/testdata/benchmark.star
+++ b/starlark/testdata/benchmark.star
@@ -25,6 +25,15 @@
for _ in range(b.n):
f()
+# Test the efficiency of named arguments.
+def bench_calling_kwargs(b):
+ def f(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p):
+ pass
+
+ for _ in range(b.n):
+ f(a=1, b=2, c=3, d=4, e=5, f=7, g=7, h=8,
+ i=9, j=10, k=11, l=12, m=13, n=14, o=15, p=16)
+
# Measure overhead of calling a trivial built-in method.
emptydict = {}
range1000 = range(1000)
