[tools] go/types/objectpath: optimize search to avoid quadratic time

0 views

Skip to first unread message

Gopher Robot (Gerrit)

unread,

Apr 23, 2026, 5:39:05 PM (2 days ago) Apr 23

to Alan Donovan, goph...@pubsubhelper.golang.org, golang-...@googlegroups.com, golang...@luci-project-accounts.iam.gserviceaccount.com, Mark Freeman, Robert Findley, Nicolas Hillegeer, Robert Griesemer, golang-co...@googlegroups.com

Gopher Robot submitted the change with unreviewed changes

Unreviewed changes

4 is the latest approved patch-set.
The change was submitted with unreviewed changes in the following files:

```
The name of the file: go/types/objectpath/bench_test.go
Insertions: 3, Deletions: 3.

@@ -15,7 +15,7 @@
 	"golang.org/x/tools/txtar"
 )
 
-// BenchmarkMonster tests that objectpath operatons on monstrously
+// BenchmarkMonster tests that objectpath operations on monstrously
 // large packages complete in linear time and space.
 func BenchmarkMonster(b *testing.B) {
 	// Construct a monster package.
@@ -85,9 +85,9 @@
 		// Pick a set of objects including a mix of types, fields, and methods.
 		var targets []types.Object
 		for j := range count {
-			// Offset of 15 avoids locking stride
+			// Offset of 17 (prime) avoids locking stride
 			// with periodicity in monster package.
-			idx := (j*len(all)/count + 15) % len(all)
+			idx := (j*len(all)/count + 17) % len(all)
 			targets = append(targets, all[idx])
 		}
 
```
```
The name of the file: go/types/objectpath/objectpath.go
Insertions: 75, Deletions: 73.

@@ -129,8 +129,8 @@
 	pkgIndex map[*types.Package]*pkgIndex
 }
 
-// A finder encapsulates the state of a single traversal of the object/type graph.
-type finder struct {
+// A traversal encapsulates the state of a single traversal of the object/type graph.
+type traversal struct {
 	pkg *types.Package
 	ix  *pkgIndex // non-nil if we are building the index
 
@@ -184,7 +184,7 @@
 type pkgIndex struct {
 	pkg        *types.Package
 	data       []byte                  // encoding of traversal; nil if not yet constructed
-	scopeNames []string                // memo of pkg.Scope().Names()
+	scopeNames []string                // memo of pkg.Scope().Names() to avoid O(n) alloc/sort at lookup
 	offsets    map[types.Object]uint32 // each object's node offset within encoded traversal data
 }
 
@@ -299,7 +299,8 @@
 		return "", fmt.Errorf("no path for %v", obj)
 
 	case *types.Var:
-		// A var, if not package-level, must be a receiver, parameter, or result.
+		// A var, if not package-level, must be a
+		// parameter (incl. receiver) or result, or a struct field.
 		if obj.Kind() == types.LocalVar {
 			return "", fmt.Errorf("no path for local %v", obj)
 		}
@@ -319,10 +320,13 @@
 		panic(obj)
 	}
 
-	// 4. Search the object+type graph for the path to
+	// 4. Search the object/type graph for the path to
 	//    the var (field/param/result) or method.
 	ix, ok := enc.pkgIndex[pkg]
 	if !ok {
+		// First search: don't build an index, just traverse.
+		// This avoids allocation in [For], whose Encoder
+		// lives for a single call.
 		ix = &pkgIndex{pkg: pkg}
 
 		if enc.pkgIndex == nil {
@@ -330,9 +334,7 @@
 		}
 		enc.pkgIndex[pkg] = ix // build the index next time
 
-		// First search: don't build an index, just traverse.
-		// This avoids allocation in a one-off call to [For].
-		f := finder{pkg: pkg, target: obj}
+		f := traversal{pkg: pkg, target: obj}
 		f.traverse()
 
 		if f.found != "" {
@@ -343,7 +345,7 @@
 		if ix.data == nil {
 			ix.offsets = make(map[types.Object]uint32)
 			ix.data = []byte{0} // offset 0 is sentinel
-			(&finder{pkg: pkg, ix: ix}).traverse()
+			(&traversal{pkg: pkg, ix: ix}).traverse()
 		}
 
 		// Second and later searches: consult the index.
@@ -356,11 +358,11 @@
 }
 
 // traverse performs a complete traversal of all symbols reachable from the package.
-func (f *finder) traverse() {
-	scope := f.pkg.Scope()
+func (tr *traversal) traverse() {
+	scope := tr.pkg.Scope()
 	names := scope.Names()
-	if f.ix != nil {
-		f.ix.scopeNames = names
+	if tr.ix != nil {
+		tr.ix.scopeNames = names
 	}
 
 	empty := make([]byte, 0, 48) // initial space for stack (ix == nil)
@@ -370,7 +372,7 @@
 	// the best paths because non-types may
 	// refer to types, but not the reverse.
 	for i, name := range names {
-		if f.found != "" {
+		if tr.found != "" {
 			return // found (ix == nil)
 		}
 
@@ -382,30 +384,30 @@
 		// emit (name, opType)
 		var path []byte
 		var offset uint32
-		if f.ix == nil {
+		if tr.ix == nil {
 			path = append(empty, name...)
 			path = append(path, opType)
 		} else {
-			offset = f.ix.emitToplevel(i)
-			f.ix.offsets[obj] = offset
-			offset = f.ix.emitNested(offset, opType, -1)
+			offset = tr.ix.emitPackageLevel(i)
+			tr.ix.offsets[obj] = offset
+			offset = tr.ix.emitPathSegment(offset, opType, -1)
 		}
 
 		// A TypeName (for Named or Alias) may have type parameters.
 		switch t := obj.Type().(type) {
 		case *types.Alias:
-			f.tparams(t.TypeParams(), path, offset, opTypeParam)
-			f.typ(path, offset, opRhs, -1, t.Rhs())
+			tr.tparams(t.TypeParams(), path, offset, opTypeParam)
+			tr.typ(path, offset, opRhs, -1, t.Rhs())
 		case *types.Named:
-			f.tparams(t.TypeParams(), path, offset, opTypeParam)
-			f.typ(path, offset, opUnderlying, -1, t.Underlying())
+			tr.tparams(t.TypeParams(), path, offset, opTypeParam)
+			tr.typ(path, offset, opUnderlying, -1, t.Underlying())
 		}
 	}
 
 	// Then inspect everything else:
 	// exported non-types, and declared methods of defined types.
 	for i, name := range names {
-		if f.found != "" {
+		if tr.found != "" {
 			return // found (ix == nil)
 		}
 
@@ -416,25 +418,25 @@
 				// exported non-type (const, var, func)
 				var path []byte
 				var offset uint32
-				if f.ix == nil {
+				if tr.ix == nil {
 					path = append(empty, name...)
 				} else {
-					offset = f.ix.emitToplevel(i)
-					f.ix.offsets[obj] = offset
+					offset = tr.ix.emitPackageLevel(i)
+					tr.ix.offsets[obj] = offset
 				}
-				f.typ(path, offset, opType, -1, obj.Type())
+				tr.typ(path, offset, opType, -1, obj.Type())
 			}
 
 		} else if T, ok := types.Unalias(tname.Type()).(*types.Named); ok {
 			// defined type
 			var path []byte
 			var offset uint32
-			if f.ix == nil {
+			if tr.ix == nil {
 				path = append(empty, name...)
 				path = append(path, opType)
 			} else {
 				// Inv: map entry for obj was populated in first pass.
-				offset = f.ix.emitNested(f.ix.offsets[obj], opType, -1)
+				offset = tr.ix.emitPathSegment(tr.ix.offsets[obj], opType, -1)
 			}
 
 			// Inspect declared methods of defined types.
@@ -445,16 +447,16 @@
 			// and must be preserved by export data.
 			for i := 0; i < T.NumMethods(); i++ {
 				m := T.Method(i)
-				f.object(path, offset, opMethod, i, m)
+				tr.object(path, offset, opMethod, i, m)
 			}
 		}
 	}
 }
 
-func (f *finder) visitType(path []byte, offset uint32, T types.Type) {
+func (tr *traversal) visitType(path []byte, offset uint32, T types.Type) {
 	switch T := T.(type) {
 	case *types.Alias:
-		f.typ(path, offset, opRhs, -1, T.Rhs())
+		tr.typ(path, offset, opRhs, -1, T.Rhs())
 
 	case *types.Basic, *types.Named:
 		// Named types belonging to pkg were handled already,
@@ -463,105 +465,105 @@
 
 	case *types.Pointer, *types.Slice, *types.Array, *types.Chan:
 		type hasElem interface{ Elem() types.Type } // note: includes Map
-		f.typ(path, offset, opElem, -1, T.(hasElem).Elem())
+		tr.typ(path, offset, opElem, -1, T.(hasElem).Elem())
 
 	case *types.Map:
-		f.typ(path, offset, opKey, -1, T.Key())
-		f.typ(path, offset, opElem, -1, T.Elem())
+		tr.typ(path, offset, opKey, -1, T.Key())
+		tr.typ(path, offset, opElem, -1, T.Elem())
 
 	case *types.Signature:
-		f.tparams(T.RecvTypeParams(), path, offset, opRecvTypeParam)
-		f.tparams(T.TypeParams(), path, offset, opTypeParam)
-		f.typ(path, offset, opParams, -1, T.Params())
-		f.typ(path, offset, opResults, -1, T.Results())
+		tr.tparams(T.RecvTypeParams(), path, offset, opRecvTypeParam)
+		tr.tparams(T.TypeParams(), path, offset, opTypeParam)
+		tr.typ(path, offset, opParams, -1, T.Params())
+		tr.typ(path, offset, opResults, -1, T.Results())
 
 	case *types.Struct:
 		for i := 0; i < T.NumFields(); i++ {
-			f.object(path, offset, opField, i, T.Field(i))
+			tr.object(path, offset, opField, i, T.Field(i))
 		}
 
 	case *types.Tuple:
 		for i := 0; i < T.Len(); i++ {
-			f.object(path, offset, opAt, i, T.At(i))
+			tr.object(path, offset, opAt, i, T.At(i))
 		}
 
 	case *types.Interface:
 		for i := 0; i < T.NumMethods(); i++ {
 			m := T.Method(i)
-			if m.Pkg() != nil && m.Pkg() != f.pkg {
+			if m.Pkg() != nil && m.Pkg() != tr.pkg {
 				continue // embedded method from another package
 			}
-			if !f.seenMethods[m] {
-				if f.seenMethods == nil {
-					f.seenMethods = make(map[*types.Func]bool)
+			if !tr.seenMethods[m] {
+				if tr.seenMethods == nil {
+					tr.seenMethods = make(map[*types.Func]bool)
 				}
-				f.seenMethods[m] = true
-				f.object(path, offset, opMethod, i, m)
+				tr.seenMethods[m] = true
+				tr.object(path, offset, opMethod, i, m)
 			}
 		}
 
 	case *types.TypeParam:
 		tname := T.Obj()
-		if tname.Pkg() != nil && tname.Pkg() != f.pkg {
+		if tname.Pkg() != nil && tname.Pkg() != tr.pkg {
 			return // type parameter from another package
 		}
-		if !f.seenTParamNames[tname] {
-			if f.seenTParamNames == nil {
-				f.seenTParamNames = make(map[*types.TypeName]bool)
+		if !tr.seenTParamNames[tname] {
+			if tr.seenTParamNames == nil {
+				tr.seenTParamNames = make(map[*types.TypeName]bool)
 			}
-			f.seenTParamNames[tname] = true
-			f.object(path, offset, opObj, -1, tname)
-			f.typ(path, offset, opConstraint, -1, T.Constraint())
+			tr.seenTParamNames[tname] = true
+			tr.object(path, offset, opObj, -1, tname)
+			tr.typ(path, offset, opConstraint, -1, T.Constraint())
 		}
 	}
 }
 
-func (f *finder) tparams(list *types.TypeParamList, path []byte, offset uint32, op byte) {
+func (tr *traversal) tparams(list *types.TypeParamList, path []byte, offset uint32, op byte) {
 	for i := 0; i < list.Len(); i++ {
-		f.typ(path, offset, op, i, list.At(i))
+		tr.typ(path, offset, op, i, list.At(i))
 	}
 }
 
 // typ descends the type graph edge (op, index), then proceeds to traverse type t.
-func (f *finder) typ(path []byte, offset uint32, op byte, index int, t types.Type) {
-	if f.ix == nil {
+func (tr *traversal) typ(path []byte, offset uint32, op byte, index int, t types.Type) {
+	if tr.ix == nil {
 		path = appendOpArg(path, op, index)
 	} else {
-		offset = f.ix.emitNested(offset, op, index)
+		offset = tr.ix.emitPathSegment(offset, op, index)
 	}
-	f.visitType(path, offset, t)
+	tr.visitType(path, offset, t)
 }
 
 // object descends the type graph edge (op, index), records object
 // obj, then proceeds to traverse its type.
-func (f *finder) object(path []byte, offset uint32, op byte, index int, obj types.Object) {
-	if f.ix == nil {
+func (tr *traversal) object(path []byte, offset uint32, op byte, index int, obj types.Object) {
+	if tr.ix == nil {
 		path = appendOpArg(path, op, index)
-		if obj == f.target && f.found == "" {
-			f.found = Path(path)
+		if obj == tr.target && tr.found == "" {
+			tr.found = Path(path)
 		}
 		path = append(path, opType)
 	} else {
-		offset = f.ix.emitNested(offset, op, index)
-		if _, ok := f.ix.offsets[obj]; !ok {
-			f.ix.offsets[obj] = offset
+		offset = tr.ix.emitPathSegment(offset, op, index)
+		if _, ok := tr.ix.offsets[obj]; !ok {
+			tr.ix.offsets[obj] = offset
 		}
-		offset = f.ix.emitNested(offset, opType, -1)
+		offset = tr.ix.emitPathSegment(offset, opType, -1)
 	}
-	f.visitType(path, offset, obj.Type())
+	tr.visitType(path, offset, obj.Type())
 }
 
-// emitToplevel encodes a record for a package-level symbol,
+// emitPackageLevel encodes a record for a package-level symbol,
 // identified by its index in ix.scopeNames.
-func (p *pkgIndex) emitToplevel(index int) uint32 {
+func (p *pkgIndex) emitPackageLevel(index int) uint32 {
 	off := uint32(len(p.data))
 	p.data = append(p.data, 0) // zero varint => no parent
 	p.data = binary.AppendUvarint(p.data, uint64(index))
 	return off
 }
 
-// emitNested emits a record for a non-initial object path segment.
-func (p *pkgIndex) emitNested(parent uint32, op byte, index int) uint32 {
+// emitPathSegment emits a record for a non-initial object path segment.
+func (p *pkgIndex) emitPathSegment(parent uint32, op byte, index int) uint32 {
 	off := uint32(len(p.data))
 	p.data = binary.AppendUvarint(p.data, uint64(parent))
 	p.data = append(p.data, op)
```
```
The name of the file: go/types/objectpath/objectpath_test.go
Insertions: 1, Deletions: 1.

@@ -251,7 +251,7 @@
 	// We also call [objectpath.Encoder.For] three times to ensure it
 	// gives consistent results with [objectpath.For] in all states:
 	//  1: searching for symbol without index
-	//  2: building index and lookup symbol
+	//  2: building index and looking up symbol
 	//  3: looking up symbol in existing index.
 	{
 		enc := new(objectpath.Encoder)
```

