flynnel 0.6.0

K-aware NUMA-aware work-stealing scheduler with extended-Flynn-taxonomy dispatch (MIMD / SIMC / MIMC / MISD / SIMT / MIMT): a rayon-shaped pool reshaped around per-call execution-class plans with first-class CPU+GPU hybrid (join_hybrid, hybrid_pipeline) and per-call dispatch profiles.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
//! Background steal-rate observer that tunes the `par_iter`
//! split-budget multiplier at runtime.
//!
//! A split budget of `workers * multiplier` is a heuristic, and this
//! multiplier is the one it scales by. When the pool is under heavy
//! contention, with a lot of cross-worker stealing, workers benefit
//! from a higher budget: more leaves spawned means finer steal
//! granularity. When the pool is mostly running owner-local work, a
//! higher budget only adds dispatch overhead with no distribution
//! benefit, so a lower one wins.
//!
//! The observer thread (hosted on the
//! [`crate::sched::io_pool::IoPool`]) samples per-worker stats
//! every 200ms, computes a global steal rate, and writes the
//! multiplier into a process-wide AtomicU32.
//!
//! What reads it is [`crate::sched::plan::JobPlan::effective_leaves_per_worker`],
//! and only for a plan whose caller did not pin a factor of their own.
//! That covers the budget-shaped dispatch entries: the triple, indexed
//! and collect helpers, the token-bucket and reduce paths, and
//! `for_each_chunk`'s probe and pinned-variant routes.
//!
//! It does not cover every dispatch. `for_each_chunk` and
//! `for_each_chunk_indexed` seed from `adaptive_seed_depth` when the
//! plan carries an authoritative per-item estimate, and that route
//! derives its leaf count from the estimate and from observed steals
//! without consulting this multiplier at all.
//!
//! ## Steal rate definition
//!
//! ```text
//! total_steals = sum over workers of stats.peer_steal_hits
//! total_pops   = sum over workers of stats.local_pops
//! steal_rate   = total_steals / (total_steals + total_pops)
//! ```
//!
//! Interpretation:
//! - `steal_rate >= 0.30`: heavy contention, peers are hungry.
//!   Recommend `multiplier = 4`.
//! - `steal_rate in [0.05, 0.30)`: moderate contention. Keep
//!   `multiplier = 2` (the baseline).
//! - `steal_rate < 0.05`: low contention. Recommend
//!   `multiplier = 1`.
//!
//! ## Activation
//!
//! Off when [`crate::sched::io_pool::global_io_pool`] is None
//! (`FLYNNEL_SCHED_SMT_AS_IO=on` to enable). Call
//! [`spawn_observer`] once at startup to begin sampling.
//!

use core::sync::atomic::{AtomicU32, Ordering};
use std::sync::OnceLock;
use std::time::Duration;

use crate::sched::arena::global_local_arena;
use crate::sched::io_pool::global_io_pool;

/// Multiplier (in units of `workers`) used by
/// [`crate::sched::par_iter::for_each_chunk`] to size its initial
/// split budget. Updated by the observer; read on the hot path.
///
/// Default `2` matches the original constant. The observer picks
/// from `{1, 2, 4}` per the steal-rate and cv^2 thresholds in
/// [`sample_and_compute`], and the final value is clamped to
/// `[1, 8]` (the max of the two axes, capped at 8). Manual
/// callers via [`set_split_multiplier`] can set any value in the
/// same `[1, 8]` clamp range.
static SPLIT_MULTIPLIER: AtomicU32 = AtomicU32::new(2);

