KPN/PERF_PLAN.md

Performance investigation plan: fanout dispatch cost and deep-chain oversubscription

Status: phase 0 implemented; gate not yet cleared Date: 2026-08-06 (phase 0 landed 2026-08-06) Baseline: master @ 3b67b7e Machine: 20 cores, GCC 16.1.1, TBB 2023.1.0, AC power, performance governor Data: 7 full benchmark passes, medians reported below

---

1. What was measured

Throughput, items/sec, median of 7 passes. N is the sample size the harness uses for that row; it is what determines whether a row can be trusted at all.

work_us = 10

row	KPN it/s	TBB it/s	TBB faster	N	reliable?
chain-1	89381	91350	+2.2%	3000	solid
chain-2	83759	87017	+3.9%	1000	solid
chain-4	83725	85973	+2.7%	1000	solid
chain-8	79730	81090	+1.7%	1000	solid
chain-16	53484	68745	+28.5%	200	weak
chain-32	32780	45030	+37.4%	200	weak
wide-4	84906	95137	+12.0%	3000	solid
diamond-4	84826	86772	+2.3%	1000	solid

work_us = 100

Everything except chain-16/32 falls within ±3.4%, with KPN often ahead (chain-1 −0.6%, chain-4 −1.7%, chain-8 −3.4%, diamond −2.6% — negative means KPN faster). chain-16 is +12.5% and chain-32 +18.6%, both at N=50 and therefore unusable.

Two deficits, different causes

1. Fanout, +12%. Solidly measured. wide-4 performs ~5 node dispatches per item; the gap works out to a fixed ~250 ns per dispatch, consistent with chain-1's ~290 ns over a single dispatch. This is dispatch efficiency.

2. Deep chains, +28–37%. The gap is 1.7–3.9% through depth 8, then jumps to 28.5% at depth 16 and 37.4% at depth 32. That is a cliff at core count, not a linear per-dispatch cost. Node<> owns a private ThreadPool(1) (include/kpn/node.hpp:21), so a depth-32 chain spawns 32 OS threads on 20 cores. TBB bounds its worker count by hardware concurrency regardless of graph size.

Scope note

At 100 µs+ per node KPN is at parity or ahead. The repository's own examples (OpenCV cellshade, frame sources, scene-actor extraction) do milliseconds of work per node, where a 290 ns dispatch cost is roughly one part in thirty thousand. Everything in this document matters only for fine-grained pipelines.

---

2. Phase 0 — the gate that comes first

Is there a target workload with sub-30 µs nodes?

If no such workload exists or is planned, the correct output of this document is section 3 (harness) plus a README correction, and nothing else. Optimising for a benchmark regime the project does not operate in is not worth the risk described in section 6.

---

3. Prerequisite — make the harness able to answer

None of the questions below are decidable with the current harness. benchmarks/bench_pipeline.cpp shrinks the sample count as work per item grows, so the rows under investigation run 50–200 items and swing 4–8× run to run.

id	change	why
M1	items_for() → fixed floor, e.g. max(2000, …), independent of work_us and depth	deep rows are currently unmeasurable
M2	report items/sec as the primary metric; keep derived overhead as secondary	overhead is elapsed − work, a difference of large numbers; it magnifies noise roughly 10×
M3	K in-process repetitions per config; report median and IQR	one shot per config is the root of the present noise
M4	discard a warm-up repetition	first-touch page faults, thread spin-up
M5	extend pool_sizes[] to {1,2,4,8,16,20}	currently {1,2,4} — the configuration the README recommends is never run
M6	record nproc, governor and AC state in the CSV header	run-to-run attribution

Acceptance: the same configuration run 7× lands within ±5% on every row. Until that holds, no number below should be acted on.

This touches only the benchmark, not the library.

Status — implemented 2026-08-06

All of M1–M6 are in benchmarks/bench_pipeline.cpp, plus a CLI so the phase-1 experiments are invocations rather than edits (--depths, --pools, --work, --topos, --modes, --reps, --target-sec, --min-items).

M1 is not a fixed floor but a time budget with a floor: sample size derives from work_us × stages / units, the steady-state throughput bound, then clamps to [--min-items, --max-sec]. A flat 2000-item floor would have made chain-32 on a 1-thread pool at 1000 µs a 64-second row; the ceiling keeps such rows short and reports their true N so a short row is visible rather than silent. The old ladder's error was treating depth as a throughput cost — in a pipeline, depth beyond the core count costs throughput, below it only latency.

