StrandExecutor's drain slows superlinearly with competing CPU load (~ratio^2.1 over three points) -- scheduler or strand, not determined

[Yaraslaut]

What

StrandExecutor's drain slows down with competing CPU load far faster than
proportionally. Whether that is the Linux scheduler doing what schedulers do,
or StrandExecutor handing off worse than it has to, is not determined here
— this issue exists so the three measurements are on record rather than living
in a comment nobody will go looking for.

morph#760 anticipated this exactly: "Re-frame as a StrandExecutor defect if
the drain rate is shown to degrade with competing threads beyond what the
scheduler explains." morph#760 is closed by a timeout change (morph#779), which
does not answer that question, so it is split out here rather than closed with
it.

Measured

tests/test_strand_race.cpp, case StrandExecutor never runs two tasks for one key concurrently under contention, on c4e21233. 12 cores, Arch Linux
7.2.6-arch2-1, clang 22.1.8, preset linux-everything (Release). Load made
with plain while :; do :; done spin loops. Whole-case wall clock, one run
each:

spin loops	run queue (/proc/loadavg field 4)	wall clock
0	1	0.136 s
12	14	23.8 s
24	27	170.5 s
36	38	396.4 s

Every run passed — All tests passed (40 assertions in 1 test case), and every
watchdog line in every run reads inFlight 1, maxInFlight 1. Nothing is
breaking here; it is only getting slower.

The steps:

• 0 → 12 spin loops: 175×
• 12 → 24: 7.2× for 2× the load
• 24 → 36: 2.3× for 1.5× the load

Fitting the last two steps gives an exponent of about 2.1 in the
oversubscription ratio. A scheduler-latency story predicts roughly 1: a woken
thread waits about N/C scheduling quanta, so the per-handoff cost should track
the ratio, not its square.

The case's shape is what makes it a sensitive probe: the strand serialises
8 × 400 = 3200 tasks per iteration, so the iteration is 3200 sequential
wakeups and almost nothing else. At the 36-spinner point that is ~6 ms of wall
clock per handoff.

Verification status

