lsp/completion: reduce garbage searching for candidates
Tweak a few things to reduce garbage:
- Pre-allocate a couple hot error objects in format.go.
- Change methodsAndFields and packageMembers to take a callback
instead of returning a slice.
- Use two queues for breadth first search. This allows us to alternate
between and reuse the queues for each search level instead of
appending to a single queue indefinitely with no reuse.
- Get rid of candidate.names field. This tracked the string name of
each object in the deep completion path. Unlike with DFS before,
due to BFS this has to be copied for every candidate we inspect. Now
we get the object names from each types.Object in candidate.path,
with the addition of a new bitmask field to remember whether each
object needs "()" appended to it.
Using TestBenchmarkFuncDeepCompletion as a benchmark:
name old time/op new time/op delta
Statistics 14.2ms ± 7% 10.3ms ± 1% -27.41% (p=0.016 n=5+4)
name old alloc/op new alloc/op delta
Statistics 4.31MB ± 1% 3.03MB ± 0% -29.60% (p=0.016 n=5+4)
name old allocs/op new allocs/op delta
Statistics 52.7k ± 1% 44.0k ± 5% -16.52% (p=0.008 n=5+5)
Change-Id: I52f619d9a2e8553115be91f05cf8cc5cfa89123e
Reviewed-on: https://go-review.googlesource.com/c/tools/+/323252
Reviewed-by: Rebecca Stambler <rstambler@golang.org>
Trust: Rebecca Stambler <rstambler@golang.org>
Trust: Robert Findley <rfindley@google.com>
Run-TryBot: Rebecca Stambler <rstambler@golang.org>
gopls-CI: kokoro <noreply+kokoro@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
diff --git a/internal/lsp/source/completion/completion.go b/internal/lsp/source/completion/completion.go
index 741e6b3..413ded4 100644
--- a/internal/lsp/source/completion/completion.go
+++ b/internal/lsp/source/completion/completion.go
@@ -365,10 +365,10 @@
// itself) for a deep candidate.
path []types.Object
- // names tracks the names of objects from search root (excluding the
- // candidate itself) for a deep candidate. This also includes
- // expanded calls for function invocations.
- names []string
+ // pathInvokeMask is a bit mask tracking whether each entry in path
+ // should be formatted with "()" (i.e. whether it is a function
+ // invocation).
+ pathInvokeMask uint16
// mods contains modifications that should be applied to the
// candidate when inserted. For example, "foo" may be insterted as
@@ -555,7 +555,6 @@
// Deep search collected candidates and their members for more candidates.
c.deepSearch(ctx)
- c.deepState.searchQueue = nil
for _, callback := range c.completionCallbacks {
if err := c.snapshot.RunProcessEnvFunc(ctx, callback); err != nil {
@@ -1088,10 +1087,9 @@
return err
}
}
- candidates := c.packageMembers(pkgName.Imported(), stdScore, nil)
- for _, cand := range candidates {
+ c.packageMembers(pkgName.Imported(), stdScore, nil, func(cand candidate) {
c.deepState.enqueue(cand)
- }
+ })
return nil
}
}
@@ -1099,10 +1097,9 @@
// Invariant: sel is a true selector.
tv, ok := c.pkg.GetTypesInfo().Types[sel.X]
if ok {
- candidates := c.methodsAndFields(tv.Type, tv.Addressable(), nil)
- for _, cand := range candidates {
+ c.methodsAndFields(tv.Type, tv.Addressable(), nil, func(cand candidate) {
c.deepState.enqueue(cand)
- }
+ })
c.addPostfixSnippetCandidates(ctx, sel)
@@ -1159,10 +1156,9 @@
if imports.ImportPathToAssumedName(path) != pkg.GetTypes().Name() {
imp.name = pkg.GetTypes().Name()
}
- candidates := c.packageMembers(pkg.GetTypes(), unimportedScore(relevances[path]), imp)
- for _, cand := range candidates {
+ c.packageMembers(pkg.GetTypes(), unimportedScore(relevances[path]), imp, func(cand candidate) {
c.deepState.enqueue(cand)
- }
+ })
if len(c.items) >= unimportedMemberTarget {
return nil
}
@@ -1209,22 +1205,20 @@
return (stdScore + .1*relevance) / 2
}
-func (c *completer) packageMembers(pkg *types.Package, score float64, imp *importInfo) []candidate {
- var candidates []candidate
+func (c *completer) packageMembers(pkg *types.Package, score float64, imp *importInfo, cb func(candidate)) {
scope := pkg.Scope()
for _, name := range scope.Names() {
obj := scope.Lookup(name)
- candidates = append(candidates, candidate{
+ cb(candidate{
obj: obj,
score: score,
imp: imp,
addressable: isVar(obj),
})
}
- return candidates
}
-func (c *completer) methodsAndFields(typ types.Type, addressable bool, imp *importInfo) []candidate {
+func (c *completer) methodsAndFields(typ types.Type, addressable bool, imp *importInfo, cb func(candidate)) {
mset := c.methodSetCache[methodSetKey{typ, addressable}]
if mset == nil {
if addressable && !types.IsInterface(typ) && !isPointer(typ) {
@@ -1237,9 +1231,8 @@
c.methodSetCache[methodSetKey{typ, addressable}] = mset
}
- var candidates []candidate
for i := 0; i < mset.Len(); i++ {
- candidates = append(candidates, candidate{
+ cb(candidate{
obj: mset.At(i).Obj(),
score: stdScore,
imp: imp,
@@ -1249,15 +1242,13 @@
// Add fields of T.
eachField(typ, func(v *types.Var) {
- candidates = append(candidates, candidate{
+ cb(candidate{
obj: v,
score: stdScore - 0.01,
imp: imp,
addressable: addressable || isPointer(typ),
})
})
-
- return candidates
}
// lexical finds completions in the lexical environment.
diff --git a/internal/lsp/source/completion/deep_completion.go b/internal/lsp/source/completion/deep_completion.go
index 45a02ff..a13d807 100644
--- a/internal/lsp/source/completion/deep_completion.go
+++ b/internal/lsp/source/completion/deep_completion.go
@@ -26,8 +26,11 @@
// once we're running out of our time budget.
queueClosed bool
- // searchQueue holds the current breadth first search queue.
- searchQueue []candidate
+ // thisQueue holds the current breadth first search queue.
+ thisQueue []candidate
+
+ // nextQueue holds the next breadth first search iteration's queue.
+ nextQueue []candidate
// highScores tracks the highest deep candidate scores we have found
// so far. This is used to avoid work for low scoring deep candidates.
@@ -40,13 +43,13 @@
// enqueue adds a candidate to the search queue.
func (s *deepCompletionState) enqueue(cand candidate) {
- s.searchQueue = append(s.searchQueue, cand)
+ s.nextQueue = append(s.nextQueue, cand)
}
// dequeue removes and returns the leftmost element from the search queue.
func (s *deepCompletionState) dequeue() *candidate {
var cand *candidate
- cand, s.searchQueue = &s.searchQueue[0], s.searchQueue[1:]
+ cand, s.thisQueue = &s.thisQueue[len(s.thisQueue)-1], s.thisQueue[:len(s.thisQueue)-1]
return cand
}
@@ -99,130 +102,135 @@
// newPath returns path from search root for an object following a given
// candidate.
-func (s *deepCompletionState) newPath(cand *candidate, obj types.Object, invoke bool) ([]types.Object, []string) {
- name := obj.Name()
- if invoke {
- name += "()"
- }
+func (s *deepCompletionState) newPath(cand candidate, obj types.Object) []types.Object {
+ path := make([]types.Object, len(cand.path)+1)
+ copy(path, cand.path)
+ path[len(path)-1] = obj
- // copy the slice since we don't want to overwrite the original slice.
- path := append([]types.Object{}, cand.path...)
- names := append([]string{}, cand.names...)
-
- return append(path, obj), append(names, name)
+ return path
}
// deepSearch searches a candidate and its subordinate objects for completion
// items if deep completion is enabled and adds the valid candidates to
// completion items.
func (c *completer) deepSearch(ctx context.Context) {
-outer:
- for len(c.deepState.searchQueue) > 0 {
- cand := c.deepState.dequeue()
- obj := cand.obj
+ defer func() {
+ // We can return early before completing the search, so be sure to
+ // clear out our queues to not impact any further invocations.
+ c.deepState.thisQueue = c.deepState.thisQueue[:0]
+ c.deepState.nextQueue = c.deepState.nextQueue[:0]
+ }()
- if obj == nil {
- continue
- }
+ for len(c.deepState.nextQueue) > 0 {
+ c.deepState.thisQueue, c.deepState.nextQueue = c.deepState.nextQueue, c.deepState.thisQueue[:0]
- // At the top level, dedupe by object.
- if len(cand.path) == 0 {
- if c.seen[obj] {
+ outer:
+ for _, cand := range c.deepState.thisQueue {
+ obj := cand.obj
+
+ if obj == nil {
continue
}
- c.seen[obj] = true
- }
- // If obj is not accessible because it lives in another package and is
- // not exported, don't treat it as a completion candidate unless it's
- // a package completion candidate.
- if !c.completionContext.packageCompletion &&
- obj.Pkg() != nil && obj.Pkg() != c.pkg.GetTypes() && !obj.Exported() {
- continue
- }
-
- // If we want a type name, don't offer non-type name candidates.
- // However, do offer package names since they can contain type names,
- // and do offer any candidate without a type since we aren't sure if it
- // is a type name or not (i.e. unimported candidate).
- if c.wantTypeName() && obj.Type() != nil && !isTypeName(obj) && !isPkgName(obj) {
- continue
- }
-
- // When searching deep, make sure we don't have a cycle in our chain.
- // We don't dedupe by object because we want to allow both "foo.Baz"
- // and "bar.Baz" even though "Baz" is represented the same types.Object
- // in both.
- for _, seenObj := range cand.path {
- if seenObj == obj {
- continue outer
+ // At the top level, dedupe by object.
+ if len(cand.path) == 0 {
+ if c.seen[obj] {
+ continue
+ }
+ c.seen[obj] = true
}
- }
- c.addCandidate(ctx, cand)
+ // If obj is not accessible because it lives in another package and is
+ // not exported, don't treat it as a completion candidate unless it's
+ // a package completion candidate.
+ if !c.completionContext.packageCompletion &&
+ obj.Pkg() != nil && obj.Pkg() != c.pkg.GetTypes() && !obj.Exported() {
+ continue
+ }
- c.deepState.candidateCount++
- if c.opts.budget > 0 && c.deepState.candidateCount%100 == 0 {
- spent := float64(time.Since(c.startTime)) / float64(c.opts.budget)
- select {
- case <-ctx.Done():
- return
- default:
- // If we are almost out of budgeted time, no further elements
- // should be added to the queue. This ensures remaining time is
- // used for processing current queue.
- if !c.deepState.queueClosed && spent >= 0.85 {
- c.deepState.queueClosed = true
+ // If we want a type name, don't offer non-type name candidates.
+ // However, do offer package names since they can contain type names,
+ // and do offer any candidate without a type since we aren't sure if it
+ // is a type name or not (i.e. unimported candidate).
+ if c.wantTypeName() && obj.Type() != nil && !isTypeName(obj) && !isPkgName(obj) {
+ continue
+ }
+
+ // When searching deep, make sure we don't have a cycle in our chain.
+ // We don't dedupe by object because we want to allow both "foo.Baz"
+ // and "bar.Baz" even though "Baz" is represented the same types.Object
+ // in both.
+ for _, seenObj := range cand.path {
+ if seenObj == obj {
+ continue outer
}
}
- }
- // if deep search is disabled, don't add any more candidates.
- if !c.deepState.enabled || c.deepState.queueClosed {
- continue
- }
+ c.addCandidate(ctx, &cand)
- // Searching members for a type name doesn't make sense.
- if isTypeName(obj) {
- continue
- }
- if obj.Type() == nil {
- continue
- }
+ c.deepState.candidateCount++
+ if c.opts.budget > 0 && c.deepState.candidateCount%100 == 0 {
+ spent := float64(time.Since(c.startTime)) / float64(c.opts.budget)
+ select {
+ case <-ctx.Done():
+ return
+ default:
+ // If we are almost out of budgeted time, no further elements
+ // should be added to the queue. This ensures remaining time is
+ // used for processing current queue.
+ if !c.deepState.queueClosed && spent >= 0.85 {
+ c.deepState.queueClosed = true
+ }
+ }
+ }
- // Don't search embedded fields because they were already included in their
- // parent's fields.
- if v, ok := obj.(*types.Var); ok && v.Embedded() {
- continue
- }
+ // if deep search is disabled, don't add any more candidates.
+ if !c.deepState.enabled || c.deepState.queueClosed {
+ continue
+ }
- if sig, ok := obj.Type().Underlying().(*types.Signature); ok {
- // If obj is a function that takes no arguments and returns one
- // value, keep searching across the function call.
- if sig.Params().Len() == 0 && sig.Results().Len() == 1 {
- path, names := c.deepState.newPath(cand, obj, true)
- // The result of a function call is not addressable.
- candidates := c.methodsAndFields(sig.Results().At(0).Type(), false, cand.imp)
- for _, newCand := range candidates {
- newCand.path, newCand.names = path, names
+ // Searching members for a type name doesn't make sense.
+ if isTypeName(obj) {
+ continue
+ }
+ if obj.Type() == nil {
+ continue
+ }
+
+ // Don't search embedded fields because they were already included in their
+ // parent's fields.
+ if v, ok := obj.(*types.Var); ok && v.Embedded() {
+ continue
+ }
+
+ if sig, ok := obj.Type().Underlying().(*types.Signature); ok {
+ // If obj is a function that takes no arguments and returns one
+ // value, keep searching across the function call.
+ if sig.Params().Len() == 0 && sig.Results().Len() == 1 {
+ path := c.deepState.newPath(cand, obj)
+ // The result of a function call is not addressable.
+ c.methodsAndFields(sig.Results().At(0).Type(), false, cand.imp, func(newCand candidate) {
+ newCand.pathInvokeMask = cand.pathInvokeMask | (1 << uint64(len(cand.path)))
+ newCand.path = path
+ c.deepState.enqueue(newCand)
+ })
+ }
+ }
+
+ path := c.deepState.newPath(cand, obj)
+ switch obj := obj.(type) {
+ case *types.PkgName:
+ c.packageMembers(obj.Imported(), stdScore, cand.imp, func(newCand candidate) {
+ newCand.pathInvokeMask = cand.pathInvokeMask
+ newCand.path = path
c.deepState.enqueue(newCand)
- }
- }
- }
-
- path, names := c.deepState.newPath(cand, obj, false)
- switch obj := obj.(type) {
- case *types.PkgName:
- candidates := c.packageMembers(obj.Imported(), stdScore, cand.imp)
- for _, newCand := range candidates {
- newCand.path, newCand.names = path, names
- c.deepState.enqueue(newCand)
- }
- default:
- candidates := c.methodsAndFields(obj.Type(), cand.addressable, cand.imp)
- for _, newCand := range candidates {
- newCand.path, newCand.names = path, names
- c.deepState.enqueue(newCand)
+ })
+ default:
+ c.methodsAndFields(obj.Type(), cand.addressable, cand.imp, func(newCand candidate) {
+ newCand.pathInvokeMask = cand.pathInvokeMask
+ newCand.path = path
+ c.deepState.enqueue(newCand)
+ })
}
}
}
@@ -273,12 +281,40 @@
cand.score = 0
}
- cand.name = strings.Join(append(cand.names, cand.obj.Name()), ".")
+ cand.name = deepCandName(cand)
if item, err := c.item(ctx, *cand); err == nil {
c.items = append(c.items, item)
}
}
+// deepCandName produces the full candidate name including any
+// ancestor objects. For example, "foo.bar().baz" for candidate "baz".
+func deepCandName(cand *candidate) string {
+ totalLen := len(cand.obj.Name())
+ for i, obj := range cand.path {
+ totalLen += len(obj.Name()) + 1
+ if cand.pathInvokeMask&(1<<uint16(i)) > 0 {
+ totalLen += 2
+ }
+ }
+
+ var buf strings.Builder
+ buf.Grow(totalLen)
+
+ for i, obj := range cand.path {
+ buf.WriteString(obj.Name())
+ if cand.pathInvokeMask&(1<<uint16(i)) > 0 {
+ buf.WriteByte('(')
+ buf.WriteByte(')')
+ }
+ buf.WriteByte('.')
+ }
+
+ buf.WriteString(cand.obj.Name())
+
+ return buf.String()
+}
+
// penalty reports a score penalty for cand in the range (0, 1).
// For example, a candidate is penalized if it has already been used
// in another switch case statement.
diff --git a/internal/lsp/source/completion/format.go b/internal/lsp/source/completion/format.go
index 166ba55..c7a7e01 100644
--- a/internal/lsp/source/completion/format.go
+++ b/internal/lsp/source/completion/format.go
@@ -20,6 +20,11 @@
errors "golang.org/x/xerrors"
)
+var (
+ errNoMatch = errors.New("not a surrounding match")
+ errLowScore = errors.New("not a high scoring candidate")
+)
+
// item formats a candidate to a CompletionItem.
func (c *completer) item(ctx context.Context, cand candidate) (CompletionItem, error) {
obj := cand.obj
@@ -27,13 +32,13 @@
// if the object isn't a valid match against the surrounding, return early.
matchScore := c.matcher.Score(cand.name)
if matchScore <= 0 {
- return CompletionItem{}, errors.New("not a surrounding match")
+ return CompletionItem{}, errNoMatch
}
cand.score *= float64(matchScore)
// Ignore deep candidates that wont be in the MaxDeepCompletions anyway.
if len(cand.path) != 0 && !c.deepState.isHighScore(cand.score) {
- return CompletionItem{}, errors.New("not a high scoring candidate")
+ return CompletionItem{}, errLowScore
}
// Handle builtin types separately.