// ---------------------------------------------------------------------------
// Per-leaf execution-time variance tracking.
// ---------------------------------------------------------------------------
//
// Steal-rate is an indirect proxy for chunk-time variance: workers
// idling = peers waiting on long chunks. But it conflates "fewer
// chunks than workers" with "uneven chunks", and the proxy lags by
// 200ms (the observer's sample period). Direct per-leaf-time
// variance is a leading indicator: a single bisect call can pick up
// leaves taking 10x different time within its own lifetime.
//
// Three counters, summed atomically across workers:
//   LEAF_TIME_SUM_NS  - sum of leaf execution times (nanoseconds)
//   LEAF_TIME_SUMSQ   - sum of (leaf_time_ns / 256)^2 (scaled to
//                       avoid u64 overflow at large workloads)
//   LEAF_COUNT        - number of leaves recorded
//
// The observer derives coefficient of variation cv^2 =
// (sumsq/N - (sum/N)^2) / (sum/N)^2 in fixed-point and bumps the
// multiplier on high-cv runs.
//
// Cost on the hot path: 3 atomic Relaxed adds per leaf. At
// MIN_LEAF_ITEMS = 256 and a 1k-100k item workload that's 4-400
// atomic adds per bisect call, well below the leaf body cost.

use core::sync::atomic::AtomicU64;

static LEAF_TIME_SUM_NS: AtomicU64 = AtomicU64::new(0);
static LEAF_TIME_SUMSQ: AtomicU64 = AtomicU64::new(0);
static LEAF_COUNT: AtomicU64 = AtomicU64::new(0);

// Items the recorded leaves covered, and the summed per-item squared
// time. A leaf's time divided by its item count is what the classifier
// can read as a property of the work: leaf times alone move when the
// scheduler changes how finely it splits, and that split is a decision
// the classifier's own output drives.
static LEAF_ITEMS: AtomicU64 = AtomicU64::new(0);
static LEAF_SUMSQ_PER_ITEM: AtomicU64 = AtomicU64::new(0);


/// Record one leaf's execution time. Called by `par_iter` leaves
/// after the body runs. Cheap: 3 Relaxed atomic adds.
///
/// `nanos` is the wall-clock elapsed time. Implementations should
/// bracket the leaf body with `read_tsc()` and convert via the
/// cpu_topology's measured TSC-to-ns ratio, OR use Instant on
/// non-x86 hosts. The conversion need not be exact for the
/// variance to be useful: relative magnitude across leaves is what
/// matters.
///
/// Hot-path callers in `par_iter::record_leaf` accumulate samples
/// in a thread-local buffer and call [`record_leaf_batch`] every
/// `LocalLeafBuffer::FLUSH_THRESHOLD` leaves instead of calling
/// this directly per leaf (the threshold is currently 4; the
/// trade-off between per-leaf atomic cost and classifier-
/// convergence latency is documented on that constant). Batching
/// drops the per-leaf cost from ~100ns (3 contended atomic
/// fetch_adds on a 16-worker host) to ~30ns.
#[inline]
pub fn record_leaf_time_ns(nanos: u64) {
    LEAF_TIME_SUM_NS.fetch_add(nanos, Ordering::Relaxed);
    let scaled = nanos >> 8;
    LEAF_TIME_SUMSQ.fetch_add(scaled.saturating_mul(scaled), Ordering::Relaxed);
    LEAF_COUNT.fetch_add(1, Ordering::Relaxed);
    // A bare time carries no item count, so it feeds the leaf
    // statistics and leaves the per-item ones untouched rather than
    // entering them as one item costing the whole leaf.
}

/// Record a batch of leaf-time samples, pre-aggregated by a
/// caller-side accumulator. Used by the per-thread sample buffer
/// in `par_iter::record_leaf` to amortize the cost of the three
/// global atomic fetch_adds across many leaves.
///
/// Mathematically equivalent to calling [`record_leaf_time_ns`]
/// once per leaf, but with the same atomic-contention cost paid
/// once per batch instead of once per leaf.
#[inline]
pub fn record_leaf_batch(
    sum_ns: u64,
    sumsq_scaled: u64,
    count: u64,
    items: u64,
    sumsq_per_item: u64,
) {
    LEAF_TIME_SUM_NS.fetch_add(sum_ns, Ordering::Relaxed);
    LEAF_TIME_SUMSQ.fetch_add(sumsq_scaled, Ordering::Relaxed);
    LEAF_ITEMS.fetch_add(items, Ordering::Relaxed);
    LEAF_SUMSQ_PER_ITEM.fetch_add(sumsq_per_item, Ordering::Relaxed);
    let prior = LEAF_COUNT.fetch_add(count, Ordering::Relaxed);
    // Drive the auto-classify-and-migrate observer at every
    // AUTO_CLASSIFY_QUANTUM-th leaf so the routing decision tracks
    // the workload's actual shape without the application calling
    // migrate_workload_class. Cheap (~2 atomic loads + a few
    // arithmetic ops + maybe one Release-store when classification
    // disagrees with active class for K rounds).
    let new_total = prior.wrapping_add(count);
    if (prior / AUTO_CLASSIFY_QUANTUM) != (new_total / AUTO_CLASSIFY_QUANTUM) {
        crate::sched::adaptive_profile::tick_auto_classify();
    }
}