Also added, ahead of schedule because it is free: ru_nivcsw / ru_nvcsw per item are captured around every timed region, so A3 is now a matter of reading a column rather than a separate experiment.

scripts/bench_repro_check.py runs the acceptance criterion directly — K passes, per-row deviation from the median, non-zero exit if any row exceeds tolerance.

Gate not yet cleared. A 3-pass run of chain-{1,8} at 10 µs on the development laptop (20 cores, powersave governor, on battery — the header now records this) lands every row within 0.7%, against the 4–8× swings this section describes. That is encouraging but is not the acceptance run: it must be 7 passes over the full row set on the reference machine.

Provisional and not to be acted on: in that same run chain-16 private was 6% behind TBB, not the 28.5% in the table above. If that survives the real acceptance run, the deep-chain deficit is substantially a measurement artefact of the N=200 rows and workstream A shrinks accordingly.

---

4. Workstream A — deep chains

Hypothesis: the deficit is thread oversubscription from the private-pool model, not dispatch cost.

Investigation

id	experiment	falsifies the hypothesis if
A1	sweep depth 8, 12, 16, 20, 24, 32 at 10 µs, private pools	the cliff is not near nproc
A2	repeat A1 under taskset -c 0-7	the cliff does not move to ~depth 8
A3	getrusage(RUSAGE_SELF).ru_nivcsw per item, depth 8 vs 32	involuntary context switches do not scale with depth
A4	chain-16/32 on a shared pool sized 16 and 20, vs private and vs TBB	a correctly sized shared pool does not recover the gap

A2 is decisive and costs one run: if the cliff tracks the core count, the mechanism is established.

Improvement, conditional on A4

If a correctly sized shared pool closes the gap, this is not an optimisation problem — the mechanism already exists and is simply not the default:

• A5 — change Network's default from per-node private pools to a single shared pool sized hardware_concurrency(). Users should not have to know.
• A6 — emit a diagnostic when total node threads exceed hardware_concurrency().
• A7 — README: state the threshold, with the measured cliff.

A5 is a change to the default execution model and must clear section 6 in full.

A5 now has a prerequisite (from B1/B2, 2026-08-06)

The dispatch microbenchmark measured what a shared pool costs per dispatch, and it is not free: 466 ns on a private ThreadPool(1) against ~1.7 µs on a shared pool of 4, because round-robin submission wakes a sleeping worker on every dispatch (see §5). A5 as written would therefore make every graph that currently fits inside its core count roughly 3–4× worse per dispatch, in exchange for fixing graphs that exceed it.

A5 must not land before the wake cost does. The order is B9/B5 first, then A5, and A4 must be read with this in mind: if a shared pool "recovers the gap" at depth 32, check what it costs at depth 4 in the same run before changing any default.

This partially inverts the prediction in §7: workstream A is not purely a default-and-documentation change, because the default it would switch to is currently the slower one per dispatch.

---

5. Workstream B — fanout dispatch cost

Hypothesis: a fixed ~250 ns per node dispatch, paid ~5× per item in wide-4. Unlike workstream A, this genuinely is dispatch efficiency.

Estimated budget for ~290 ns, per item — estimates, to be replaced by B3:

cost	est.
shared_lock(lifecycle_mx_) in submit()	20–40 ns
queues_[target]->mx lock/unlock	20–40 ns
priority_queue push + pop (heap ops, std::function moves)	50–100 ns
{ lock_guard lk(cv_mx_); } + notify_one()	20–40 ns, or µs if a worker actually sleeps
2–3 × clock_t::now() in fire_once	50–75 ns
gate CAS + ~6 stats atomics	30–60 ns

Investigation — measure before touching anything

• B1 — microbenchmark submit→execute turnaround for a null task on ThreadPool(1) and ThreadPool(4). Yields ns/dispatch directly, in seconds rather than minutes.
• B2 — does a worker actually sleep per item? Count cv_.wait returns, or strace -c -f -e futex. The entire spin-window hypothesis depends on this; if workers are not sleeping, B5 is worthless and drops off the list.
• B3 — ablation, one variant per suspected cost, each measured against B1 rather than guessed at:

variant	suspected cost
stats and clock calls compiled out	2–3 × clock_t::now() plus ~6 atomics per firing
priority_queue → FIFO ring	heap operations, std::function moves
shared_lock(lifecycle_mx_) removed (measurement only, unsafe)	include/kpn/scheduler.hpp:113
bounded spin before sleeping	include/kpn/scheduler.hpp:210-227

B1/B2 — first results, 2026-08-06

