go/types, types2: optimize instance lookup in LookupFieldOrMethod
LookupFieldOrMethod appears as a hotspot when benchmarking gopls'
auto-completion. In particular, instanceLookup.add was allocating in the
common case of structs with no embedding.
This is easily fixed, by using a small array in front of the map inside
of instanceLookup. Do this, and additionally add a microbenchmark.
The benchmark improvement is significant:
name old time/op new time/op delta
LookupFieldOrMethod-12 388µs ± 6% 154µs ± 3% -60.36% (p=0.000 n=10+10)
name old alloc/op new alloc/op delta
LookupFieldOrMethod-12 152kB ± 0% 2kB ± 0% -98.77% (p=0.000 n=9+10)
name old allocs/op new allocs/op delta
LookupFieldOrMethod-12 1.41k ± 0% 0.07k ± 0% -95.38% (p=0.000 n=10+10)
It should also be noted that instanceLookup is used elsewhere, in
particular by validType. In those contexts, the scope is not just the
current type but the entire package, and so the newly added buffer is
likely to simply cause extra Identical checks. Nevertheless, those
checks are cheap, and on balance the improved LookupFieldOrMethod
performance leads overall to improved type-checking performance.
Standard library benchmark results varied by package, but type checking
speed for many packages improved by ~5%, with allocations improved by
~10%. If this weren't the case we could let the caller control the
buffer size, but that optimization doesn't seem necessary at this time.