/// How many recorded leaves between auto-classifier ticks. Each
/// tick reads the global LeafStats snapshot, runs
/// [`crate::sched::adaptive_profile::classify_observed`], and
/// applies the K-consecutive-disagreement migration policy. Set
/// to 16 to give the classifier enough samples to compute a
/// stable cv^2 estimate per tick. Smaller quanta (4 leaves) made
/// the classifier flap on noise -- observed cv^2 of a 4-sample
/// window can swing 10x between adjacent buckets even when the
/// true workload shape is uniform.
pub const AUTO_CLASSIFY_QUANTUM: u64 = 16;

/// Reset the variance counters. Used by tests and benches; the
/// observer also resets after each sample so consecutive samples
/// measure independent windows.
#[inline]
pub fn reset_leaf_stats() {
    LEAF_TIME_SUM_NS.store(0, Ordering::Relaxed);
    LEAF_TIME_SUMSQ.store(0, Ordering::Relaxed);
    LEAF_COUNT.store(0, Ordering::Relaxed);
    LEAF_ITEMS.store(0, Ordering::Relaxed);
    LEAF_SUMSQ_PER_ITEM.store(0, Ordering::Relaxed);
}

/// Snapshot of the variance counters. Used by the observer + tests.
#[derive(Copy, Clone, Debug)]
pub struct LeafStats {
    /// Number of leaves observed.
    pub count: u64,
    /// Sum of leaf wall-clock times (nanoseconds).
    pub sum_ns: u64,
    /// Sum of squared leaf times in fixed-point scale; the unit
    /// matches the `cv2_fixed` consumer's expected scaling.
    pub sumsq_scaled: u64,
    /// Items the observed leaves covered. Zero when no recorded leaf
    /// carried a count, which the per-item readings report as no
    /// reading rather than as zero cost.
    pub items: u64,
    /// Sum over leaves of a leaf's squared time divided by its item
    /// count, in the same fixed-point scale as `sumsq_scaled`.
    pub sumsq_per_item: u64,
}

/// Read the current variance counters atomically. Returned snapshot is
/// a point-in-time view; concurrent updates land in the next snapshot.
#[inline]
pub fn snapshot_leaf_stats() -> LeafStats {
    LeafStats {
        count: LEAF_COUNT.load(Ordering::Relaxed),
        sum_ns: LEAF_TIME_SUM_NS.load(Ordering::Relaxed),
        sumsq_scaled: LEAF_TIME_SUMSQ.load(Ordering::Relaxed),
        items: LEAF_ITEMS.load(Ordering::Relaxed),
        sumsq_per_item: LEAF_SUMSQ_PER_ITEM.load(Ordering::Relaxed),
    }
}

/// Mean observed leaf execution time in nanoseconds from recent
/// recorded leaves, or `None` when fewer than 4 leaves have been
/// recorded (statistically insignificant).
///
/// Used by `adaptive_min_leaf` in `crate::sched::par_iter` to size
/// the leaf floor for callers that did not supply an explicit
/// per-item ns hint. Observer-driven: the first dispatch on a
/// fresh process pays the classifier-default min_leaf, but
/// subsequent dispatches (criterion iter loops, multi-call
/// batches, NMFD repeated calls) use the observed mean to pick
/// a sharper granularity.
///
/// Returns the leaf-level mean rather than the per-item mean: observer
/// does not track items-per-leaf, so callers compare against
/// per-leaf overhead thresholds rather than dividing by leaf size.
#[inline]
pub fn observed_mean_leaf_ns() -> Option<u64> {
    let stats = snapshot_leaf_stats();
    if stats.count < 4 {
        return None;
    }
    Some(stats.sum_ns / stats.count)
}