benchmarks/bench_dispatch.cpp answers both without touching the library. Sleeping is inferred from ru_nvcsw: a thread blocking on a condition variable books a voluntary context switch, so voluntary switches per task is sleeps per task. Three modes, because "the cost of a dispatch" is three numbers: latency (idle pool, one task in flight), batch (submit flat out, drain once), steady (the task resubmits its successor, as fire_once does).

Laptop, powersave, battery, 3 reps — the nanoseconds are provisional; the sleep counts are structural and will hold. steady, 10 µs payload:

pool threads	ns/dispatch	sleeps/task
1	466	0.00
2	1494	0.97
4	1722	1.00
8	1996	1.00

B1 is answered and the abandon criterion is not met. A ThreadPool(1) dispatch is 291 ns for a null task, 466 ns with a payload — against the ~290 ns the section-1 budget estimated for chain-1. The estimate was good. Dispatch cost is not already under 100 ns, so workstream B stays alive.

B2 is answered, and the answer is conditional — which the question did not anticipate. It is not "do workers sleep?" but "which pool?":

• On a private ThreadPool(1) — the Node<> default — the worker never sleeps. It resubmits into its own queue and finds the work already there.
• On any pool of 2 or more, a worker sleeps exactly once per task.

submit() round-robins (next_.fetch_add(1) % thread_count_, scheduler.hpp:131), so on a shared pool every task is handed to a different worker, which is asleep, and every single dispatch pays a futex wake. That is the entire 466 ns → 1.7 µs difference.

Consequently B5 (bounded spin) is worthless for the default configuration and is the highest-value item for shared pools. It does not drop off the list, it moves onto a different one.

B9 — submit-to-self affinity (new, not in the original plan)

If a submit() originating on a pool worker pushed to that worker's own queue instead of round-robining, the shared pool would inherit the property that makes ThreadPool(1) fast: the work is already local when the worker loops, so no wake. This is roughly what TBB does, and it plausibly subsumes most of B5 at lower risk — it changes task placement, not the sleep/wake protocol that the August wedge fixes hardened. Work stealing already exists to correct the resulting imbalance.

Measure before believing it: an affinity policy can starve peers, and try_steal only rebalances when a peer goes idle.

Improvement — only what B3 shows pays

1. B4 — compile-time-optional instrumentation. No concurrency risk; the only item here that cannot reintroduce a wedge. Worth doing regardless.
2. B5 — bounded spin before sleeping, mirroring the channel's existing spin_count_ (~4 µs). Note the tension: b9698fa deliberately moved from "spin whenever any task runs" to "sleep as soon as nothing is queued" in order to fix pathological spinning. A bounded window is the middle ground; unbounded spin would undo that fix.
3. B6 — cheaper queue on the common path. A private pool holds ≤1–2 tasks; priority_queue<Task> is heavy for that.
4. B7 — batched firing. fire_once processes one token then re-submits; looping while inputs stay ready, bounded, amortises the submit, gate CAS and wake. The largest algorithmic win, but it changes latency and interacts with compute_priority().
5. B8 — lifecycle_mx_ off the hot path. Last, and possibly never. It is load-bearing: it prevents submit() racing stop()'s queues_.clear(), a documented segfault reproducible "about 12 runs in 20".

Abandon criteria: if B1 shows dispatch cost already under ~100 ns, or the best surviving variant buys under 5%, stop and document the finding.

---

6. Guardrails

Both workstreams modify the machinery responsible for roughly twenty wedge fixes in August 2026, plus the lost wake fixed in 6802328. Every change:

1. 146/146 ctest, examples included.
2. Wedge soak before and after — benchmarks/repro_wedge.cpp, ≥50k iterations clean. Reference point: the pre-6802328 code wedged 5/5 inside 45 s, at iterations 149, 1249, 332, 1740 and 493.
3. ThreadSanitizer on scheduler and pool_node tests for any change to either.
4. One change at a time, measured independently. Bundling is how the August audit became twenty commits.
5. G1 — wire the reproducer in as an opt-in CTest stress target (e.g. -L soak) so that performance work cannot silently reintroduce a wedge. This should land before either workstream starts.

G1 — implemented 2026-08-06

tests/soak_wedge.cpp (supersedes benchmarks/repro_wedge.cpp, which was never wired into any build and can be deleted). Always compiled so it cannot rot; its CTest cases register only under -DKPN_ENABLE_SOAK_TESTS=ON, so the default ctest count is unchanged.

cmake -B build -DKPN_ENABLE_SOAK_TESTS=ON -DKPN_SOAK_ITERS=50000
cmake --build build --target kpn_soak_wedge
ctest --test-dir build -L soak

