commit 613a0345a2743d577a50d21d5d6abbabc62bc678
author Muir Manders <muir@mnd.rs> Fri Mar 13 12:10:42 2020 -0700
committer Rebecca Stambler <rstambler@golang.org> Wed Mar 18 05:47:12 2020 +0000
tree 3e8d01cc6b405fd65d3f7d1366afaa7d5c80634d
parent dba9bee06b6c0782119926f9e9ccad8b52ca0077

internal/lsp/source: optimize enumeration of a type's fields

When searching for deep completions, we can end up enumerating struct
types' fields a lot. Optimize fieldSelections to reduce work:

- Wait until we see an embedded field before we create the "seen"
  map.
- Use a callback style to iterate over the struct's fields rather than
  returning a slice of fields.
- Change "seen" checking strategy back to track struct types rather
  than each individual field.

Struct with 5 non-embedded fields:

name       old time/op    new time/op    delta
Fields-16     293ns ± 1%      20ns ± 2%   -93.13%  (p=0.008 n=5+5)

name       old alloc/op   new alloc/op   delta
Fields-16      120B ± 0%        0B       -100.00%  (p=0.008 n=5+5)

name       old allocs/op  new allocs/op  delta
Fields-16      4.00 ± 0%      0.00       -100.00%  (p=0.008 n=5+5)

Same struct but add an embedded struct with 2 fields:

name       old time/op    new time/op    delta
Fields-16     389ns ± 1%     142ns ± 1%  -63.53%  (p=0.008 n=5+5)

name       old alloc/op   new alloc/op   delta
Fields-16      120B ± 0%      144B ± 0%  +20.00%  (p=0.008 n=5+5)

name       old allocs/op  new allocs/op  delta
Fields-16      4.00 ± 0%      2.00 ± 0%  -50.00%  (p=0.008 n=5+5)

I think the alloc/op went up because the "seen" map is no longer
allocated on the stack. There is more room for more optimization, but
it's probably not worth making things more complicated.

Change-Id: I6f9f2124334a8594ef9d6f9b5ac4b3a8aead5f49
Reviewed-on: https://go-review.googlesource.com/c/tools/+/223419
Run-TryBot: Muir Manders <muir@mnd.rs>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Rebecca Stambler <rstambler@golang.org>