Optimization catalog

Every performance decision that shipped, in one place: what it is, where it lives, why it’s safe, and the invariant that keeps it valid. If you change code near one of these, the invariant column is the contract you must re-verify. Measured numbers come from benchmarks.md; the decision history is in git (the log was retired 2026-09-02).

The headline numbers live in benchmarks.md and move with each measurement; this catalog carries the decisions and the invariants, not the figures.

Hashing & cache keys

#	What	Where	Why / effect	Invariant to preserve
1	xxHash3 for every cache-key site (was SHA-256)	util/hash.ts, cache/key-fold.ts, orchestrator/task-hash.ts, workspace/fingerprint.ts, workspace/project-loader.ts	~5× faster derivation on the warm path; 16-hex keys match Turbo’s xxh64 width	Not cryptographic — fine for content addressing, never use for auth/integrity vs. an adversary
2	Seed-chained key folding (xxh3(part, prevDigest)) instead of a streaming hasher	cache/key-fold.ts	Bun has no streaming xxh3; chaining avoids concatenating a big key buffer	Every variable-length part must be length-prefixed or \0-delimited so part boundaries stay unambiguous
3	Workspace fingerprint computed once per run, folded into every task key	workspace/fingerprint.ts	One lockfile read/hash instead of N	Must cover every supported lockfile + pnpm-workspace.yaml; fixed file order
4	Config module-cache busting by content hash, not mtime	workspace/project-loader.ts	Same content → Bun module-cache hit; changed content → fresh eval. Hashing a <10 KB config is ~50 µs	The hash must cover the full file bytes; mtime is not reliable (Bun mtimeNs undefined; ms granularity misses rapid edits)
5	Per-run hashCache for repeated file/config hashes	orchestrator/prepare.ts → orchestrator/task-hash.ts	Shared files (presets) hash once per run	Cache is per-run only; nothing may persist across runs without entering the key itself

Input enumeration

#	What	Where	Why / effect	Invariant to preserve
6	git ls-files -s -v + git status --porcelain -uall instead of an FS walk + ignore parsing (ls-files --others --exclude-standard only in the per-project fallback, runGitLsFiles)	cache/git-inputs.ts	Turbo/Nx parity; git’s C-speed ignore handling; correct nested-.gitignore anchoring (fixed a real v13 bug); -s also harvests index OIDs (row 31)	vx hard-requires git — no fallback walker. Absent git → UserError, never silent degradation
7	One workspace-root git snapshot per run, partitioned per project (gitFilesCache, applyGitEnumeration)	cache/git-inputs.ts, invalidated in orchestrator/miss-save.ts and orchestrator/hit-restore.ts	One snapshot’s spawns instead of P; zero re-spawns in src→dist layouts	Staleness rule: after a SAVE and after a RESTORE the exact changed (declared-output) paths are recorded via GitFilesCache.markOutputsChanged; downstream tasks re-spawn git only when their input globs can match a changed path. (The save-path used to DROP the whole entry — replaced 2026-06, −28% cold; a CACHED task writing UNDECLARED files a same-project downstream reads is undeclared behavior — declare your outputs; a task with NO cache block cannot declare any, so its project’s entry, OIDs and package.json digest are dropped once its command exits, item 743)
8	O(P log P) nested-project-boundary computation (sort + contiguous prefix scan; was O(P²))	workspace/nested-dirs.ts	Negligible at 10 projects, real at 1000	Prefix match must include the trailing path.sep so pkg/a is not treated as parent of pkg/ab
34	Per-run memo of inputs.files resolution, keyed by project + declaration (projectFilesCache)	cache/inputs.ts, held in orchestrator/task-hash.ts’s HashCache	Tasks of one project declaring the same inputs and outputs walk the git snapshot once, not once each: this repo’s twelve shard tasks took task hash from 50.6-54.9 ms to 37.1-40.5 ms over 44 tasks (2026-09-20)	Reuse is gated on the snapshot being the SAME ARRAY the entry walked, so a mid-run re-enumeration misses; the key must carry every exclude (own outputs, negations, project boundaries)
35	key() checks input order instead of copying and sorting every call	cache/key-fold.ts	resolveFiles already returns sorted paths, so the common case is one comparison per file instead of n log n: 7.4 ms of a 44-task run over ~3,000 files each (2026-09-20)	An unsorted list must still be sorted — the fold order is what makes a key stable across runs
36	The per-file digests are gathered synchronously when the caller’s OID map covers them	cache/key-fold.ts	A warm task builds no promises for values already in hand: 8.4 ms of that same run	The first gap falls back to the awaited form for the WHOLE list, so a partial map keys exactly as before
37	relPosix memoized per Cache while the workspace root holds	cache/cache.ts:relFor	The same files are re-relativized for every task of a project — 132,000 calls for 3,000 answers on this repo’s gate	The memo clears when a caller arrives with a different root, or one workspace’s names would fold under another’s

