go/types: Implements is an allocation hotspot

[adonovan]

While profiling the rapid type analysis (golang.org/x/tools/go/callgraph/rta) I noticed that it spends a majority of its time in the types.Implements function. It's not entirely surprising as it's a key part of the algorithm, but we could easily make the analysis several times faster by optimizing this step. Allocation of the next slice in types.lookupFieldOrMethod is a major cost: 43s out of 141s CPU.

Here's an overview of the profile:

You can reproduce it by building cmd/deadcode in https://go.dev/cl/507738 and running it on k8s.io/cmd/kubelet.

[gopherbot]

Change https://go.dev/cl/507855 mentions this issue: go/callgraph/rta: optimise 'implements' operation

[adonovan]

To be fair, the RTA algorithm calls this function too much, so I've changed it to use the Bloom filter technique to reject obvious candidates, which made it 10x faster. Implements still uses 10% of CPU though, which seems high.

^ click this vast empty space to see the profile

[griesemer]

Agreed that this function could use some TLC.

[findleyr]

I looked into this briefly last week, and didn't quite reproduce what Alan saw. I think we could do better here, for example by reusing slices, but it doesn't seem urgent. Moving to 1.23.