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 — 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)