/// Mean cost of one item across the recorded leaves, in nanoseconds, or
/// `None` below 4 leaves and when no leaf carried an item count.
///
/// The process-wide counterpart of
/// [`crate::sched::call_site::CallSiteState::per_item_ns`], and what
/// the classifier's per-item bands are stated in.
#[inline]
pub fn observed_per_item_ns(stats: LeafStats) -> Option<u64> {
    if stats.count < 4 || stats.items == 0 {
        return None;
    }
    Some(stats.sum_ns / stats.items)
}

/// cv^2 per mille of per-item cost, weighted by the items each leaf
/// covered, or `None` on the same terms as [`observed_per_item_ns`].
///
/// Also `None` when the mean item costs under 256 ns. The squares are
/// kept in units of 2^16 square nanoseconds, so a smaller mean squares
/// to zero and no spread about it can be read; zero would say the items
/// were uniform, which nothing measured.
///
/// Unlike [`leaf_cv_squared_per_mille`] this does not move when the
/// scheduler splits the same work into leaves of different sizes, which
/// is what lets a class describe the workload rather than the split.
pub fn per_item_cv_squared_per_mille(stats: LeafStats) -> Option<u64> {
    if stats.count < 4 || stats.items == 0 {
        return None;
    }
    // Squared in 128 bits and scaled once, as the recorder forms each
    // leaf's term: scaling the mean first subtracts a smaller square
    // than the terms carry, and the difference reads as spread.
    let mean_ns = stats.sum_ns / stats.items;
    let mean_sq = ((mean_ns as u128).saturating_mul(mean_ns as u128) >> 16) as u64;
    if mean_sq == 0 {
        return None;
    }
    let spread = stats
        .sumsq_per_item
        .saturating_sub(mean_sq.saturating_mul(stats.items));
    // Over the items, not the leaves: each leaf contributed its squared
    // time over its item count, so the subtraction leaves an
    // item-weighted sum of squared deviations.
    let var = spread / stats.items;
    Some(var.saturating_mul(1000) / mean_sq)
}

/// Coefficient of variation squared (cv^2 = var/mean^2) of leaf times
/// in fixed-point parts-per-1000. Returns `None` when fewer than 4
/// leaves have been recorded (statistically insignificant), and when
/// the mean leaf is under 256 ns: each leaf's time is squared after a
/// shift by 8, so leaves that short all scale to the same few units and
/// their spread cannot be read. Zero would say they were uniform, and a
/// reader acting on that, such as the SMT decision of a plan with no
/// call site, would act on a measurement nobody took.
///
/// It is the spread of whole leaves, so it moves when the same work is
/// split into leaves of different sizes. That is what the split
/// multiplier wants to know, and it is what a class must not be decided
/// on, since the class decides the split;
/// [`per_item_cv_squared_per_mille`] is the reading that holds still.
///
/// cv^2 interpretation:
/// - `0..50` (cv < ~0.22): leaves are nearly uniform. Static SLAW
///   budget is optimal; multiplier=1 is fine.
/// - `50..500` (0.22 <= cv < ~0.71): moderate spread. Baseline
///   multiplier=2 is the right call.
/// - `>= 500` (cv >= ~0.71): high variance. Recommend multiplier=4
///   so steal pressure can rebalance long leaves.
pub fn leaf_cv_squared_per_mille(stats: LeafStats) -> Option<u64> {
    if stats.count < 4 {
        return None;
    }
    let n = stats.count;
    let mean_scaled = (stats.sum_ns >> 8) / n;
    if mean_scaled == 0 {
        return None;
    }
    let sumsq_per_n = stats.sumsq_scaled / n;
    let mean_sq = mean_scaled.saturating_mul(mean_scaled);
    let var = sumsq_per_n.saturating_sub(mean_sq);
    Some(var.saturating_mul(1000) / mean_sq.max(1))
}

