perf: StrawberryShake generator is O(N²) + a hard HC0107 validation wall on large clients

[cliedeman]

StrawberryShake generator: O(N²) code generation + a hard validation wall on large clients

Tracking issue for the StrawberryShake C# generator's performance on large clients, found by profiling a real consumer (ILOPS: 703 operation documents against a 373 KB schema) on graphql-platform main (HC16/SS16). Generating that client is currently impossible on main and takes ~an hour on the pinned strawberryshake.tools 13.9.15.

How it was measured

A standalone harness drives the exact file-based pipeline dotnet graphql generate uses — parse → SchemaHelper.Load → merge-all-ops + validate → DocumentAnalyzer.Analyze → CSharpGenerator.Generate — with per-phase + per-mapper Stopwatch timing, over the 672 "clean" ops (the schema is reused across runs; numbers below are warm, single-file unless noted).

Two sequential walls

Wall 1 — HC0107 field-merge validation budget (analyze stage)

The analyzer merges every operation into one document and runs OverlappingFieldsCanBeMergedRule with a 100,000-comparison budget (ValidationOptions.MaxAllowedFieldMergeComparisons, default 100_000). At ~280–300 of these ops the budget is exhausted and DocumentAnalyzer.Analyze() throws:

HC0107: The field merge validation budget of 100000 comparisons was exhausted. The document is too complex to validate.

So a 672-op client cannot even be analyzed on main — even though every operation passes validation individually. The analyzer path uses default ValidationOptions (OperationDocumentHelper.CreateOperationDocuments → DocumentValidatorBuilder.New().AddDefaultRules() → OverlappingFieldsCanBeMergedRule(o.MaxAllowedFieldMergeComparisons)).

Validated fix: raising MaxAllowedFieldMergeComparisons (to int.MaxValue) clears HC0107 at every size; analyze stays cheap (≤14 s even at 500 ops). This is a small, necessary companion change (make it configurable for codegen, or skip the merged-document OverlappingFieldsCanBeMerged since per-operation validation already guarantees correctness). It is necessary but not sufficient — it just exposes Wall 2.

Wall 2 — CSharpGenerator.Generate is super-quadratic (the real cost)

End-to-end generate time (single file), with the budget raised so larger N can run:

ops	analyze	generate
100	0.5 s	14 s
200	1.6 s	44–53 s
275	3.9 s	~107 s
500	14 s	333 s (5.5 min)
672	(cheap)	>45 min + OOM (~6.6 GB cold)

500→672 (1.34× ops) ≈ 8× generate time. Per-step profile pins the cost (single file):

generate sub-step	N=100	N=275	growth for 2.75× ops
TypeDescriptorMapper	660 ms	4,654 ms	7× (O(N²))
OperationDescriptorMapper	56 ms	731 ms	13×
DataTypeDescriptorMapper	559 ms	18,750 ms	33× (super-quadratic)
run generators	1,829 ms	3,670 ms	2×
format-documents (Roslyn NormalizeWhitespace, single file)	11,079 ms	~79,000 ms	~7× (O(N²))

Child fixes (in-generator, each on its own branch, measured before/after) — ALL DONE, all output byte-identical

• feat(strawberry-shake): persist Razor query components across prerender #1 DataTypeDescriptorMapper super-quadratic → perf(strawberryshake): index data-type components by runtime name #18 (perf/ss-datatype-mapper). context.Types.Single(name-match) linear scan over a list that grows to 33k–48k entries. Fix: one-time Dictionary keyed on RuntimeType.Name (preserves Single's throw semantics). Mapper: 2,804 ms→40 ms @200 (~70×); 11,376 ms→34 ms @275 (~335×) — now flat with N.
• feat(strawberry-shake): persist IOperationResult via [PersistentState] (.NET 10) #2 Single-file formatting → perf(strawberry-shake): format single-file output per namespace #19 (perf/ss-single-file-format). The dominant cost was not NormalizeWhitespace but AddMembers in a loop copying a growing immutable list (O(N²), ~27 s of 40 s @200). Fix: set namespace members once via WithMembers(List(...)) + normalize each namespace subtree independently. generate: 88 s→22 s @200 (~4.1×); 182 s→40 s @275 (~4.6×); OOM eliminated (no client-sized tree built). A per-type variant was rejected (changes output for #if directives).
• fix: Use Operation Interface Type instead of Runtime Type #3 TypeDescriptorMapper O(N²) → perf(strawberry-shake): index type descriptor lookups to remove O(N²) mapping #20 (perf/ss-type-mapper). GetFieldTypeDescriptor looped over every operation + .First(model-match) per field (~cubic). Fix: O(1) dictionaries (by model, by selection-set node, by type name); loop kept as fallback. Mapper: 1,933 ms→454 ms @200 (4.3×); 4,307 ms→435 ms @275 (9.9×) — now flat with N.

All three verified output byte-identical (diffed with-fix vs without-fix; #3 also equivalence-checked all 33,781 field resolutions). They target different stages and compose: the two worst super-linear terms (DataType 33×, formatting AddMembers O(N²)) are now flat/linear. Projected combined generate at N=275 ≈ 107 s → ~20 s, with the scaling curve flattened so the full 672-op client should drop from impractical-or-OOM to a few minutes (pending a combined-branch measurement). The HC0107 budget raise (Wall 1) is still required alongside these to analyze 300+ ops.

Combined run (all 3 fixes + budget raised) — branch perf/ss-combined

The full ILOPS 672-op client now generates end-to-end, single file, errs=0, no OOM:

N	analyze	generate	total
200	1.4 s	16 s	18 s
400	8.8 s	46 s	55 s
672	46 s	157 s	204 s (~3.4 min)

vs stock main (HC0107, can't analyze) and vs budget-raised-only (>45 min + OOM). So the three generator fixes are what turn ">45 min/OOM" into "~3.4 min". The fixes are necessary AND sufficient to make the client buildable, but it is not yet linear — two clear follow-ups remain:

1. analyze is now ~46 s at 672 because, once the budget is uncapped, OverlappingFieldsCanBeMerged runs to completion over the merged doc. The right fix is codegen-scoped: skip (or per-operation-scope) the merged-document field-merge validation rather than just raising the budget — operations don't share response objects, so the cross-operation check is meaningless for codegen, and this reclaims the ~46 s.
2. generate is still super-linear (16 s→157 s for 200→672, ~N^1.9). The three fixes removed the worst offenders; profiling the residual (likely OperationDescriptorMapper, the per-type generators, and/or per-namespace normalize when one namespace holds most types) is the next round.

Notes

• CI "works" only on SS 13.9.15, which predates the HC0107 guard (no Wall 1) — but is still slow (60-min timeout, deletes the 10 largest ops as a workaround).
• Correctness gate for every fix: the generated output must be byte-identical before/after (run CodeGeneration.CSharp.Tests snapshots + diff generated output on the ILOPS sample). These are pure perf changes.
• Separate, consumer-side: the checked-out ILOPS schema.gql is ~5 weeks stale (26 ops reference missing fields, 5 large ops don't parse).

— Claude
🤖 Generated with Claude Code