Scheduling & graph

#	What	Where	Why / effect	Invariant to preserve
9	O(N + E) scheduler tick: per-node dep counters + ready priority queue (was O(N²) rescan per completion)	graph/scheduler.ts	Tick cost independent of graph size: O(E) counter decrements over the run, one O(log N) heap op per enqueue and per dispatch	Priority contract: higher transitive-reverse-dep count first; ties break in graph-insertion order (the ready heap orders by priority DESC, enqueue-seq ASC)
9b	Bitset transitive-dependent closure in reverse-topo order (was memoized DFS over string Sets)	graph/priorities.ts:computeReverseDepCount	Set closures were O(N²) entries: 8.5 s of a 10 s warm run on a 1090-package / 100-layer repo; bitsets = O(E·N/32), single-digit ms	Counts must stay EXACT (popcount of the closure), not a summed approximation — diamonds double-count under naive summing. With a restore tier, exec-tier counts are exact over the exec tier and a restore’s rank is a sum (item 754)
10	Iterative cycle detection with Uint8Array color array (was recursion + Map)	graph/task-graph.ts:detectCycle	No V8 stack ceiling on deep dependsOn chains; no per-node Map cost	Must still report the cycle path in the error
11	Group tasks execute with zero I/O — hash rolled up from upstream outcomes	orchestrator/task-hash.ts:computeGroupHash	Umbrella tasks (install, ci) cost microseconds	Group hash must fold every upstream id:hash pair, sorted, so it stays order-independent

Cache store

