fold/docs/internal/perf-audit.md

# fold performance audit (2026-05-23)

## Purpose and scope

fold's `--profile` output rolls per-detector wall-clock into a flat
list. That answered "which detector is slow?" but not "where does
the unaccounted time go?" or "what overhead is self-inflicted?".

This audit captures a baseline on a real codebase (curl), surfaces
the previously-hidden phases, ranks the self-inflicted overhead by
observed cost rather than gut feel, and queues concrete fixes
against the data.

**In scope:**

- Phase-level breakdown of `analyze_ms`.
- Existing cache + shared-state surfaces.
- Multi-walk redundancy (does the same TU/function get visited
  multiple times when one pass would do?).
- Fold-on-fold static findings — does our own code have duplication
  worth refactoring?

**Out of scope:**

- Z3 algorithmic complexity (not ours to optimise).
- Clang's `ASTUnit::create` cost per TU (architectural; mitigations
  listed in the backlog).
- Worker fanout + IPC mechanics beyond timing them.
- Detector precision/recall (separate concern; tracked in
  `docs/research/frontier.md` and `bench/results/`).

## Methodology

- **Target:** curl (`../curl-source/curl/build/compile_commands.json`),
  306 TUs, 2339 functions. Picked because it's the documented bench
  baseline (`bench/run_curl_ab.py`) and fits a single-machine session.
- **Detector set:** `clone,dead,equiv,null-deref` — covers the clone
  hashing phase + the most expensive security detector (null-deref).
- **Mode:** `--profile` forces single-process serial execution
  (`src/cli/scan_router.cpp:244`). All wall-clock numbers below are
  serial; multi-worker reduces wall-clock proportionally for the
  detector phases but not for the parts that already serialise (call-
  graph build, cross-TU priming).
- **Tooling:** `/usr/bin/time -p` for wall-clock; `--profile-output`
  for JSON breakdown; `python3` + `jq`-equivalents for parsing.
- **Baseline artifact:** `docs/internal/perf-audit/baseline-instrumented-2026-05-23.json`.
- **Fold-on-fold artifact:** `docs/internal/perf-audit/fold-on-fold-2026-05-23.json`
  (639 findings); triage in `docs/internal/perf-audit/fold-on-fold.md`.

## Existing caches inventory

Six caches were mapped (Phase-1 exploration). Summary:

| Cache | Scope | Key | Invalidation | Notes |
|---|---|---|---|---|
| `CrossTUCache` | per-scan, process-global | qualified function name → `CalleeProperties` | cleared at shard boundary | Primed by a dedicated walk; rebuilt every scan |
| `SummaryStore` | per-scan, process-global | qualified name → `SymbolicSummary` | transitive on dependent change | In-memory only; no disk persistence |
| `ExprCache` | **per-TU**, process-global | z3 expr hash → check_result | cleared at TU boundary | Aggressive invalidation; solver results don't carry across functions |
| `IncrementalCache` | per-scan, disk-persisted | function (src hash, callee hash) | source/callee hash change | Opt-in via `--incremental`; forces `--processes=1` |
| `ProjectCallGraph` | per-scan, in-memory | def → callees + SCCs | rebuilt every scan | Not persisted |
| `BufferSizeTracker`, `HeapModel` | per-function | per-SymbolicEnv | end of function | Correct lifetime; not a cache problem |

**Note:** subprocess workers don't share any of these — each cold-
starts. That's a clang-binding limitation we can mitigate but not
eliminate.

## Empirical baseline

From `docs/internal/perf-audit/baseline-instrumented-2026-05-23.json`:

```
total_wall_ms:                455,756 (7.6 min)
compile_db_load_ms:                 2
fanout_orchestration_ms:            0   (profile mode → serial)
serial_dispatch_ms:           455,682
parse_ms:                           0
analyze_ms:                   455,685
report_ms:                         71

detector wall_ms breakdown:
  null-deref                  297,955  (65.4% of total)
  dead                          8,750  ( 1.9%)
  equiv                         2,240  ( 0.5%)
  clone                           216  ( 0.05%)
  -------------------------------------
  sum                         309,161  (67.8%)

  serial_dispatch_ms - sum    146,521  (32.2%)
```

Two findings jump out:

1. **null-deref dominates: 65% of total wall.** With ~3s of actual
   Z3 query time (from `[solver-profile]` z3_time_ms aggregate), the
   other ~297s is in the encoder / state-merging / walker.
