Pooled run_dada is not uniform: occupancy climbs 22 -> 42 cores across a run, and the serial fraction is concentrated in the early rounds

[cjfields]

The per-window progress lines added in #150 show that pooled run_dada is not
a uniform workload, and that every phase figure we have ranked levers against
is a mean over a run that spans nearly a factor of two in occupancy.

What the lines show

Soil ITS2 R1, 64 threads, 30-second windows (main, verbose):

window	eff cores	clusters added	align	map	shuffle	bud+pupd
0–30 s	24.4	+492	1.62%	12.6 s	9.1 s	6.6 s
30–60 s	28.7	+617	0.76%	15.1 s	8.2 s	3.7 s
60–90 s	29.0	+639	0.42%	15.4 s	8.5 s	3.1 s
90–120 s	29.1	+643	0.27%	15.4 s	8.8 s	2.7 s
120–150 s	37.9	+832	1.01%	20.2 s	4.0 s	1.7 s

Occupancy climbs from ~22 to ~42 effective cores of 64 over a single run. The
end-of-run mean (~29) describes no window of it.

It is the serial fraction, not the workload

align falls six-fold and then rises again while occupancy climbs straight
through, so the alignment pass rate is not driving this. Serial work per window
collapses from 15.7 s to 5.7 s — roughly 52% of the early windows against
19% of the late ones.

Normalising for progress makes it sharper. Serial time per cluster added:

• early: 15.7 s / 492 = 31.9 ms/cluster
• late: 5.7 s / 832 = 6.9 ms/cluster

A 4.6× drop, so this is not simply "more clusters get added later". The early
rounds genuinely do far more shuffle and p-update work per bud, presumably
because the partition is unstable and more raws move per round.

Why this matters beyond curiosity

1. Our headline occupancy numbers are means over a bimodal run. "Effective
   cores 31.4 → 38.4" (perf(compare): hoist e_minmax into a dense array — store −71%, run_dada −20% (#147) #148) and "map parallel efficiency 86–90%" have both been
   used to rank levers. A change that helps the early serial-heavy phase and one
   that helps the late map-heavy phase are indistinguishable in the totals.
