Simon Jakobi pushed to branch wip/sjakobi/cgwork-perf-aggregate at Glasgow Haskell Compiler / GHC
Commits:
7afb38df by Simon Jakobi at 2026-06-30T00:54:17+02:00
cgwork perf-aggregate: agent guide for investigating a hot function
A short operational recipe so an agent can be pointed at a single hot
compiler function and work it through the (A) cheaper-body / (B) call-it-less
axes using the existing perf+profiled_ghc tooling: build/data sources, a
4-step procedure (locate + driver test, ticky entries/alloc, Core for (A),
late-CCS caller attribution for (B)), the recurring opportunity patterns, and
the trust pitfalls distilled from FINDINGS.md.
Assisted-by: Claude Opus 4.8
- - - - -
2ed3e335 by Simon Jakobi at 2026-06-30T01:02:43+02:00
cgwork perf-aggregate: ticky now covers all 82 tests in the guide
The ticky sweep is complete, so ticky-out is a first-class suite-wide
dataset rather than a regenerate-on-demand fallback. Update the data-source
table and step 2 accordingly.
Assisted-by: Claude Opus 4.8
- - - - -
8c7af844 by Simon Jakobi at 2026-06-30T01:09:32+02:00
cgwork perf-aggregate: sharpen axis (B) — interrogate caller requirements
(B) was framed as "call it less", which understates the real lever: a hot
function is often cheap but used wastefully by its callers. Reframe (B) around
fixing the callers in three depths, the deepest being to walk the transitive
hot callers and question what each actually needs — the cheapest call is the
one the caller didn't require. Push step 4 from naming the immediate caller to
climbing and interrogating it.
Assisted-by: Claude Opus 4.8
- - - - -
443a8f5d by Simon Jakobi at 2026-06-30T01:30:19+02:00
cgwork perf-aggregate: add specialization-of-fixed-combinations lever
Small hot functions that recur in a fixed pipeline are often passed
polymorphically into a higher-order combinator (e.g. the UniqDFM comparator
into actualSort) instead of inlined/specialized, turning every call into an
indirect boxed one. Add this as an opportunity pattern with the tell-tale Core
signature, note it is a constant-factor (A) win distinct from fusion, and wire
a check into the Core-reading step.
Assisted-by: Claude Opus 4.8
- - - - -
9d148bde by Simon Jakobi at 2026-06-30T01:46:42+02:00
cgwork perf-aggregate: add the classic codegen/laziness opportunity patterns
The catalogue leaned toward allocation/data-structure patterns; add the
standard compiler-perf checks: laziness leaks / missing strictness, boxing &
worker-wrapper/CPR, dictionary passing / un-specialized overloading, wrong
structure & quadratic blow-up, and redundant recomputation. Each with its
tell-tale (ticky Alloc'd, Core signature, or super-linear scaling in the cg
aggregate) and lever.
Assisted-by: Claude Opus 4.8
- - - - -
d18e6482 by Simon Jakobi at 2026-06-30T01:53:46+02:00
cgwork perf-aggregate: frame the opportunity list as priors, not a closed taxonomy
Assisted-by: Claude Opus 4.8
- - - - -
4997934f by Simon Jakobi at 2026-06-30T02:19:28+02:00
cgwork perf-aggregate: resolve coVarsOfType(s) attribution to occAnal
Late-CCS profile pins ~6.5% of suite Ir (coVarsOfType1/coVarsOfTypes1)
on occAnal (Type ty) computing free CoVars for deadness tracking — a
0-alloc deep walk that returns empty on coercion-free types. Link the
investigation TODO with the (B) levers.
Assisted-by: Claude Opus 4.8
- - - - -
2 changed files:
- FINDINGS.md
- + investigate-hot-function.md
Changes:
=====================================
FINDINGS.md
=====================================
@@ -102,6 +102,13 @@ deliverable.
functions being `tidyType`, `$wzonkTyVarOcc` → forcing/tidying/FV-scanning whole
types during **zonk + tidy**. Source-level attribution here needs the profiled
build (laziness).
+- **`coVarsOfType(s)` (~6.5 %) is resolved**: the late-CCS profile pins 99 % of
+ `coVarsOfType1`'s external entries on `$woccAnal` — i.e. `occAnal (Type ty)`
+ (`OccurAnal:2583`) computing free CoVars of *every* `Type` argument for CoVar
+ deadness. The walk is 0-alloc and the result is ~always ∅ (T16577's types are
+ coercion-free), so it's a pure wasted deep traversal redone each occanal pass.
+ Investigation + (B) levers (short-circuit/memoise coercion-free types):
+ [[occanal-covarsoftype-coercion-free-walk]] in `~/ghc/todos`.
### Type-keyed maps & equality (Core.Map.Type, eq_type)
=====================================
investigate-hot-function.md
=====================================
@@ -0,0 +1,193 @@
+# Investigating a hot GHC compiler function (perf + profiled_ghc)
+
+A recipe for: *"Investigate function `xyz` in GHC using this guide."* Run everything
+from `~/ghc/work-trees/cgwork-perf-aggregate`. Background and worked examples are in
+`FINDINGS.md`; this is the operational short form.
+
+## The framing: two axes
+
+Every hot function is attacked on exactly two levers. Decide which one(s) apply
+before proposing anything:
+
+- **(A) make the body cheaper** — boxing, a missing fast path, a lazy accumulator,
+ redundant re-allocation. Checked by *reading the generated Core*.
+- **(B) fix the callers** — the function is already optimal but its callers use it
+ wastefully. This is usually the bigger lever, and it has three depths, from
+ shallowest to deepest:
+ 1. *Call it fewer times* — memoise, hoist out of a loop, deduplicate.
+ 2. *Call it on smaller/cheaper data* — the caller passes more, or bigger, than the
+ result actually depends on.
+ 3. **Question the requirement** — walk the (transitive) hot callers and ask what
+ each one *actually needs* from the call. Often the caller over-asks: it forces a
+ whole structure when a shallow check suffices, materialises and orders a list it
+ only folds over, or compares full types when a cheap predicate would do. If the
+ caller's real need can be met another way, the hot function isn't called less —
+ it isn't called at all. (This is where the largest wins in this suite live, e.g.
+ `RoughMap.lookupRM'` materialising a full element list it only filters.)
+
+A third, cross-cutting axis falls out of the data: **entries vs. allocation are
+decoupled**. The highest-*entry* functions (`seqType`, `eq_type_*`, `coVarsOfType`)
+allocate **0 B** — pure walks, only (B) helps. The highest-*allocation* functions
+are list/map *materialisation* (`Word64Map.elems1` = 11.2 GB), often invisible in a
+cachegrind Ir profile because a cons is Ir-cheap. Always look at both numbers.
+
+## Build & data sources (all at commit `3b2a9409ba`)
+
+| What | Where |
+|---|---|
+| Profiled (late-CCS) GHC | `~/ghc/prof-late/_build/stage1/bin/ghc` (`perf+profiled_ghc`, `-fprof-late`) |
+| Ticky GHC | `~/ghc/ticky/_build/stage1/bin/ghc` (`perf+ticky_ghc+no_profiled_libs`) |
+| Plain perf GHC (Ir + Core) | `~/ghc/head0/_build/stage1/bin/ghc` |
+| **Generated Core** of the compiler | `~/ghc/head0/_build/stage1/compiler/build/compiler/.dump-simpl` |
+| Suite-wide cachegrind Ir ranking | `cg-out/aggregate.md` (which functions are hot suite-wide, SCALES vs startup) |
+| Late-CCS caller profiles (all 82 tests) | `prof-out/<TEST>.prof` (JSON cost-centre stack tree) |
+| Ticky entry+alloc profiles | `ticky-out/<TEST>.ticky` (all 82 tests) |
+| Per-test command table | `cg_batch.py` `TESTS` (drives every runner) |
+
+`-fprof-late` inserts cost centres *after* optimisation, so attribution is on the
+real optimised program; `+RTS -V0` turns off the time sampler but **entries and
+alloc stay exact** and match ticky to the digit.
+
+## Procedure
+
+1. **Locate the function & its driver test.** Find where `xyz` is hottest:
+ - `grep` it in `cg-out/aggregate.md` for its suite rank, % of suite Ir, and the
+ `SCALES`/`startup` flag (startup = fixed per-invocation cost, usually not worth
+ chasing).
+ - Pick the test that *drives* it. The driver map at the end of `FINDINGS.md`
+ covers the known top functions; otherwise scan ticky/prof across tests:
+ `python3 ticky_top.py xyz` (aggregated) or `python3 prof_callers.py xyz --file <T>`
+ across a few candidate tests to see which test entry-count is largest.
+
+2. **Get the two definition-site numbers (entries & alloc).** Ticky, keyed to the
+ real definition site even through thunks:
+ ```
+ python3 ticky_top.py xyz --file <TEST> # entries + Alloc + Alloc'd
+ python3 ticky_top.py --alloc --file <TEST> # what this test allocates most
+ ```
+ (`ticky-out/` is complete; `python3 ticky_run.py <TEST> --force` to regenerate.)
+ High entries + 0 alloc ⇒ pure walk ⇒ (B) only. High alloc ⇒ ask *what structure
+ is being built* (list, env, map) and whether it must be.
+
+3. **Read the Core for axis (A).** Open the defining module's `*.dump-simpl` under
+ `~/ghc/head0/.../compiler/build/compiler/` and read the worker (`$w…`). Look for:
+ boxing of an `Int#`/`Word#`, a `foldr (:) []` that materialises a list, a
+ re-`cons`ing `map` (`strictMap`), a missing `reallyUnsafePtrEquality#` short
+ circuit, an accumulator that isn't strict. Also check the *call site*: is this
+ small function passed polymorphically into a higher-order combinator (e.g. a
+ comparator into `actualSort`) rather than inlined/specialized into it? — see the
+ "small functions in fixed combinations" pattern below. If the body is a tight
+ unboxed traversal with a fast path already present, declare (A) done and move to (B).
+
+4. **Caller attribution for axis (B)** — the late-CCS profile, which pierces laziness
+ (the *logical* source caller, not the `stg_ap_*` thunk that forced it):
+ ```
+ python3 prof_callers.py xyz --file <TEST> # external callers by entries
+ python3 prof_callers.py xyz --file <TEST> --by alloc # ... by inherited alloc
+ python3 prof_callers.py --file <TEST> --top 20 # flat top compiler ccs (context)
+ ```
+ This names *who* drives the entries/alloc and how concentrated it is (one caller
+ at 99 % vs. broad fan-out across many). That concentration decides the fix.
+
+ Then **don't stop at the immediate caller — interrogate it.** Climb the hot callers
+ (rerun `prof_callers.py` on the dominant caller itself, and read its source) and for
+ each ask: *what does this caller actually need from `xyz`?* Does it consume the whole
+ result or one field; the ordered list or just a fold/membership test; a deep
+ comparison or a shallow one? Where the caller over-asks, the fix lives there, not in
+ `xyz` — the deepest (B) win is replacing the call with one that matches the real
+ requirement (or removing it).
+
+## What "performance opportunities" to look for
+
+The patterns below are the ones that have actually recurred in this suite — a
+**checklist of priors, not a closed taxonomy.** Use them to recognise the common
+cases fast, but stay open-minded: the goal is the cheapest correct way to meet the
+caller's real requirement, and the biggest wins are often *structural* and specific
+to this function — they won't have a name on this list. Let the data (entries, alloc,
+Core, caller stacks) lead; if what you find doesn't fit any pattern here, that's a
+finding, not a dead end — describe the mechanism in its own terms and propose the fix.
+If it's a clean new pattern, say so so it can be added.
+
+Common patterns (each seen in this suite):
+
+- **List/map materialisation** — a deterministic fold that builds and orders an
+ element list (`Word64Map.elems1` ← `RoughMap.lookupRM'`, 11.2 GB). Lever: stream /
+ fold without materialising, or avoid the ordering.
+- **Env building by repeated single insertion** — `Word64Map.$winsert` from
+ `extendVarSet`/`extendNameEnv` one element at a time. Lever: bulk/`fromList`
+ construction, or a cheaper structure.
+- **Pure structural re-walks** — `seqType`, `eq_type_expand_ignore`, `coVarsOfType`:
+ 0-alloc, body optimal, but entered 10²–10⁸×. Lever: cache/memoise the result, hoist
+ the walk out of a loop, or avoid forcing/comparing whole types when a cheaper
+ predicate suffices. Watch for **fanout** (T8095: 251k top-level compares → 187M node
+ compares) — the win is upstream, in the caller that triggers the fanout.
+- **Price of determinism** — `$fFoldableUniqDFM2` is a `sortBy` for deterministic
+ UniqDFM folds. Lever: does this fold need to be deterministic/ordered here?
+- **Small functions in fixed combinations — specialize the combination.** When a tiny
+ hot function always appears in the *same pipeline*, check whether it is passed/called
+ *polymorphically through a runtime argument* rather than inlined into its partner.
+ Tell-tale in the Core: a higher-order callee applied to a function value (and in
+ ticky/profile the inner function shows up as its own millions of entries via
+ `stg_ap_*`). E.g. `eltsUDFM` compiles to `map taggedFst (actualSort
+ ($fFoldableUniqDFM2) (elems1 m))` — `actualSort` takes the comparator as an argument,
+ so all 200M compares are indirect calls on a boxed path instead of inlined unboxed
+ `Int#` compares. Lever: a monomorphic/specialized variant of the combinator (or a
+ static-argument-transform lifting the function out of the recursion) turns the
+ indirect calls into direct, often unboxed, ones. This is a **constant-factor (A)**
+ win (it does not change the call count), but it is cheap and pays off precisely for
+ the small functions that recur in fixed combinations across the suite. Note what
+ fusion can and cannot do here: a `sortBy`/`foldl'`-style barrier in the middle of the
+ pipeline blocks fusion of the intermediate list, and fusion never reduces a
+ comparison/iteration *count* — so reach for specialization, not fusion, when the cost
+ is CPU in a fixed combination rather than intermediate allocation.
+- **Laziness leak / missing strictness** — thunks build up in an accumulator or a
+ lazy field (`foldl` where `foldl'` is meant, a lazy pair/state threaded through a
+ loop, a non-strict record field). Tell-tale: ticky shows large `Alloc'd` in
+ `THUNK`/`sat_s…` closures, or far more closures allocated than the producer's entry
+ count. Lever: strict accumulator (`foldl'`, bang), `!`-fields + `{-# UNPACK #-}`,
+ force intermediate state. (Conversely a space leak from *over*-sharing — a big thunk
+ retained — shows as live-heap growth, not alloc.)
+- **Boxing / worker–wrapper / CPR** — a hot function returns or threads a boxed
+ `Int`/`Word`/tuple, reboxes at a join point, or a strict field isn't unpacked.
+ Tell-tale in Core: an `I#`/`W64#` built then immediately `case`d; a `$w` worker that
+ still allocates a box; a boxed result the caller unboxes. Lever: let worker/wrapper +
+ CPR fire — strict fields, `{-# UNPACK #-}`, monomorphise, avoid polymorphism that
+ forces boxing.
+- **Dictionary passing / un-specialized overloading** — an overloaded function
+ (`Ord`/`Eq`/`Foldable`/`Outputable`…) called at a fixed type in a hot loop but not
+ specialized, so class methods are indirect dictionary calls. Tell-tale in Core:
+ `$dOrd`/`$fEq…` dictionary arguments threaded through the loop; class methods reached
+ via `stg_ap`. Lever: `{-# SPECIALIZE #-}` / `{-# INLINABLE #-}` at the definition,
+ `-fexpose-all-unfoldings` so cross-module specialization can fire. (Distinct from
+ passing a *known function* above; this is about class dictionaries.)
+- **Wrong structure / quadratic blow-up** — a list where a set/map is needed
+ (`elem`/`nub`/`lookup` inside a loop → O(n²)), repeated `++`/`concat`, or
+ **lookup-then-insert** done as two traversals (`member` then `insert`). Tell-tale:
+ entry counts that grow *super-linearly* with input size across tests (cross-check the
+ `SCALES` flag and per-test totals in `cg-out/aggregate.md`); a `lookup` and `insert`
+ on the same map co-resident. Lever: the right structure (`Set`/`IntMap`), a single
+ pass (`insertWith`/`alterF`), difference lists / accumulators for append.
+- **Redundant recomputation (no sharing)** — the same non-trivial value (a free-var
+ set, a kind, a `tcView`/`coreView` result) recomputed at each use instead of being
+ `let`-bound or cached in the structure. Tell-tale: a pure function with high entries
+ whose argument is structurally identical across those calls. Lever: hoist/`let`-bind,
+ compute once and thread, or memoise in the data type.
+- **Cross-cutting allocators** — `strictMap`, the iface Alex lexer (`$walexGetByte`).
+ Broad, no single caller; flag as systemic rather than point-fixable.
+
+Output: state the rank/%, the driver test, the entries & alloc, the (A) verdict from
+Core, the dominant caller(s) from the late-CCS profile, and a concrete (A) and/or (B)
+lever — with the concentration that justifies it.
+
+## Pitfalls (don't repeat these)
+
+- **Don't trust callgrind inclusive cost** for GHC's recursive workers (it prints
+ 45,000 %+); and on the shipped `.so`, `addr2line`/nearest-symbol guesses are wrong
+ (it named a span `Data.OldList.permutations`, which the compiler never calls). Use
+ self-Ir + exact call counts, or prefer ticky/late-CCS, which key to the real site.
+- **Co-residence ≠ causation.** Two hot functions appearing together does not mean one
+ calls the other (callgrind-era guesses "seqType ← zonk+tidy" and "elems1 ← solver
+ folds" were both wrong; the truth was Simplifier and `RoughMap.lookupRM'`). Confirm
+ callers with the late-CCS stack, not by what's nearby in the ranking.
+- **A trivial single-module profile overweights startup.** Use `cg-out/aggregate.md`'s
+ SCALES flag to tell pay-per-invocation startup from work that scales.
View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/compare/66e89f03e7264b2a0bb17f55df5af2b...
--
View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/compare/66e89f03e7264b2a0bb17f55df5af2b...
You're receiving this email because of your account on gitlab.haskell.org.