2. **~32% (146s) was previously unaccounted.** New instrumentation
   localizes it to `serial_dispatch_ms` minus detector wall — i.e.,
   inside `runDetectorsOnShard` but outside any detector handler.
   That bucket contains: clang ASTUnit construction per TU (~1.0s ×
   306 ≈ 306s of CPU, but clang parses are roughly 0.5s wall each
   on this hardware → ~150s wall, matches), cross-TU priming
   (~1 full extra AST walk per TU), call-graph collection, function
   fingerprinting.

## Self-inflicted-overhead findings (ranked by observed cost)

### 1. clang ASTUnit constructed once per TU, never shared

**Observed cost:** ~150s of the 455s baseline (33%). Dominant
contributor to `serial_dispatch_ms - sum(detector.wall_ms)`.

**Where:** `src/frontend/clang_backend.cpp:144`. Each TU spawns a
fresh `clang::tooling::ClangTool::run()`. Worker subprocesses
amplify this: each worker re-parses every TU it owns from cold.

**Remediation sketch:**

- Short-term: emit precompiled headers (PCH) for project headers
  used by every TU; clang accepts `-include-pch` per invocation.
- Medium-term: persistent worker that holds an LRU of recently-
  parsed ASTUnits keyed by TU + clang flags hash; new commands
  reach it over a Unix socket. Requires a daemon model that fold
  doesn't have today.
- Long-term: explore clang's `ASTReader` snapshot format if it
  becomes usable for our access patterns.

**Estimated payoff:** 30–50% wall-clock reduction on warm runs.
The exact number depends on PCH coverage of fold's clang include
graph.

### 2. null-deref encoder + walker traversal: 5 min CPU per curl scan

**Observed cost:** ~287s of detector wall, ~99% outside Z3.

**Where:** `src/detect/null_deref.cpp` + `src/symbolic/encoder.cpp`
+ the security walker's path enumeration.

**Phase breakdown (final — `baseline-hooks-2026-05-23.json`):**

```
null-deref wall_ms:       344,644
  walker_ms:              340,329   (98.8% of wall — almost all in walk/walkCFG)
  encode_ms:               24,156   (7.1% of walker — NOT the target)
  hook_ms:                 11,860   (3.5% of walker — NOT the target)
  state_merge_ms:              75   (0.02% of walker — NOT the target)
  walker - the above:     304,238   (89.4% of walker — the actual cost)
```

Aggregate z3_time_ms across the entire scan: ~33ms (<0.01% of total).

**Four wrong hypotheses, four pivots:**

1. Hash-walk fusion (original plan): 0.04% of total.
2. State-merge optimization: 0.02% of null-deref walker.
3. Encoder optimization: 7% of null-deref walker.
4. Hook body optimization: 3.5% of null-deref walker.

The 304s that remains after subtracting all four was originally
hypothesised as "per-stmt bookkeeping that fires for every
statement." A second-round decomposition (Backlog #2) added four
timers — `cfg_build_ms`, `nonnull_precompute_ms`, `control_walk_ms`,
`stmt_overhead_ms` — and revised that hypothesis with measurement.

**Final decomposition (curl null-deref baseline):**

| Phase | ms | % of walker_ms |
|---|---|---|
| `control_walk_ms` (walkIf + walkSwitch + walkFor + walkWhile + walkDo) | 254,102 | 85.3% |
| `encode_ms` | 4,614 | 1.5% |
| `hook_ms` | 2,808 | 0.9% |
| `stmt_overhead_ms` (snapshot-delta remainder) | 287 | 0.1% |
| `state_merge_ms` / `cfg_build_ms` / `nonnull_precompute_ms` | 0 | 0% |
| `walker_ms` total | 297,749 | 100% |

The 89% bucket is **recursive control-flow body walks**, not
per-stmt bookkeeping. Each `walkIf` clones envs, recursively walks
each arm, and merges; `walkFor`/`walkWhile` unroll; the recursion
re-enters the per-block loop. Most source code lives inside
control structures, so most analysis time naturally falls there.

Caveat on double-counting: `control_walk_ms` covers the full wall
of the recursive walks, including the nested `encode_ms`/`hook_ms`
slices fired inside them. The 254s double-counts ≈7s of inner
encode+hook; net ≈247s is the recursive walking machinery itself
(env clone, refine ranges, body walk, merge).

