Concurrent Demand + Prefetch Retention

Item 10d: item 10c produced two null results, both correctly explained, and both explanations pointed at a specific experiment that was not run. This item runs them. Nothing from item 10c is retracted — T-6's dedup_fetching=14494 still stands as proof the async handler works; this item makes that result measurable on the benchmark arms rather than only in the correctness harness. Full background: CLAUDE.md's "ITEM 10c" and "ITEM 10d" notes, docs/design-history.md Amendments A-8/A-9.

VERDICT

Task A's driver verification gate passed on all three checks (reference trace, total bytes, OPT — all identical at --driver-threads 1 vs 8). Device-busy did not rise with driver threads under either handler mode (async included) — a genuine negative result, traced to the barrier structure the driver's own correctness requirement mandates, not a defect in the async architecture. Prefetch hit rate rose under --prefetch-retention pinned relative to none at every one of 12 directly-compared cells, and clearly exceeded item 10b's original 14-27% ceiling in 2 of 6 (ratio, depth) cells — a real, partial, disclosed improvement, not a clean win.

Machine exclusivity

Before Sweep B: free -h 7.0 GiB available, load average 0.14-0.23, no foreign workload (pgrep -f "cn-spike|gate5r_driver|iperf3" clean, ps aux --sort=-%cpu showed only routine systemd/WSL services).

After Sweep B: load average 1.08 (transient, from the sweep itself having just finished — no unrecognized process in ps aux), 6.9 GiB free, swap untouched.

Before Sweep C: clean (free -h 6.9-7.0 GiB available, ps aux clean).

