|
|
1
|
+# Investigating a hot GHC compiler function (perf + profiled_ghc)
|
|
|
2
|
+
|
|
|
3
|
+A recipe for: *"Investigate function `xyz` in GHC using this guide."* Run everything
|
|
|
4
|
+from `~/ghc/work-trees/cgwork-perf-aggregate`. Background and worked examples are in
|
|
|
5
|
+`FINDINGS.md`; this is the operational short form.
|
|
|
6
|
+
|
|
|
7
|
+## The framing: two axes
|
|
|
8
|
+
|
|
|
9
|
+Every hot function is attacked on exactly two levers. Decide which one(s) apply
|
|
|
10
|
+before proposing anything:
|
|
|
11
|
+
|
|
|
12
|
+- **(A) make the body cheaper** — boxing, a missing fast path, a lazy accumulator,
|
|
|
13
|
+ redundant re-allocation. Checked by *reading the generated Core*.
|
|
|
14
|
+- **(B) fix the callers** — the function is already optimal but its callers use it
|
|
|
15
|
+ wastefully. This is usually the bigger lever, and it has three depths, from
|
|
|
16
|
+ shallowest to deepest:
|
|
|
17
|
+ 1. *Call it fewer times* — memoise, hoist out of a loop, deduplicate.
|
|
|
18
|
+ 2. *Call it on smaller/cheaper data* — the caller passes more, or bigger, than the
|
|
|
19
|
+ result actually depends on.
|
|
|
20
|
+ 3. **Question the requirement** — walk the (transitive) hot callers and ask what
|
|
|
21
|
+ each one *actually needs* from the call. Often the caller over-asks: it forces a
|
|
|
22
|
+ whole structure when a shallow check suffices, materialises and orders a list it
|
|
|
23
|
+ only folds over, or compares full types when a cheap predicate would do. If the
|
|
|
24
|
+ caller's real need can be met another way, the hot function isn't called less —
|
|
|
25
|
+ it isn't called at all. (This is where the largest wins in this suite live, e.g.
|
|
|
26
|
+ `RoughMap.lookupRM'` materialising a full element list it only filters.)
|
|
|
27
|
+
|
|
|
28
|
+A third, cross-cutting axis falls out of the data: **entries vs. allocation are
|
|
|
29
|
+decoupled**. The highest-*entry* functions (`seqType`, `eq_type_*`, `coVarsOfType`)
|
|
|
30
|
+allocate **0 B** — pure walks, only (B) helps. The highest-*allocation* functions
|
|
|
31
|
+are list/map *materialisation* (`Word64Map.elems1` = 11.2 GB), often invisible in a
|
|
|
32
|
+cachegrind Ir profile because a cons is Ir-cheap. Always look at both numbers.
|
|
|
33
|
+
|
|
|
34
|
+## Build & data sources (all at commit `3b2a9409ba`)
|
|
|
35
|
+
|
|
|
36
|
+| What | Where |
|
|
|
37
|
+|---|---|
|
|
|
38
|
+| Profiled (late-CCS) GHC | `~/ghc/prof-late/_build/stage1/bin/ghc` (`perf+profiled_ghc`, `-fprof-late`) |
|
|
|
39
|
+| Ticky GHC | `~/ghc/ticky/_build/stage1/bin/ghc` (`perf+ticky_ghc+no_profiled_libs`) |
|
|
|
40
|
+| Plain perf GHC (Ir + Core) | `~/ghc/head0/_build/stage1/bin/ghc` |
|
|
|
41
|
+| **Generated Core** of the compiler | `~/ghc/head0/_build/stage1/compiler/build/compiler/<Module/Path>.dump-simpl` |
|
|
|
42
|
+| Suite-wide cachegrind Ir ranking | `cg-out/aggregate.md` (which functions are hot suite-wide, SCALES vs startup) |
|
|
|
43
|
+| Late-CCS caller profiles (all 82 tests) | `prof-out/<TEST>.prof` (JSON cost-centre stack tree) |
|
|
|
44
|
+| Ticky entry+alloc profiles | `ticky-out/<TEST>.ticky` (all 82 tests) |
|
|
|
45
|
+| Per-test command table | `cg_batch.py` `TESTS` (drives every runner) |
|
|
|
46
|
+
|
|
|
47
|
+`-fprof-late` inserts cost centres *after* optimisation, so attribution is on the
|
|
|
48
|
+real optimised program; `+RTS -V0` turns off the time sampler but **entries and
|
|
|
49
|
+alloc stay exact** and match ticky to the digit.
|
|
|
50
|
+
|
|
|
51
|
+## Procedure
|
|
|
52
|
+
|
|
|
53
|
+1. **Locate the function & its driver test.** Find where `xyz` is hottest:
|
|
|
54
|
+ - `grep` it in `cg-out/aggregate.md` for its suite rank, % of suite Ir, and the
|
|
|
55
|
+ `SCALES`/`startup` flag (startup = fixed per-invocation cost, usually not worth
|
|
|
56
|
+ chasing).
|
|
|
57
|
+ - Pick the test that *drives* it. The driver map at the end of `FINDINGS.md`
|
|
|
58
|
+ covers the known top functions; otherwise scan ticky/prof across tests:
|
|
|
59
|
+ `python3 ticky_top.py xyz` (aggregated) or `python3 prof_callers.py xyz --file <T>`
|
|
|
60
|
+ across a few candidate tests to see which test entry-count is largest.
|
|
|
61
|
+
|
|
|
62
|
+2. **Get the two definition-site numbers (entries & alloc).** Ticky, keyed to the
|
|
|
63
|
+ real definition site even through thunks:
|
|
|
64
|
+ ```
|
|
|
65
|
+ python3 ticky_top.py xyz --file <TEST> # entries + Alloc + Alloc'd
|
|
|
66
|
+ python3 ticky_top.py --alloc --file <TEST> # what this test allocates most
|
|
|
67
|
+ ```
|
|
|
68
|
+ (`ticky-out/` is complete; `python3 ticky_run.py <TEST> --force` to regenerate.)
|
|
|
69
|
+ High entries + 0 alloc ⇒ pure walk ⇒ (B) only. High alloc ⇒ ask *what structure
|
|
|
70
|
+ is being built* (list, env, map) and whether it must be.
|
|
|
71
|
+
|
|
|
72
|
+3. **Read the Core for axis (A).** Open the defining module's `*.dump-simpl` under
|
|
|
73
|
+ `~/ghc/head0/.../compiler/build/compiler/` and read the worker (`$w…`). Look for:
|
|
|
74
|
+ boxing of an `Int#`/`Word#`, a `foldr (:) []` that materialises a list, a
|
|
|
75
|
+ re-`cons`ing `map` (`strictMap`), a missing `reallyUnsafePtrEquality#` short
|
|
|
76
|
+ circuit, an accumulator that isn't strict. Also check the *call site*: is this
|
|
|
77
|
+ small function passed polymorphically into a higher-order combinator (e.g. a
|
|
|
78
|
+ comparator into `actualSort`) rather than inlined/specialized into it? — see the
|
|
|
79
|
+ "small functions in fixed combinations" pattern below. If the body is a tight
|
|
|
80
|
+ unboxed traversal with a fast path already present, declare (A) done and move to (B).
|
|
|
81
|
+
|
|
|
82
|
+4. **Caller attribution for axis (B)** — the late-CCS profile, which pierces laziness
|
|
|
83
|
+ (the *logical* source caller, not the `stg_ap_*` thunk that forced it):
|
|
|
84
|
+ ```
|
|
|
85
|
+ python3 prof_callers.py xyz --file <TEST> # external callers by entries
|
|
|
86
|
+ python3 prof_callers.py xyz --file <TEST> --by alloc # ... by inherited alloc
|
|
|
87
|
+ python3 prof_callers.py --file <TEST> --top 20 # flat top compiler ccs (context)
|
|
|
88
|
+ ```
|
|
|
89
|
+ This names *who* drives the entries/alloc and how concentrated it is (one caller
|
|
|
90
|
+ at 99 % vs. broad fan-out across many). That concentration decides the fix.
|
|
|
91
|
+
|
|
|
92
|
+ Then **don't stop at the immediate caller — interrogate it.** Climb the hot callers
|
|
|
93
|
+ (rerun `prof_callers.py` on the dominant caller itself, and read its source) and for
|
|
|
94
|
+ each ask: *what does this caller actually need from `xyz`?* Does it consume the whole
|
|
|
95
|
+ result or one field; the ordered list or just a fold/membership test; a deep
|
|
|
96
|
+ comparison or a shallow one? Where the caller over-asks, the fix lives there, not in
|
|
|
97
|
+ `xyz` — the deepest (B) win is replacing the call with one that matches the real
|
|
|
98
|
+ requirement (or removing it).
|
|
|
99
|
+
|
|
|
100
|
+## What "performance opportunities" to look for
|
|
|
101
|
+
|
|
|
102
|
+The patterns below are the ones that have actually recurred in this suite — a
|
|
|
103
|
+**checklist of priors, not a closed taxonomy.** Use them to recognise the common
|
|
|
104
|
+cases fast, but stay open-minded: the goal is the cheapest correct way to meet the
|
|
|
105
|
+caller's real requirement, and the biggest wins are often *structural* and specific
|
|
|
106
|
+to this function — they won't have a name on this list. Let the data (entries, alloc,
|
|
|
107
|
+Core, caller stacks) lead; if what you find doesn't fit any pattern here, that's a
|
|
|
108
|
+finding, not a dead end — describe the mechanism in its own terms and propose the fix.
|
|
|
109
|
+If it's a clean new pattern, say so so it can be added.
|
|
|
110
|
+
|
|
|
111
|
+Common patterns (each seen in this suite):
|
|
|
112
|
+
|
|
|
113
|
+- **List/map materialisation** — a deterministic fold that builds and orders an
|
|
|
114
|
+ element list (`Word64Map.elems1` ← `RoughMap.lookupRM'`, 11.2 GB). Lever: stream /
|
|
|
115
|
+ fold without materialising, or avoid the ordering.
|
|
|
116
|
+- **Env building by repeated single insertion** — `Word64Map.$winsert` from
|
|
|
117
|
+ `extendVarSet`/`extendNameEnv` one element at a time. Lever: bulk/`fromList`
|
|
|
118
|
+ construction, or a cheaper structure.
|
|
|
119
|
+- **Pure structural re-walks** — `seqType`, `eq_type_expand_ignore`, `coVarsOfType`:
|
|
|
120
|
+ 0-alloc, body optimal, but entered 10²–10⁸×. Lever: cache/memoise the result, hoist
|
|
|
121
|
+ the walk out of a loop, or avoid forcing/comparing whole types when a cheaper
|
|
|
122
|
+ predicate suffices. Watch for **fanout** (T8095: 251k top-level compares → 187M node
|
|
|
123
|
+ compares) — the win is upstream, in the caller that triggers the fanout.
|
|
|
124
|
+- **Price of determinism** — `$fFoldableUniqDFM2` is a `sortBy` for deterministic
|
|
|
125
|
+ UniqDFM folds. Lever: does this fold need to be deterministic/ordered here?
|
|
|
126
|
+- **Small functions in fixed combinations — specialize the combination.** When a tiny
|
|
|
127
|
+ hot function always appears in the *same pipeline*, check whether it is passed/called
|
|
|
128
|
+ *polymorphically through a runtime argument* rather than inlined into its partner.
|
|
|
129
|
+ Tell-tale in the Core: a higher-order callee applied to a function value (and in
|
|
|
130
|
+ ticky/profile the inner function shows up as its own millions of entries via
|
|
|
131
|
+ `stg_ap_*`). E.g. `eltsUDFM` compiles to `map taggedFst (actualSort
|
|
|
132
|
+ ($fFoldableUniqDFM2) (elems1 m))` — `actualSort` takes the comparator as an argument,
|
|
|
133
|
+ so all 200M compares are indirect calls on a boxed path instead of inlined unboxed
|
|
|
134
|
+ `Int#` compares. Lever: a monomorphic/specialized variant of the combinator (or a
|
|
|
135
|
+ static-argument-transform lifting the function out of the recursion) turns the
|
|
|
136
|
+ indirect calls into direct, often unboxed, ones. This is a **constant-factor (A)**
|
|
|
137
|
+ win (it does not change the call count), but it is cheap and pays off precisely for
|
|
|
138
|
+ the small functions that recur in fixed combinations across the suite. Note what
|
|
|
139
|
+ fusion can and cannot do here: a `sortBy`/`foldl'`-style barrier in the middle of the
|
|
|
140
|
+ pipeline blocks fusion of the intermediate list, and fusion never reduces a
|
|
|
141
|
+ comparison/iteration *count* — so reach for specialization, not fusion, when the cost
|
|
|
142
|
+ is CPU in a fixed combination rather than intermediate allocation.
|
|
|
143
|
+- **Laziness leak / missing strictness** — thunks build up in an accumulator or a
|
|
|
144
|
+ lazy field (`foldl` where `foldl'` is meant, a lazy pair/state threaded through a
|
|
|
145
|
+ loop, a non-strict record field). Tell-tale: ticky shows large `Alloc'd` in
|
|
|
146
|
+ `THUNK`/`sat_s…` closures, or far more closures allocated than the producer's entry
|
|
|
147
|
+ count. Lever: strict accumulator (`foldl'`, bang), `!`-fields + `{-# UNPACK #-}`,
|
|
|
148
|
+ force intermediate state. (Conversely a space leak from *over*-sharing — a big thunk
|
|
|
149
|
+ retained — shows as live-heap growth, not alloc.)
|
|
|
150
|
+- **Boxing / worker–wrapper / CPR** — a hot function returns or threads a boxed
|
|
|
151
|
+ `Int`/`Word`/tuple, reboxes at a join point, or a strict field isn't unpacked.
|
|
|
152
|
+ Tell-tale in Core: an `I#`/`W64#` built then immediately `case`d; a `$w` worker that
|
|
|
153
|
+ still allocates a box; a boxed result the caller unboxes. Lever: let worker/wrapper +
|
|
|
154
|
+ CPR fire — strict fields, `{-# UNPACK #-}`, monomorphise, avoid polymorphism that
|
|
|
155
|
+ forces boxing.
|
|
|
156
|
+- **Dictionary passing / un-specialized overloading** — an overloaded function
|
|
|
157
|
+ (`Ord`/`Eq`/`Foldable`/`Outputable`…) called at a fixed type in a hot loop but not
|
|
|
158
|
+ specialized, so class methods are indirect dictionary calls. Tell-tale in Core:
|
|
|
159
|
+ `$dOrd`/`$fEq…` dictionary arguments threaded through the loop; class methods reached
|
|
|
160
|
+ via `stg_ap`. Lever: `{-# SPECIALIZE #-}` / `{-# INLINABLE #-}` at the definition,
|
|
|
161
|
+ `-fexpose-all-unfoldings` so cross-module specialization can fire. (Distinct from
|
|
|
162
|
+ passing a *known function* above; this is about class dictionaries.)
|
|
|
163
|
+- **Wrong structure / quadratic blow-up** — a list where a set/map is needed
|
|
|
164
|
+ (`elem`/`nub`/`lookup` inside a loop → O(n²)), repeated `++`/`concat`, or
|
|
|
165
|
+ **lookup-then-insert** done as two traversals (`member` then `insert`). Tell-tale:
|
|
|
166
|
+ entry counts that grow *super-linearly* with input size across tests (cross-check the
|
|
|
167
|
+ `SCALES` flag and per-test totals in `cg-out/aggregate.md`); a `lookup` and `insert`
|
|
|
168
|
+ on the same map co-resident. Lever: the right structure (`Set`/`IntMap`), a single
|
|
|
169
|
+ pass (`insertWith`/`alterF`), difference lists / accumulators for append.
|
|
|
170
|
+- **Redundant recomputation (no sharing)** — the same non-trivial value (a free-var
|
|
|
171
|
+ set, a kind, a `tcView`/`coreView` result) recomputed at each use instead of being
|
|
|
172
|
+ `let`-bound or cached in the structure. Tell-tale: a pure function with high entries
|
|
|
173
|
+ whose argument is structurally identical across those calls. Lever: hoist/`let`-bind,
|
|
|
174
|
+ compute once and thread, or memoise in the data type.
|
|
|
175
|
+- **Cross-cutting allocators** — `strictMap`, the iface Alex lexer (`$walexGetByte`).
|
|
|
176
|
+ Broad, no single caller; flag as systemic rather than point-fixable.
|
|
|
177
|
+
|
|
|
178
|
+Output: state the rank/%, the driver test, the entries & alloc, the (A) verdict from
|
|
|
179
|
+Core, the dominant caller(s) from the late-CCS profile, and a concrete (A) and/or (B)
|
|
|
180
|
+lever — with the concentration that justifies it.
|
|
|
181
|
+
|
|
|
182
|
+## Pitfalls (don't repeat these)
|
|
|
183
|
+
|
|
|
184
|
+- **Don't trust callgrind inclusive cost** for GHC's recursive workers (it prints
|
|
|
185
|
+ 45,000 %+); and on the shipped `.so`, `addr2line`/nearest-symbol guesses are wrong
|
|
|
186
|
+ (it named a span `Data.OldList.permutations`, which the compiler never calls). Use
|
|
|
187
|
+ self-Ir + exact call counts, or prefer ticky/late-CCS, which key to the real site.
|
|
|
188
|
+- **Co-residence ≠ causation.** Two hot functions appearing together does not mean one
|
|
|
189
|
+ calls the other (callgrind-era guesses "seqType ← zonk+tidy" and "elems1 ← solver
|
|
|
190
|
+ folds" were both wrong; the truth was Simplifier and `RoughMap.lookupRM'`). Confirm
|
|
|
191
|
+ callers with the late-CCS stack, not by what's nearby in the ranking.
|
|
|
192
|
+- **A trivial single-module profile overweights startup.** Use `cg-out/aggregate.md`'s
|
|
|
193
|
+ SCALES flag to tell pay-per-invocation startup from work that scales. |