#	What	Where	Why / effect	Invariant to preserve
12	In-process tar pack/read/extract (Bun.Archive in v27, vx’s own streaming tar code since 2026-09-03), + a .vx-meta.json mode/mtime sidecar	cache/archive.ts	Replaced the hand-rolled reader AND the tar subprocess (v27). Pack no longer stages a copy of every output: measured on Cache.save, min-of-5, interleaved against a git worktree of the previous commit — 1 file 6.15 → 0.32 ms, 20 files 11.9 → 0.65 ms, 300 files / 12 MB 158 → 11 ms. Restore is a wash (0.27 / 2.16 ms unchanged). Corrects the earlier entry here claiming Bun.Archive was 15–400× slower for this shape: not true on Bun 1.4	Entry-name validation and destination containment stay vx’s (absolute, .., backslash/drive, symlinked-ancestor walk, symlink-unlink before write); non-regular entries are never surfaced by the reader, so they cannot be materialised at all
13	Restore skip via output_files rows + stat check (isOutputsCurrent)	cache/output-index.ts, orchestrator/hit-restore.ts	Warm-warm hit = N stats, zero writes, zero decompress	Stored size/mode/mtime fingerprint must match what the restore produces (both come from the .vx-meta.json sidecar, at millisecond precision), and the inode + ctime stamp recorded after each save and restore must match — a row with no stamp is never current
14	SQLite metadata index, WAL, busy_timeout = 5000, one handle per run	cache/cache.ts	Indexed lookups; concurrent vx run invocations don’t crash	Entry metadata lives in SQL only (artifacts carry just stdout, outputs/<rel>, workspace-outputs/<rel> and the .vx-meta.json mode/mtime sidecar) — never move entry metadata into the artifact, where it can drift from the rows
15	Atomic artifact publish: unique tmp name → rename (no pre-rm)	cache/cache.ts:writeArtifactAndIndex	Concurrent saves of the same hash are either-or; readers never see partial bytes	POSIX rename replaces atomically; the pre-rm variant reintroduces a delete-after-rename race
16	Single-transaction batch writes: recordRuns, prune deletes (+ parallel artifact rm)	cache/run-history.ts, cache/cache.ts	One fsync instead of N	Prune’s IN-list binding must stay under SQLite’s 999-placeholder limit per statement
17	Artifact = stdout + outputs/<rel> + workspace-outputs/<rel> + .vx-meta.json sidecar; identical bytes local and remote	cache/cache.ts, cache/layered-cache.ts	No stage-dir repack for upload — save re-reads the just-written artifact and PUTs it verbatim; remote hit writes the body straight to disk	Local and remote layers must keep transporting the same byte format; metadata travels out-of-band (SQL row / HTTP headers)
17b	Async remote prefetch: derive stable keys up front, fire remote GETs in the background, overlapping network with execution	orchestrator/remote-prefetch.ts, cache/layered-cache.ts (prefetch + inflight map)	A remote-served warm run no longer pays remote-GET latency on each task’s critical path; the GETs race alongside execution and land in local before execute-task needs them	Remote-only (gated on a remote layer, prepared.hasRemoteLayer; a local-only run takes 17d’s batched local probe instead, never this remote path). Stable-key-only (a task whose inputs could match an upstream output is skipped → lazy read-through; gate shared with 17d via orchestrator/stable-keys.ts). At-most-once per key (prefetch + get share the inflight map; a settled-false miss blocks a second probe). Provenance stays remote (outcome cache-hit-remote) ONLY for genuinely remote-pulled hashes — local-first: a hash local already holds is skipped before the GET (no redundant download on a warm-local run) and stays local. Caller awaits the prefetch pool before cache.close() so no ingest hits a closed DB
17c	Background remote uploads: LayeredCache.save PUTs in the background; run() drains before cache.close()	cache/layered-cache.ts	A task’s outcome (and its dependents) never wait on upload latency; uploads race alongside the rest of the run	Every upload must be drained before the process exits (a short run still ships all artifacts); failures log via onRemoteError, never propagate; the uploaded bytes stay the verbatim local artifact (no repack)
17d	Local short-circuit + two-tier restore-ahead scheduler: up-front stable-key classify + ONE batched local probe (getMany); confirmed hits become a restore tier the scheduler runs ahead of their deps as LOW-priority worker backfill	orchestrator/local-shortcircuit.ts, orchestrator/stable-keys.ts, graph/scheduler.ts	−6.6% on a mixed slow-upstream/warm-downstream workload; parity on all-hit warm runs (probe reuse means zero double work)	Local-only (never with a remote layer, cache.hasRemote — prefetch owns those; an awaited up-front remote GET would sit on the critical path). Probe reuse — execute-task consumes preProbed, exactly one probe per stable task (per-task cache.get only when the layer has no getMany). Misses own the worker pool (execReady drains first). A task whose project dir (or workspace inputs) an outputs.workspaceFiles glob’s static prefix reaches stays out of the restore tier, with every transitive dependant; a glob with no literal prefix reaches every task. Never throws — degrades to the plain schedule
17e	--dry / --graph remote prediction via HEAD existence probe	orchestrator/plan.ts, cache/layered-cache.ts	Planning a remote-warm graph costs headers, not artifact downloads + local ingest	Planning stays side-effect-free on artifact storage: no download, no ingest; a predicted hit-remote = the artifact exists remotely
17f	Pure-SQL cache.get: stdout in the entries row; artifact untouched on probe; accessed_at bumps batch at flush	cache/cache.ts	Hit cost no longer scales with artifact size (118 ms → 5 ms for four ~70 MB binaries); one batched UPDATE instead of per-hit writes	The entries-row stdout and the artifact’s stdout entry must stay identical (the artifact copy is what remote round-trips)

I/O & process

