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
//! Fcl (Fat Chase-Lev): K_inner=3 Chase-Lev with shared counter.
//!
//! Wraps [`crate::sched::chase_lev_local`] with a 3-job batched slot
//! type ([`FatSlot`]) so each push from the producer's perspective
//! accumulates into a 64-byte cache-line slot that ultimately costs
//! one Chase-Lev push + one cache-line steal-coherence-transfer to
//! deliver 3 jobs to a thief. The amortization win: per-item
//! Chase-Lev cost is divided by 3.
//!
//! ## When Fcl wins
//!
//! Producer-fast patterns where the owner emits many jobs rapidly:
//! - Recursive splits (parallel for, divide-and-conquer reductions)
//! - Batched task submission (loop-body parallelism)
//! - Burst-y push from a single-thread driver
//!
//! ## When Fcl does not win (and falls back gracefully)
//!
//! Single-push call sites (classic `join(a, b)` where the parent
//! pushes a single right-half then runs the left half inline) get no
//! batching benefit. The single right-half sits unflushed in the
//! owner buffer where thieves cannot see it; we provide an explicit
//! [`SchedFclDeque::flush`] for sites that know to publish before
//! waiting.
//!
//! The adaptive WorkerCtx carries both Fcl and KHL backings and
//! swaps by tag.
//!
//! ## Slot layout (exactly 64 bytes)
//!
//! ```text
//! +----+----+----+----+--------+---------------------------------+
//! | n  | ko | nh | va | _pad 12| items: [CompactJobRef; 3] (48B) |
//! +----+----+----+----+--------+---------------------------------+
//! ```
//!
//! `n_items` counts how many of the 3 slots are filled (1..=3).
//! `k_outer / numa_hint / variant` are shared across the slot's 3
//! jobs: recursive splits emit children with identical metadata,
//! and the shared header is what lets 3 jobs fit one 64-byte line.
//!
//! Slot is `#[repr(C, align(64))]` so it always starts on a cache-
//! line boundary.

#![allow(clippy::missing_errors_doc)]

use core::cell::UnsafeCell;
use core::mem::MaybeUninit;

use crate::sched::chase_lev_local::{self, new_chase_lev};
use crate::sched::job::{CompactJobRef, JobRef};

/// Items per Fcl slot. 3 is the cache-line-fit number for K_inner=3
/// (16-byte CompactJobRef * 3 = 48 bytes + 16-byte header = 64 B).
pub const FCL_LINE_ITEMS: usize = 3;

/// Fat Chase-Lev slot: shared metadata header + 3 inline
/// [`CompactJobRef`]s. Exactly 64 bytes.
#[repr(C, align(64))]
pub(crate) struct FatSlot {
    /// Filled count, 1..=3. The owner-side accumulator increments
    /// this as items arrive; on flush it stamps the slot into the
    /// underlying Chase-Lev deque.
    pub(crate) n_items: u8,
    /// `K_outer = log2(n_limbs)` for all jobs in this slot. Shared
    /// per the handoff's shared-header design.
    pub(crate) k_outer: u8,
    /// NUMA hint for all jobs in this slot.
    pub(crate) numa_hint: u8,
    /// Variant for all jobs in this slot.
    pub(crate) variant: u8,
    /// Padding so the items array starts at offset 16.
    pub(crate) _pad: [u8; 12],
    /// Compact-ref payload. `items[..n_items]` are valid; the rest
    /// are uninitialized slack (the pop / steal path honors
    /// `n_items` to avoid touching them).
    pub(crate) items: [CompactJobRef; FCL_LINE_ITEMS],
}

impl FatSlot {
    /// Construct an empty slot with `n_items = 0` and the named
    /// shared metadata. Used to initialize the owner accumulator.
    #[inline]
    pub(crate) fn empty(k_outer: u8, numa_hint: u8, variant: u8) -> Self {
        Self {
            n_items: 0,
            k_outer,
            numa_hint,
            variant,
            _pad: [0u8; 12],
            // Initialize with null sentinels; the pop / steal path
            // never touches indices >= n_items.
            items: [
                CompactJobRef::null(),
                CompactJobRef::null(),
                CompactJobRef::null(),
            ],
        }
    }
}

