x/tools/gopls: deepCompletionState.enqueue is an allocation hotspot

[adonovan]

I noticed while running TestBenchmarkConfiguredCompletion on k8s that deepCompletionState.enqueue

func (s *deepCompletionState) enqueue(cand candidate) {
	s.nextQueue = append(s.nextQueue, cand)
}

allocates 10GB of memory because it adds 5 million completion candidates to the queue, each being an 18-word structure. This causes each call of env.Completion in the benchmark to take 10s. There are two calls, the warmup and the one in the b.N loop (which only reaches N=1).

This was the command. The .go file is my favorite large file in k8s.

$ go test -bench=TestBenchmarkConfiguredCompletion ./gopls/internal/regtest/bench -completion_workdir=$HOME/w/kubernetes -completion_file=../kubernetes/pkg/generated/openapi/zz_generated.openapi.go -completion_regexp=Get

Also, 2GB (and 3s CPU) are spent on this call to Type.String in completer.methodsAndFields:

if typ.String() == "*testing.F" && addressable {
	// is that a sufficient test? (or is more care needed?)
	if c.fuzz(typ, mset, imp, cb, c.snapshot.FileSet()) {
		return
	}
}

@muirdm

[muirdm]

The queue was added when the candidate search was changed from DFS to BFS. I presume the benchmark disables the completion budget to avoid flakiness. In practice the budget is set to ~100ms, so the search gives up sooner. Improving this hotspot would allow gopls to search more candidates within its 100ms budget, but might not end up materially improving the completion results or reducing overall CPU usage (assuming it couldn't search 5 million candidates in 100ms anyway).

[findleyr]

Ah, thanks @muirdm. Right: the benchmark takes 10s because IIRC the regtest environment sets a completion budget of 10s.

We should investigate whether reducing allocation allows us to search more candidates per second, as that might matter more for smaller repos.

[adonovan]

Thanks @muirdm for the insight. The running time of both calls---warmup and the first benchmark run---did seem curiously similar, not to mention close to 10s.

So, the benchmark is fundamentally flawed: it always measures the first 10s of a loop that never completes, and that includes completion tasks and other tasks (parsing and type checking). Therefore making the production code faster at the task the benchmark claims to measure does not improve the benchmark numbers, it merely reduces the fraction of the constant 10s of wall time that is spent in completion tasks. Consequently memory allocation appears to go through the roof (because parsing and type-checking are so allocy). I don't know the code well enough to say how, but we should change the benchmark to measure a task that corresponds to the latency experienced by the user in a completion request.

[Update: Rob pointed out that it's really my choice of using the large k8s module as input that exposes the problem with the benchmark.]

[gopherbot]

Change https://go.dev/cl/422906 mentions this issue: internal/lsp/completion: don't use Type.String for checking identity

[adonovan]

The typ.String() issue has been fixed, and the other problem is really an artifact of using a much larger input than the benchmark was designed to handle. The actual allocations on smaller repos look more reasonable. Closing.