#	What	Where	Why / effect	Invariant to preserve
18	Logger buffers chunks as string[], joins on flush (was += accumulation)	orchestrator/logger.ts	+= was O(N²) over total bytes for chatty tasks	Per-task ordering within a stream must be append-only
19	Memoized Bun.color ANSI lookups	orchestrator/colors.ts	Called thousands of times with a handful of hex strings	Cache key is the color string; gating (NO_COLOR etc.) happens before lookup
20	Bun.Glob for filter matching + recursive listing (was hand-rolled regex / readdir recursion)	workspace/filter.ts, cache/inputs.ts	Native glob engine	Glob semantics are now Bun’s — brace/bracket behavior changes with Bun upgrades
21	Concurrent project discovery (Promise.all over package globs)	workspace/workspace.ts	Was serialized	Dedupe pass after must keep deterministic order
22	AbortSignal.timeout for remote-cache fetches	turboCache(), nxCache() in @vzn/vx-migrate (the wires left core)	Drops the manual controller + setTimeout ceremony	Catch both AbortError and TimeoutError
23	toPosix fast path when path.sep === '/'	util/paths.ts	Skips split/join on the dominant platform	Windows is unsupported anyway; revisit if that changes
24	Hoisted dynamic imports out of per-task paths	orchestrator/execute-task.ts, cache/layered-cache.ts	await import() per task was measurable	—
25	Bun.spawn everywhere (with resourceUsage())	exec/runner.ts	Native spawn + free cpu_ms / peak-RSS capture per child	—
25b	Status-region force-floor coalescing (forced redraws within 30 ms collapse into one trailing draw)	orchestrator/status-line.ts	6,540 forced redraws ≈ 6.7 MB of ANSI on a 3,270-task warm run → ~20 KB	The FINAL state must always land (the trailing draw); the first draw after idle stays immediate

June 2026 scaling pass (1090-package stress repo: 10.2 s → 0.62 s)

#	What	Where	Why / effect	Invariant to preserve
26	Bitset transitive-dependent closure for scheduler priority (was Set-DFS)	graph/priorities.ts:computeReverseDepCount	8.5 s → ms on dense 100-layer graphs; O(E·N/32)	Counts stay EXACT (popcount); own Kahn pass — never trust Map insertion order
27	Bitset package-graph closures, sorted-name indexing (sort-free materialization)	workspace/package-graph.ts	68 ms → ~ms at 1090 projects	Cyclic dep graphs fall back wholesale to legacy DFS
28	Binary-search git-file partitioning (was O(P·F) startsWith)	cache/git-inputs.ts:applyGitEnumeration	54 ms → ~5 ms at 1090×9k	Prefix ranges need the array sorted with the SAME comparator as the search
29	Parallel project discovery; config lookup is one readdir per project on Linux, in-order stats of the candidate names on macOS	workspace/workspace.ts:listProjects	serial I/O → concurrent	Duplicate-name check stays a deterministic sequential pass
30	Frontier ^task expansion (nearest holder per path, sparse bridging kept) — v19	graph/task-graph.ts	8.5× fewer edges on dense graphs; shrinks group-hash sorts, dep sorts, closures, upstream folds at once	Holder’s own dependsOn owns deeper ordering (Turbo parity, documented stop)
31	Git blob OIDs as input-file hashes; dirty files get in-process blob OIDs; three git spawns concurrent (ls-files -s -v, status, var -l), rev-parse memoized, check-attr only where a filter could convert bytes — v20	cache/git-inputs.ts, cache/file-hashes.ts:hashFile	Clean-tree hashing: zero reads/stats/SQLite. 3.2× warm run-phase at 15k files (245→76 ms)	A file’s key contribution must never flip across dirty↔clean (uniform blob-OID domain); symlinks/conflict stages never trusted
32	Early cutoff: downstream keys fold upstream OUTPUT content identity — v21 REVERTED in v22	orchestrator/upstream.ts (now folds the upstream INPUT key)	Removed: pure-input transitive hashing replaced it (owner: “rely only on task input hashes”). Identical-output rebuilds re-run dependents again — rare in practice; see caching.md.	n/a — no output content participates in any cache key in v22
33	Scoped config loading: only in-scope projects + their transitive dep closure evaluate	orchestrator/prepare.ts	1090 config evals (~200 ms) → only the run’s closure; single-task wall 0.32 s → ~0.19 s on the 1090-package repo	Boundary geometry still considers EVERY config-bearing project (loaded or not); a broken out-of-scope config surfacing only when it enters scope is the documented Turbo-like semantic

Known headroom (deliberately not taken yet)

From benchmarks.md and the perf-pass backlog — candidates with a measured or suspected win, parked until profiled:

• Group-task reverse-index for ^build fan-out re-resolution.
• relPosix fast path for ASCII workspace-root prefixes in the enumeration loop.

Two earlier entries here shipped: the batched cache-entry lookup for the all-hits path (#17d, one probe per task from the stable-key classify, 2026-09-02) and the per-run memo of taskConfigHash (#5).

For the record: restores are tar extracts with a stat-check fast path (see #12/#13) — there is no hardlink-based restore, and tar hardlink entries are rejected as a security measure.