/// Snapshot of a popped or stolen slot. The caller is responsible
/// for executing each `items[i]` for `i < n_items` exactly once.
pub struct PoppedSlot {
    /// Number of valid items in `items` (1..=3). Items beyond this
    /// index are unspecified.
    pub n_items: u8,
    /// Shared `k_outer` metadata for the slot's items.
    pub k_outer: u8,
    /// Shared NUMA hint metadata for the slot's items.
    pub numa_hint: u8,
    /// Shared variant metadata for the slot's items.
    pub variant: u8,
    pub(crate) items: [CompactJobRef; FCL_LINE_ITEMS],
}

impl core::fmt::Debug for PoppedSlot {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_struct("PoppedSlot")
            .field("n_items", &self.n_items)
            .field("k_outer", &self.k_outer)
            .field("numa_hint", &self.numa_hint)
            .field("variant", &self.variant)
            .finish_non_exhaustive()
    }
}

impl PoppedSlot {
    #[inline]
    fn from_slot(s: FatSlot) -> Self {
        Self {
            n_items: s.n_items,
            k_outer: s.k_outer,
            numa_hint: s.numa_hint,
            variant: s.variant,
            items: s.items,
        }
    }

    /// Crate-internal accessor for the underlying compact-ref
    /// array. Used by the [`super::fcl_worker::FclStash`] adapter
    /// to drain stash items without going through the LIFO-execute
    /// path. Caller must respect `n_items` to avoid touching
    /// padding slots.
    #[inline]
    pub(crate) fn compact_items_for_adapter(&self) -> &[CompactJobRef; FCL_LINE_ITEMS] {
        &self.items
    }

    /// Execute every item in this slot in LIFO order
    /// (`items[n_items-1]` first). Useful in single-thief drain
    /// loops; multi-thief code may execute in any order.
    ///
    /// # Safety
    ///
    /// Each item's captured-state pointer must still be valid; the
    /// slot's underlying job handles must not have been executed
    /// already. PoppedSlot is single-use - call this exactly once
    /// per slot.
    #[inline]
    pub unsafe fn execute_all_lifo(self) {
        for i in (0..self.n_items as usize).rev() {
            // SAFETY: items[i] is in the active prefix; the
            // caller-side contract on PoppedSlot says each item is
            // executed exactly once by execute_all_lifo.
            unsafe { self.items[i].execute() }
        }
    }
}

/// Fcl deque: owner accumulator + underlying
/// [`chase_lev_local::Worker`].
pub struct SchedFclDeque {
    inner: chase_lev_local::Worker<FatSlot>,
    /// Owner-side accumulator. Single-owner so UnsafeCell suffices;
    /// access is single-threaded by the Chase-Lev owner invariant.
    accumulator: UnsafeCell<MaybeUninit<FatSlot>>,
}

// SAFETY: only the owner thread accesses `accumulator`; Chase-Lev's
// owner-private invariant makes the UnsafeCell access single-
// threaded. The underlying Worker handles its own thread-safety.
unsafe impl Send for SchedFclDeque {}

/// Thief handle for a [`SchedFclDeque`]. Clonable.
pub struct FclStealer {
    inner: chase_lev_local::Stealer<FatSlot>,
}

impl Clone for FclStealer {
    fn clone(&self) -> Self {
        Self {
            inner: self.inner.clone(),
        }
    }
}

/// Construct a new Fcl deque with `capacity` slots (each slot holds
/// up to [`FCL_LINE_ITEMS`] jobs). Returns owner + one thief
/// handle.
pub fn new_fcl(capacity: usize) -> (SchedFclDeque, FclStealer) {
    let (w, s) = new_chase_lev::<FatSlot>(capacity);
    let acc = UnsafeCell::new(MaybeUninit::new(FatSlot::empty(0, 0, 0)));
    (
        SchedFclDeque {
            inner: w,
            accumulator: acc,
        },
        FclStealer { inner: s },
    )
}