2. The serial fraction is concentrated somewhere we have not looked. Every
   b_shuffle optimisation so far (Re-evaluate b_shuffle: its share grows with thread count, so #124's closure was conditional #132, Is b_shuffle's reconcile redundancy actually unreachable? Measure the necessary fraction #136, b_shuffle's build scan on high-diversity pools: ~38% of run_dada on a soil 16S set, and #87's own gate says it is winnable #139) was designed against
   whole-run totals. Whether they helped the early phase — where the serial
   fraction actually lives — is unmeasured.
3. b_p_update has never been targeted at all. It is fully serial and runs
   18.2 s (R1) / 25.8 s (R2) of a 167 s / 211 s run_dada — 11–12% — and its
   cost is concentrated in exactly the windows where occupancy is worst.

Proposed first step: measure, do not design

Consistent with what #143 established the hard way — do not design an
optimisation against a share-of-wall figure before re-measuring what it is made
of:

• Progress lines on soil 16S as well as ITS2 (only ITS2 has been run),
  and on both reads. 16S has 2.4× the clusters and a 5.6× higher align rate,
  so the ramp may have a different shape or none at all.
• Attribute the early-phase serial block the way Attribute b_compare's serial store + 329s unaccounted — now ~48% of run_dada #143 attributed b_compare:
  split shuffle into reconcile/move/build and p-update into its own passes,
  per window rather than per run.
• Check whether the ramp is thread-count dependent. The flat serial floor
  found in the Measure b_compare: split screen vs alignment time before considering any redesign #127 thread sweep was measured from end-of-run totals and may
  be a late-run property.

Only then decide whether there is a lever. It is entirely possible the early
rounds are irreducibly serial and this closes as a documented property of the
algorithm — which would still be worth having written down.

Not to be assumed

A prediction made before looking was that occupancy should fall over the run,
because greedy skips increase as cluster centres get less abundant. That was
reasoning about the map, and the map is not where the answer is. Do not carry a
model of the bud loop into this without checking it against the lines.

Context: docs/findings/compare-store-scan.md ("The run is not uniform"), and
DADA2RS_PROGRESS_SECS (#150) for the instrument.

[cjfields]

The occupancy ceiling is set by the serial block, and it varies ~3× across the run

Prompted by the question of whether the ceiling depends on allocated cores. It
does, but that is not the binding constraint — and working the arithmetic out
per window turns this issue's first step into a falsifiable prediction.

With W core-seconds of parallel work and S seconds of serial, wall is
W/N + S, so effective cores asymptote at (W+S)/S as N grows, regardless
of allocation. Applying that per window to soil ITS2 R1 (main, rep 1):

window	serial	parallel work	eff cores @64	ceiling as N→∞
0–30 s	17.4 s	715 core-s	24.4	42.1
30–60 s	14.9 s	846 core-s	28.7	57.8
60–90 s	14.6 s	855 core-s	29.0	59.6
90–120 s	14.6 s	858 core-s	29.1	59.8
120–150 s	9.8 s	1127 core-s	37.9	116.0
whole run	80.9 s	4834 core-s	29.4	60.8

The early phase saturates around 42 effective cores no matter what is
allocated. Allocating 128 to this run would buy the first window almost
nothing while the last window could in principle absorb well over 100. A ~3×
swing in headroom inside one run.

Two caveats on those numbers

They assume W is constant in N, and it is not: #127 found the DP kernel
execution-bound to ~48 threads and bandwidth-bound above, so busy grows as
threads are added. Every ceiling above is therefore an optimistic upper bound,
most of all the late-phase one.

And #127's "flat serial floor" was measured from end-of-run totals. If the
serial block is concentrated early, that floor averages two regimes with very
different headroom, and the sweep's conclusions may not survive a per-window
re-read. Adding that to the checklist above.

The prediction this makes

A thread sweep on this pool should show the early windows barely responding
to thread count above ~48 while the late windows keep improving. If instead the
early windows scale normally, the serial attribution above is wrong and this
issue needs re-scoping before any lever is designed.

That is a cheap test — one sweep with DADA2RS_PROGRESS_SECS set — and it
should come before the per-window phase attribution, not after.

[cjfields]

Before attributing the early-phase serial block: check whether we made the ramp

A hypothesis that should be tested before the per-window shuffle/p-update
split, because it is cheaper and it partitions the hypothesis space first.

Every serial optimisation landed since #86 has the same shape: cost
proportional to change, not to state size. That is exactly the
transformation that manufactures a ramp, because change is maximal in the early
rounds.

• b_shuffle's build scan on high-diversity pools: ~38% of run_dada on a soil 16S set, and #87's own gate says it is winnable #139 carry (shuffle_carry, on by default) — without it every bud
  rebuilds the whole compmax map: O(nraw x nclust), a cost that grows
  monotonically as clusters accumulate. With the carry, per-round cost becomes
  O(comps touched by the two changed clusters). We replaced a rising curve
  with a change-proportional one.
• Is b_shuffle's reconcile redundancy actually unreachable? Measure the necessary fraction #136 incremental reconcile — walks (raw, changed-cluster) pairs. Early
  rounds have the most raws whose argmax actually flips; late rounds most raws
  are settled and the test exits cheap. Same sign.
• Re-evaluate b_shuffle: its share grows with thread count, so #124's closure was conditional #132 dirty-cluster move pass — keys on the raw's holder. Early on the
  holder is overwhelmingly cluster 0, which still contains nearly all uniques,
  so pruning to dirty clusters prunes to a cluster of size ~nraw. It buys
  almost nothing early and nearly everything late.

The confound cuts both ways

b_p_update is dirty-gated on update_e in the original C++ too
(src/pval.rs:57), and its cost is the sum of members over dirty clusters.
Early in a run the giant cluster is dirty constantly and repricing it is
O(nraw). So there is an intrinsic ramp from the cluster-size distribution
— cluster 0 being carved down — that would exist in stock DADA2 with none of
our optimisations.

These are therefore not competing hypotheses but additive. The 4.6x drop in
ms/cluster is some mix of:

1. intrinsic — cluster-0 shrinkage makes dirty-set repricing cheaper, and
2. induced — the three levers each traded a size-proportional cost for a
   change-proportional one, and change decays.

The split matters for whether there is a lever at all. (1) is irreducible. (2)
would mean the early phase is precisely where our existing optimisations do not
yet reach, which is a different roadmap item from "the early rounds are
irreducibly serial".

The experiment (no code, one binary)

All three levers already have single-binary kill switches, which exist for
exactly this reason:

DADA2RS_SHUFFLE_NO_CARRY=1   # revert #139
DADA2RS_RECONCILE_FULL=1     # revert #136
DADA2RS_SHUFFLE_NO_PRUNE=1   # revert #132

• Re-run the ITS2 R1 progress lines with all three set, then bisect if the
  ramp moves.

Prediction if the ramp is induced: occupancy flattens, and total wall
rises substantially — that second half is the control channel proving the arm
actually took effect. If the ramp survives all three off, it is intrinsic
and this can close as a documented property of the algorithm.

Instrument hygiene, given this is a null-hunting run on a shared node: pin with
dev/numa_pin.sh --interleave (not bind), report an untouched control channel,
and replicate the same arm before believing a flattening. A flat line is
evidence only once the instrument is shown capable of returning a ramp — the
all-on arm is that demonstration, so run it in the same session, not from the
table above.

Unrelated but worth pairing on the same node time

The R comparison is stale: #131 (rolling-d16), #134 (-8.6% pooled wall) and
#144 (-28.8/-32.0% run_dada soil 16S) all landed since it was last run. It is
a ratio measured against R on the same hardware at the same time, so it
tolerates a busier node than an absolute-vs-past-release comparison would.
Harness: dev/benchmark/run_dada2_pooled.R + bench_step.R on the R side,
bench_pooled.py / compare_bench.py for the roll-up. Soil 16S is the natural
target — it is where #144 paid best and where this issue still has no
progress lines, so one run feeds both checklists.

[cjfields]

Amending the R-comparison arm: R pooled on soil 16S may not be measurable

Flagging before anyone books node time on the plan as written above. Past
experience on more diverse soil samples is that a full pool=TRUE R run can
take a week or more, which is why pseudo-pooling has always been the
default in practice.

That is not a slow benchmark, it is a censored one: an arm that does not
finish yields no ratio, and it would consume exactly the node booking the
rs-only progress-line runs need. So the R pooled arm must not gate anything
here.

Restructured:

• Primary R arm on soil 16S = pool=pseudo. It is what we actually
  ship and recommend, it is tractable on both sides, and it needs no code —
  pool=pseudo is already a supported value in both run_dada2_pooled.R
  and bench_step.R.
• Keep the pooled R-vs-rs ratio on a dataset where R demonstrably
  finishes (MiSeqSOP 384 / ITS2), so we still have a pooled datapoint that
  is a measurement rather than a bound.
• Optional, only if the node is genuinely idle: treat R pooled on soil 16S
  as a bounded probe, not a benchmark — subsample to a depth where R
  completes, check whether the rs/R ratio is depth-stable, and extrapolate.
  That turns "a week" from a blocker into a reportable bound, which is
  directly the kind of number Is full pooling worth it at scale? Measure dada-pooled vs dada-pseudo on a large diverse run #106 wants (where "pooled is infeasible" is
  hardware-conditional and has never actually been quantified).

Confound to state explicitly on the pseudo arm: per #100, R appears to
re-estimate the error model between pseudo turns (dada.R:371-378, no
selfConsist guard) and we do not. For timing that means R's pseudo wall
includes work we simply never perform, so a raw whole-pipeline pseudo ratio
flatters us. Time at step granularity — bench_step.R already isolates
dada_fwd/dada_rev as their own processes — and report what is inside each
side rather than a single headline multiple.

None of this touches the kill-switch experiment: that arm is rs-only pooled and
needs no R at all, so it stands regardless of what happens to the comparison.

[cjfields]

The #100 confound is now a measurable arm, not a caveat

Two updates that change the pseudo comparison above.

1. #100 is settled. R's inter-turn error re-fit has been confirmed with
DADA2's author as unintended behaviour — and one that somewhat blunts the
intended effect of pseudo-pooling. So it is not an open question about which
implementation is right: our behaviour matches the published definition, and R's
extra re-fit is an artefact of implementing pseudo as two turns of the
self-consistency loop.

2. We can already emulate it, so the confound does not need to be
caveated away — dada-pseudo --reestimate-err-between-rounds re-fits round 1's
transitions and denoises round 2 with the result, mirroring dada.R:371-378.

That turns the "R's pseudo wall includes work we never do" problem into a
measurement:

• Run the rs pseudo arm twice — default (off) and
  --reestimate-err-between-rounds.
  • The flag-on arm is the apples-to-apples timing ratio against R: both
    sides now do the same work, so the number means what a reader will assume it
    means.
  • The flag-off vs flag-on delta is the price of R's accidental re-fit,
    isolated. That is a number worth having on its own, and it is the kind of
    thing worth handing upstream given the behaviour is now acknowledged as
    unintended.

Bonus that costs nothing extra: the flag-on arm is also a concordance
check. If rs-with-the-flag reproduces R's pseudo output, that both validates the
emulation and pins down the re-fit as the entire source of the #100 divergence
rather than one contributor among several.

Supersedes the "time at step granularity and state what is inside each side"
mitigation in my previous comment — step granularity is still good practice, but
it is no longer load-bearing for this confound.

Also updated the flag's --help text on main, which still described #100 as
an open question and whether the re-fit was intended as unknown.

[cjfields]

Sweep results: the prediction is half right, and the knee is pool-specific

ITS2: two reps, 48/64/96 threads. 16S: one rep so far. DADA2RS_PROGRESS_SECS=15,
numactl --interleave=all, exclusive node.

run_dada — the two pools go in opposite directions

	48	64	96
ITS2 R1	194.0 s	198.2	203.8
ITS2 R2	254.9 s	258.2	263.2
16S R1	710.4 s	645.8	582.0 s
16S R2	773.0 s	714.4 s	729.6

ITS2 is past the knee below 48 — more threads are strictly worse. 16S R1 is
still improving at 96 (−18%); 16S R2 turns over between 64 and 96. So "48 is
past the knee" was an ITS2 statement, not a hardware one, and I had it as the
latter in an earlier comment on #28. Corrected there.

Why they differ: arithmetic intensity, and it is already in our logs

map busy split (R1, 48 threads)	ITS2	16S
k-mer screen	85.8%	50.8%
alignment (DP)	7.6%	41.7%
screen pass rate	0.8%	4.5%

The screen streams k-mer vectors and is bandwidth-bound; the aligner does DP and
is compute-bound. ITS2's map is 86% streaming, so it saturates early. 16S's is
42% arithmetic, so it keeps scaling. The align fraction predicts the knee,
and it is printed in every verbose run — so the right thread count is choosable
per pool from a figure we already have.

The prediction

I predicted early windows flat, late windows improving. Cluster-aligned marginal
segments:

segment	16S R1: 96 vs 48	ITS2 R1: 96 vs 48
first	−14.6%	+2.7%
second	−17.2%	+3.6%
third	−21.1%	+5.8%
fourth	−20.7%	+6.4%

Half right, and the half that failed is instructive. "Early is less
responsive to threads" holds on both pools — the early phase is
serial-dominated, so it moves least in either direction. "Late improves" was
wrong as stated: the late phase is map-dominated, so it tracks whatever the map
does with threads. On 16S that means improving most (−21%); on ITS2, degrading
most (+6.4%). One rule, two signs.

That also kills the ceiling arithmetic I posted earlier in this issue, which
assumed parallel work is constant in thread count. It is not — ITS2 busy rises
+87% from 48 to 96 threads for identical work.

What holds, unchanged

Serial time is thread-invariant, exactly as this issue claimed. 16S R1
serial block: 208.5 s at 48 threads, 207.3 s at 96. What changes is its share —
29.3% → 35.6% — so scaling the map walks us into the serial wall rather than
away from it. ITS2 at 48 threads is already at 40.8%.

b_p_update is likewise thread-invariant (30.19 / 30.27 / 29.53 s across
48/64/96), confirming it as serial — see #154.

Caveat

16S is one rep. The R1 scaling (−18%) is far outside ITS2's ~1–2% replicate
spread, but R2's turnover between 64 and 96 is a ~2% effect and should not be
believed until the second rep lands.