capstones — end-to-end investigations

A capstone is the whole skill in one artifact: an unfamiliar codebase, a performance question, evidence gathered with the tools from every track, one change, and proof. Capstone 0 below is worked in full on this machine so you can calibrate what "done" looks like. Capstones 1 and 2 are templates you fill in with public code, on your own time, and can publish.

Rules for every capstone (they are the rules of the whole lab):

• Public or synthetic code only. Nothing derived from employer work.
• Every number comes with the command that produced it and the machine state (tools/pin.sh banner, governor, what else was running).
• The write-up follows the template at the end; the "surprise" line is mandatory.

Capstone 0 (worked): "Why does APInt.cpp take three seconds to compile, and what would make it faster?"

Subject. llvm/lib/Support/APInt.cpp in the local LLVM tree, compiled by the distro clang++ 21.1.8 with the exact Release flags from the compile database (-O3, no -g). Machine: i7-1260P, pinned P-core, powersave, no turbo.

Step 1 — Reproduce one TU outside the build (bigcode/01): ninja -t commands lib/Support/CMakeFiles/LLVMSupport.dir/APInt.cpp.o | tail -1, compiler swapped to /usr/bin/clang++ (the tree was built with g++ via ccache; which clang++ is a ccache wrapper, so the real binary is used). Wall time 2.8–3.1 s, 150 MB RSS, three runs.

Step 2 — Where does the time go, by library (bigcode/04): perf record -F 4000, reading the cpu_core section (11K samples; the 69-sample cpu_atom section is discarded):

Flat profile: top symbol _int_malloc 2.5%, then ScalarEvolution::getRangeRef 1.4%, getAddExpr 1.2%, FoldingSetBase::FindNodeOrInsertPos 1.1%, computeKnownBits 1.0%, Lexer::Lex 0.9%, MachineCopyPropagation 0.8%, SelectionDAGISel::SelectCodeCommon 0.8%, InstCombinerImpl::run 0.8%.

Step 3 — Where does the time go, by work (bigcode/05): -ftime-trace: ExecuteCompiler 3.1 s = Frontend 0.82 s + Backend 2.24 s (Optimizer 1.19 s of which the inliner/CGSCC pipeline 0.74 s; CodeGenPasses 1.05 s). Largest single function in the optimizer: APIntOps::SolveQuadraticEquationWrap 107 ms; then APInt::divide 36 ms, GreatestCommonDivisor 30 ms, sdivrem 25 ms.

Step 4 — Interpretation. The two instruments agree: this TU's compile time is three quarters optimization and code generation of a mathematically heavy file at -O3, with SCEV (loop analysis) and the inliner prominent, and ~8% in the allocator. The front end (0.8 s, 258 headers) is not the lever.

Step 5 — The experiment that would follow (left as the reader's step; the method is what matters): compile the same TU at -O2 and at -O3 -fno-inline-functions, three runs each, and compare wall time and the Backend phase; then check whether the produced code's speed matters for this library (it is APInt: probably yes, so a per-file -O2 would need a benchmark of APInt-heavy passes before being proposed). Report either "keep -O3, the 2.2 s is the price of the code quality" with the benchmark, or "-O2 saves N% at no measured runtime cost".

Surprise. Two convincing wrong answers preceded the right one: a profile of a ccache hit (dynamic loader + zstd), and the E-core PMU section (69 samples) read as if it were the profile, which claimed the front end dominated. The -ftime-trace phase split is what exposed the second mistake.

Capstone 1 (template): a public x86 codebase, profile → fix → prove

Pick something with a build, a benchmark or a reproducible workload, and a hot loop you can reason about. Good sizes: 10k–200k lines. Candidates that are public and neutral: zstd, lz4, xxHash, simdjson's tests, sqlite with a query workload, jq on a large JSON, cJSON, a libpng encode, bzip2.

1. Build topology (bigcode/01): how is it built, with which flags, how do you rebuild one file.
2. Baseline (perf/01, perf/04): a pinned, repeatable workload; min/p50/p99 of the end-to-end time; perf stat cycles and instructions.
3. Locate (perf/02, perf/03): counters → is it branchy, memory-bound, compute-bound? perf record → hot symbol → hot line, through inlining.
4. Explain (cache/, codegen/): what is the line bound by? A dependency chain, a miss pattern, a mispredict, a missing vectorization, a call across a TU?
5. Change one thing: layout, a restrict, a pragma, an algorithmic batch, a flag (-march, LTO, PGO), or a rewrite of the loop. One change per measurement.
6. Prove: same workload, ABAB interleaved, three runs; counters before and after; the assembly diff (tools/asmdiff.sh); correctness checks (tests, checksums).
7. Write it up with the template below; if the change is real, send it upstream as a PR with the numbers.

Capstone 2 (template): NEON vs SVE kernel selection, validated

Using the aarch64 track's toolchain (correctness under qemu at several vector lengths; performance by llvm-mca and, if you have access, real Arm hardware):

1. Take a kernel (dot product, saxpy, a reduction, a small GEMM) in three versions: scalar reference, NEON intrinsics, SVE intrinsics (aarch64/04 shape).
2. Correctness at VL 128/256/512/2048 under qemu with sizes that are not multiples of any VL, against the scalar reference with a tolerance.
3. Codegen: -Rpass=loop-vectorize on the auto-vectorized C version for both targets; compare with the intrinsics versions; llvm-mca -mcpu=neoverse-v1 (SVE 256) and -mcpu=neoverse-n1 (NEON only) throughput per element.
4. Dispatch: an ifunc or function-pointer selection on HWCAP (aarch64/04), plus an override for benchmarking.
5. Decision: a table of predicted cost per element by core and size, the crossover size below which NEON (or scalar) wins, and the sentence "on hardware X we measured …" only if you measured it. Without hardware, say so; the model-based answer with the validation matrix is still a complete deliverable.
6. Extend to SME (aarch64/05) as a stretch: the outer-product tile version of the GEMM, correct at three streaming VLs.

The write-up template

title:      one sentence: what was slow and what you found
subject:    repo, commit, build flags, workload, machine (tools/pin.sh banner)
question:   the performance question in one line
baseline:   min/p50/p99 of the workload; cycles, instructions, IPC
location:   hot symbol -> hot line; the counters that classify it
mechanism:  what the line is bound by, with the lab that taught it
change:     the one change (diff or flag)
proof:      before/after table, ABAB, three runs; counters; asm diff; correctness evidence
residual:   what is still slow and why you stopped
surprise:   the thing you did not expect (mandatory; if there was none, you did not look hard enough)