Two cases: soak.wedge.pool (depth 4, 4 threads — the configuration the August wedges were reproduced on) and soak.wedge.private (depth 8, one pool per node — the model workstream A would change). Both parameterised, so A5-style changes can be soaked at the depth that matters.

A wedge is a hang, and a hang under CTest is an unattributable timeout, so the binary carries a watchdog: if an iteration stops making progress for --watchdog-sec it aborts naming the iteration and the phase (pushed, drained, nodes stopped, pool stopped). Measured cost: ~13 ms per iteration, so the 50k-iteration guardrail is ~11 minutes.

Guardrail 1 needs a correction. The stated reference is 146/146; the tests-only configuration used here reports 136/136 passing, and neither examples/ nor python/ registers any add_test. The true reference count must be pinned down before it is used to certify a change.

---

7. Sequencing

phase	contents	gate to proceed	state
0	workload question; M1–M6; G1	±5% reproducibility achieved	tooling done, acceptance run outstanding
1	A1–A4	A2 confirms the cliff tracks core count	harness supports it; not run
2	A5–A7, or documentation only	A4 shows a shared pool recovers the gap	now gated on B9/B5
3	B1–B3	B2 answers the sleep question	B1/B2 answered; B3 outstanding
4	B4, then whichever of B5–B8 survived B3	each ≥5% and soak-clean	B5 rescoped to shared pools

B1/B2 ran early because the microbenchmark cost seconds rather than minutes, and the result reordered phases 2 and 4 — the shared-pool default now depends on the wake cost being fixed first. Phase 1 is unchanged but its A4 row needs a shallow-depth control, per §4.

Reproducing this

cmake -B build_bench -DKPN_BUILD_BENCHMARKS=ON -DCMAKE_BUILD_TYPE=Release
cmake --build build_bench -j

# Phase 0 acceptance — must pass before any number below is acted on
python3 scripts/bench_repro_check.py ./build_bench/benchmarks/bench_pipeline \
    --passes 7 --tolerance 5 -- --work=10,100 --reps=5

# B1/B2
./build_bench/benchmarks/bench_dispatch --threads=1,2,4,8,20 --reps=5 \
    | tee dispatch.csv

# A1/A2 — the depth sweep, and the same under taskset to move the cliff
./build_bench/benchmarks/bench_pipeline --work=10 --topos=chain \
    --depths=8,12,16,20,24,32 --modes=priv,tbb --reps=5 | tee a1.csv
taskset -c 0-7 ./build_bench/benchmarks/bench_pipeline --work=10 \
    --topos=chain --depths=4,6,8,10,12,16,32 --modes=priv,tbb --reps=5 | tee a2.csv

# A4 — shared pool sized to the machine, against private and TBB.
# Include a shallow depth: A5's risk is what a shared pool costs when the
# graph already fits in its cores.
./build_bench/benchmarks/bench_pipeline --work=10 --topos=chain \
    --depths=4,16,32 --pools=16,20 --reps=5 | tee a4.csv

Check the # governor= line in each CSV before trusting it. A3 needs no separate run: ivcsw_per_item is a column in every row above.

Success criteria

• chain-32 @10 within 10% of TBB in the recommended configuration
• wide-4 @10 within 5% of TBB
• zero wedges across 100k soak iterations

Prediction, recorded so it can be proven wrong: workstream A resolves into a default-and-documentation change rather than an optimisation, and workstream B yields 5–10% on fanout from B4 and B5, with the remainder not worth the risk.

Prediction, revised 2026-08-06 after B1/B2 — the original is already half wrong and is left above unedited:

• Workstream A does not resolve into a documentation change, because the shared pool it would recommend costs 3–4× more per dispatch than the private default. It resolves into B9 first.
• The largest single win is not B4, B5 or B7 but B9, submit-to-self affinity: one sleep per dispatch is being paid on every shared pool, and eliminating it is worth roughly 1.2 µs per dispatch — far more than the 5–10% predicted for fanout.
• Standing: chain-16's 28.5% deficit is a measurement artefact of N=200.

---

8. Related correction

Independently of the above, the README's TBB comparison overstates its case. The claim that KPN++ beats TBB "for every chain and diamond topology at 100 µs/node" is not supported: at 100 µs only chain-1 and diamond lean KPN, while chain-16, chain-32 and wide-4 lean TBB. The tables are also quoted in derived overhead, which magnifies small differences — the same rows expressed as throughput are mostly within a few percent. Restating them in items/sec would be both more accurate and more favourable.