cmd/compile: since CL 725380, equality functions are no longer shared across nested struct types

[ReneWerner87]

Go version

go version go1.27.0 darwin/arm64

Reproduced identically on go1.25.12, go1.26.6 and go1.26.7 (all fine); new in go1.27.0.

Output of go env in your module/workspace:

GOARCH='arm64'
GOARM64='v8.0'
GOOS='darwin'
GOVERSION='go1.27.0'
GOEXPERIMENT=''
GODEBUG=''
CGO_ENABLED='1'
CC='clang'
GOGCCFLAGS='-fPIC -arch arm64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -gno-record-gcc-switches -fno-common'

What did you do?

Compile a package containing a comparable struct type assembled from nested named struct types. The four shapes below all have exactly 4096 string leaves and the same memory layout; only the nesting differs.

// 0 levels: one flat struct of 4096 string fields
type T struct { F0, F1, ... F4095 string }

// 1 level: 64 fields, each a struct of 64 strings
type Leaf struct { F0, ... F63 string }
type T struct { G0, ... G63 Leaf }

// 2 levels: 16 x 16 x struct of 16 strings
type L0 struct { F0, ... F15 string }
type L1 struct { G0, ... G15 L0 }
type T struct { H0, ... H15 L1 }

// 12 levels: doubling
type fan0 struct{ V string }
type fan1 struct{ A, B fan0 }
// ... through
type fan12 struct{ A, B fan11 }

The doubling shape is the shortest to reproduce and needs no generator:

mkdir /tmp/fan && cd /tmp/fan && go mod init fan
python3 -c "
print('package fan\n')
print('type fan0 struct{ V string }')
for i in range(1, 13): print(f'type fan{i} struct{{ A, B fan{i-1} }}')" > fan.go
go build -gcflags=-S . 2>&1 | grep 'type:\.eq.*STEXT'

Under go1.26.6 that prints 12 symbols of 112 to 224 bytes. Under go1.27.0 the largest is 289,040 bytes with a 4,105 character name. Raise 12 to 14 and that same file takes 109s and 6.7 GB. The four shapes in the table differ only in how the same 4096 leaves are grouped. All sizes below are the sum of the generated type:.eq.* symbols from go build -gcflags=-S.

What did you see happen?

Total generated equality-function code, same 4096 leaves in every row:

shape	levels	source	go1.26.6	go1.27.0
one flat struct	0	55 KB	348,848 B	289,040 B	1.27 is better
64 x struct{64 strings}	1	1.4 KB	5,168 B	292,176 B	57x
16 x 16 x struct{16 strings}	2	489 B	1,728 B	302,224 B	175x
doubling (fan12)	12	422 B	1,504 B	493,328 B	328x

go1.27.0 emits the same 289,040 byte function with the same 4,105 character symbol name in all four cases, because the signature is SSSS...S (4096 S) for every shape. Structure is flattened away entirely. go1.26.6 ranges from 348,848 bytes (flat, nothing to share) down to 1,504 bytes (maximum sharing).

Those four shapes are synthetic, to hold the leaf count fixed while varying only the nesting. The effect is not confined to synthetic types. Here is ordinary domain code, 401 bytes, mixed field types, no doubling and nothing unusual:

type Addr struct { Street, City, Zip, Country string; Lat, Lon float64; Verified bool }
type Contact struct { Name, Email, Phone string; Home, Work, Billing Addr; Age int }
type Party struct { ID string; Primary, Secondary, Emergency Contact; Score float64 }
type Deal struct { Ref string; Buyer, Seller, Broker, Agent Party; Amount int64 }
type Book struct { A, B, C, D, E, F, G, H Deal }

	go1.26.6	go1.27.0
total generated eq code	1,264 B	108,448 B	86x
largest single function	288 B	93,600 B	325x
longest symbol name	18	3,457

Five type declarations that could come from any application's data model.

One point I want to be precise about: on the genuinely flat type, 1.27 is better than 1.26. So this is not "the type has 4096 fields, therefore 4096 units of work". The regression appears only where there is structure that could have been shared, and it grows with how much sharing was available.

Mechanism, reflectdata/alg.go:745 in the TSTRUCT case of eqSigBuilder.build:

	case types.TSTRUCT:
		var off int64
		for _, f := range t.Fields() {
			if f.Sym.IsBlank() {
				continue
			}
			if off < f.Offset {
				e.skip(f.Offset - off)
			}
			e.build(f.Type)          // recurses into every field, unconditionally
			off = f.Offset + f.Type.Size()
		}

