x/tools/go/types/objectpath: frequent use of scope.Names burns significant cycles

[amscanne]

What version of Go are you using (go version)?

go1.18-pre10

Does this issue reproduce with the latest release?

Yes.

What operating system and processor architecture are you using (go env)?

Linux, amd64. Not dependent on OS or architecture, however.

What did you do?

The objectpath.For method relies on frequent calls to scope.Names(), which always performs a sort of all names. For large-scale analysis trees, this can consume a significant portion of cycles (30-50% in my case) and can easily be memoized. This can either be done by objectpath as a consumer of the API, or within the *types.Scope object.

What did you expect to see?

Fewer cycles spent sorting.

What did you see instead?

Lots of cycles spent sorting.

[gopherbot]

Change https://golang.org/cl/383075 mentions this issue: go/types: memoize scope.Names() result

[findleyr]

Thanks for filing.

Need to think about this. I'll just note that in the profile linked on that CL, there is also significant amount of time spent in Scope.Lookup. But objectpath just needs to walk all the objects, and doesn't care about sorting. I wonder if we should be considering an entirely new Scope API... Or maybe that is further evidence that it would be better for us to build a layer in objectpath that can significantly optimize the calculation of paths. Compare x/tools/go/ast/inspector.

[gopherbot]

Change https://go.dev/cl/404514 mentions this issue: go/types/objectpath: implement fast path for concrete methods

[gopherbot]

Change https://go.dev/cl/405354 mentions this issue: go/types/objectpath: cache repeated queries (WiP)

[findleyr]

@griesemer @alandonovan what do you think about this change? https://go.dev/cl/383075 appears to be stuck in limbo, and it would be good to make a decision for 1.20.

Being conservative, I am inclined to say that changing scope.Names to return a memoized slice is a breaking change, may increase steady-state memory, and is inconsistent with the rest of the go/types API which goes to lengths to avoid exposing internal data (consider Struct.NumFields, etc.). If the problem is mostly isolated to usage of objectpath, we could expose a batch or memoizing API.

But I don't feel strongly. If it is most expedient to save sorted names on the scope, in reality it is probably harmless.

[adonovan]

The actual code review hasn't addressed all the comments (e.g. re: atomicity) required for +2, but perhaps that's just because the author doesn't know if the design is worth pursuing.

I agree that if the problem is really just in objectpath, then that's a safer place for the fix: perhaps objectpath could compute the paths for the entire package more cheaply in a single pass, then serve a large number of queries on that---like the AST inspector. Even if we don't implement all that at once, the same API could take the first step of memoizing scope.Names() across multiple calls, but it seems likely there are even bigger potential wins if we take that approach.

[findleyr]

The actual code review hasn't addressed all the comments (e.g. re: atomicity) required for +2, but perhaps that's just because the author doesn't know if the design is worth pursuing.

I assumed as much. We did not resolve the viability of the approach in that CL.

I agree that if the problem is really just in objectpath, then that's a safer place for the fix: perhaps objectpath could compute the paths for the entire package more cheaply in a single pass, then serve a large number of queries on that---like the AST inspector. Even if we don't implement all that at once, the same API could take the first step of memoizing scope.Names() across multiple calls, but it seems likely there are even bigger potential wins if we take that approach.

Yes, that is approximately the API I had in mind, and the AST inspector is a good example. Agree that there are probably other potential optimizations in that approach.