Repository navigation
go/doc: repeated declaration indexing makes Examples quadratic #82675
Description
Go version and environment
go1.28-devel_99291162c3 (2026-10-26), linux/amd64. Intel i9-13900K; GOMAXPROCS=1. Measurements recorded on 27 October 2026.
Also reproduced at 63313a0 on linux/arm64 (CIX P1 CP8180) on 28 October 2026.
What did you do?
Save this as examples.go, then run go run examples.go -n=1000 and go run examples.go -n=2000. Parsing is outside the measured operation.
Reproducer
package main
import (
"flag"
"fmt"
"go/doc"
"go/parser"
"go/token"
"strings"
"testing"
)
func main() {
n := flag.Int("n", 1000, "number of examples")
flag.Parse()
var src strings.Builder
src.WriteString("package p_test\n")
for i := 0; i < *n; i++ {
fmt.Fprintf(&src, "func ExampleF%d() {}\n", i)
}
file, err := parser.ParseFile(token.NewFileSet(), "p_test.go", src.String(), 0)
if err != nil {
panic(err)
}
result := testing.Benchmark(func(b *testing.B) {
b.ReportAllocs()
for b.Loop() {
if got := len(doc.Examples(file)); got != *n {
b.Fatalf("got %d examples, want %d", got, *n)
}
}
})
fmt.Println(result, result.MemString())
}What did you see happen?
Each playable example rebuilds the same top-level declaration and method indexes. Index construction takes O(E*D) work for E examples and D declarations, becoming quadratic when both grow together.
At 1,000 examples the measured operation took 68.412 ms and allocated 104.69 MiB; at 2,000 it took 319.380 ms and allocated 417.710 MiB.
What did you expect to see?
Examples from the same file should share its read-only declaration indexes.
CartoGopher tooling for source navigation; reproduction, implementation and testing with Codex.
Activity
seankhliao commentedon Oct 28, 2026
given the low number of examples in a typical package I can hardly see this as a problem
gopherbot commentedon Oct 28, 2026
Change https://go.dev/cl/855661 mentions this issue:
go/doc: reuse declaration indexes across examplesthatnealpatel commentedon Oct 28, 2026
@nicholashusin Is this the elusive
go docbug we saw a few months ago?!nicholashusin commentedon Oct 28, 2026
#78801 right?
I think it's different. #78801 was already fixed and seems to be more so an infinite loop (judging from how it never finishes and eventually OOMs).
JakeNesler commentedon Oct 28, 2026
I just tried it and they are indeed different 👍
thatnealpatel commentedon Oct 28, 2026
I agree with @seankhliao
JakeNesler commentedon Oct 28, 2026
All good, I won’t be offended if it’s not as useful as I thought. I did try it on the Google Cloud SDK: example extraction went from 116 ms to 68 ms, and allocated memory from 68.5 MiB to 34.5 MiB. Overall it was small, but I still figured it was something :)
JunyangShao commentedon Oct 29, 2026
@griesemer