There is no depth counter, size budget or fallback. Before CL 725380 (30dff41, "cmd/compile: redo how equality functions are generated") one function was emitted per named type and it called the child type's function, visible in the 1.26.6 assembly:

type:.eq.fan.fan8 STEXT dupok size=112
	CALL	type:.eq.fan.fan7(SB)
	...
	CALL	type:.eq.fan.fan7(SB)

Sizes on 1.26.6 are 112 to 224 bytes per function and constant in depth. On 1.27.0 both the function and the symbol name grow with the leaf count; the symbol name is exactly 2^depth + 9 characters, verified without deviation over depths 1 to 13. Depth 19 would be a 524,297 character symbol name and, extrapolating the measured 70 to 79 bytes per leaf, at least ~37 MB of machine code in one function; it does not finish compiling.

Compile time and peak RSS follow, though these are the least stable numbers here: at depth 13 (8192 leaves) with a cold cache, go1.26.6 takes 0.17s at 20 MB and go1.27.0 takes 13.6s at 4.37 GB. Repeated runs vary by roughly a factor of two and GOMAXPROCS shifts the wall clock several fold, so the generated-code sizes above are the reliable evidence and the timings only indicative. At depth 19 the compile had not finished after 160s, with RSS oscillating between 3.7 and 5.2 GB rather than climbing, which is what GC pacing trading memory against time looks like.

This is not #80271. The backend's cost on one huge function is superlinear, but that is pre-existing and unchanged in 1.27. A hand-written function doing 4096 straight-line struct field comparisons, with the struct made non-comparable so that no equality function is generated for it, costs a median 1.85s on go1.26.6 and 1.93s on go1.27.0 over three cold-cache runs each, with overlapping ranges (1.84 to 2.03 against 1.91 to 2.17). The backend is not what changed. What changed is that the frontend now generates such a function from a 422 byte source file.

Trigger: declaring the types at package scope is sufficient. No variable, no use, no reflect call. gc/main.go:327 queues a descriptor for every ir.OTYPE extern, and dcommontype calls geneq(t) to fill the Equal field of abi.Type. So there is no workaround via not instantiating the type.

Two honest limits on the blast radius: a *T field ends the flattening (the comparison becomes a pointer compare, and no function is generated at all, so depth 19 with pointer children compiles in 0.05s), and a slice or map field makes the type non-comparable, so no function exists there either. That does exclude a good deal of real code, protobuf-generated types and most Kubernetes API types among it. What remains is any tree of comparable value types, which the Book example above suggests is not an exotic shape.

The hash side behaves the same way after CL 727500 (0da8979, "use equality signatures in hash function generation"): map[fan12]bool yields a 97,280 byte type:.hash symbol with a 4,107 character name.

What did you expect to see?

Cost that scales with the number of distinct sub-signatures in a type, not with its total flattened leaf count, since each sub-signature already has its own generated function.

CL 725380's stated goal was binary size: "The number of generated equality functions in the go binary is reduced from 634 to 286. The go binary is ~1% smaller." On nested types that metric regresses by up to 328x (the table above), so bounding this should be consistent with the CL's own intent rather than in tension with it.

The machinery already exists in the same file. The TARRAY path emits a call to the sub-signature's function rather than to a type's, alg.go:513:

	elemFn := eqFunc(sigTrimSkip(elemSig)).Nname

and parseArray already tracks bracket depth, so nested sub-signatures parse. Expressing the identical layout as nested arrays instead of nested structs, on go1.27.0:

depth 19, 524,288 leaves	result
nested arrays (type a19 [2]a18)	19 functions, 2,752 B total, largest 160 B, names type:.eq.[2[2[2...SS...]]] growing 3 characters per level (11 to 65), 0.05s
nested structs (type fan19 struct{ A, B fan18 })	does not compile

Same compiler, same layout, same leaf count. Two candidate fixes:

1. Minimal. Run-length encode runs of adjacent fields with identical signature and stride into the existing [N ...] form. struct{ A, B fan18 } is layout-identical to [2]fan18, giving sig(fanN) = "[2" + sig(fanN-1) + "]", an O(depth) symbol name and one small function per level. The nested-array row above is that output. All four shapes in the table have fields of one type per level, so this would cover every one of them. It would not help a struct whose fields have many different types, where there is no run to collapse.
2. General. A "call this sub-signature's function" form emitted once a field's own sub-signature exceeds a size threshold, keyed by sub-signature so the sharing property of CL 725380 is preserved. This needs a grammar addition, since the current signature language has no such form.