Change information

Commit message:

go/types/objectpath: optimize search to avoid quadratic time

The previous implementation of objectpath would search the entire
breadth of a package API for a field/param/result/method symbol,
every time it was asked to do so. If a client requests ~every
symbol of a large package, this results in quadratic work.
This was the cause of the associated bug, which caused Google
analysis jobs to time out.

This CL rewrites the traversal logic to avoid this quadratic
asymptote. Now, when the search is requested, it builds an
index of each object's path so that it can be efficiently
reconstructed on a subsequent call. (The traversal is recorded
as a compressed trie of nodes that each record the index of
their immediate ancestor, plus a single objectpath segment
operation.)

However, we don't want to construct the index on the very
first call, as this would allocate O(n) memory where today
a single-use Encoder, such as the ephemeral ones created by
objectpath.For, allocates very little. So, the traversal has
been factored so that it uses the traditional search on the
first call (ix==nil) and emits the compressed index at the
start of the second call (ix==nil && ix.data==nil).
Thereafter all calls hit the index.

Also:

- skip local variables at the outset, now that we can
discriminate them thanks to go.dev/issue/70250.

- test consistency between the two different search
strategies.

- fixed one error message

- benchmark of "monstrous" packages that exhibits the problem.

darwin/arm64 Apple M1 Pro

Before
BenchmarkMonster/Single-8 932 1188380 ns/op 164232 B/op 6 allocs/op
BenchmarkMonster/Many-8 45 25100278 ns/op 170480 B/op 204 allocs/op
BenchmarkMonster/All-8 1 12159657083 ns/op 3683904 B/op 150004 allocs/

After
BenchmarkMonster/Single-8 823 1482937 ns/op 82184 B/op 5 allocs/op
BenchmarkMonster/Many-8 100 12526129 ns/op 13833970 B/op 773 allocs/op
BenchmarkMonster/All-8 50 26003344 ns/op 18155589 B/op 150574 allocs/op

The Single case is 20% slower but Many is 2x faster and All case is 468x better.
Space usage is higher, but could perhaps be reduced by using an only-2-level trie.

Fixes golang/go#78893