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,
{
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().total_workers();
if n < n_workers {
cooperative_join_n_tree(plan, closures)
} else {
cooperative_join_n_flat_mailbox(plan, closures)
}
}
}
}
pub fn cooperative_join_n_tree<R>(
plan: &JobPlan,
closures: Vec<Box<dyn FnOnce() -> R + Send>>,
) -> Vec<R>
where
R: Send + 'static,
{
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,
{
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,
{
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.stealers.len();
let mode = if n >= 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.stealers.len();
let effective_mode = match mode {
FanOutMode::Mailbox if n < 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 => {
ctx.push_burst(r);
}
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;
for _ in 0..SPIN_CYCLES {
if wrapper.latch.is_set() {
return unsafe { wrapper.into_result() };
}
std::hint::spin_loop();
}
wrapper.latch.wait();
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]
);
}
}