impl SchedFclDeque {
    /// Buffer a `JobRef` into the owner accumulator. When the
    /// accumulator fills (`n_items == 3`) the slot is flushed to
    /// the underlying Chase-Lev. Infallible: on inner-full, spins
    /// until a thief frees capacity.
    ///
    /// Back-pressure rationale: the inner deque is owner-private,
    /// sized at construction. The only way it fills is if thieves
    /// cannot keep up; spinning at the push site hands time
    /// naturally to thieves. The bench harness sizes inner
    /// capacity to absorb typical bursts.
    ///
    /// The first push of a fresh accumulator stamps the slot's
    /// shared metadata from the JobRef. Subsequent pushes inherit
    /// that metadata; if the caller pushes jobs with different
    /// metadata, the first push wins. (The metadata is dispatch
    /// hints; execute() never reads it.)
    #[inline(always)]
    pub fn push(&self, job: JobRef) {
        // SAFETY: owner-private accumulator; single-threaded access
        // by Chase-Lev convention.
        let acc = unsafe { (*self.accumulator.get()).assume_init_mut() };
        if acc.n_items == 0 {
            acc.k_outer = job.k_outer;
            acc.numa_hint = job.numa_hint;
            acc.variant = job.variant;
        }
        let idx = acc.n_items as usize;
        // SAFETY: idx == n_items (pre-increment); n_items < 3 by
        // the auto-flush below resetting to 0; bounds-check-free.
        unsafe { *acc.items.get_unchecked_mut(idx) = job.compact(); }
        acc.n_items += 1;
        // JobRef has no Drop; dropping `job` here is byte-discard
        // with no cleanup. Captured-state ownership has moved into
        // the accumulator's compact slot.
        if acc.n_items == FCL_LINE_ITEMS as u8 {
            let slot = core::mem::replace(acc, FatSlot::empty(0, 0, 0));
            self.flush_slot(slot);
        }
    }

    /// Cold path: flush a full slot to the inner Chase-Lev, spin
    /// on inner-full. Hoisted out of `push` so the hot path stays
    /// linear in the instruction stream.
    #[cold]
    #[inline(never)]
    fn flush_slot(&self, slot: FatSlot) {
        let mut s = slot;
        loop {
            match self.inner.push(s) {
                Ok(()) => return,
                Err(retry) => {
                    s = retry;
                    std::hint::spin_loop();
                }
            }
        }
    }

    /// Non-blocking single push: refuses with `Err(job)` instead of
    /// spinning when the inner deque is full. A pending burst is
    /// flushed first under the same rule; on refusal the accumulator
    /// is left as it was. Twin of the KHL
    /// [`super::khl_local::SchedKhlDeque::try_push_one`].
    #[inline]
    pub fn try_push_one(&self, job: JobRef) -> Result<(), JobRef> {
        // SAFETY: owner-private accumulator; single-threaded access.
        let acc = unsafe { (*self.accumulator.get()).assume_init_mut() };
        if acc.n_items != 0 {
            let pending = core::mem::replace(acc, FatSlot::empty(0, 0, 0));
            if let Err(returned) = self.inner.push(pending) {
                *acc = returned;
                return Err(job);
            }
        }
        let mut slot = FatSlot::empty(job.k_outer, job.numa_hint, job.variant);
        slot.items[0] = job.compact();
        slot.n_items = 1;
        self.inner.push(slot).map_err(|slot| {
            // SAFETY: the slot was built from `job` just above and
            // never published; once-only ownership returns intact.
            unsafe { slot.items[0].to_jobref(slot.k_outer, slot.numa_hint, slot.variant) }
        })
    }

    /// Force-flush any buffered items to the underlying Chase-Lev.
    /// Infallible: spins on inner-full like `push` does (same
    /// back-pressure semantics).
    #[inline]
    pub fn flush(&self) {
        // SAFETY: owner-private accumulator.
        let acc = unsafe { (*self.accumulator.get()).assume_init_mut() };
        if acc.n_items == 0 {
            return;
        }
        let slot = core::mem::replace(acc, FatSlot::empty(0, 0, 0));
        self.flush_slot(slot);
    }

    /// Pop one slot's worth of work. Drains the owner accumulator
    /// first (LIFO ordering across slots: most-recent push first),
    /// then falls through to the underlying Chase-Lev.
    pub fn pop(&self) -> Option<PoppedSlot> {
        // SAFETY: owner-private accumulator.
        let acc = unsafe { (*self.accumulator.get()).assume_init_mut() };
        if acc.n_items > 0 {
            let slot = core::mem::replace(acc, FatSlot::empty(0, 0, 0));
            return Some(PoppedSlot::from_slot(slot));
        }
        match self.inner.pop() {
            chase_lev_local::Steal::Success(s) => Some(PoppedSlot::from_slot(s)),
            chase_lev_local::Steal::Empty | chase_lev_local::Steal::Retry => None,
        }
    }

