x/tools/go/types/objectpath: add Encoder type, to amortize Scope.Names

[adonovan]

The objectpath.For function calls Scope.Names, which allocates and sorts a slice of all package members. If For is called for every member of a package (or for every declaration within a package, which is much more), then it incurs an amount of allocation that is quadratic in the number of package members. Some packages (e.g. for CPU instructions sets) are very large, and objectpath loops become so slow they appear to be stuck.

I propose we add a new Encoder type with a For method so that new(Encoder).For gives the old behavior, but re-using the encoder across multiple calls for objects in the same package amortizes the expensive steps like Scope.Names.

See https://go.dev/cl/470679 for the expedient workaround in gopls (merged).
See https://go.dev/cl/470678 for the change to the public API.

[gopherbot]

Change https://go.dev/cl/470679 mentions this issue: go/types/objectpath: add encoder type, to amortize Scope.Names

[gopherbot]

Change https://go.dev/cl/470678 mentions this issue: go/types/objectpath: add Encoder type, to amortize Scope.Names

[findleyr]

To add additional context: we simply wouldn't be able to use the objectpath package in gopls without this optimization.

Furthermore, I think Encoder is a good name.

[rsc]

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

[rsc]

The API is

package objectpath // import "golang.org/x/tools/go/types/objectpath"

func For(obj types.Object) (Path, error) {
	return new(Encoder).For(obj)
}

// An Encoder amortizes the cost of encoding the paths of multiple objects.
// The zero value of an Encoder is ready to use.
type Encoder struct {
	...
}

func (enc *Encoder) For(obj types.Object) (Path, error) 

Are there any concerns about this API?

[rsc]

Based on the discussion above, this proposal seems like a likely accept.
— rsc for the proposal review group

[timothy-king]

Overall I am in favor of this. I have one minor concern I might as well voice.

func (enc *Encoder) For(obj types.Object) (Path, error) suggests each path can be independently serialized by the encoder. An encoding scheme that shares object path prefixes would be more compact for very large packages but does require a notion of encoding many objs at once to get a benefit. For example instead of serializing a list of paths {"T.T1O", "T.T1CM0"} as {"T.T1O", "T.T1CM0"}, we can serialize it as a shared prefix map plus a list {"T.T1"}, {"0O","0CM0"}. Fact serialization for unitchecker is a bulk operation like this.

It is possible that if objectpath has such a scheme like this in the future, it might be more ergonomic for func (enc *Encoder) For(obj types.Object) (Path, error) to generate a relative path instead. But I don't think this is a serious objection as the compression can be done at the file level later (say gzip) or Encoder can be extended with other functions in the future func (enc *Encoder) All(objs []types.Object) (Table, []Path, error).

[rsc]

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.
— rsc for the proposal review group

[adonovan]

@timothy-king: func (enc *Encoder) For(obj types.Object) (Path, error) suggests each path can be independently serialized by the encoder.

Yes, and that's the existing contract of the objectpath package. Think of it schematically as:

types.Object₁ - types.Package₁ = objectpath.Path
objectpath.Path + types.Package₂ = types.Object₂

If you need some other data structure (Table in your example) to make sense of the Path then either the Path is incomplete, or the Table is just something that can be derived from the Package by an analogous Decoder interface.

You're right that there may be more efficient encodings of sets of Paths, but that's not a compatible evolution of this API.

[adonovan]

This was fixed by https://go.dev/cl/470678.

[gopherbot]

Change https://go.dev/cl/496875 mentions this issue: internal/typesinternal: remove NewObjectpathFunc

[dominikh]

@adonovan Wouldn't objectpath.Object also benefit from memoization? In Staticcheck I am seeing

[adonovan]

There has been a memoized version of namedMethods since CL 470679. Of course you have to use an objectpath.Encoder, but it's an easy change.

[Edit: ignore me, replying before coffee.]

[adonovan]

I question whether it's necessary to sort named-type methods at all. So long as the export/import process preserves whatever order was there in the original types.Named produced from syntax, it doesn't actually matter what order that is. Perhaps we could just delete the expectation of Id-ordered method lists and use "whatever order go/types gives us". We should probably add some normative text to the Named.Method doc comment ("arbitrary but deterministic order"), and to the export/import package ("preserves order"), but then we could just remove the sort method. I see Rob just filed an issue.

[findleyr]

@adonovan unfortunately the sorting was added in https://go.dev/cl/354433 to fix https://go.dev/issue/44195. At the time, we didn't understand the implications of the fix.

We're going to have to do something else to avoid the sort. It is prohibitively expensive when doing modular analysis of certain repositories.

[adonovan]

Fortunately that change didn't promise anything in the API, so I think we can simply use whatever unspecified yet deterministic order the type checker produces (and the exporter and importer preserve) and delete the sort.

[findleyr]

@adonovan that CL description cites parse independence as one of the main goals. Probably this requires more investigation.

[adonovan]

The CL description talks about "parse order" as if it is something different from "what's in the source file". I don't know why we would need or want to be independent of that. The attached issue is about the fact that gcexportdata used to sort and thus lose the order, but it has since been fixed so that it now preserves order.

If go/types promises that method order is deterministic, and gcexportdata promises that it preserves method order, then there's nothing more to do.