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>
diff --git a/internal/lsp/source/completion.go b/internal/lsp/source/completion.go
index d883be6..e103e26 100644
--- a/internal/lsp/source/completion.go
+++ b/internal/lsp/source/completion.go
@@ -869,14 +869,15 @@
}
// Add fields of T.
- for _, f := range fieldSelections(typ) {
+ eachField(typ, func(v *types.Var) {
c.found(candidate{
- obj: f,
+ obj: v,
score: stdScore - 0.01,
imp: imp,
addressable: addressable || isPointer(typ),
})
- }
+ })
+
return nil
}
diff --git a/internal/lsp/source/util.go b/internal/lsp/source/util.go
index b691f7c..09f3569 100644
--- a/internal/lsp/source/util.go
+++ b/internal/lsp/source/util.go
@@ -272,34 +272,39 @@
return len(args)
}
-// fieldSelections returns the set of fields that can
-// be selected from a value of type T.
-func fieldSelections(T types.Type) (fields []*types.Var) {
+// eachField invokes fn for each field that can be selected from a
+// value of type T.
+func eachField(T types.Type, fn func(*types.Var)) {
// TODO(adonovan): this algorithm doesn't exclude ambiguous
// selections that match more than one field/method.
// types.NewSelectionSet should do that for us.
- seen := make(map[*types.Var]bool) // for termination on recursive types
+ // for termination on recursive types
+ var seen map[*types.Struct]bool
var visit func(T types.Type)
visit = func(T types.Type) {
if T, ok := deref(T).Underlying().(*types.Struct); ok {
+ if seen[T] {
+ return
+ }
+
for i := 0; i < T.NumFields(); i++ {
f := T.Field(i)
- if seen[f] {
- continue
- }
- seen[f] = true
- fields = append(fields, f)
+ fn(f)
if f.Anonymous() {
+ if seen == nil {
+ // Lazily create "seen" since it is only needed for
+ // embedded structs.
+ seen = make(map[*types.Struct]bool)
+ }
+ seen[T] = true
visit(f.Type())
}
}
}
}
visit(T)
-
- return fields
}
// typeIsValid reports whether typ doesn't contain any Invalid types.