/// Read the current split-budget multiplier. Cheap atomic load
/// (single instruction on x86 with Relaxed ordering).
#[inline]
pub fn split_multiplier() -> u32 {
    SPLIT_MULTIPLIER.load(Ordering::Relaxed)
}

/// Set the split multiplier manually. Intended for tests or for
/// callers that want to lock the multiplier to a known value.
/// In production, [`spawn_observer`] handles updates.
pub fn set_split_multiplier(value: u32) {
    let clamped = value.clamp(1, 8);
    SPLIT_MULTIPLIER.store(clamped, Ordering::Relaxed);
}

/// Spawn the background observer. The first call schedules an
/// ever-self-respawning task on the IoPool; subsequent calls are
/// no-ops (the `OnceLock` ensures single-instance semantics).
///
/// No-op when the IoPool is disabled - the heuristic baseline
/// multiplier remains.
///
/// The observer task body:
/// 1. Sleep 200ms (the sampling interval).
/// 2. Sum stats across all workers via
///    [`crate::sched::arena_numa::NumaArena::iter_worker_stats`].
/// 3. Compute steal rate; update SPLIT_MULTIPLIER.
/// 4. Resubmit itself to the IoPool so the next sample fires in
///    200ms.
///
/// The resubmit pattern avoids holding an IoPool thread captive in
/// a loop (which would tie up that worker for the program's
/// lifetime). Each sample run is short (sleep + ~8 atomic loads +
/// 1 atomic store) so even if it lands on a different IoPool
/// thread each time, cache locality is minimal.
pub fn spawn_observer() {
    static STARTED: OnceLock<()> = OnceLock::new();
    STARTED.get_or_init(|| {
        if global_io_pool().is_none() {
            // SMT_AS_IO disabled; keep heuristic baseline.
            return;
        }
        schedule_next_sample();
    });
}

fn schedule_next_sample() {
    let Some(pool) = global_io_pool() else { return };
    pool.submit(|| {
        std::thread::sleep(Duration::from_millis(200));
        let new_mult = sample_and_compute();
        SPLIT_MULTIPLIER.store(new_mult, Ordering::Relaxed);
        // Tail-respawn: schedule the next sample.
        schedule_next_sample();
    });
}

/// Events a sampled window needs before its steal rate is read.
const MIN_WINDOW_EVENTS: u64 = 100;

/// The multiplier a sampled window implies.
///
/// `cv2` is the leaf spread in parts per mille, absent when fewer than
/// four leaves were timed or when they were too short for their spread
/// to be read. A window carrying fewer than `MIN_WINDOW_EVENTS` events
/// returns `current` unchanged.
fn multiplier_for_window(
    total_pops: u64,
    total_steals: u64,
    cv2: Option<u64>,
    current: u32,
) -> u32 {
    let total = total_pops.saturating_add(total_steals);
    if total < MIN_WINDOW_EVENTS {
        return current;
    }
    // Steal rate in fixed-point parts per 1000, keeping float out of
    // the observer hot path.
    let steal_per_mille: u64 = (total_steals * 1000) / total;
    let from_steal = if steal_per_mille >= 300 {
        4u32
    } else if steal_per_mille >= 50 {
        2u32
    } else {
        1u32
    };

    // Per-leaf variance is an orthogonal signal: some leaves take much
    // longer than others even where the steal rate reads low because
    // workers are individually busy. More leaves let steals rebalance
    // the long ones onto idle workers.
    let from_variance = match cv2 {
        Some(cv2) if cv2 >= 500 => 4u32,
        Some(cv2) if cv2 >= 50 => 2u32,
        Some(_) => 1u32,
        None => from_steal,
    };

    // The max of the two signals, so a high reading on either axis
    // bumps the multiplier. Capped at 8 to bound the budget.
    from_steal.max(from_variance).min(8)
}

