use std::panic;
use crate::sched::arena::{global_local_arena, join};
use crate::sched::arena_local::{WorkerCtx, current_worker_ctx};
use crate::sched::job::{NUMA_HINT_ANY, StackJob};
use crate::sched::latch::{CountLatch, LockLatch};
use crate::sched::plan::JobPlan;
pub fn cooperative_join_n<R>(
plan: &JobPlan,
closures: Vec<Box<dyn FnOnce() -> R + Send>>,
) -> Vec<R>
where
R: Send + 'static,
{
if plan.capped_to_caller() {
return run_on_caller(closures);
}
let n = closures.len();
if n < 3 {
return cooperative_join_n_tree(plan, closures);
}
use crate::sched::adaptive_cooperative::CooperativeRouting;
match plan.cooperative_routing {
CooperativeRouting::ForceTree => cooperative_join_n_tree(plan, closures),
CooperativeRouting::ForceMailbox => {
cooperative_join_n_flat_mailbox(plan, closures)
}
CooperativeRouting::ForceDeque => cooperative_join_n_flat(plan, closures),
CooperativeRouting::Auto => {
let n_workers = global_local_arena().local_worker_count();
if n < n_workers {
cooperative_join_n_tree(plan, closures)
} else {
cooperative_join_n_flat_mailbox(plan, closures)
}
}
}
}
const DEQUE_FIRST_BURST: usize = crate::sched::arena_local::JOBS_PER_SLOT;
const MAILBOX_GATE_POOL_MULTIPLE: usize = 32;
#[inline]
fn mailbox_gate(n_workers: usize) -> usize {
n_workers.saturating_mul(MAILBOX_GATE_POOL_MULTIPLE)
}
fn run_on_caller<R>(closures: Vec<Box<dyn FnOnce() -> R + Send>>) -> Vec<R> {
closures.into_iter().map(|c| c()).collect()
}
pub fn cooperative_join_n_tree<R>(
plan: &JobPlan,
closures: Vec<Box<dyn FnOnce() -> R + Send>>,
) -> Vec<R>
where
R: Send + 'static,
{
if plan.capped_to_caller() {
return run_on_caller(closures);
}
let n = closures.len();
if n == 0 {
return Vec::new();
}
if n == 1 {
let mut iter = closures.into_iter();
let c = iter.next().expect("len == 1 checked");
return vec![c()];
}
if n == 2 {
let mut iter = closures.into_iter();
let a = iter.next().expect("len == 2 checked");
let b = iter.next().expect("len == 2 checked");
let (ra, rb) = join(plan, a, b);
return vec![ra, rb];
}
let mid = n / 2;
let mut closures = closures;
let right = closures.split_off(mid);
let left = closures;
let plan_left = *plan;
let plan_right = *plan;
let (left_results, right_results) = join(
plan,
move || cooperative_join_n_tree::<R>(&plan_left, left),
move || cooperative_join_n_tree::<R>(&plan_right, right),
);
let mut out = left_results;
out.extend(right_results);
out
}
pub fn cooperative_join_n_flat<R>(
plan: &JobPlan,
closures: Vec<Box<dyn FnOnce() -> R + Send>>,
) -> Vec<R>
where
R: Send + 'static,
{
if plan.capped_to_caller() {
return run_on_caller(closures);
}
let n = closures.len();
if n == 0 {
return Vec::new();
}
if n == 1 {
let mut iter = closures.into_iter();
let c = iter.next().expect("len == 1 checked");
return vec![c()];
}
if n == 2 {
let mut iter = closures.into_iter();
let a = iter.next().expect("len == 2 checked");
let b = iter.next().expect("len == 2 checked");
let (ra, rb) = join(plan, a, b);
return vec![ra, rb];
}
let ctx_ptr = current_worker_ctx();
if !ctx_ptr.is_null() {
let ctx = unsafe { &*ctx_ptr };
return fan_out_in_worker(ctx, plan, closures, FanOutMode::Deque);
}
fan_out_external(plan, closures, FanOutMode::Deque)
}
pub fn cooperative_join_n_flat_mailbox<R>(
plan: &JobPlan,
closures: Vec<Box<dyn FnOnce() -> R + Send>>,
) -> Vec<R>
where
R: Send + 'static,
{
if plan.capped_to_caller() {
return run_on_caller(closures);
}
let n = closures.len();
if n == 0 {
return Vec::new();
}
if n == 1 {
let mut iter = closures.into_iter();
let c = iter.next().expect("len == 1 checked");
return vec![c()];
}
if n == 2 {
let mut iter = closures.into_iter();
let a = iter.next().expect("len == 2 checked");
let b = iter.next().expect("len == 2 checked");
let (ra, rb) = join(plan, a, b);
return vec![ra, rb];
}
let ctx_ptr = current_worker_ctx();
if !ctx_ptr.is_null() {
let ctx = unsafe { &*ctx_ptr };
let n_workers = ctx.sleep.worker_count();
let mode = if n >= mailbox_gate(n_workers) {
FanOutMode::Mailbox
} else {
FanOutMode::Deque
};
return fan_out_in_worker(ctx, plan, closures, mode);
}
fan_out_external(plan, closures, FanOutMode::Mailbox)
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum FanOutMode {
Deque,
Mailbox,
}
type WrappedClosure<R> = Box<dyn FnOnce(bool) -> R + Send>;
type FanOutStackJob<R> =
crate::sched::job::StackJobShared<CountLatch, WrappedClosure<R>, R>;
fn fan_out_in_worker<R>(
ctx: &WorkerCtx,
plan: &JobPlan,
mut closures: Vec<Box<dyn FnOnce() -> R + Send>>,
mode: FanOutMode,
) -> Vec<R>
where
R: Send + 'static,
{
let n = closures.len();
debug_assert!(n >= 2, "fan_out_in_worker should not see n < 2 (caller branches early)");
let last_closure = closures.pop().expect("n >= 2 checked");
let n_to_dispatch = closures.len();
let my_parker: std::sync::Arc<crate::sched::sleep::Parker> = ctx
.parkers[ctx.index]
.get()
.expect("worker parker initialized by worker_loop before any fan_out_in_worker call")
.clone();
let shared_latch: std::sync::Arc<CountLatch> =
std::sync::Arc::new(CountLatch::new(n_to_dispatch, my_parker));
let stack_jobs: Vec<Box<FanOutStackJob<R>>> = closures
.into_iter()
.map(|c| {
let wrapped: WrappedClosure<R> = Box::new(move |_stolen| c());
Box::new(crate::sched::job::StackJobShared::new(
wrapped,
shared_latch.clone(),
))
})
.collect();
let numa_hint_byte = plan.numa_hint.unwrap_or(NUMA_HINT_ANY as u32) as u8;
let n_workers = ctx.sleep.worker_count();
let effective_mode = match mode {
FanOutMode::Mailbox if n < mailbox_gate(n_workers) => FanOutMode::Deque,
other => other,
};
let _wake_scope = match effective_mode {
FanOutMode::Mailbox => {
crate::sched::arena_local::DispatchScope::new_if_change(false)
}
FanOutMode::Deque => None,
};
let n_to_push = stack_jobs.len();
unsafe {
for (i, sj) in stack_jobs.iter().enumerate() {
let r = sj.as_job_ref(plan.k_outer, numa_hint_byte, plan.variant);
match effective_mode {
FanOutMode::Deque if i < DEQUE_FIRST_BURST => {
ctx.push_burst(r);
}
FanOutMode::Deque => {
if i == DEQUE_FIRST_BURST {
ctx.flush_all();
}
if let Err(refused) = ctx.try_push(r) {
refused.execute();
}
}
FanOutMode::Mailbox => {
let target = if n_workers > 1 {
let mut t = (ctx.index + 1 + i) % n_workers;
if t == ctx.index {
t = (t + 1) % n_workers;
}
t
} else {
ctx.index
};
if target == ctx.index {
ctx.push_burst(r);
} else if let Err(returned) =
ctx.push_to_mailbox(target, r)
{
ctx.push_burst(returned);
}
}
}
}
}
ctx.flush_all();
crate::sched::trace::emit(crate::sched::trace::TraceEvent::JoinPush, n as u32);
let needs_batched_broadcast = _wake_scope.is_some();
drop(_wake_scope);
if needs_batched_broadcast && n_to_push > 0 {
ctx.sleep.new_internal_jobs(n_to_push as u32, true);
}
let last_result = panic::catch_unwind(panic::AssertUnwindSafe(last_closure));
crate::sched::trace::emit(crate::sched::trace::TraceEvent::JoinWaitBegin, n as u32);
while !shared_latch.is_set() {
if let Some(job) = ctx.find_work() {
unsafe { job.execute() };
} else {
std::thread::yield_now();
}
}
crate::sched::trace::emit(crate::sched::trace::TraceEvent::JoinWaitEnd, n as u32);
let mut out: Vec<R> = Vec::with_capacity(n);
for sj in stack_jobs {
out.push(unsafe { (*sj).into_result() });
}
match last_result {
Ok(r) => out.push(r),
Err(payload) => {
drop(out);
panic::resume_unwind(payload);
}
}
out
}
fn fan_out_external<R>(
plan: &JobPlan,
closures: Vec<Box<dyn FnOnce() -> R + Send>>,
mode: FanOutMode,
) -> Vec<R>
where
R: Send + 'static,
{
let arena = global_local_arena();
let _smt_guards: Vec<crate::sched::arena_local::SmtGuard> = if plan.effective_use_smt() {
arena.acquire_smt()
} else {
Vec::new()
};
let plan_copy = *plan;
let wrapper = StackJob::new(
move |_stolen: bool| -> Vec<R> {
let ctx_ptr = current_worker_ctx();
debug_assert!(
!ctx_ptr.is_null(),
"fan_out_external wrapper must run on a worker thread"
);
let ctx = unsafe { &*ctx_ptr };
fan_out_in_worker(ctx, &plan_copy, closures, mode)
},
LockLatch::new(),
);
let numa_hint_byte = plan.numa_hint.unwrap_or(NUMA_HINT_ANY as u32) as u8;
unsafe {
let r = wrapper.as_job_ref(plan.k_outer, numa_hint_byte, plan.variant);
arena.submit(r, plan.numa_hint);
}
const SPIN_CYCLES: usize = 500_000;
wrapper.latch.wait_spin_then_monitor(SPIN_CYCLES);
unsafe { wrapper.into_result() }
}
#[cfg(test)]
mod tests {
use super::*;
use std::sync::Arc;
use std::sync::atomic::{AtomicU32, Ordering};
fn plan() -> JobPlan {
JobPlan::new(8, 1)
}
#[test]
fn tree_empty_input_returns_empty_vec() {
let p = plan();
let v: Vec<Box<dyn FnOnce() -> u32 + Send>> = Vec::new();
let results = cooperative_join_n(&p, v);
assert!(results.is_empty());
}
#[test]
fn tree_one_closure_runs_inline() {
let p = plan();
let closures: Vec<Box<dyn FnOnce() -> u32 + Send>> =
vec![Box::new(|| 42)];
let results = cooperative_join_n(&p, closures);
assert_eq!(results, vec![42]);
}
#[test]
fn tree_two_closures_route_through_join() {
let p = plan();
let closures: Vec<Box<dyn FnOnce() -> u32 + Send>> =
vec![Box::new(|| 10), Box::new(|| 20)];
let results = cooperative_join_n(&p, closures);
assert_eq!(results, vec![10, 20]);
}
#[test]
fn tree_three_closures_preserve_caller_order() {
let p = plan();
let closures: Vec<Box<dyn FnOnce() -> u32 + Send>> = vec![
Box::new(|| 1),
Box::new(|| 2),
Box::new(|| 3),
];
let results = cooperative_join_n(&p, closures);
assert_eq!(results, vec![1, 2, 3]);
}
#[test]
fn tree_eight_closures_balanced_tree() {
let p = plan();
let closures: Vec<Box<dyn FnOnce() -> u32 + Send>> =
(0..8u32).map(|i| Box::new(move || i * 10) as _).collect();
let results = cooperative_join_n(&p, closures);
assert_eq!(results, vec![0, 10, 20, 30, 40, 50, 60, 70]);
}
#[test]
fn tree_sixteen_closures() {
let p = plan();
let closures: Vec<Box<dyn FnOnce() -> u32 + Send>> =
(0..16u32).map(|i| Box::new(move || i) as _).collect();
let results = cooperative_join_n(&p, closures);
let expected: Vec<u32> = (0..16u32).collect();
assert_eq!(results, expected);
}
#[test]
fn flat_empty_input_returns_empty_vec() {
let p = plan();
let v: Vec<Box<dyn FnOnce() -> u32 + Send>> = Vec::new();
let results = cooperative_join_n_flat(&p, v);
assert!(results.is_empty());
}
#[test]
fn flat_one_closure_runs_inline() {
let p = plan();
let closures: Vec<Box<dyn FnOnce() -> u32 + Send>> =
vec![Box::new(|| 42)];
let results = cooperative_join_n_flat(&p, closures);
assert_eq!(results, vec![42]);
}
#[test]
fn flat_two_closures_route_through_join() {
let p = plan();
let closures: Vec<Box<dyn FnOnce() -> u32 + Send>> =
vec![Box::new(|| 10), Box::new(|| 20)];
let results = cooperative_join_n_flat(&p, closures);
assert_eq!(results, vec![10, 20]);
}
#[test]
fn flat_three_closures_preserve_caller_order() {
let p = plan();
let closures: Vec<Box<dyn FnOnce() -> u32 + Send>> = vec![
Box::new(|| 1),
Box::new(|| 2),
Box::new(|| 3),
];
let results = cooperative_join_n_flat(&p, closures);
assert_eq!(results, vec![1, 2, 3]);
}
#[test]
fn flat_twelve_closures_match_xeon_simc_shape() {
let p = plan();
let closures: Vec<Box<dyn FnOnce() -> u64 + Send>> = (0..12u64)
.map(|i| Box::new(move || {
let mut v: u64 = i.wrapping_mul(0x9E37_79B9_7F4A_7C15) | 1;
for _ in 0..200_000u64 {
v = v.wrapping_mul(0x9E37_79B9_7F4A_7C15);
v ^= v >> 31;
}
v
}) as _)
.collect();
let results = cooperative_join_n_flat(&p, closures);
assert_eq!(results.len(), 12);
for (i, v) in results.iter().enumerate() {
assert_ne!(*v, 0, "closure {i} produced zero, body did not run");
}
}
#[test]
fn flat_sixteen_closures_full_fan_out() {
let p = plan();
let closures: Vec<Box<dyn FnOnce() -> u32 + Send>> =
(0..16u32).map(|i| Box::new(move || i) as _).collect();
let results = cooperative_join_n_flat(&p, closures);
let expected: Vec<u32> = (0..16u32).collect();
assert_eq!(results, expected);
}
#[test]
fn flat_results_in_caller_order_invariant_of_execution_thread() {
let p = plan();
let exec_order = Arc::new(AtomicU32::new(0));
let closures: Vec<Box<dyn FnOnce() -> (u32, u32) + Send>> = (0..8u32)
.map(|i| {
let order = Arc::clone(&exec_order);
Box::new(move || {
let run_idx = order.fetch_add(1, Ordering::SeqCst);
(i, run_idx)
}) as _
})
.collect();
let results = cooperative_join_n_flat(&p, closures);
let caller_indices: Vec<u32> = results.iter().map(|(i, _)| *i).collect();
assert_eq!(caller_indices, vec![0, 1, 2, 3, 4, 5, 6, 7]);
}
#[test]
fn flat_closures_return_different_types_via_boxed_trait_object() {
let p = plan();
let closures: Vec<Box<dyn FnOnce() -> String + Send>> = vec![
Box::new(|| "alpha".to_string()),
Box::new(|| "beta".to_string()),
Box::new(|| "gamma".to_string()),
Box::new(|| "delta".to_string()),
];
let results = cooperative_join_n_flat(&p, closures);
assert_eq!(
results,
vec![
"alpha".to_string(),
"beta".to_string(),
"gamma".to_string(),
"delta".to_string(),
]
);
}
#[test]
fn nested_tree_inside_flat_composes() {
let p = plan();
let mut outer: Vec<Box<dyn FnOnce() -> Vec<u32> + Send>> =
Vec::with_capacity(4);
for o in 0..4u32 {
let p_inner = p;
outer.push(Box::new(move || {
let inner: Vec<Box<dyn FnOnce() -> u32 + Send>> = (0..3u32)
.map(|i| Box::new(move || o * 100 + i) as _)
.collect();
cooperative_join_n(&p_inner, inner)
}));
}
let results = cooperative_join_n_flat(&p, outer);
let flat: Vec<u32> = results.into_iter().flatten().collect();
assert_eq!(
flat,
vec![0, 1, 2, 100, 101, 102, 200, 201, 202, 300, 301, 302]
);
}
#[test]
fn a_deque_fan_out_wider_than_the_ring_completes() {
let n = 2 * crate::sched::arena_local::ADAPTIVE_SLOT_CAPACITY
* crate::sched::arena_local::JOBS_PER_SLOT;
assert!(
n > crate::sched::arena_local::ADAPTIVE_SLOT_CAPACITY
* crate::sched::arena_local::JOBS_PER_SLOT,
"the fan-out must exceed the ring or this tests nothing"
);
let (tx, rx) = std::sync::mpsc::channel();
std::thread::spawn(move || {
let p = JobPlan::new(8, 1);
let closures: Vec<Box<dyn FnOnce() -> u32 + Send>> = (0..n)
.map(|i| Box::new(move || i as u32) as _)
.collect();
tx.send(cooperative_join_n_flat(&p, closures))
.expect("the test thread holds the receiver until it times out");
});
let results = rx
.recv_timeout(std::time::Duration::from_secs(60))
.expect("a deque fan-out wider than the ring must complete");
assert_eq!(results, (0..n as u32).collect::<Vec<_>>());
}
#[test]
fn the_mailbox_gate_sits_where_the_crossing_was_measured() {
assert_eq!(mailbox_gate(24), 768, "24 workers, the measured host");
assert!(
mailbox_gate(24) > 640,
"640 is the widest fan-out measured with deque still ahead"
);
assert_eq!(mailbox_gate(usize::MAX), usize::MAX);
}
#[test]
fn flat_mailbox_completes_once_its_gate_opens() {
let n = mailbox_gate(global_local_arena().local_worker_count()).max(
global_local_arena().total_workers()
+ crate::sched::arena_local::EXTERNAL_SLOT_COUNT,
);
let (tx, rx) = std::sync::mpsc::channel();
std::thread::spawn(move || {
let p = JobPlan::new(8, 1);
let closures: Vec<Box<dyn FnOnce() -> u32 + Send>> = (0..n)
.map(|i| Box::new(move || i as u32) as _)
.collect();
tx.send(cooperative_join_n_flat_mailbox(&p, closures))
.expect("the test thread holds the receiver until it times out");
});
let results = rx
.recv_timeout(std::time::Duration::from_secs(60))
.expect("mailbox fan-out at N >= worker count must complete");
assert_eq!(results, (0..n as u32).collect::<Vec<_>>());
}
#[test]
fn flat_mailbox_completes_after_a_foreign_pool_has_run() {
let n = mailbox_gate(global_local_arena().local_worker_count());
let mut warm: Vec<u64> = (0..n as u64).collect();
rayon::scope(|s| {
for slot in warm.iter_mut() {
s.spawn(move |_| {
*slot = slot.wrapping_mul(0x100000001B3);
});
}
});
std::hint::black_box(&warm);
let (tx, rx) = std::sync::mpsc::channel();
std::thread::spawn(move || {
let p = JobPlan::new(8, 1);
let closures: Vec<Box<dyn FnOnce() -> u32 + Send>> = (0..n)
.map(|i| Box::new(move || i as u32) as _)
.collect();
tx.send(cooperative_join_n_flat_mailbox(&p, closures))
.expect("the test thread holds the receiver until it times out");
});
let results = rx
.recv_timeout(std::time::Duration::from_secs(60))
.expect("mailbox fan-out must complete after a foreign pool has run");
assert_eq!(results, (0..n as u32).collect::<Vec<_>>());
}
#[test]
fn a_worker_cap_of_one_keeps_every_join_on_the_calling_thread() {
use crate::numa_topology::numa_topology;
use crate::sched::plan::{SchedTier, pick_tier};
use std::thread::ThreadId;
let uncapped = JobPlan::new(6, 4096);
assert_ne!(
pick_tier(&uncapped, numa_topology()),
SchedTier::Inline,
"without its cap the plan must reach the pool, or this test cannot see the cap"
);
let capped = uncapped.with_workers(1);
let caller = std::thread::current().id();
let halves = join(
&capped,
|| std::thread::current().id(),
|| std::thread::current().id(),
);
assert_eq!(
halves,
(caller, caller),
"sched::join ran a half off the calling thread"
);
type Shape = fn(&JobPlan, Vec<Box<dyn FnOnce() -> ThreadId + Send>>) -> Vec<ThreadId>;
let shapes: [(&str, Shape); 4] = [
("cooperative_join_n", cooperative_join_n),
("cooperative_join_n_tree", cooperative_join_n_tree),
("cooperative_join_n_flat", cooperative_join_n_flat),
(
"cooperative_join_n_flat_mailbox",
cooperative_join_n_flat_mailbox,
),
];
for (name, run) in shapes {
let closures: Vec<Box<dyn FnOnce() -> ThreadId + Send>> = (0..64)
.map(|_| Box::new(|| std::thread::current().id()) as _)
.collect();
let ids = run(&capped, closures);
assert_eq!(ids.len(), 64, "{name} returned every result");
let elsewhere = ids.iter().filter(|&&id| id != caller).count();
assert_eq!(
elsewhere, 0,
"{name} ran {elsewhere} of 64 closures off the calling thread"
);
}
}
}