A separate hypothesis — "env clones in walkIf dominate
`control_walk_ms`" — was added and refuted by direct measurement:
`env_clone_ms` totals 0 across 770,748 clones (under 1 µs each,
since `z3::expr` refcount bumps and 11 `unordered_map` shallow
copies amortize to nothing).

**Remediation candidates for the 89%:**

1. Bound `walkForStmt`/`walkWhileStmt` unroll cost — large loops
   multiply the recursion factor.
2. Cache `refineRangesForCondition` / `refineOctagonForCondition`
   results across re-entries of the same branch.

Neither will eliminate the bucket. The cost is symbolic execution
proportional to (statements × control-nesting depth). Meaningful
wall reduction requires changing the *semantic model* (lower
precision, deeper bounded unroll cap, branch pruning, AST+env
memoization) — design tradeoffs around precision vs speed, not
optimizations of a single hot loop. Those belong in a separate
proposal, not a perf-audit follow-up.

**Older notes (kept for context):** the pre-decomposition guesses
  walked per statement to find DeclRef writes; the result is used
  to invalidate octagon entries.
- **`getParentMapContext()` / parent-map queries** — clang's parent
  lookup, allocated lazily but consulted frequently.
- **`buildNonNullAtBlockEntry`** — pre-pass that walks the entire
  CFG to compute per-block non-null facts; runs at the start of
  every walkCFG.
- **`BranchLivenessBuilder` + `WriteCollector`** — ancillary
  per-function RecursiveASTVisitor passes (~4× per function).
- **`liveAtJoin(is)`** — live-set computation per if-statement.

**Remediation targets (ranked by likely payoff):**