Worth noting for whoever picks this up: capping the generated code size without changing the signature does not help on its own, because the signature is the symbol name (alg.go:330, sym := types.TypeSymLookup(".eq." + sig)) and the grammar has no back-reference form. Wrapping a single field as [1<subsig>] would leave struct{ A, B fanN } as two textual copies of subsig, so the name stays at 2^depth. Option 1 avoids this precisely because it turns the repetition into a count rather than a wrapper, which is why the array names above grow linearly instead.

One correction to my own framing above, for fairness: the array comment at alg.go:775 documents this asymmetry deliberately ("two types which could share an equality function do not ... That's ok, just a tad inefficient"). It was a known trade-off. What seems not to have been anticipated is that for nested structs the same trade-off costs 328x the generated code rather than "a tad", and that the [N ...] form caps only the repeat count, not the element's own nesting: [64]fan12 still produces a 4,105 character element signature and a 289,040 byte element function.

Related issues

• cmd/compile: exponential behavior for deeply nested structs #65540 "cmd/compile: exponential behavior for deeply nested structs" (open, filed by randall77) is the closest relative and uses the same doubling shape, but with an int leaf. That makes the type AMEM, so no equality function is generated at all and the cost sits in types.AlgType walking the type. The two are cleanly separable: that issue's exact reproducer, 24 levels and 2^24 leaves, compiles in 6.9s at 110 MB on go1.27.0 and emits zero eq symbols, while 12 levels with a string leaf, 4096 leaves and 4000x fewer of them, takes 1.49 GB and emits the 289 KB function above. Anyone who recognises the shape from cmd/compile: exponential behavior for deeply nested structs #65540 should know this is a different mechanism.
• all: binaries too big and growing #6853 "all: binaries too big and growing" is the tracking issue CL 725380 cites ("Update all: binaries too big and growing #6853").
• cmd/compile: surprisingly slow compilation of 100 line file #80271 (backend cost on large functions) and cmd/compile: increased compilation time for a parser package generated with goyacc #77011 (computeLive on a large goyacc function) are the same symptom from different causes; see the paragraph above on why this is distinct.
• runtime: unboundedly expensive equality testing #62488 "runtime: unboundedly expensive equality testing" is the runtime-side analogue of the same type shape.

Impact

Found via https://github.com/gofiber/schema, which declares such a type in a test covering a path-precomputation cap:

• Debian moved their default Go from 1.26 to 1.27; their build daemons then needed 45 GB to build that package against roughly 1 GB before: uses 45GB RAM when being compiled with golang 1.27 gofiber/schema#85. That figure is their report, on linux, not my measurement.
• The project's CI runners were OOM killed on six consecutive runs, with no logs, because the machine died before it could upload them.

Both have been worked around by reducing the nesting depth, so nothing is currently on fire. All timings and RSS figures above are from one darwin/arm64 machine; the generated-code sizes are deterministic and should reproduce anywhere. A linux/amd64 confirmation of the memory figures would be worth having.

Requesting consideration for the Go1.27.1 milestone, since 1.27.0 is the only 1.27 release so far and the fix would be contained.

[gabyhelp]

Related Issues

• cmd/compile: CSE has quadratic running time #77506
• cmd/compile: exponential behavior for deeply nested structs #65540
• runtime: unboundedly expensive equality testing #62488
• cmd/compile: struct equality code optimization #39428 (closed)
• cmd/compile: binaries contain many ..type.eq funcs #38782
• cmd/compile: exponential compile-time with nested generic instantiations #78342
• cmd/compile: prioritize non-CALL struct member comparisons #59409 (closed)

Related Code Changes

• cmd/compile: new inline heuristic for struct compares
• cmd/compile: optimize generated struct/array equality code
• cmd/compile: prioritize non-CALL struct member comparisons

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[randall77]

Interesting pathological case.

The generated functions have a size that is linear in the size of the type itself, so I don't think this is algorithmically incorrect. It's just that the constants are pretty large, and I'm sure the superlinear parts of the compiler (regalloc?) don't help.

I'm not sure exactly what the fix here would be. Maybe we could just give really large types their own bespoke equality function.

I don't think this warrants backporting, unfortunately. It has several pretty easy workarounds. https://go.dev/wiki/MinorReleases . You might need to wait for 1.28.

[prattmic]

cc @golang/compiler

[gopherbot]

Change https://go.dev/cl/828824 mentions this issue: cmd/compile: use subroutines for eq/hash functions of large types