Starlark: faster stmt/expr switch in the interpreter

[stepancheg]

trafficstars

Apparently, virtual calls Statement.kind() and Expression.kind() are quite expensive. JVM/CPU are unable to predict/inline/optimize it properly.

Make them non-virtual.

Speed up is 5-10% in statements/expression heavy code.

This is a very simple optimization. I don't know how far the bytecode interpreter is. If it is not going to be committed soon, maybe it's worth landing this.

A: n=47 mean=3.978 std=0.257 se=0.037 min=3.730 med=3.860
B: n=47 mean=3.660 std=0.268 se=0.039 min=3.395 med=3.490
B/A: 0.920 0.894..0.947 (95% conf)

def test():
  for i in range(10):
    print(i)
    for j in range(1000000):
      k = list()
      l = []
      m = k + l
      if j % 2 == 0:
        type(k)

test()

[brandjon]

I wonder what the cost is to RAM during parsing/compilation, storing the kind for each expression/statement AST node. Does it fit within the existing padding in those objects?

I'm probably overthinking it, I don't think we're so space-constrained for space in ASTs.

[brandjon]

I'll have to run some internal benchmarks to repro the cpu improvement and more importantly ensure no significant RAM regression, though I suspect that won't be an issue. Scheduling time on Wednesday.

[brandjon]

I ran a bazel query deps(...) command on a large Google-internal target, and analyzed the resulting heap histogram. Filtering to just objects that live in net.starlark.java.syntax, the impact of this change on retained heap size is a little over 2%. The actual impact on overall retained heap size is under a tenth of a percent. So I'm comfortable with disregarding the memory impact.

Over the same command line, our internal benchmark script reported no statistically significant change to CPU performance (5 repeated runs with and without this PR).

A ~5% speedup in eval-heavy code seems enough to justify this relatively straightforward change, even if it doesn't impact Bazel's builds in practice.

[brandjon]

Waiting on internal review, expecting to merge next week.