1. **Cache `collectWrittenVars` per statement** — **landed.**
   Memoizes a deterministic per-stmt result by `Stmt*` pointer; 5
   call sites previously re-walked the same subtree (octagon
   invalidation in walk() / walkCFG() main loops, BFS in
   `buildNonNullAtBlockEntry`'s `writtenIn` lambda, loop-inc in
   `unrollLoop`). Architecturally sound; perf delta within
   run-to-run variance on a single curl scan (see "On measurement
   discipline").
2. **Consolidate the 6 non-null-marking maps into one.** Each
   stmt currently consults/updates several; merging them into a
   single accumulator removes 5× the hash-lookup overhead.
3. **Skip `refineRanges` / `refineOctagon` when no IfStmt is in
   the immediate continuation.** Today they fire unconditionally.
4. **Lazy `buildNonNullAtBlockEntry`** — only run when a detector
   actually queries non-null facts. Currently runs for every
   function.

Beyond these four, the next round needs profiling-grade
flame-graph data (perf, samply, Instruments) — phase-level
instrumentation isolated the 304s to the walker but can't
subdivide further without adding O(stmts) timers that would
themselves perturb the measurement.

## On measurement discipline

Cross-baseline data from this session shows ~15% run-to-run
variance on the same curl invocation:

```
baseline (no timers):              465s
baseline (+compile-db timers):     455s
baseline (+walker/merge):          454s
baseline (+encode timer):          442s
baseline (+hook timer):            533s   ← anomalously slow run
after writtenvars cache:           451s
```

The baseline-hooks run is an outlier (likely system load or the
~millions of hook RAII timers compounding). After-cache lands at
451s, statistically indistinguishable from the 442–465s spread of
the earlier baselines. **Single-run measurements at this
resolution don't reliably attribute small wins.**

**Use `bench/perf_audit_run.py`** for any future perf claim
≤15%. It runs fold N times against a fixed compile DB and
reports median + IQR + min/max for every `--profile` metric:

```
bench/perf_audit_run.py --label baseline --runs 5
# ... apply change ...
bench/perf_audit_run.py --label after-fix --runs 5 \
    --diff docs/internal/perf-audit/runs/baseline.json
```

The `--diff` output flags moves outside 1.5×IQR as "significant".
For high-confidence claims (sub-5%), bump `--runs 10+` and
quiesce the machine (close browsers etc.) during the window.

Other tactics worth knowing about:

- Pin CPU frequency where the OS allows (macOS: hard; Linux:
  `cpupower frequency-set`).
- Use `samply` or `Instruments` for absolute line-level
  attribution; reserve `--profile` JSON diff for monitoring
  large regressions only.

The instrumentation that landed in this audit survives this
variance — it's about *relative* attribution within one run, not
absolute wall-time deltas across runs.

### 3. Cross-TU priming = one extra full AST walk per TU

**Observed cost:** baked into the 146s unaccounted bucket; not
isolated yet.

**Where:** `src/cli/scan_runner.cpp:1109-1115`. Before detector
dispatch, every TU is walked once to populate `CrossTUCache` with
"this function dereferences param 2", "this function returns null
sometimes", etc. The cache lives one scan and dies.

**Remediation sketch:** persist `CrossTUCache` to disk like
`IncrementalCache`. Cache key: (qualified name, body hash). Reuse
across runs unless the body changed.

**Estimated payoff:** the priming pass takes roughly 1× the
detector AST-walk cost, so eliminating it on warm scans saves
~30–60s on curl. Needs measurement.

### 4. `--incremental` is mutually exclusive with `--processes >1`

**Observed cost:** users pick speed (parallel) OR freshness
(incremental); never both.

**Where:** `src/cli/scan_router.cpp:210-212`. The incremental
implementation runs serially because the parent-side fingerprint
map can't be sharded today.

**Remediation sketch:** sharded fingerprint files per worker;
parent merges at completion. Already partially modelled by
SubprocessFanout's NDJSON merge.

**Estimated payoff:** for users on big repos who re-scan
frequently (CI runs, IDE), the speedup multiplies — incremental
already skips most functions; pairing with fanout gives near-zero
warm-scan times.

### 5. ExprCache lifetime is per-TU instead of per-scan

**Observed cost:** unmeasured but bounded by Z3 query time (~3s
across the whole scan, per `[solver-profile]` z3_time_ms summed).
Small absolute payoff today but rises with detector heaviness.

**Where:** `src/cli/scan_runner.cpp:1511`. ExprCache is cleared at
each TU boundary. Same arithmetic expression queried in TU A and
TU B re-solves from scratch.

**Remediation sketch:** extend lifetime to per-scan, with the
canonical expression hash as the key. Risk: if two different
expressions canonicalise to the same hash (collision), we'd
return the wrong cached result. Audit the hash function for
non-collision properties before changing lifetime.

**Estimated payoff:** small on curl (Z3 is already cheap here);
larger on z3-heavy targets (loops, complex bit manipulation).

### 6. Security-detector path fans out to 7 walks when ≤1 is enabled

**Observed cost:** zero today (the audit baseline runs >1, so the
composite path activates).

**Where:** `src/cli/scan_runner.cpp:1890-1995` —
`use_composite_security_walk` only flips on when
`enabledSecurityDetectorCount() > 1`. If a user runs `--detectors
null-deref` alone, we fall back to 7 independent walks.

**Remediation sketch:** drop the fallback; always use the
composite walker even for single-detector runs. The composite
walker handles the single-detector case correctly already.

**Estimated payoff:** negligible for default runs; clean-up for
single-detector debugging paths.

### Lower-priority items

| Item | Where | Estimated payoff |
|---|---|---|
| Dup CFG-build elimination (dead-statement + security walker build same CFG) | `src/detect/dead_statement.cpp:66` + `src/ir/cfg_walker.cpp:21` | small (CFG build ≪ encoder) |
| 5 hash/tokenize walks per function in clone phase | `src/frontend/ast_visitor.cpp:174-180` | ~170 ms on curl (clone is 0.05% of total) |
| Suppressions/baseline reparsed every command | `src/report/triage.cpp:73-90` | trivial |

The hash-walk fusion was the *plan's* highest-leverage target before
the baseline. Empirically it's ~0.04% of total — keep it on the
backlog for cleanliness, not perf.

## Fold-on-fold findings (summary)

Full triage in `docs/internal/perf-audit/fold-on-fold.md`. Top patterns
worth refactoring:

- **`mixHash` 5+ copies** across security-detector anonymous
  namespaces. Lift to a shared helper.
- **`supportsParam` / `collectConjuncts`** repeated across detectors.
  Move to a `src/symbolic/z3_helpers.{hpp,cpp}` sibling of the
  existing `z3_model_support`.
- **`onFunctionEnd` boilerplate** across the 5 security observers.
  Default implementation in a base class.
- **`ir::*::valid` / `operator bool` / `operator==`** boilerplate
  for `Call`, `MemberRef`, `Symbol`, `Expr`. CRTP or macro.

The fold-on-fold pass also surfaced 152 dead-statement findings;
most are cache-layer short-circuits where a guard later in the
function makes an early-return provably unreachable. Some are
encoder bails that are intentionally defensive. Triage requires
file-by-file review; the JSON is the full record.

**Notable absence:** equiv detector emitted zero findings. That's
honest progress — the prior scout-rule extractions (encoder_arms,
clang_type_queries, callee names) moved colliding helpers out of
the per-detector files. The remaining duplication is in small
helpers that don't reach equiv's signature-match threshold.

## Phase-1 result: instrumentation, not the planned hash fusion

The original plan committed to fusing the 5 hash/tokenize walks
into one pass as the "highest-leverage" fix. Empirically that
target is 0.04% of total. **Plan pivot:** ship the
instrumentation (3 new ScanProfile fields:
`compile_db_load_ms`, `fanout_orchestration_ms`,
`serial_dispatch_ms`) so subsequent rounds have phase-level data
instead of a flat per-detector list. Commit: `503799a`.

Result: the 146s previously-unaccounted bucket is now named
(`serial_dispatch_ms - sum(detector.wall_ms)`) and the next
optimisation round can target it specifically.

## Phase-2 backlog (ranked by estimated payoff, after measurement)

For Z3 and Clang library-expansion opportunities (separate axis
from this backlog), see
[`library-expansion-matrix.md`](library-expansion-matrix.md) —
20 scored rows with file-cited insertion sites and a
recommended top-3 sequence.

The first two items below shipped in the same round as the
audit. They are kept on the list because each surfaced a
measurement worth recording.

1. **Persist CrossTUCache across scans — SHIPPED, ~8s wall (~2%).**
   v2 reaches 100% hit rate and exact finding-count parity
   (7112==7112 on curl null-deref). The audit's 30–60s estimate
   was inflated 3–6×; actual priming cost on curl is ~9s and v2
   saves essentially all of it. Treat the cache as a correctness
   invariant for incremental scans + small wall win + infrastructure
   for future caching. Design + measurement:
   `docs/internal/perf-audit/cross-tu-cache-persistence.md`.
2. **Per-phase null-deref decomposition — SHIPPED, identified 89%
   bucket.** Four new timers (`cfg_build_ms`,
   `nonnull_precompute_ms`, `control_walk_ms`, `stmt_overhead_ms`)
   resolve the previously-unattributed null-deref walker time.
   The 89% turned out to be `control_walk_ms` (recursive control-
   flow body walks), not per-stmt bookkeeping. See the null-deref
   section above for the full breakdown.
3. **`--incremental` + `--processes >1` compatibility.** Requires
   sharded fingerprint files.
4. **ExprCache lifetime extension to per-scan** (with collision
   audit).
5. **Always-on composite security walker** (drop the ≤1 fallback).
   Attempted as a ~115-line cleanup (delete the 7
   `if (!use_composite && detectorEnabled(...))` blocks, force the
   composite path). Build + 47/47 tests stayed green, but the
   curl A/B at the standard `--budget-seconds 5` showed up to ~1.5%
   finding drift across runs against the same code, indistinguishable
   from the ~0.8% run-to-run noise observed between back-to-back
   identical reruns. Reverted pending a longer-budget parity check
   (60s/TU, ~30 min per leg) that can separate semantic drift from
   budget-truncation noise.
6. **Dup CFG-build elimination** (small).
7. **Hash-walk fusion** (cleanliness, ~170ms).
8. **Fold-on-fold refactor: `mixHash`, `supportsParam`,
   `onFunctionEnd`, `ir::*` boilerplate.** Cleanliness.
9. **PCH for project headers** — measured ceiling ~0.3% wall.
   Keep on the list for documentation but do not invest design
   effort until the 89% bookkeeping bucket is decomposed and proven
   not to dominate.

## Regression prevention

Recommended addition to `bench/run_curl_ab.py`: capture the new
phase timings (`compile_db_load_ms`, `fanout_orchestration_ms`,
`serial_dispatch_ms`) alongside per-detector wall_ms. Diff the
JSON against `docs/internal/perf-audit/baseline-instrumented-2026-05-23.json`
on each release; alert on >10% regression in any phase.

The bench harness already parses `--profile` JSON; only the field
list needs extending.

## Pointers

- Baseline JSON: `docs/internal/perf-audit/baseline-instrumented-2026-05-23.json`
- Fold-on-fold JSON: `docs/internal/perf-audit/fold-on-fold-2026-05-23.json`
- Fold-on-fold triage: `docs/internal/perf-audit/fold-on-fold.md`
- Instrumentation commit: `503799a`
- Fold-on-fold commit: (this series)
- Audit commit (this doc): (HEAD)