    /// Clone a fresh thief handle.
    #[inline]
    pub fn stealer(&self) -> FclStealer {
        FclStealer {
            inner: self.inner.stealer(),
        }
    }
}

impl Drop for SchedFclDeque {
    fn drop(&mut self) {
        // Drop the accumulator's FatSlot in place so any held items
        // run their destructors (compact refs are pointer-only and
        // have no Drop; the slot itself is POD-shaped, so this is
        // mostly hygiene for the future where slots might carry
        // owned data).
        //
        // SAFETY: owner-private accumulator; we hold &mut self so no
        // concurrent access is possible.
        unsafe {
            (*self.accumulator.get()).assume_init_drop();
        }
    }
}

impl FclStealer {
    /// Steal one slot's worth of work. The slot may carry 1-3
    /// items; caller honors `n_items`.
    #[inline]
    pub fn steal(&self) -> chase_lev_local::Steal<PoppedSlot> {
        match self.inner.steal() {
            chase_lev_local::Steal::Success(s) => {
                chase_lev_local::Steal::Success(PoppedSlot::from_slot(s))
            }
            chase_lev_local::Steal::Empty => chase_lev_local::Steal::Empty,
            chase_lev_local::Steal::Retry => chase_lev_local::Steal::Retry,
        }
    }

    /// Architectural prefetch hint for the next steal target.
    #[inline]
    pub fn prefetch_for_steal(&self) {
        self.inner.prefetch_for_steal();
    }