/// One sampling pass. Reads counters, computes steal rate,
/// derives the new multiplier. Public for testing.
pub fn sample_and_compute() -> u32 {
    let arena = global_local_arena();
    let mut total_pops: u64 = 0;
    let mut total_steals: u64 = 0;
    for stats in arena.iter_worker_stats() {
        total_pops = total_pops.saturating_add(
            stats.local_pops.load(Ordering::Relaxed),
        );
        total_steals = total_steals.saturating_add(
            stats.peer_steal_hits.load(Ordering::Relaxed),
        );
    }
    let current = SPLIT_MULTIPLIER.load(Ordering::Relaxed);
    if total_pops.saturating_add(total_steals) < MIN_WINDOW_EVENTS {
        return current;
    }
    let cv2 = leaf_cv_squared_per_mille(snapshot_leaf_stats());
    let mult = multiplier_for_window(total_pops, total_steals, cv2, current);
    // Reset for the next sample window so the next reading does not
    // count these leaves again.
    reset_leaf_stats();
    mult
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn split_multiplier_starts_at_baseline_two() {
        // Test isolation: this test reads the process-global atomic so
        // run-order can affect it. Allow either 2 (baseline) or
        // whatever set_split_multiplier left it at from earlier
        // tests in the same process.
        let m = split_multiplier();
        assert!((1..=8).contains(&m), "multiplier should be in [1, 8]");
    }

    #[test]
    fn set_split_multiplier_clamps_to_valid_range() {
        set_split_multiplier(100);
        assert_eq!(split_multiplier(), 8);
        set_split_multiplier(0);
        assert_eq!(split_multiplier(), 1);
        // Restore baseline so we don't pollute other tests.
        set_split_multiplier(2);
    }

    #[test]
    fn spawn_observer_noop_when_pool_disabled() {
        // FLYNNEL_SCHED_SMT_AS_IO is not set in the test env;
        // global_io_pool() returns None and spawn_observer is
        // a no-op.
        let t0 = std::time::Instant::now();
        spawn_observer();
        assert!(
            t0.elapsed() < Duration::from_millis(50),
            "spawn_observer should return immediately"
        );
    }

    // The counters are process-global and every dispatch in the suite
    // writes them, so a test that resets them, records, and reads back
    // an exact total is reading whatever else was running as well. The
    // readings below are computed over a `LeafStats` value built the way
    // `record_leaf_time_ns` builds the counters, which no other test can
    // touch; the one test that goes through the global recorder asserts
    // deltas as floors, since a neighbor's leaves can only add.
    fn stats_of_leaf_times(leaf_ns: &[u64]) -> LeafStats {
        let mut s = LeafStats {
            count: 0,
            sum_ns: 0,
            sumsq_scaled: 0,
            items: 0,
            sumsq_per_item: 0,
        };
        for &nanos in leaf_ns {
            let scaled = nanos >> 8;
            s.count += 1;
            s.sum_ns += nanos;
            s.sumsq_scaled += scaled.saturating_mul(scaled);
        }
        s
    }

    #[test]
    fn recording_a_leaf_adds_its_time_and_one_to_the_counters() {
        let before = snapshot_leaf_stats();
        record_leaf_time_ns(1_000);
        record_leaf_time_ns(2_000);
        record_leaf_time_ns(3_000);
        let after = snapshot_leaf_stats();
        let expected = stats_of_leaf_times(&[1_000, 2_000, 3_000]);
        assert!(
            after.count.wrapping_sub(before.count) >= expected.count,
            "three leaves recorded, the count rose by {}",
            after.count.wrapping_sub(before.count)
        );
        assert!(
            after.sum_ns.wrapping_sub(before.sum_ns) >= expected.sum_ns,
            "{} ns recorded, the sum rose by {}",
            expected.sum_ns,
            after.sum_ns.wrapping_sub(before.sum_ns)
        );
        assert!(
            after.sumsq_scaled.wrapping_sub(before.sumsq_scaled) >= expected.sumsq_scaled,
            "the scaled squares rose by {} against {} recorded",
            after.sumsq_scaled.wrapping_sub(before.sumsq_scaled),
            expected.sumsq_scaled
        );
    }

    #[test]
    fn leaf_cv_squared_handles_insufficient_samples() {
        let s = stats_of_leaf_times(&[1_000, 1_000, 1_000]);
        assert!(
            leaf_cv_squared_per_mille(s).is_none(),
            "fewer than 4 leaves should return None"
        );
    }

    #[test]
    fn leaf_cv_squared_zero_for_uniform_leaves() {
        // 8 leaves, identical time = 0 variance.
        let s = stats_of_leaf_times(&[10_000; 8]);
        let cv2 = leaf_cv_squared_per_mille(s).unwrap();
        // Allow small fixed-point rounding error from the >>8 scaling.
        assert!(cv2 < 20, "uniform leaves should have cv^2 ~ 0; got {cv2}");
    }

    #[test]
    fn leaf_cv_squared_high_for_spread_leaves() {
        // Mix of fast and slow leaves: half at 1us, half at 100us.
        // cv = sqrt(((100-50.5)^2 + (1-50.5)^2)/2) / 50.5 ~ 49.5/50.5 ~ 0.98.
        // cv^2 ~ 0.96 ~ 960 per mille.
        let s = stats_of_leaf_times(&[
            1_000, 1_000, 1_000, 1_000, 100_000, 100_000, 100_000, 100_000,
        ]);
        let cv2 = leaf_cv_squared_per_mille(s).unwrap();
        assert!(
            cv2 >= 500,
            "spread leaves should have cv^2 >= 500; got {cv2}"
        );
    }

    #[test]
    fn leaves_shorter_than_the_unit_have_no_spread_rather_than_none_of_one() {
        // 100 and 200 ns both scale to zero units, so a zero here would
        // read as uniform leaves that were never told apart.
        let s = stats_of_leaf_times(&[100, 200, 100, 200, 100, 200, 100, 200]);
        assert_eq!(leaf_cv_squared_per_mille(s), None);
    }

    #[test]
    fn items_cheaper_than_the_unit_have_no_per_item_spread() {
        // Eight leaves of 1024 items at 100 ns an item. Every counter
        // is filled, and the mean still squares to nothing in units of
        // 2^16, while the leaves themselves are long enough to read.
        let leaf = 100u64 * 1024;
        let per_item_sq = ((leaf as u128 * leaf as u128) / (1024u128 << 16)) as u64;
        let s = LeafStats {
            count: 8,
            sum_ns: 8 * leaf,
            sumsq_scaled: 8 * (leaf >> 8) * (leaf >> 8),
            items: 8 * 1024,
            sumsq_per_item: 8 * per_item_sq,
        };
        assert_eq!(observed_per_item_ns(s), Some(100));
        assert_eq!(per_item_cv_squared_per_mille(s), None);
        assert!(leaf_cv_squared_per_mille(s).is_some());
    }

    #[test]
    fn a_window_too_sparse_to_read_keeps_the_current_multiplier() {
        assert_eq!(multiplier_for_window(40, 9, None, 3), 3);
        assert_eq!(multiplier_for_window(40, 9, Some(900), 3), 3);
    }

    #[test]
    fn the_window_multiplier_takes_the_higher_of_its_two_signals() {
        // No steals, wide leaves: the variance axis carries it.
        assert_eq!(multiplier_for_window(1000, 0, Some(900), 1), 4);
        // Half the events stolen, even leaves: the steal axis does.
        assert_eq!(multiplier_for_window(500, 500, Some(0), 1), 4);
        // Neither axis reads high.
        assert_eq!(multiplier_for_window(1000, 0, Some(0), 1), 1);
    }

    #[test]
    fn a_window_with_no_timed_leaves_reads_its_steal_rate_alone() {
        assert_eq!(multiplier_for_window(500, 500, None, 1), 4);
        assert_eq!(multiplier_for_window(1000, 0, None, 1), 1);
    }
}