• Reproduced: all four rows, on the revision named, one run per row.
• Not established: that this is a StrandExecutor defect at all. Three
  loaded data points, one run each, on one kernel, one machine, one core count.
  No error bars. Plausible alternative explanations not ruled out: CFS wakeup
  placement changing character as the run queue grows, the spin loops never
  yielding (a real build's load would), std::this_thread::yield() inside the
  task interacting with an oversubscribed run queue, or cache/IPC effects from
  36 hot loops that have nothing to do with wakeups.
• Not attempted: perf sched, which is what would actually separate
  "waiting to be scheduled" from "doing more work per handoff".

What would settle it

perf sched latency (or perf trace -e sched:sched_switch) on one iteration at
each load point, split into time-to-wakeup versus time-in-task. If the
per-handoff wakeup latency grows as the ratio and the rest is flat, this is
the scheduler and the issue closes as "explained". If the non-wakeup part grows,
it is StrandExecutor and this becomes a real defect against
include/morph/core/strand.hpp.

A cheaper first cut: re-run the four points with load generated by sleep-y
processes rather than spin loops, and with the run queue held fixed while the
core count varies. If the exponent survives both, it is not an artefact of how
the load was made.

Why it is worth the trouble

Not for this test's runtime — morph#779 handles that with a per-case TIMEOUT 900, and says in the same breath that a host oversubscribed past ~4.5× will
blow through 900 s too. It matters because StrandExecutor is on the
per-model serialisation path for every execute() that goes through a strand.
If handoff cost really is quadratic in oversubscription, that is a property of
the framework under a busy server, not a property of one test.

What would change the verdict

Close as "scheduler, explained" if the perf split above attributes the growth
to wakeup latency. Re-frame as a strand.hpp defect if it does not. Close as
"not reproducible" if the exponent does not survive a different load generator
or a different machine — and say which, because that is a useful result too.

Related

• morph#760 — the timeout this was found under, and where the re-frame clause
  comes from.
• morph#779 — the timeout change. It deliberately does not address this.
• morph#717 — the watchdog that makes this measurable at all.

[Yaraslaut]

Triage: unverified, area: core — the measurement is real, the attribution is the open question

unverified rather than valid deliberately. The numbers are measured and the
issue is right to exist; what is untested is the claim that would make it
actionable — that this is StrandExecutor rather than the scheduler. The issue
says so itself, which is the correct way to file this. It is blocked on an
experiment, not on a decision.

A candidate mechanism, from reading rather than measuring

include/morph/core/strand.hpp blocks on a condition_variable — no spin, no
yield, no sleep_for. So the naive "it busy-waits under load" story is out,
and that is worth knowing before anyone goes looking for it.

But :373 is _cv.notify_all(). That is the classic source of exactly the
shape reported. A strand serialises tasks, so a drain is a chain of N handoffs;
notify_all wakes every waiter at each handoff, all but one find nothing to do
and sleep again. Idle, those wasted wakeups are nearly free. With a run queue of
38 on 12 cores, each wasted wakeup costs a scheduling slot, so the wasted
work scales with both the chain length and the queue depth — which multiplies
into superlinearity, where a pure scheduler-latency story stays linear.

That fits the reported curve's direction. It is a hypothesis from one line of
code. It has not been measured, and there may be a good reason for
notify_all here — if waiters block on different predicates, notify_one can
lose a wakeup, which is a correctness bug far worse than slowness. Check why
before changing it, and check git log -S on that line: AGENTS.md's "undoing a
deliberate fix" failure mode applies squarely to condition-variable code.

What the measurement still needs

• One run per point. Three points at one run each is not a scaling law. The
  exponent ~2.1 should not be quoted as a property of anything until each point
  has several runs and a spread.
• The idle point (0.136 s) is four orders of magnitude from the loaded ones and
  is probably not on the same curve at all; fitting through it will flatter or
  distort the exponent depending on how it is weighted.
• The perf sched split the filing proposes is the right discriminator, and it
  distinguishes the two candidate causes directly. A cheaper first cut:
  instrument the wakeup count per drain and see whether it grows
  superlinearly. If wakeups stay linear while wall clock does not, the
  scheduler owns it; if wakeups blow up, the strand does.

Why it matters beyond a slow test

If the strand is the cause, this is not a test-only property. StrandExecutor
is the mechanism every model's execute() is serialised on
(docs/spec/concurrency_and_lifetimes.md), so a drain that degrades
superlinearly with machine load degrades application dispatch on a loaded
host, not just a benchmark. That is what would make it a bug rather than a
curiosity — and equally, if the scheduler owns it, there is nothing here to fix
and the issue should close saying so.

Relationship to morph#760

Correctly split rather than folded. morph#779 closes morph#760 with a timeout
change, which does not answer this, and morph#760's own re-frame clause pointed
here. Closing this one as "fixed by the timeout" would be wrong.

What would change the verdict

Promote to valid when several runs per load point confirm the exponent with a
stated spread and the wakeup-count or perf sched split attributes it. Close
as invalid if the attribution lands on the scheduler — with the numbers left
on record, because the next person to see a slow drain will ask this again.

[Yaraslaut]

The discriminator ran: wakeups are load-invariant, so the strand does not own this

PR #803 (comment and spec only — nothing about the algorithm changed).

notify_all is out, and not only by measurement

Before instrumenting anything, the line does not do what a herd needs it to do.
_cv.notify_all() sits inside the --_inFlight == 0 branch, and the re-arm
in scheduleNext increments _inFlight for the next dispatch before the
current one decrements — so the count never reaches zero across a handoff, and a
handoff signals nothing at all. ~StrandExecutor is the only waiter on _cv
(strand.hpp:66 is the only wait). So notify_all wakes at most one thread and
is semantically identical to notify_one here: there is no herd to wake, and no
second predicate for a wakeup to land on and be lost.

git log -S notify_all --follow -- include/morph/core/strand.hpp:

00d480d5 [morph] Init

One commit, the initial import. git log -S notify_one on the same path returns
nothing. It has never been notify_one — so there is no deliberate fix to
undo, and equally no history that makes notify_all load-bearing. What makes it
load-bearing is the single-waiter structure, which is now stated in a comment at
the line, because reading it invites exactly the inference this issue made.

The wakeup count per drain

An instrumented copy of the executor — counters around the notify, the drain's
wait predicate, each dispatch, and each _mapMtx acquisition (a try_lock probe
in front, so a blocking acquisition is counted) — driving the saturation case's
exact shape: 8 producers × 400 posts on one key, 3 iterations = 9600 tasks.
Synthetic spinner load. 12-thread host (Ryzen 5 7600X), clang 22.1.8, -O2,
otherwise idle.

spinners  wall_s per run              us/task    handoffs  notifies  predChk  wakeups-that-found-nothing  contended _mapMtx
   0      0.019 0.019 0.020              2.0       9600       3         6            3                     2216-2712
  12      2.11 3.53 3.60 4.71          220-490     9600       3         6            3                      777-960
  24      30.6 32.3 36.5              3186-3803    9600       3         6            3                        0-303
  36      58.9 59.2 60.4              6140-6290    9600       3         6            3                         0-81

Wakeups stay linear — flat, in fact — while wall clock does not. One handoff
per task, one notification per drain, one wakeup per drain, at every load point.
Per-task wall clock moves by three orders of magnitude across the same rows.
Contended _mapMtx acquisitions fall as load rises, because the producers get
less CPU with which to contend, so the global-mutex story goes the same way as
the herd story.

By the discriminator this issue's triage set: the scheduler owns it.

Scaled to the case's 20 iterations, those rows are 24 s / 214 s / 394 s against
the 23.8 / 170.5 / 396.4 on record — the instrument reproduces the reported curve
rather than a different one, which is the only reason to trust its counters.

Measurement hygiene, as asked

3–4 runs per point rather than one. The spread at 12 spinners is 2.11–4.71 s,
a factor of 2.2 inside one point, which is why the ~2.1 exponent should not be
quoted as a property of anything: it is within the noise of two adjacent points.
No curve is fitted and the idle point is not on the same axis as the loaded ones.
For the record, µs/task ratios: queue 14 → 38 is 2.7× the competing threads for
16.6× the cost, but 27 → 38 is 1.4× for 1.8× — so the steep part is the crossing
from just-saturated to genuinely oversubscribed, not a smooth power law.

What the cost actually is — the task's own yield()

The task body ends with std::this_thread::yield() ("Tiny window so drains and
re-arms interleave heavily"). Removing only that, changing nothing else, same
36 spinners:

spinners=36 iterations=3 (tasks/iteration=3200)
     run     wall_s    us/task   handoffs   notifies    predChk    predFalse
       0      0.025       2.62       9600          9          5            2
       1      0.018       1.87       9600         10          6            3
       2      0.035       3.60       9600         15          5            2

2.6 µs/task at 4× oversubscription: the idle figure, ~2300× faster than the
same run with the yield, with the strand untouched. A yielding thread goes to the
back of the run queue with no sleeper credit and must wait a full queue round; a
thread woken from a condition variable has sleeper credit and preempts a
CPU-bound spinner promptly. That is why the strand's own handoff path is flat in
load and the yield is not.

This also answers the triage's "why it matters beyond a slow test" — and answers
it the other way. Model::execute() does not call yield(), so application
dispatch through StrandExecutor does not degrade superlinearly with machine
load; the no-yield rows are the evidence. The thing that degrades is a task
body that yields, which is a property of the posted task.

What I did not do

• No perf sched run. The counter discriminator answered it, so the more
  expensive split was not needed; if anyone wants the per-wakeup latency
  distribution rather than the counts, that is still unmeasured.
• Did not touch the case. The yield is how it manufactures the drain/re-arm
  interleaving it exists to detect, so removing it would trade away detection
  power, and cutting kIterations would do the same — both are the mistake this
  issue's own text warns against.
• Did not change notify_all. With one waiter it would be a no-op change, and a
  no-op change to condition-variable code is worse than no change.

Verification status

• Reproduced and measured on 7a994c15, clang 22.1.8, -O2, 12-thread
  Ryzen 5 7600X, Linux 7.2.6. Counters come from a mechanically derived copy of
  strand.hpp (algorithm untouched; only counter increments and the try_lock
  probe added) compiled into a standalone harness — the repository's own header
  and test are unmodified.
• Inferred, not measured: the CFS sleeper-credit explanation for why a
  yield costs a full queue round while a cv wakeup does not. The two numbers are
  measured; the kernel-side reason for the gap is read, not traced.
• Not verified: the same experiment on another platform or scheduler. The
  original figures and these are both Linux/x86-64.
• Not verified: whether the 2.2× spread at 12 spinners is thermal, SMT
  placement, or spinner phase. It is reported, not explained.

What would change the verdict

Suggested: close invalid as a StrandExecutor defect, with these numbers
on record — which is the disposition this issue's own "what would change the
verdict" names for a scheduler attribution.

Re-open if a drain is ever observed slowing down while the handoff or
notification counts grow with it, which is the signal that would put it back
on the strand. A drain that is merely slow on a loaded host is this, and this is
the scheduler's price for a yielding task.

[Yaraslaut]

Closing invalid as a StrandExecutor defect — the scheduler owns it, and my hypothesis was structurally impossible

The discriminator this issue was waiting on has been run, and it is decisive.

Wakeups are flat while wall clock moves three orders of magnitude

Instrumented executor, the saturation case's exact shape (8×400 posts on one
key, 3 iterations = 9600 tasks), 12-core box:

spinners   wall_s              µs/task     handoffs  notifies  empty wakeups  contended _mapMtx
   0       0.019 0.019 0.020      2.0         9600       3          3            2216-2712
  12       2.11 3.53 3.60 4.71  220-490       9600       3          3             777-960
  24       30.6 32.3 36.5      3186-3803      9600       3          3               0-303
  36       58.9 59.2 60.4      6140-6290      9600       3          3                0-81

Three notifications at every load level. Contended _mapMtx acquisitions
fall as load rises, so the global-mutex story dies alongside the wakeup one.
Scaled to 20 iterations these reproduce the curve on record (24 / 214 / 394 s
against 23.8 / 170.5 / 396.4), so the instrument is measuring the same thing.

My notify_all hypothesis was wrong, and wrong structurally

I suggested a thundering herd: every waiter woken per handoff, all but one
finding nothing. That cannot happen here, and reading the code was enough to
establish it:

• strand.hpp:373's notify_all sits inside if (--_inFlight == 0) — it
  fires at quiescence, never per handoff;
• there is exactly one _cv.wait, at :66, in the destructor.

One waiter means notify_all is notify_one. git log -S notify_all returns
only the initial commit and -S notify_one returns nothing, so it was never the
other thing — there is no deliberate fix here to undo, and equally no history
making the choice load-bearing. What makes it load-bearing is the structure
above.

I should have checked the waiter count before proposing the mechanism. The
measurement was run against a hypothesis that fifteen seconds of reading would
have eliminated.

The actual cause is the test's own yield, and it is not in the dispatch path

Removing only std::this_thread::yield() from the task body drops the same
9600 tasks at 36 spinners from ~59 s to 0.018–0.035 s, 2.6 µs/task — the idle
figure, roughly 2300× faster, with the strand untouched.

A yielding thread goes to the back of the run queue with no sleeper credit; a
cv-woken thread has credit and preempts a spinner promptly. That is a scheduler
property, reproduced by subtraction.

This also refutes the claim in my triage that this would degrade application
dispatch. I wrote that a superlinear drain "degrades application dispatch on a
loaded host, not just a benchmark". execute() does not yield. The
superlinearity belongs to the case's own interleaving device, not to anything a
model's dispatch does.

The yield was correctly left in place — it is how the case manufactures the
drain/re-arm interleaving it exists to detect.

On the exponent this issue quoted

Not supportable, and worth saying so rather than leaving the number on record.
Three to four runs per point put the 12-spinner spread at 2.11–4.71 s — 2.2×
within a single point. And the shape is not a power law: 14→38 queue is 2.7×
for 16.6× cost, but 27→38 is 1.4× for 1.8×. The steep part is the
saturated→oversubscribed crossing, not an exponent.

What survives

Landed alongside: a comment at the notify explaining the single-waiter
structure, and a bullet in docs/spec/concurrency_and_lifetimes.md stating that
the drain's work is one handoff per task and one notification per quiescence
whatever the host is doing. That is the durable output — the next person to see a
slow drain finds the answer at the code rather than reopening this.

Re-open condition

Re-open if a drain is measured doing more than one handoff per task or more
than one notification per quiescence — that would be a real strand defect and
these numbers are the baseline to compare against. A slow drain alone is not
enough: measure the wakeup count first, because that is what separates the two
explanations in one run.

Not measured: any non-Linux platform, and no perf sched trace — the
counter discriminator answered the question, so the per-wakeup latency
distribution remains unknown.