    /// Approximate is-empty snapshot. Same semantics as the
    /// underlying [`chase_lev_local::Stealer::is_empty`]: a hint,
    /// not a guarantee, since concurrent activity may invalidate
    /// the snapshot immediately.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.inner.is_empty()
    }
}

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

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

    #[test]
    fn slot_is_exactly_one_cache_line() {
        assert_eq!(core::mem::size_of::<FatSlot>(), 64,
            "FatSlot must be exactly 64 bytes (one cache line)");
        assert_eq!(core::mem::align_of::<FatSlot>(), 64,
            "FatSlot must be 64-byte aligned");
    }

    #[test]
    fn compact_jobref_is_two_words() {
        assert_eq!(core::mem::size_of::<CompactJobRef>(), 16,
            "CompactJobRef must be 16 bytes");
    }

    // ---- Functional tests using a fake JobRef-shaped payload ---

    use crate::sched::job::StackJob;
    use crate::sched::latch::CoreLatch;
    use crate::foundation::Variant;

    /// A full inner deque with no consumer refuses the next push
    /// and hands the job back; one steal makes the same push
    /// succeed.
    #[test]
    fn try_push_one_refuses_when_inner_full() {
        let (deque, stealer) = new_fcl(4);
        let jobs: Vec<_> = (0..5u32)
            .map(|i| StackJob::new(move |_| i, CoreLatch::new()))
            .collect();
        for job in &jobs[..4] {
            let r = unsafe { job.as_job_ref(8, 0, Variant::Faithful) };
            assert!(deque.try_push_one(r).is_ok());
        }
        let fifth = unsafe { jobs[4].as_job_ref(8, 0, Variant::Faithful) };
        let refused = match deque.try_push_one(fifth) {
            Err(job) => job,
            Ok(()) => panic!("fifth push into a 4-slot deque must be refused"),
        };
        match stealer.steal() {
            chase_lev_local::Steal::Success(s) => unsafe { s.execute_all_lifo() },
            other => panic!("expected Success, got {other:?}"),
        }
        assert!(deque.try_push_one(refused).is_ok());
        for _ in 0..4 {
            match stealer.steal() {
                chase_lev_local::Steal::Success(s) => unsafe { s.execute_all_lifo() },
                other => panic!("expected Success, got {other:?}"),
            }
        }
        assert!(jobs.iter().all(|j| j.latch.is_set()));
        assert!(matches!(stealer.steal(), chase_lev_local::Steal::Empty));
    }

    #[test]
    fn push_single_then_flush_then_steal() {
        let (deque, stealer) = new_fcl(4);
        let job = StackJob::new(|_stolen| 7u32, CoreLatch::new());
        let r = unsafe { job.as_job_ref(8, 0, Variant::Faithful) };
        deque.push(r);
        // Without flush, the item sits in the accumulator; steal
        // sees nothing.
        assert!(matches!(stealer.steal(), chase_lev_local::Steal::Empty));
        deque.flush();
        // Now the slot is in the deque; steal should return it.
        match stealer.steal() {
            chase_lev_local::Steal::Success(s) => {
                assert_eq!(s.n_items, 1);
                // Execute and verify latch.
                unsafe { s.execute_all_lifo(); }
                assert!(job.latch.is_set());
                let result = unsafe { job.into_result() };
                assert_eq!(result, 7);
            }
            other => panic!("expected Success, got {other:?}"),
        }
    }

    #[test]
    fn buffer_fills_to_3_then_auto_flushes() {
        let (deque, stealer) = new_fcl(4);
        let j1 = StackJob::new(|_| 1u32, CoreLatch::new());
        let j2 = StackJob::new(|_| 2u32, CoreLatch::new());
        let j3 = StackJob::new(|_| 3u32, CoreLatch::new());
        let r1 = unsafe { j1.as_job_ref(8, 0, Variant::Faithful) };
        let r2 = unsafe { j2.as_job_ref(8, 0, Variant::Faithful) };
        let r3 = unsafe { j3.as_job_ref(8, 0, Variant::Faithful) };
        deque.push(r1);
        deque.push(r2);
        // First two are buffered; steal still sees empty.
        assert!(matches!(stealer.steal(), chase_lev_local::Steal::Empty));
        deque.push(r3);
        // Third push triggers auto-flush; the slot is in the inner deque.
        match stealer.steal() {
            chase_lev_local::Steal::Success(s) => {
                assert_eq!(s.n_items, 3);
                unsafe { s.execute_all_lifo(); }
                assert!(j1.latch.is_set());
                assert!(j2.latch.is_set());
                assert!(j3.latch.is_set());
                assert_eq!(unsafe { j1.into_result() }, 1);
                assert_eq!(unsafe { j2.into_result() }, 2);
                assert_eq!(unsafe { j3.into_result() }, 3);
            }
            other => panic!("expected Success, got {other:?}"),
        }
    }

    #[test]
    fn owner_pop_drains_accumulator_first_lifo() {
        let (deque, _stealer) = new_fcl(4);
        let j1 = StackJob::new(|_| 10u32, CoreLatch::new());
        let j2 = StackJob::new(|_| 20u32, CoreLatch::new());
        let r1 = unsafe { j1.as_job_ref(4, 0, Variant::Fast) };
        let r2 = unsafe { j2.as_job_ref(4, 0, Variant::Fast) };
        deque.push(r1);
        deque.push(r2);
        // Owner pop drains the accumulator (n_items=2).
        match deque.pop() {
            Some(slot) => {
                assert_eq!(slot.n_items, 2);
                // Execute in LIFO: item 1 = r2, item 0 = r1.
                unsafe { slot.execute_all_lifo(); }
                assert!(j1.latch.is_set());
                assert!(j2.latch.is_set());
            }
            None => panic!("expected Some(slot)"),
        }
        // Subsequent pop is empty.
        assert!(deque.pop().is_none());
    }

    #[test]
    #[allow(clippy::type_complexity)]
    fn batched_push_then_steal_round_trip() {
        // Producer-fast pattern: push 9 items (3 batches),
        // steal them as 3 slots.
        let (deque, stealer) = new_fcl(8);
        let jobs: Vec<StackJob<CoreLatch, fn(bool) -> u32, u32>> =
            (0..9).map(|_| StackJob::new(default_job_fn as fn(bool) -> u32, CoreLatch::new())).collect();
        for j in &jobs {
            let r = unsafe { j.as_job_ref(4, 0, Variant::Fast) };
            deque.push(r);
        }
        // After 9 pushes, accumulator empty (3 auto-flushes).
        // Three slots are in the inner deque.
        let mut executed = 0;
        for _ in 0..3 {
            match stealer.steal() {
                chase_lev_local::Steal::Success(s) => {
                    assert_eq!(s.n_items, 3);
                    executed += s.n_items as usize;
                    unsafe { s.execute_all_lifo(); }
                }
                other => panic!("expected Success, got {other:?}"),
            }
        }
        assert_eq!(executed, 9);
        // No more slots.
        assert!(matches!(stealer.steal(), chase_lev_local::Steal::Empty));
    }

    fn default_job_fn(_stolen: bool) -> u32 { 0 }
}