cmd/compile: exponential compile-time with nested generic instantiations

[jake-ciolek]

Go version

go 1.26.1 / tip

Output of go env in your module/workspace:

GOARCH=arm64

What did you do?

case 1:

package p

type T[P any] struct { _,_,_,_,_,_,_,_ P }

type U T[T[T[T[T[T[T[T[T[T[int]]]]]]]]]]

case 2:

package p

type T[P any] struct { _,_,_,_,_,_,_,_ P }

type U T[T[T[T[T[T[T[T[T[T[T[int]]]]]]]]]]]

case 3:

package p

type T[P any] struct { _,_,_,_,_,_,_,_ P }

type U T[T[T[T[T[T[T[T[T[T[T[T[int]]]]]]]]]]]]

Run go build on the above and measure the time.

What did you see happen?

Very long compile time.

What did you expect to see?

Fast compilation.

[verysleepylemon]

This is a known class of compile-time complexity issues with deeply nested generic type aliases. The root cause is that the type-checker (and/or the DWARF/size computation passes) re-expands T[...] at each nesting level, leading to exponential work proportional to the branching factor (8 fields) raised to the nesting depth.

For the example:

type T[P any] struct { _,_,_,_,_,_,_,_ P }  // 8 fields
type U T[T[T[T[T[T[T[T[T[T[int]]]]]]]]]]    // 10 levels deep → 8^10 ≈ 1 billion expansions

Each additional nesting level multiplies the work by 8. This should be caught by memoization/caching of already-computed type instances, but something in the type-size or DWARF emission path is apparently doing repeated re-traversal.

A similar hang was reported for recursive generic types in #78341 — this variant is distinct because it's a finite (non-recursive) nesting, so it should in principle be handleable by a simple visited-set or size-cache check. The fix likely belongs in the type-size computation or the generic instantiation deduplication logic in cmd/compile/internal/types2.

As a workaround until this is fixed: keep nesting depth below ~7 or introduce a named intermediate type to break the chain.

[hesam-oxe]

I'd like to investigate this. The issue points to missing memoization
in the type-size computation or DWARF emission path in
cmd/compile/internal/types2.

I'll look at:

• Adding a visited-set or size-cache for already-computed type instances
• Checking where repeated re-traversal happens in the instantiation
  deduplication logic

verysleepylemon's analysis is spot-on — I'll start there.

/assign