After Sweep C: load average 1.90 (again transient, consistent with the sweep's own just-finished CPU usage), no foreign process, 6.9-7.0 GiB free throughout, swap untouched.

No contamination was found or needed remediation in this item (unlike item 10c, which caught and redid one updatedb.plocate-contaminated cell). Both sweeps (72 + 36 runs) completed within a single background-task invocation each — neither hit the harness's 10-minute background-task cap that forced resumptions in item 10c.

Task A — Multi-threaded driver

Implementation. --driver-threads N (default 1 → the original, unmodified replay_cyclic(), byte-for-byte). N>1 uses the new replay_cyclic_mt(): N threads collectively execute the SAME reference sequence as N=1, partitioned WITHIN each chunk's page range (thread t reads every N-th page starting at page t) — never across chunks — with a pthread_barrier_t at every chunk boundary so all N threads finish chunk i before any of them starts chunk i+1. Models parallel compute over one layer, then advancing together, matching how llama.cpp's multi-threaded matmul actually behaves. The reference trace is still emitted once per (pass, chunk) by a single coordinating thread (tid 0), in the same order as N=1. Also wired in Task C's pager_notify_access() "consumed" signal (see below), once per (pass, chunk) by tid 0, identically to the single-threaded driver — this doesn't affect the identity gate below, since it only touches internal pin/retention bookkeeping, never the elision-guard sink, byte counts, or the reference trace.

Verification gate (--driver-threads 1 vs 8, identical parameters — 2 GiB region, 128 MiB chunks, 5 passes, budget ratio 0.5):

Check	N=1	N=8	Result
Reference trace (seq, chunk_id, fault_type, was_prefetched per record — `timestamp_ns` excluded, see note)	80 records	80 records	IDENTICAL, 0 mismatches
`pager_bytes_fetched`	6,979,321,856	6,979,321,856	IDENTICAL
`absent_handled`	52	52	IDENTICAL
`evictions`	44	44	IDENTICAL
`bytes_touched`	10,737,418,240	10,737,418,240	IDENTICAL
OPT `minimum_misses`	48	48	IDENTICAL
OPT `minimum_bytes_fetched`	6,442,450,944	6,442,450,944	IDENTICAL

PASS on all three required checks (trace identity, byte identity, OPT identity). Note on "byte-identical": trace_record_t carries a real wall-clock timestamp_ns (clock_gettime(CLOCK_MONOTONIC)), which cannot be literally identical across two separate process invocations regardless of threading — even two N=1 runs would differ there. belady_main itself never reads that field (only chunk_id), so "byte-identical" is verified here as "identical in every field that determines the reference sequence and the OPT bound" (seq, chunk_id, fault_type, was_prefetched), explicitly excluding the unavoidably non-deterministic timestamp — a disclosed interpretation, not a silently loosened one.

Confirmed via objdump on replay.o (-O2 -g -pthread, same flags as the Makefile) that the multi-threaded read loop is not compiler-elided: the disassembly of replay_thread_main shows a real stride loop (add $0x1000,%rsi) and a lock add %rax,0x0(%rip) instruction for the atomic accumulation into the shared elision-guard sink — g_replay_sink is written by up to N threads concurrently in the multi-threaded path, so the implementation uses __sync_fetch_and_add there rather than the plain += the single-threaded path uses (which would be a genuine data race under real concurrency).

Incidental confirmation of I-8's dedup path firing under genuine cross-thread contention on a single chunk: dedup_fetching rose from 0 at N=1 to 298 at N=8 on the same gate run (dedup_resident 0→29) — expected and explained in Task B below, not a surprise.

Task B — Sync vs async under concurrency

Arm D (layer_order, prefetch off — the only concurrency present is genuine demand from the driver itself), V2 parameters (2 GiB region, 128 MiB chunks, 5 passes), 3 budget ratios × n=3 × --driver-threads {1,2,4,8} × handler {--sync-handler, async --fetch-workers 4} — 72 runs. Raw data: results/data/historical/task-d-sweep-b.csv; full log: experiments/logs/task_d_sweep_b_log.txt. Device-busy fraction via --fetch-trace and the union-of-read-intervals method (item 10b/10c's method, unchanged); median dispatch latency (entry to enqueue) via the two new --fetch-trace fields (t_dispatch_entry_ns/t_dispatch_enqueue_ns) added this item, populated by the dispatcher (handle_absent_dispatch()) and consumed by whichever worker picks the job up.

`stat_dedup_fetching` (median of n=3)

Ratio	Threads	async
0.25	1	0
0.25	2	66
0.25	4	201
0.25	8	428
0.50	1	0
0.50	2	54
0.50	4	170
0.50	8	341
0.75	1	0
0.75	2	39
0.75	4	118
0.75	8	266

Device-busy fraction (median of n=3)

Ratio	Threads	sync	async
0.25	1	0.816	0.811
0.25	2	0.818	0.818
0.25	4	0.816	0.817
0.25	8	0.812	0.808
0.50	1	0.835	0.831
0.50	2	0.836	0.833
0.50	4	0.835	0.828
0.50	8	0.823	0.822
0.75	1	0.847	0.846
0.75	2	0.851	0.859
0.75	4	0.857	0.848
0.75	8	0.844	0.864

Median dispatch latency, entry to enqueue (async only; sync has no

separate dispatch phase to measure)

Ratio	Threads	µs
0.25	1	16.8
0.25	2	14.6
0.25	4	14.2
0.25	8	17.9
0.50	1	16.0
0.50	2	13.8
0.50	4	13.0
0.50	8	14.3
0.75	1	16.2
0.75	2	14.4
0.75	4	13.5
0.75	8	15.2

Wall-clock (median of n=3, seconds) and `read_bytes`

read_bytes (pager_bytes_fetched) is exactly identical across all 24 cells at each ratio — 9,261,023,232 / 7,650,410,496 / 5,502,926,848 at r=0.25/0.5/0.75 respectively, no exceptions. Wall-clock at 8 threads: sync=4.421s async=4.434s (r=0.25); sync=3.701s async=3.646s (r=0.5); sync=2.685s async=3.144s (r=0.75).

Expectations 1-5

stat_dedup_fetching is 0 at --driver-threads 1 in both handler modes, rises with thread count under async, stays 0 under sync at every thread count: HELD. Exactly as the table above shows, at every ratio.
Device-busy under sync stays pinned near 0.83 regardless of driver threads: HELD. 0.808-0.864 across the whole grid, flat within normal noise (same 0.82-0.86 band item 10b/10c already established).
Device-busy under async rises with driver threads: DID NOT HOLD. Async's device-busy fraction (0.808-0.864) is statistically indistinguishable from sync's at every matching (ratio, threads) cell — reported plainly as the negative result the spec required, with the mechanism traced rather than left as a bare observation: Task A's barrier requirement (all N driver threads work on the SAME chunk simultaneously, then advance together) means more driver threads create more concurrent demand for that ONE chunk — visible directly as stat_dedup_fetching rising with N in the table above — but never concurrent demand for DIFFERENT chunks. Device-busy fraction measures whether the fetch path ever has more than one chunk's I/O outstanding at once to overlap; on arm D under this driver, there is structurally never more than one chunk's fetch in flight regardless of --driver-threads, so extra fetch workers still have nothing to overlap with — the same root cause item 10c's Sweep 1 found for the single-threaded driver, now shown to persist even under a driver that generates real, measurable cross-thread contention (dedup_fetching proves the contention is real), because that contention lands on the SAME chunk by construction. The async handler's throughput benefit is not visible on this arm at any driver-thread count; it remains visible where genuine cross-chunk concurrent demand exists (T-3/T-6/T-7's non-barrier-synchronized storms, and arm E's prefetch-driven overlap, Sweep C below).
Wall-clock under async at 8 threads is lower than under sync at 8 threads, at every ratio: DID NOT HOLD. True only at r=0.5 (3.646s<3.701s); false at r=0.25 (4.434s>4.421s, +0.3%) and r=0.75 (3.144s>2.685s, +17%). Consistent with expectation 3's finding: with no extra I/O overlap to gain on this arm, async's per-fetch dispatch hop (median 13-18µs, table above) is a small added cost rather than a throughput win here.
read_bytes identical across all cells at a given ratio: HELD, with zero exceptions — the correctness check the spec flagged as a stop-and-report trigger if violated. It was not violated.

Task C — Prefetch retention

Implementation. budget.c gained prefetch_retain_on_resident() (pins a prefetch target's existing fetch-time pin in place and pushes it onto a bounded FIFO, capacity prefetch_depth, evicting-and-unpinning the oldest entry first if the cap would be exceeded), prefetch_retain_release() (removes a chunk from the FIFO and releases its pin — the "consumed" trigger), and pin_break_select_victim() (picks the coldest pinned target by policy->next_use_distance, falling back to FIFO-oldest). pager.h gained pager_notify_access(), called once per (pass, chunk) reference by both replay_cyclic() and replay_cyclic_mt() right before the read, regardless of hit/miss — the only way to observe "consumed" given a touch on an already-resident chunk generates no uffd event at all (the same observability gap disclosed since item 8). ensure_budget()'s eviction loop — demand fetches only, never ensure_budget_prefetch() — now breaks the coldest pinned target's pin instead of going infeasible when select_victim() finds nothing, counted in the new stat_pin_broken. --prefetch-retention {none,pinned}, default pinned.

Found and fixed a third latent unlocked-pin race while touching this exact code (after item 10c's two): prefetch_pool.c's do_one_prefetch() had THREE bare target->pin++/target->pin-- operations with no lock at all (the pre-fetch pin, the infeasible-abandon unpin, and the post-fetch unpin). Harmless at item 10b's original scale (a genuine data race that had never been observed to matter), a real hazard once multiple prefetch workers run concurrently (item 10c). Fixed using the existing unpin_chunk() helper and a new symmetric pin_chunk() helper, both under budget_lock — the same pattern items 10b/10c already established for this class of bug.

Correctness gate: T-1..T-7 re-run with --eager-reconcile, all existing test binaries picking up the new pinned default automatically (no test file needed changes, same pattern as items 10b/10c). All PASS. T-3's infeasible counter (27314) looked alarming in isolation but is statistically unchanged from the pre-Task-C baseline (27036, same test, prior commit 4c3ee84) — confirmed by checking git history before concluding anything, not assumed. The large count is a pre-existing property of ensure_budget()'s bounded 200×2ms retry loop under this specific tight 2-chunk-budget 8-thread storm, not a regression introduced by retention. T-6 (dedup_fetching=14307) and T-7 (all 8 threads joined well within the 120s watchdog, 0 mismatches) both PASS even with prefetch_depth defaulting to 1 — meaning up to half of T-3/T-6/T-7's 2-chunk budget can be permanently retained at once — a genuine, meaningful stress test of the pin-break override under real contention, not merely a smoke test that happened not to exercise it.

Sweep. Arm E, --prefetch-retention {none, pinned} × 3 ratios × --prefetch-depth {2,4} × n=3, async handler, --fetch-workers 4, --driver-threads 8 — 36 runs. Raw data: results/data/historical/task-d-sweep-c.csv; full log: experiments/logs/task_d_sweep_c_log.txt; hit-rate script: scratch/analyze_sweep_c_hitrate.py (same "hit if no later fetch for that chunk_id" post-hoc method item 10b/10c used).

Prefetch hit rate, `read_bytes`, demand faults, `stat_pin_broken`

Ratio	Depth	Retention	Prefetches (n)	Hits	Hit rate	`read_bytes` (median)	`absent_handled` (median)	`pin_broken`	`infeasible`
0.25	2	none	126	25	0.20	11,811,160,064	43	—	—
0.25	2	pinned	120	27	0.23	12,213,813,248	52	4,7,9	1,1,0
0.25	4	none	211	35	0.17	15,166,603,264	40	—	—
0.25	4	pinned	136	33	0.24	14,361,296,896	57	23,28,29	44,39,38
0.50	2	none	114	12	0.11	11,140,071,424	44	—	—
0.50	2	pinned	93	25	0.27	9,663,676,416	41	0,0,0	0,0,0
0.50	4	none	120	25	0.21	9,932,111,872	35	—	—
0.50	4	pinned	134	34	0.25	10,737,418,240	34	0,0,0	0,0,0
0.75	2	none	42	8	0.19	5,502,926,848	27	—	—
0.75	2	pinned	37	12	0.32	6,039,797,760	34	0,0,0	0,0,0
0.75	4	none	63	20	0.32	6,442,450,944	26	—	—
0.75	4	pinned	50	23	0.46	5,905,580,032	27	0,0,0	0,0,0

For reference, arm D (prefetch off) at --driver-threads 8 (from Sweep B, constant across handler/thread configuration): read_bytes = 9,261,023,232 / 7,650,410,496 / 5,502,926,848 at r=0.25/0.5/0.75.

Expectations 1-4

Hit rate rises above the 14-27% band under pinned: PARTIALLY HELD. pinned beat none at 12/12 directly-compared reps in this sweep — a consistent, real improvement with no exceptions, ranging from a small rise (0.25/d2: 0.20→0.23) to more than doubling (0.5/d2: 0.11→0.27) to nearly tripling (0.75/d2: 0.19→0.32; 0.75/d4: 0.32→0.46). It clearly exceeds item 10b's original 14-27% ceiling at 2 of 6 (ratio, depth) cells (r=0.75/d2: 0.32; r=0.75/d4: 0.46). At the two tighter ratios (0.25, 0.5) pinned's hit rate mostly lands at or just inside the old band (0.23-0.27) rather than clearly above it — reported as a genuine partial result, not rounded up to a clean win or down to a null one.
read_bytes falls, and E no longer exceeds D at r=0.25: DID NOT HOLD. read_bytes fell under pinned in 3 of 6 (ratio, depth) cells and rose in the other 3 — no consistent direction. At r=0.25 specifically, E under pinned (12.2G at depth 2, 14.4G at depth 4) still substantially exceeds D's 9.26G at every depth — the same qualitative finding item 10c's admission rule produced, now via a different mechanism, reported as the second attempt at the same outcome that it is.
stat_pin_broken is non-zero at r=0.25: HELD. Depth 2: 4, 7, 9 per rep; depth 4: 23, 28, 29 per rep — clearly exercised, and scaling with depth (more permanently-retainable chunks at once → tighter effective budget → more demand fetches need the override). Alongside this, a real infeasible count (38-44) appears at r=0.25/depth=4 specifically — the tightest budget combined with the deepest retention genuinely strains the budget; the runs still completed cleanly (no OOM, no assertion failure, PASS reported). stat_pin_broken is exactly 0 at r=0.5 and r=0.75 in every rep — the override was simply never needed at those looser budgets, not unreachable.
Demand fault count falls relative to none: DID NOT HOLD. absent_handled fell under pinned in 2 of 6 cells (0.5/d2: 44→41, 0.5/d4: 35→34) and rose in the other 4 (0.25/d2: 43→52, 0.25/d4: 40→57, 0.75/d2: 27→34, 0.75/d4: 26→27) — no consistent direction.

Concurrency bugs found

One latent bug found by inspection while implementing Task C (a third, after item 10c's two): prefetch_pool.c's do_one_prefetch() had three bare, unlocked target->pin++/target->pin-- operations (pre-fetch pin, infeasible-abandon unpin, post-fetch unpin). At item 10b's original scale this was a genuine data race that had simply never been observed to matter (pin mutations elsewhere in the codebase — commit_reserved_and_pin, unpin_chunk, evict_chunk's read — are all budget_lock-protected); once item 10c made multiple prefetch workers run concurrently by default, the race became a real hazard, not merely hypothetical. Fixed with the existing unpin_chunk() and a new, symmetric pin_chunk(), both under budget_lock — found and fixed proactively, before any test failure revealed it, the same way item 10c's two bugs were.

No hangs, deadlocks, or data mismatches were produced by reproduction or stress-testing during this item's build phase — T-6/T-7's storm remained clean throughout Task C's iteration under --prefetch-retention pinned even before the pin-break override was fully wired in (an early build without it produced sporadic E_INFEASIBLE storms under T-3's tight budget, confirming the override is load-bearing, not decorative — it was completed before any correctness run was treated as final).

Anomalies

Sweep C's absent_handled (demand fault count) is not monotonic in either retention or depth (see the table above) — this tracks the same source of non-determinism item 10c's report already disclosed ("byte counts are no longer perfectly deterministic across reps" once genuinely concurrent fetch workers exist): exactly which speculative fetches complete before their target is next needed is timing-dependent under real concurrency, and retention changes which chunks are even eligible to be evicted at a given moment, compounding that variance. Not a correctness bug — no test asserts exact reproducibility for prefetch-enabled, retention-enabled runs.
infeasible was 0 in every cell of Sweep B and every cell of Sweep C except r=0.25/depth=4/pinned — the censoring rule fired for the first time across this project's entire history (V1, V2, item 10b, item 10c all reported infeasible=0 everywhere) at exactly the cell where retention is tightest relative to budget. Not treated as a bug: the pager's own accounting and the kernel's memory.stat[shmem] never diverged (no RECONCILE FAILED in any log), and every affected run still completed and reported PASS — this is the data point the pre-registered censoring rule exists to record, not discard.
Byte-accounting cross-check (pager vs kernel /proc/self/io) matched exactly in every row across both sweeps — no DISCREPANCY line in either log.

What I did NOT test

--sync-handler combined with --prefetch-retention pinned — the retention logic is wired into both prefetch call sites (prefetch.c's maybe_prefetch and prefetch_pool.c's do_one_prefetch) and should work under --sync-handler too, but no sweep specifically exercises that combination.
--driver-threads values other than {1, 2, 4, 8}, or values that don't evenly divide a chunk's page count.
Arm E's pinned retention combined with item 10c's admission gate at something other than the default guarded — Sweep C left --prefetch-admission at its default throughout; the interaction between the two mechanisms together was not swept.
Any chunk size or region size other than the V2 scale (2 GiB / 128 MiB) — same limitation as V2/10b/10c.
--driver-threads on arms other than D/E (A/B/C were not re-swept this item; nothing about A-8 changes how those arms work).
A budget tight enough to make retention's stat_pin_broken fire at r=0.5 or r=0.75 — it was zero at both in every rep tested.
llama.cpp integration — still explicitly out of scope.

Final check

No fabricated numbers: every value in this report is either a direct read from results/data/historical/task-d-sweep-b.csv / results/data/historical/task-d-sweep-c.csv (raw data from real runs, machine exclusivity checked before/after both sweeps) or a disclosed, straightforward computation over it (median, the reused hit-rate script, objdump disassembly actually inspected, not assumed). T-1 through T-7 all re-run and passing is reported as such, including the one counter (T-3's infeasible) that looked concerning until checked against the actual prior-commit baseline. Task A's gate passing on all three checks is reported as such. Task B's negative result (device-busy not rising with driver threads under async) is reported plainly, with the mechanism traced to the barrier structure Task A itself requires — not attributed to a flaw in the async architecture, and not hidden. Task C's partial result (hit rate rises consistently but doesn't clearly exceed the old band at every ratio; 2 of 4 expectations fully held, 1 partially, 1 did not) is reported at that same granularity, not rounded up or down. The one latent concurrency bug found this item is disclosed with its exact mechanism and fix, matching the standard item 10b/10c already set.

FilesExpand file tree

06-concurrent-demand.md

Latest commit

History