engine: optimize the graphical-function Lookup hot path (~4% of the C-LEARN run) #602

Activity

1. bpowers

   added

   enhancementNew feature or requestNew feature or request

   engineIssues with the rust-based simulation engineIssues with the rust-based simulation engine

   on May 21, 2026
2. bpowers commented on Jun 4, 2026

   

   bpowers

   on Jun 4, 2026

   OwnerAuthor

   More actions

   Follow-up idea from VM perf round 2 (2026-06-03): per-GF last-segment memo

   Adding this here rather than as a new issue since it belongs to this issue's "hoist invariant per-table work" / large-table-search scope. (docs/design/engine-performance.md already lists "Lookup last-segment memo (#602)" under its unprioritized run-side swings.)

   Observation. C-LEARN has 161 graphical functions (36,814 points, ~229 avg) that are mostly year-indexed tables evaluated at slowly-advancing TIME (dt = 0.25 against a year-indexed x-axis). Consecutive lookups therefore land in the same x-segment ~75%+ of the time.

   Idea. Keep a per-GF "last segment index" memo — e.g. a Vec<u32> hint in the Vm, one entry per GF id, correctness-independent (a wrong hint just falls back to the full search). On a lookup:

   1. Check whether x still falls in [breakpoints[hint], breakpoints[hint+1]] (and the adjacent segment for the common forward step).
   2. On a hit, interpolate directly and skip the ~8-iteration binary search entirely.
   3. On a miss, run the normal search and update the hint.

   Expected impact. ~780k lookups per C-LEARN run; the lookup path is ~2.2% of the run (after this issue's other suggested optimizations / round-2 measurements). With a ~75%+ same-segment hit rate the memo would eliminate most of the binary-search iterations on the hot path. Bit-preserving — the memo only changes how the segment is located, not the interpolation result.

   Note. This stacks with (and is independent of) the binary-search-vs-linear-scan suggestion already in this issue: the memo short-circuits the search on hits; binary search bounds the cost on misses for large tables.
3. bpowers commented on Jun 4, 2026

   

   bpowers

   on Jun 4, 2026

   OwnerAuthor

   More actions

   Data point: the last-segment memo was implemented, adversarially reviewed, and reverted on branch engine-vm-perf (commits a411b5a / efd7425, reverted in 83f3c60). Measurements on an Apple M-series (Asahi) host against the ~137 ms C-LEARN run:

   • Gross win of the memo alone: ~0.7 ms (0.5%). The ~8-deep binary search over the 229-point tables is already well-predicted at a slowly-advancing TIME index, so there was little to save.
   • Review found the hint diverges from lookup on unsorted-x tables, which are reachable (no import path validates x ordering -- engine: graphical-function tables with unsorted/NaN x-coordinates are accepted silently and produce undefined lookup results #715). Soundness therefore requires a per-table gate.
   • Every sound formulation (sentinel checked inside lookup_with_hint, or hoisted into the dispatch arm) measured a consistent +9..15 ms regression via interleaved worktree A/B: one extra branch + call edge in eval_bytecode's Lookup arm perturbs the giant function's codegen (instructions +1.5%, cycles +6.4%, IPC 4.34 -> 4.13, branch count down).

   Net: 0.5% gross win, ~7% soundness cost on this microarchitecture -- the memo idea is a measured dead end here (recorded in docs/design/engine-performance.md as negative result #2). The remaining ideas on this issue (approx_eq on the hot path, hoisting invariant per-table work) are unaffected by this data; a future attempt on a BTB-limited core (the Ryzen profile) might see different economics, but should budget for the dispatch-arm codegen sensitivity.