use crate::sched::arena::{global_local_arena, join_context};
use crate::sched::plan::JobPlan;
const HEARTBEAT_CYCLES: u64 = 60_000;
const POLL_MASK: usize = 0x1F;
fn scopeguard_dispatch_exit(n: usize) -> DispatchExitGuard {
DispatchExitGuard { n: n as u32 }
}
struct DispatchExitGuard {
n: u32,
}
impl Drop for DispatchExitGuard {
fn drop(&mut self) {
crate::sched::trace::emit(
crate::sched::trace::TraceEvent::DispatchExit,
self.n,
);
}
}
#[inline(always)]
fn read_tsc() -> u64 {
#[cfg(target_arch = "x86_64")]
unsafe {
std::arch::x86_64::_rdtsc()
}
#[cfg(not(target_arch = "x86_64"))]
{
std::time::Instant::now().elapsed().as_nanos() as u64
}
}
#[inline(always)]
fn record_leaf<F: FnOnce() -> R, R>(
site: Option<crate::sched::call_site::SiteRef>,
body: F,
) -> R {
crate::sched::trace::emit(crate::sched::trace::TraceEvent::LeafStart, 0);
let t0 = read_tsc();
let out = body();
let dt = read_tsc().wrapping_sub(t0);
crate::sched::trace::emit(crate::sched::trace::TraceEvent::LeafEnd, 0);
LOCAL_LEAF_BUFFER.with(|cell| {
let mut buf = cell.borrow_mut();
buf.add(site, dt);
});
out
}
#[inline(always)]
pub(crate) fn record_leaf_span_ns(
site: Option<crate::sched::call_site::SiteRef>,
nanos: u64,
) {
if let Some(site) = site {
let scaled = nanos >> 8;
site.get()
.record_batch_site_only(nanos, scaled.saturating_mul(scaled), 1);
}
}
struct LocalLeafBuffer {
global_sum_ns: u64,
global_sumsq_scaled: u64,
global_count: u64,
site_sum_ns: u64,
site_sumsq_scaled: u64,
site_count: u64,
site: *const crate::sched::call_site::CallSiteState,
}
impl LocalLeafBuffer {
const FLUSH_THRESHOLD: u64 = 4;
const fn new() -> Self {
Self {
global_sum_ns: 0,
global_sumsq_scaled: 0,
global_count: 0,
site_sum_ns: 0,
site_sumsq_scaled: 0,
site_count: 0,
site: core::ptr::null(),
}
}
#[inline(always)]
fn add(&mut self, site: Option<crate::sched::call_site::SiteRef>, nanos: u64) {
let scaled = nanos >> 8;
let sq = scaled.saturating_mul(scaled);
self.global_sum_ns = self.global_sum_ns.saturating_add(nanos);
self.global_sumsq_scaled = self.global_sumsq_scaled.saturating_add(sq);
self.global_count += 1;
if self.global_count >= Self::FLUSH_THRESHOLD {
self.flush_global();
}
if let Some(s) = site {
let site_ptr: *const crate::sched::call_site::CallSiteState = s.get();
if !core::ptr::eq(site_ptr, self.site) {
self.flush_site();
self.site = site_ptr;
}
self.site_sum_ns = self.site_sum_ns.saturating_add(nanos);
self.site_sumsq_scaled = self.site_sumsq_scaled.saturating_add(sq);
self.site_count += 1;
if self.site_count >= Self::FLUSH_THRESHOLD {
self.flush_site();
}
}
}
fn flush_global(&mut self) {
if self.global_count == 0 {
return;
}
crate::sched::split_observer::record_leaf_batch(
self.global_sum_ns,
self.global_sumsq_scaled,
self.global_count,
);
self.global_sum_ns = 0;
self.global_sumsq_scaled = 0;
self.global_count = 0;
}
fn flush_site(&mut self) {
if self.site_count == 0 || self.site.is_null() {
self.site_count = 0;
self.site_sum_ns = 0;
self.site_sumsq_scaled = 0;
return;
}
let site: &'static crate::sched::call_site::CallSiteState =
unsafe { &*self.site };
site.record_batch_site_only(
self.site_sum_ns,
self.site_sumsq_scaled,
self.site_count,
);
self.site_sum_ns = 0;
self.site_sumsq_scaled = 0;
self.site_count = 0;
}
}
impl Drop for LocalLeafBuffer {
fn drop(&mut self) {
self.flush_global();
self.flush_site();
}
}
thread_local! {
static LOCAL_LEAF_BUFFER: std::cell::RefCell<LocalLeafBuffer>
= const { std::cell::RefCell::new(LocalLeafBuffer::new()) };
}
struct FlushLeafStatsOnExit;
impl Drop for FlushLeafStatsOnExit {
fn drop(&mut self) {
LOCAL_LEAF_BUFFER.with(|cell| {
let mut buf = cell.borrow_mut();
buf.flush_global();
buf.flush_site();
});
}
}
const MIN_LEAF_ITEMS: usize = 256;
const LEAF_SAMPLE_STRIDE: u32 = 8;
const TARGET_PER_LEAF_OVERHEAD_NS_HELPER: u64 = 5_000;
const TARGET_LEAF_WORK_NS: u64 = 1_000_000;
#[inline]
fn adaptive_seed_depth(plan: &JobPlan, items: usize, workers: usize) -> usize {
let workers = workers.max(1);
let items = items.max(1);
let workers_log2 = (workers as u64).next_power_of_two().trailing_zeros() as usize;
let target_leaf_count = match plan.estimated_per_item_ns {
Some(ns) if ns > 0 => {
let total_work_ns = (ns as u64).saturating_mul(items as u64);
let from_work = (total_work_ns / TARGET_LEAF_WORK_NS).max(workers as u64);
(from_work as usize).min(items)
}
_ => workers,
};
let depth = (target_leaf_count as u64).next_power_of_two().trailing_zeros() as usize;
depth.max(workers_log2)
}
#[inline]
fn adaptive_min_leaf(plan: &JobPlan, caller_floor: usize) -> usize {
if !plan.estimated_per_item_ns_explicit {
if plan.use_smt {
return 1;
}
return caller_floor;
}
match plan.estimated_per_item_ns {
Some(ns) if ns > 0 => {
let raw = (TARGET_PER_LEAF_OVERHEAD_NS_HELPER / ns as u64)
.max(1) as usize;
raw.min(caller_floor)
}
_ => caller_floor,
}
}
#[track_caller]
pub fn for_each_chunk<T, F>(plan: &JobPlan, items: &mut [T], op: F)
where
T: Send,
F: Fn(&mut [T]) + Sync,
{
let n = items.len();
crate::sched::trace::emit(
crate::sched::trace::TraceEvent::DispatchEnter,
n as u32,
);
let _trace_exit_guard = scopeguard_dispatch_exit(n);
if n == 0 {
return;
}
let plan_owned = plan
.with_site_if_none(crate::sched::call_site::caller_site())
.apply_site_class();
let plan = &plan_owned;
let _flush_on_exit = FlushLeafStatsOnExit;
const HYBRID_JEC_THRESHOLD_NS: u64 = 200_000;
let estimated_total_ns: u64 = plan
.effective_ns_per_elem()
.map(|ns| (ns as u64).saturating_mul(n as u64))
.unwrap_or(u64::MAX);
let use_jec_wake = estimated_total_ns >= HYBRID_JEC_THRESHOLD_NS;
let _jec_scope = crate::sched::arena_local::DispatchScope::new_if_change(use_jec_wake);
const INLINE_COLLAPSE_THRESHOLD_NS: u64 = 50_000;
if plan.estimated_per_item_ns_explicit
&& let Some(per_elem_ns) = plan.effective_ns_per_elem()
&& (per_elem_ns as u64).saturating_mul(n as u64) < INLINE_COLLAPSE_THRESHOLD_NS
{
record_leaf(plan.site, || op(items));
return;
}
let arena_workers = global_local_arena().total_workers();
let workers = plan
.worker_cap
.map(|cap| (cap as usize).min(arena_workers))
.unwrap_or(arena_workers)
.max(1);
let effective_min_leaf = adaptive_min_leaf(plan, MIN_LEAF_ITEMS);
const TARGET_PER_LEAF_OVERHEAD_NS: u64 = 5_000;
let target_per_leaf_overhead_ns: u64 = TARGET_PER_LEAF_OVERHEAD_NS;
const PROBE_SIZE: usize = 32;
let cost_authoritative = plan.estimated_per_item_ns_explicit;
if !cost_authoritative
&& !plan.use_smt
&& n < workers.saturating_mul(MIN_LEAF_ITEMS)
{
core::hint::cold_path();
let probe_size = (n / 8).clamp(1, PROBE_SIZE);
let (first, after_first) = items.split_at_mut(1);
let start = std::time::Instant::now();
record_leaf(plan.site, || op(first));
let first_ns = start.elapsed().as_nanos() as u64;
if after_first.is_empty() {
return;
}
let (probe_ns, probed, tail) = if first_ns >= probe_trust_floor_ns() || probe_size == 1 {
(first_ns, 1usize, after_first)
} else {
let extra = (probe_size - 1).min(after_first.len().saturating_sub(1));
if extra == 0 {
(first_ns, 1usize, after_first)
} else {
let (more, rest) = after_first.split_at_mut(extra);
let t2 = std::time::Instant::now();
record_leaf(plan.site, || op(more));
let more_ns = t2.elapsed().as_nanos() as u64;
(first_ns + more_ns, 1 + extra, rest)
}
};
let mut per_elem_ns = probe_ns.max(1) / probed as u64;
let mut tail = tail;
let dispatch_floor_ns = (workers as u64)
.saturating_mul(target_per_leaf_overhead_ns)
.saturating_mul(crate::cpu_info::small_host_dispatch_factor());
const CONFIRM_SIZE: usize = 4;
const CONFIRM_SINGLE_MAX: usize = 3;
let cold_start_allowance_ns = dispatch_floor_ns.saturating_mul(4);
if probed == 1 && first_ns < cold_start_allowance_ns && tail.len() >= workers {
for _ in 0..CONFIRM_SINGLE_MAX {
if per_elem_ns.saturating_mul(tail.len() as u64) < dispatch_floor_ns
|| tail.len() <= 1
{
break;
}
let (one, rest) = tail.split_at_mut(1);
let start = std::time::Instant::now();
record_leaf(plan.site, || op(one));
per_elem_ns = per_elem_ns.min(start.elapsed().as_nanos().max(1) as u64);
tail = rest;
}
}
if per_elem_ns.saturating_mul(tail.len() as u64) >= dispatch_floor_ns
&& probed >= 8
&& tail.len() > CONFIRM_SIZE
{
let (confirm, rest) = tail.split_at_mut(CONFIRM_SIZE);
let start = std::time::Instant::now();
record_leaf(plan.site, || op(confirm));
let confirm_ns = start.elapsed().as_nanos() as u64;
per_elem_ns = per_elem_ns.min(confirm_ns.max(1) / CONFIRM_SIZE as u64);
tail = rest;
}
let est_tail_ns = per_elem_ns.saturating_mul(tail.len() as u64);
if est_tail_ns < dispatch_floor_ns {
record_leaf(plan.site, || op(tail));
return;
}
let leaves_per_worker = crate::sched::split_observer::split_multiplier() as usize;
let max_budget = workers.saturating_mul(leaves_per_worker).max(1);
let probe_min_leaf = target_per_leaf_overhead_ns
.checked_div(per_elem_ns)
.map(|raw| (raw.max(1) as usize).min(MIN_LEAF_ITEMS))
.unwrap_or(MIN_LEAF_ITEMS);
let mut amended_plan = *plan;
amended_plan.estimated_per_item_ns = Some(per_elem_ns.min(u32::MAX as u64) as u32);
amended_plan.estimated_per_item_ns_explicit = true;
amended_plan.batch_size = tail.len() as u32;
bisect(&amended_plan, tail, &op, max_budget, max_budget, false, probe_min_leaf);
return;
}
if plan.bisect_variant.is_none() {
let seed_depth = adaptive_seed_depth(plan, items.len(), workers);
bisect_lazy_steal_driven(plan, items, &op, seed_depth, 0, effective_min_leaf);
return;
}
let (leaves_per_worker, use_rayon_replenish) = match plan.bisect_variant {
Some(crate::sched::plan::BisectVariant::ProducerMaxLenWorkers) => {
(1usize, false)
}
Some(crate::sched::plan::BisectVariant::RayonStyleReplenish) => {
(1usize, true)
}
None => unreachable!("None branch handled above"),
};
let max_budget = workers.saturating_mul(leaves_per_worker).max(1);
if use_rayon_replenish {
bisect_rayon_style(plan, items, &op, max_budget, workers, false, effective_min_leaf);
} else {
bisect(plan, items, &op, max_budget, max_budget, false, effective_min_leaf);
}
}
#[track_caller]
pub fn for_each_fixed_chunk<T, F>(
plan: &JobPlan,
items: &mut [T],
chunk_size: usize,
op: F,
)
where
T: Send,
F: Fn(&mut [T]) + Sync,
{
let n = items.len();
if n == 0 {
return;
}
let plan_owned = plan
.with_site_if_none(crate::sched::call_site::caller_site())
.apply_site_class();
let plan = &plan_owned;
let chunk = chunk_size.max(1);
if n <= chunk {
let t0 = std::time::Instant::now();
op(items);
record_leaf_span_ns(plan.site, t0.elapsed().as_nanos() as u64);
return;
}
let n_chunks = n.div_ceil(chunk);
let max_budget = n_chunks.max(1);
bisect_fixed(plan, items, &op, max_budget, max_budget, chunk, false);
}
fn bisect<T, F>(
plan: &JobPlan,
items: &mut [T],
op: &F,
splits: usize,
max_budget: usize,
migrated: bool,
min_leaf: usize,
)
where
T: Send,
F: Fn(&mut [T]) + Sync,
{
if items.len() <= min_leaf {
record_leaf(plan.site, || op(items));
return;
}
let cur_splits = if migrated { max_budget } else { splits };
if cur_splits <= 1 {
record_leaf(plan.site, || op(items));
return;
}
let mid = items.len() / 2;
let (left, right) = items.split_at_mut(mid);
let half = cur_splits >> 1;
join_context(
plan,
|left_injected| bisect(plan, left, op, half, max_budget, left_injected, min_leaf),
|right_stolen| bisect(plan, right, op, half, max_budget, right_stolen, min_leaf),
);
}
fn bisect_rayon_style<T, F>(
plan: &JobPlan,
items: &mut [T],
op: &F,
splits: usize,
workers_floor: usize,
migrated: bool,
min_leaf: usize,
)
where
T: Send,
F: Fn(&mut [T]) + Sync,
{
if items.len() <= min_leaf {
record_leaf(plan.site, || op(items));
return;
}
let cur_splits = if migrated {
workers_floor.max(splits / 2)
} else {
splits
};
if cur_splits <= 1 {
record_leaf(plan.site, || op(items));
return;
}
let mid = items.len() / 2;
let (left, right) = items.split_at_mut(mid);
let half = cur_splits >> 1;
join_context(
plan,
|left_injected| {
bisect_rayon_style(plan, left, op, half, workers_floor, left_injected, min_leaf)
},
|right_stolen| {
bisect_rayon_style(plan, right, op, half, workers_floor, right_stolen, min_leaf)
},
);
}
#[inline]
fn record_leaf_sampled<F: FnOnce() -> R, R>(
site: Option<crate::sched::call_site::SiteRef>,
body: F,
) -> R {
thread_local! {
static STRIDE_TICK: std::cell::Cell<u32> = const { std::cell::Cell::new(0) };
}
let should_sample = STRIDE_TICK.with(|c| {
let v = c.get().wrapping_add(1);
c.set(if v >= LEAF_SAMPLE_STRIDE { 0 } else { v });
v >= LEAF_SAMPLE_STRIDE
});
if should_sample { record_leaf(site, body) } else { body() }
}
fn bisect_lazy_steal_driven<T, F>(
plan: &JobPlan,
items: &mut [T],
op: &F,
seed_splits_remaining: usize,
last_seen_steals: u64,
min_leaf: usize,
)
where
T: Send,
F: Fn(&mut [T]) + Sync,
{
if items.len() <= min_leaf {
record_leaf_sampled(plan.site, || op(items));
return;
}
let ctx_ptr = crate::sched::arena_local::current_worker_ctx();
let (should_split, new_last_seen) = if seed_splits_remaining > 0 {
(true, last_seen_steals)
} else if ctx_ptr.is_null() {
(true, last_seen_steals)
} else {
let ctx = unsafe { &*ctx_ptr };
let cur = ctx
.stats
.times_stolen_from
.load(core::sync::atomic::Ordering::Relaxed);
if cur != last_seen_steals {
(true, cur)
} else {
(false, last_seen_steals)
}
};
if !should_split {
record_leaf_sampled(plan.site, || op(items));
return;
}
let mid = items.len() / 2;
let (left, right) = items.split_at_mut(mid);
let next_seed = seed_splits_remaining.saturating_sub(1);
join_context(
plan,
|_| bisect_lazy_steal_driven(plan, left, op, next_seed, new_last_seen, min_leaf),
|_| bisect_lazy_steal_driven(plan, right, op, next_seed, new_last_seen, min_leaf),
);
}
#[track_caller]
pub fn for_each_chunk_triple<T1, T2, T3, F>(
plan: &JobPlan,
out: &mut [T1],
a: &[T2],
b: &[T3],
op: F,
)
where
T1: Send,
T2: Send + Sync,
T3: Send + Sync,
F: Fn(&mut [T1], &[T2], &[T3]) + Sync,
{
let leaf = adaptive_min_leaf(plan, MIN_LEAF_ITEMS);
for_each_chunk_triple_min_leaf(plan, out, a, b, leaf, op)
}
#[track_caller]
pub fn for_each_chunk_triple_min_leaf<T1, T2, T3, F>(
plan: &JobPlan,
out: &mut [T1],
a: &[T2],
b: &[T3],
min_leaf: usize,
op: F,
)
where
T1: Send,
T2: Send + Sync,
T3: Send + Sync,
F: Fn(&mut [T1], &[T2], &[T3]) + Sync,
{
assert_eq!(out.len(), a.len(), "for_each_chunk_triple: out.len() != a.len()");
assert_eq!(out.len(), b.len(), "for_each_chunk_triple: out.len() != b.len()");
let n = out.len();
if n == 0 {
return;
}
let plan_owned = plan
.with_site_if_none(crate::sched::call_site::caller_site())
.apply_site_class();
let plan = &plan_owned;
let leaf = min_leaf.max(1);
let workers = global_local_arena().total_workers();
let multiplier = crate::sched::split_observer::split_multiplier() as usize;
let max_budget = workers.saturating_mul(multiplier).max(1);
bisect_triple(plan, out, a, b, &op, leaf, max_budget, max_budget, false);
}
#[allow(clippy::too_many_arguments)]
fn bisect_triple<T1, T2, T3, F>(
plan: &JobPlan,
out: &mut [T1],
a: &[T2],
b: &[T3],
op: &F,
min_leaf: usize,
splits: usize,
max_budget: usize,
migrated: bool,
)
where
T1: Send,
T2: Send + Sync,
T3: Send + Sync,
F: Fn(&mut [T1], &[T2], &[T3]) + Sync,
{
if out.len() <= min_leaf {
record_leaf(plan.site, || op(out, a, b));
return;
}
let cur_splits = if migrated { max_budget } else { splits };
if cur_splits <= 1 {
record_leaf(plan.site, || op(out, a, b));
return;
}
let mid = out.len() >> 1;
let (out_lo, out_hi) = out.split_at_mut(mid);
let (a_lo, a_hi) = a.split_at(mid);
let (b_lo, b_hi) = b.split_at(mid);
let half = cur_splits >> 1;
join_context(
plan,
|left_inj| bisect_triple(plan, out_lo, a_lo, b_lo, op, min_leaf, half, max_budget, left_inj),
|right_stolen| bisect_triple(plan, out_hi, a_hi, b_hi, op, min_leaf, half, max_budget, right_stolen),
);
}
#[track_caller]
pub fn for_each_chunk_indexed<T, F>(plan: &JobPlan, items: &mut [T], op: F)
where
T: Send,
F: Fn(usize, &mut [T]) + Sync,
{
let leaf = adaptive_min_leaf(plan, MIN_LEAF_ITEMS);
for_each_chunk_indexed_min_leaf(plan, items, leaf, op)
}
fn timer_bracket_ns() -> u64 {
static BRACKET_NS: std::sync::OnceLock<u64> = std::sync::OnceLock::new();
*BRACKET_NS.get_or_init(|| {
let iters = 4_096u32;
let t0 = std::time::Instant::now();
for _ in 0..iters {
std::hint::black_box(std::time::Instant::now().elapsed());
}
((t0.elapsed().as_nanos() as u64) / iters as u64).max(1)
})
}
fn probe_trust_floor_ns() -> u64 {
timer_bracket_ns().saturating_mul(20)
}
const PROBE_SIZE_FLOOR: usize = 16;
const PROBE_MIN_N: usize = 64;
const PROBE_SMALL_MIN_N: usize = 2;
#[track_caller]
pub fn for_each_chunk_indexed_min_leaf<T, F>(
plan: &JobPlan,
items: &mut [T],
min_leaf: usize,
op: F,
)
where
T: Send,
F: Fn(usize, &mut [T]) + Sync,
{
let n = items.len();
if n == 0 {
return;
}
let plan_owned = plan
.with_site_if_none(crate::sched::call_site::caller_site())
.apply_site_class();
let plan = &plan_owned;
let _flush_on_exit = FlushLeafStatsOnExit;
let leaf = min_leaf.max(1);
let workers = global_local_arena().total_workers();
let plan_holder: JobPlan;
let cost_authoritative = plan.estimated_per_item_ns_explicit;
let probe_quota: usize = if cost_authoritative || plan.use_smt {
0
} else if n >= PROBE_MIN_N.max(leaf) {
PROBE_SIZE_FLOOR.max(leaf).min(n)
} else if n >= PROBE_SMALL_MIN_N.max(2 * leaf) {
leaf
} else {
0
};
let (effective_plan, items_to_dispatch, start_offset): (&JobPlan, &mut [T], usize) =
if probe_quota > 0 {
let (first, rest) = items.split_at_mut(leaf.min(probe_quota));
let first_n = first.len();
let t0 = std::time::Instant::now();
record_leaf(plan.site, || op(0, first));
let first_ns = t0.elapsed().as_nanos() as u64;
let (probe_ns, probed, tail): (u64, usize, &mut [T]) =
if first_ns >= probe_trust_floor_ns() || probe_quota <= first_n {
(first_ns, first_n, rest)
} else {
let extra = (probe_quota - first_n).min(rest.len().saturating_sub(1));
if extra == 0 {
(first_ns, first_n, rest)
} else {
let (more, rest2) = rest.split_at_mut(extra);
let t2 = std::time::Instant::now();
record_leaf(plan.site, || op(first_n, more));
let more_ns = t2.elapsed().as_nanos() as u64;
(first_ns + more_ns, first_n + extra, rest2)
}
};
let per_item_ns = (probe_ns.max(1) / probed as u64).min(u32::MAX as u64) as u32;
plan_holder = (*plan).with_estimated_per_item_ns(per_item_ns);
(&plan_holder, tail, probed)
} else {
(plan, items, 0)
};
if items_to_dispatch.is_empty() {
return;
}
if effective_plan.bisect_variant.is_none() {
let seed_depth = adaptive_seed_depth(effective_plan, items_to_dispatch.len(), workers);
bisect_lazy_steal_driven_indexed(
effective_plan, items_to_dispatch, start_offset, &op, leaf, seed_depth, 0,
);
return;
}
let multiplier = crate::sched::split_observer::split_multiplier() as usize;
let max_budget = workers.saturating_mul(multiplier).max(1);
bisect_indexed(
effective_plan, items_to_dispatch, start_offset, &op, leaf, max_budget, max_budget, false,
);
}
#[track_caller]
pub fn for_each_indexed<F>(plan: &JobPlan, n: usize, min_leaf: usize, f: F)
where
F: Fn(usize) + Sync,
{
if n == 0 {
return;
}
let mut units: Vec<()> = vec![(); n];
for_each_chunk_indexed_min_leaf(plan, &mut units, min_leaf, |start, chunk| {
for i in start..start + chunk.len() {
f(i);
}
});
}
#[track_caller]
pub fn for_each_chunk_ref<T, F>(plan: &JobPlan, items: &[T], min_leaf: usize, f: F)
where
T: Sync,
F: Fn(usize, &[T]) + Sync,
{
let n = items.len();
if n == 0 {
return;
}
let width = min_leaf.max(1);
let n_chunks = n.div_ceil(width);
for_each_indexed(plan, n_chunks, 1, |i| {
let lo = i * width;
let hi = (lo + width).min(n);
f(lo, &items[lo..hi]);
});
}
#[allow(clippy::too_many_arguments)]
fn bisect_lazy_steal_driven_indexed<T, F>(
plan: &JobPlan,
items: &mut [T],
start: usize,
op: &F,
min_leaf: usize,
seed_splits_remaining: usize,
last_seen_steals: u64,
)
where
T: Send,
F: Fn(usize, &mut [T]) + Sync,
{
if items.len() <= min_leaf {
record_leaf(plan.site, || op(start, items));
return;
}
let ctx_ptr = crate::sched::arena_local::current_worker_ctx();
let (should_split, new_last_seen) = if seed_splits_remaining > 0 {
(true, last_seen_steals)
} else if ctx_ptr.is_null() {
(true, last_seen_steals)
} else {
let ctx = unsafe { &*ctx_ptr };
let cur = ctx
.stats
.times_stolen_from
.load(core::sync::atomic::Ordering::Relaxed);
if cur != last_seen_steals {
(true, cur)
} else {
(false, last_seen_steals)
}
};
if !should_split {
record_leaf(plan.site, || op(start, items));
return;
}
let mid = items.len() / 2;
let (left, right) = items.split_at_mut(mid);
let right_start = start + mid;
let next_seed = seed_splits_remaining.saturating_sub(1);
join_context(
plan,
|_| bisect_lazy_steal_driven_indexed(plan, left, start, op, min_leaf, next_seed, new_last_seen),
|_| bisect_lazy_steal_driven_indexed(plan, right, right_start, op, min_leaf, next_seed, new_last_seen),
);
}
#[allow(clippy::too_many_arguments)]
fn bisect_indexed<T, F>(
plan: &JobPlan,
items: &mut [T],
start: usize,
op: &F,
min_leaf: usize,
splits: usize,
max_budget: usize,
migrated: bool,
)
where
T: Send,
F: Fn(usize, &mut [T]) + Sync,
{
if items.len() <= min_leaf {
record_leaf(plan.site, || op(start, items));
return;
}
let cur_splits = if migrated { max_budget } else { splits };
if cur_splits <= 1 {
record_leaf(plan.site, || op(start, items));
return;
}
let mid = items.len() >> 1;
let (left, right) = items.split_at_mut(mid);
let right_start = start + mid;
let half = cur_splits >> 1;
join_context(
plan,
|left_inj| {
bisect_indexed(plan, left, start, op, min_leaf, half, max_budget, left_inj)
},
|right_stolen| {
bisect_indexed(
plan, right, right_start, op, min_leaf, half, max_budget, right_stolen,
)
},
);
}
#[track_caller]
pub fn collect_indexed<R, F>(plan: &JobPlan, n: usize, min_leaf: usize, f: F) -> Vec<R>
where
R: Send,
F: Fn(usize) -> R + Sync,
{
if n == 0 {
return Vec::new();
}
let plan_owned = plan
.with_site_if_none(crate::sched::call_site::caller_site())
.apply_site_class();
let plan = &plan_owned;
let _flush_on_exit = FlushLeafStatsOnExit;
let leaf = min_leaf.max(1);
let workers = global_local_arena().total_workers();
let multiplier = crate::sched::split_observer::split_multiplier() as usize;
let max_budget = workers.saturating_mul(multiplier).max(1);
let mut buf: Vec<std::mem::MaybeUninit<R>> = Vec::with_capacity(n);
unsafe { buf.set_len(n); }
let cost_authoritative = plan.estimated_per_item_ns_explicit;
let probe_quota: usize = if cost_authoritative || plan.use_smt {
0
} else if n >= PROBE_MIN_N.max(leaf) {
PROBE_SIZE_FLOOR.max(leaf).min(n)
} else if n >= PROBE_SMALL_MIN_N.max(2 * leaf) {
leaf
} else {
0
};
let plan_holder: JobPlan;
let (effective_plan, start_offset): (&JobPlan, usize) = if probe_quota > 0 {
let base = buf.as_mut_ptr() as *mut R;
let first_n = leaf.min(probe_quota);
let t0 = std::time::Instant::now();
record_leaf(plan.site, || {
for i in 0..first_n {
unsafe {
base.add(i).write(f(i));
}
}
});
let first_ns = t0.elapsed().as_nanos() as u64;
let (probe_ns, probed): (u64, usize) =
if first_ns >= probe_trust_floor_ns() || probe_quota <= first_n {
(first_ns, first_n)
} else {
let extra = (probe_quota - first_n).min(n - first_n - 1);
if extra == 0 {
(first_ns, first_n)
} else {
let t2 = std::time::Instant::now();
record_leaf(plan.site, || {
for i in first_n..first_n + extra {
unsafe {
base.add(i).write(f(i));
}
}
});
let more_ns = t2.elapsed().as_nanos() as u64;
(first_ns + more_ns, first_n + extra)
}
};
let per_item_ns = (probe_ns.max(1) / probed as u64).min(u32::MAX as u64) as u32;
plan_holder = (*plan).with_estimated_per_item_ns(per_item_ns);
(&plan_holder, probed)
} else {
(plan, 0)
};
if start_offset < n {
collect_inner(
effective_plan,
&mut buf[start_offset..],
start_offset,
&f,
leaf,
max_budget,
max_budget,
false,
);
}
let mut buf = std::mem::ManuallyDrop::new(buf);
unsafe { Vec::from_raw_parts(buf.as_mut_ptr() as *mut R, n, buf.capacity()) }
}
#[allow(clippy::too_many_arguments)]
fn collect_inner<R, F>(
plan: &JobPlan,
items: &mut [std::mem::MaybeUninit<R>],
start: usize,
f: &F,
min_leaf: usize,
splits: usize,
max_budget: usize,
migrated: bool,
)
where
R: Send,
F: Fn(usize) -> R + Sync,
{
#[inline(always)]
fn fill_leaf<R, F>(items: &mut [std::mem::MaybeUninit<R>], start: usize, f: &F)
where
F: Fn(usize) -> R,
{
let len = items.len();
let base = items.as_mut_ptr() as *mut R;
for i in 0..len {
unsafe { base.add(i).write(f(start + i)); }
}
}
if items.len() <= min_leaf {
record_leaf(plan.site, || fill_leaf(items, start, f));
return;
}
let cur_splits = if migrated { max_budget } else { splits };
if cur_splits <= 1 {
record_leaf(plan.site, || fill_leaf(items, start, f));
return;
}
let mid = items.len() >> 1;
let (left, right) = items.split_at_mut(mid);
let right_start = start + mid;
let half = cur_splits >> 1;
join_context(
plan,
|left_inj| {
collect_inner(plan, left, start, f, min_leaf, half, max_budget, left_inj)
},
|right_stolen| {
collect_inner(
plan, right, right_start, f, min_leaf, half, max_budget, right_stolen,
)
},
);
}
const HEARTBEAT_GATE_ITEMS: usize = 100_000;
#[track_caller]
pub fn collect_indexed_heartbeat<R, F>(plan: &JobPlan, n: usize, f: F) -> Vec<R>
where
R: Send,
F: Fn(usize) -> R + Sync,
{
if n == 0 {
return Vec::new();
}
let plan_owned = plan
.with_site_if_none(crate::sched::call_site::caller_site())
.apply_site_class();
let plan = &plan_owned;
if plan.estimated_per_item_ns_explicit
&& let Some(total_ns) = plan.estimated_total_ns()
{
const HEARTBEAT_NS: u64 = 20_000;
if total_ns < HEARTBEAT_NS {
return serial_collect_indexed(n, &f);
}
return collect_indexed(plan, n, 1, f);
}
let site = plan.site.expect("attached above");
let cv2 = site.get().cv2_per_mille();
let cv2_high = crate::sched::adaptive_profile::class_thresholds()
.cv2_high_per_mille
.load(std::sync::atomic::Ordering::Relaxed);
let arm = match cv2 {
Some(c) if c < cv2_high => crate::sched::call_site::PolicyArm::Default,
Some(_) => site
.get()
.choose_arm(n >= HEARTBEAT_MIN_ITEMS),
None => {
if n < HEARTBEAT_GATE_ITEMS {
crate::sched::call_site::PolicyArm::Default
} else {
crate::sched::call_site::PolicyArm::Alternative
}
}
};
if arm == crate::sched::call_site::PolicyArm::Default {
let t0 = std::time::Instant::now();
let out = collect_indexed(plan, n, 1, f);
if cv2.is_some() {
site.get().record_arm(arm, t0.elapsed().as_nanos() as u64);
}
return out;
}
let t0 = std::time::Instant::now();
let mut buf: Vec<std::mem::MaybeUninit<R>> = Vec::with_capacity(n);
unsafe { buf.set_len(n); }
heartbeat_fill(plan, &mut buf[..], 0, &f);
let mut buf = std::mem::ManuallyDrop::new(buf);
if cv2.is_some() {
site.get().record_arm(arm, t0.elapsed().as_nanos() as u64);
}
unsafe { Vec::from_raw_parts(buf.as_mut_ptr() as *mut R, n, buf.capacity()) }
}
const HEARTBEAT_MIN_ITEMS: usize = 4096;
fn serial_collect_indexed<R, F>(n: usize, f: &F) -> Vec<R>
where
R: Send,
F: Fn(usize) -> R + Sync,
{
let mut buf: Vec<std::mem::MaybeUninit<R>> = Vec::with_capacity(n);
unsafe { buf.set_len(n); }
let base = buf.as_mut_ptr() as *mut R;
for i in 0..n {
unsafe { base.add(i).write(f(i)); }
}
let mut buf = std::mem::ManuallyDrop::new(buf);
unsafe { Vec::from_raw_parts(buf.as_mut_ptr() as *mut R, n, buf.capacity()) }
}
fn heartbeat_fill<R, F>(
plan: &JobPlan,
items: &mut [std::mem::MaybeUninit<R>],
start: usize,
f: &F,
)
where
R: Send,
F: Fn(usize) -> R + Sync,
{
let n = items.len();
if n == 0 {
return;
}
if n <= MIN_LEAF_ITEMS {
let t0 = std::time::Instant::now();
fill_serial(items, start, f);
record_leaf_span_ns(plan.site, t0.elapsed().as_nanos() as u64);
return;
}
let base = items.as_mut_ptr() as *mut R;
let last_tick = read_tsc();
let span_t0 = last_tick;
let mut i = 0;
while i < n {
unsafe { base.add(i).write(f(start + i)); }
i += 1;
if (i & POLL_MASK) == 0 && (n - i) >= 2 * MIN_LEAF_ITEMS {
let now = read_tsc();
if now.wrapping_sub(last_tick) >= HEARTBEAT_CYCLES {
record_leaf_span_ns(plan.site, now.wrapping_sub(span_t0));
let (_filled, tail) = items.split_at_mut(i);
let mid = tail.len() >> 1;
let (near, far) = tail.split_at_mut(mid);
let near_start = start + i;
let far_start = start + i + mid;
join_context(
plan,
|_left_inj| heartbeat_fill(plan, near, near_start, f),
|_right_stolen| heartbeat_fill(plan, far, far_start, f),
);
return;
}
}
}
record_leaf_span_ns(plan.site, read_tsc().wrapping_sub(span_t0));
}
#[inline(always)]
fn fill_serial<R, F>(items: &mut [std::mem::MaybeUninit<R>], start: usize, f: &F)
where
F: Fn(usize) -> R,
{
let len = items.len();
let base = items.as_mut_ptr() as *mut R;
for i in 0..len {
unsafe { base.add(i).write(f(start + i)); }
}
}
#[track_caller]
pub fn collect_indexed_token_bucket<R, F, W>(
plan: &JobPlan,
n: usize,
work_per_item: W,
f: F,
) -> Vec<R>
where
R: Send,
F: Fn(usize) -> R + Sync,
W: Fn(usize) -> u32 + Sync,
{
if n == 0 {
return Vec::new();
}
let plan_owned = plan
.with_site_if_none(crate::sched::call_site::caller_site())
.apply_site_class();
let plan = &plan_owned;
if plan.estimated_per_item_ns_explicit
&& let Some(total_ns) = plan.estimated_total_ns()
{
const HEARTBEAT_NS: u64 = 20_000;
if total_ns < HEARTBEAT_NS {
return serial_collect_indexed(n, &f);
}
return collect_indexed(plan, n, 1, f);
}
if n < HEARTBEAT_GATE_ITEMS {
return collect_indexed(plan, n, 1, f);
}
let mut buf: Vec<std::mem::MaybeUninit<R>> = Vec::with_capacity(n);
unsafe { buf.set_len(n); }
token_bucket_fill(plan, &mut buf[..], 0, &f, &work_per_item);
let mut buf = std::mem::ManuallyDrop::new(buf);
unsafe { Vec::from_raw_parts(buf.as_mut_ptr() as *mut R, n, buf.capacity()) }
}
#[track_caller]
pub fn collect_indexed_tiny_tasks<R, F>(plan: &JobPlan, n: usize, f: F) -> Vec<R>
where
R: Send,
F: Fn(usize) -> R + Sync,
{
if n == 0 {
return Vec::new();
}
let workers = global_local_arena().total_workers().max(1);
let chunks = plan.optimal_chunk_count(workers);
let min_leaf = match chunks {
Some(c) if c > 0 => (n / c as usize).max(1),
_ => 1,
};
collect_indexed(plan, n, min_leaf, f)
}
const TOKEN_BUCKET_PROMOTE: u64 = 20_000;
fn token_bucket_fill<R, F, W>(
plan: &JobPlan,
items: &mut [std::mem::MaybeUninit<R>],
start: usize,
f: &F,
tokens_fn: &W,
)
where
R: Send,
F: Fn(usize) -> R + Sync,
W: Fn(usize) -> u32 + Sync,
{
let n = items.len();
if n == 0 {
return;
}
let base = items.as_mut_ptr() as *mut R;
let mut last_tick = read_tsc();
let span_t0 = last_tick;
let mut tokens_since_check: u64 = 0;
let workers = global_local_arena().total_workers();
let multiplier = crate::sched::split_observer::split_multiplier() as usize;
let max_budget = workers.saturating_mul(multiplier).max(1);
let mut i = 0;
while i < n {
let idx = start + i;
unsafe { base.add(i).write(f(idx)); }
tokens_since_check =
tokens_since_check.saturating_add(tokens_fn(idx) as u64);
i += 1;
let token_trip = tokens_since_check >= TOKEN_BUCKET_PROMOTE;
let tick_trip = (i & POLL_MASK) == 0 && {
let now = read_tsc();
let elapsed = now.wrapping_sub(last_tick);
if elapsed >= HEARTBEAT_CYCLES {
true
} else {
last_tick = now;
false
}
};
if (token_trip || tick_trip) && i + 1 < n {
let remaining = n - i;
if remaining >= 2 {
record_leaf_span_ns(plan.site, read_tsc().wrapping_sub(span_t0));
let (_filled, tail) = items.split_at_mut(i);
collect_inner(
plan, tail, start + i, f, 1,
max_budget, max_budget, false,
);
return;
}
tokens_since_check = 0;
last_tick = read_tsc();
}
}
record_leaf_span_ns(plan.site, read_tsc().wrapping_sub(span_t0));
}
fn bisect_fixed<T, F>(
plan: &JobPlan,
items: &mut [T],
op: &F,
splits: usize,
max_budget: usize,
chunk_size: usize,
migrated: bool,
)
where
T: Send,
F: Fn(&mut [T]) + Sync,
{
if items.len() <= chunk_size {
record_leaf(plan.site, || op(items));
return;
}
let cur_splits = if migrated { max_budget } else { splits };
if cur_splits <= 1 {
record_leaf(plan.site, || op(items));
return;
}
let mid = items.len() / 2;
let (left, right) = items.split_at_mut(mid);
let half = cur_splits >> 1;
join_context(
plan,
|left_inj| bisect_fixed(plan, left, op, half, max_budget, chunk_size, left_inj),
|right_stolen| bisect_fixed(plan, right, op, half, max_budget, chunk_size, right_stolen),
);
}
#[track_caller]
pub fn reduce_chunks<T, A, F, R, I>(
plan: &JobPlan,
items: &[T],
init: I,
fold: F,
reduce: R,
) -> A
where
T: Sync,
A: Send + 'static,
I: Fn() -> A + Sync,
F: Fn(A, &[T]) -> A + Sync,
R: Fn(A, A) -> A + Sync,
{
use std::sync::atomic::Ordering::Relaxed;
let plan_owned = plan.with_site_if_none(crate::sched::call_site::caller_site());
let plan = &plan_owned;
let site = plan.site.expect("attached above").get();
let trivial_reduce_cycles_threshold: u64 =
crate::sched::adaptive_profile::class_thresholds()
.trivial_reduce_cycles
.load(Relaxed);
let workers = global_local_arena().total_workers();
let multiplier = crate::sched::split_observer::split_multiplier() as usize;
let max_budget = match std::env::var("FLYNNEL_REDUCE_CHUNKS_CHUNKS")
.ok()
.and_then(|s| s.parse::<usize>().ok())
{
Some(n) if n >= 1 => n,
_ => workers.saturating_mul(multiplier).max(1),
};
if site.reduce_cost_wants_sample() {
let cal_slice_len = MIN_LEAF_ITEMS.min(items.len());
if cal_slice_len > 0 {
let cal_a = fold(init(), &items[..cal_slice_len]);
let cal_b = fold(init(), &items[..cal_slice_len]);
let t0 = read_tsc();
let drained = reduce(cal_a, cal_b);
let dt = read_tsc().wrapping_sub(t0);
site.record_reduce_cost_sample(dt);
drop(drained);
}
}
let observed_trivial = site
.reduce_cost_avg_cycles()
.is_some_and(|avg_cycles| avg_cycles < trivial_reduce_cycles_threshold);
let flat_enabled = std::env::var_os("FLYNNEL_ENABLE_FLAT_FANOUT")
.is_some_and(|v| v != "0" && v != "false" && !v.is_empty());
if flat_enabled
&& observed_trivial
&& items.len() >= max_budget.saturating_mul(MIN_LEAF_ITEMS)
{
record_reduce_chunks_path(ReduceChunksPath::Flat);
return reduce_chunks_flat(plan, items, &init, &fold, &reduce, max_budget);
}
record_reduce_chunks_path(ReduceChunksPath::Bisect);
reduce_inner(plan, items, &init, &fold, &reduce, max_budget, max_budget, false)
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ReduceChunksPath {
Flat,
Bisect,
}
thread_local! {
static LAST_REDUCE_CHUNKS_PATH: std::cell::Cell<Option<ReduceChunksPath>> =
const { std::cell::Cell::new(None) };
}
#[inline(always)]
fn record_reduce_chunks_path(p: ReduceChunksPath) {
LAST_REDUCE_CHUNKS_PATH.with(|c| c.set(Some(p)));
}
pub fn last_reduce_chunks_path() -> Option<ReduceChunksPath> {
LAST_REDUCE_CHUNKS_PATH.with(|c| c.get())
}
fn reduce_chunks_flat<T, A, F, R, I>(
plan: &JobPlan,
items: &[T],
init: &I,
fold: &F,
reduce: &R,
n_chunks: usize,
) -> A
where
T: Sync,
A: Send + 'static,
I: Fn() -> A + Sync,
F: Fn(A, &[T]) -> A + Sync,
R: Fn(A, A) -> A + Sync,
{
let len = items.len();
debug_assert!(
len >= n_chunks * MIN_LEAF_ITEMS,
"reduce_chunks_flat called below chunk-size floor: len={len}, n_chunks={n_chunks}, MIN_LEAF_ITEMS={MIN_LEAF_ITEMS}",
);
let chunk_size = len.div_ceil(n_chunks);
let n_real = len.div_ceil(chunk_size);
let item_size = std::mem::size_of::<T>();
let base_addr: usize = items.as_ptr() as usize;
let fold_addr: usize = fold as *const F as usize;
let init_addr: usize = init as *const I as usize;
let closures: Vec<Box<dyn FnOnce() -> A + Send>> = (0..n_real)
.map(|i| {
let start = i * chunk_size;
let chunk_len = chunk_size.min(len - start);
let chunk_addr = base_addr + start * item_size;
let boxed: Box<dyn FnOnce() -> A + Send> = Box::new(move || {
let chunk_ptr = chunk_addr as *const T;
let chunk: &[T] = unsafe {
std::slice::from_raw_parts(chunk_ptr, chunk_len)
};
let fold_ref: &F = unsafe { &*(fold_addr as *const F) };
let init_ref: &I = unsafe { &*(init_addr as *const I) };
fold_ref(init_ref(), chunk)
});
boxed
})
.collect();
let results = crate::sched::cooperative_join_n_flat(plan, closures);
tree_reduce_in_parallel(plan, results, reduce)
}
fn tree_reduce_in_parallel<A, R>(plan: &JobPlan, mut results: Vec<A>, reduce: &R) -> A
where
A: Send + 'static,
R: Fn(A, A) -> A + Sync,
{
while results.len() > 1 {
let reduce_addr: usize = reduce as *const R as usize;
let odd_tail = if results.len() % 2 == 1 {
results.pop()
} else {
None
};
let mut pairs: Vec<(A, A)> = Vec::with_capacity(results.len() / 2);
let mut iter = results.into_iter();
loop {
let a = match iter.next() {
Some(x) => x,
None => break,
};
let b = iter
.next()
.expect("even results count after odd-tail pop");
pairs.push((a, b));
}
let closures: Vec<Box<dyn FnOnce() -> A + Send>> = pairs
.into_iter()
.map(|(a, b)| {
let boxed: Box<dyn FnOnce() -> A + Send> = Box::new(move || {
let reduce_ref: &R = unsafe { &*(reduce_addr as *const R) };
reduce_ref(a, b)
});
boxed
})
.collect();
let mut next_round = crate::sched::cooperative_join_n_flat(plan, closures);
if let Some(extra) = odd_tail {
next_round.push(extra);
}
results = next_round;
}
results.into_iter().next().expect("at least 1 result")
}
#[allow(clippy::too_many_arguments)]
fn reduce_inner<T, A, F, R, I>(
plan: &JobPlan,
items: &[T],
init: &I,
fold: &F,
reduce: &R,
splits: usize,
max_budget: usize,
migrated: bool,
) -> A
where
T: Sync,
A: Send,
I: Fn() -> A + Sync,
F: Fn(A, &[T]) -> A + Sync,
R: Fn(A, A) -> A + Sync,
{
if items.len() <= MIN_LEAF_ITEMS {
return fold(init(), items);
}
let cur_splits = if migrated { max_budget } else { splits };
if cur_splits <= 1 {
return fold(init(), items);
}
let mid = items.len() / 2;
let (left, right) = items.split_at(mid);
let half = cur_splits >> 1;
let (la, ra) = join_context(
plan,
|left_inj| reduce_inner(plan, left, init, fold, reduce, half, max_budget, left_inj),
|right_stolen| reduce_inner(plan, right, init, fold, reduce, half, max_budget, right_stolen),
);
reduce(la, ra)
}
#[track_caller]
pub fn par_map_in_place<T, F>(plan: &JobPlan, items: &mut [T], op: F)
where
T: Send,
F: Fn(&mut T) + Sync,
{
for_each_fixed_chunk(plan, items, 1, |slice| {
for x in slice {
op(x);
}
});
}
#[track_caller]
pub fn par_zip_apply<T, U, F>(plan: &JobPlan, lhs: &mut [T], rhs: &[U], op: F)
where
T: Send,
U: Sync,
F: Fn(&mut T, &U) + Sync,
{
assert_eq!(
lhs.len(),
rhs.len(),
"par_zip_apply requires matching slice lengths"
);
let n = lhs.len();
if n == 0 {
return;
}
let lhs_addr: usize = lhs.as_mut_ptr() as usize;
let mut indices: Vec<usize> = (0..n).collect();
for_each_fixed_chunk(plan, &mut indices, 1, move |chunk| {
let lhs_ptr: *mut T = lhs_addr as *mut T;
for &i in chunk.iter() {
let t: &mut T = unsafe { &mut *lhs_ptr.add(i) };
op(t, &rhs[i]);
}
});
}
#[cfg(test)]
mod tests {
use super::*;
use std::sync::Arc;
use std::sync::atomic::{AtomicU64, Ordering};
use crate::sched::plan::JobPlan;
#[test]
fn for_each_chunk_zero_items_is_noop() {
let mut v: Vec<u32> = Vec::new();
let plan = JobPlan::new(6, 1);
for_each_chunk(&plan, &mut v, |slice| {
for x in slice {
*x += 1;
}
});
assert!(v.is_empty());
}
#[test]
fn bisect_variants_all_produce_identical_result() {
let n = 20_000usize;
let template: Vec<u32> = (0..n as u32).collect();
let run = |variant: Option<crate::sched::plan::BisectVariant>| -> Vec<u32> {
let mut v = template.clone();
let mut plan = JobPlan::new(6, n as u32);
plan.bisect_variant = variant;
for_each_chunk(&plan, &mut v, |slice| {
for x in slice {
*x = x.wrapping_mul(3).wrapping_add(7);
}
});
v
};
let baseline = run(None);
assert_eq!(run(Some(crate::sched::plan::BisectVariant::ProducerMaxLenWorkers)), baseline);
assert_eq!(run(Some(crate::sched::plan::BisectVariant::RayonStyleReplenish)), baseline);
}
#[test]
fn for_each_chunk_touches_every_element_exactly_once() {
let n = 10_000usize;
let mut v: Vec<u32> = (0..n as u32).collect();
let plan = JobPlan::new(6, n as u32);
for_each_chunk(&plan, &mut v, |slice| {
for x in slice {
*x = x.wrapping_mul(2);
}
});
for (i, &x) in v.iter().enumerate() {
assert_eq!(x, (i as u32).wrapping_mul(2),
"element {i} = {x}, expected {}", (i as u32).wrapping_mul(2));
}
}
#[test]
fn for_each_chunk_small_input_runs_serial() {
use std::sync::atomic::{AtomicUsize, Ordering};
let _profile = crate::sched::adaptive_profile::global_profile_test_lock();
crate::sched::adaptive_profile::migrate_dispatch_profile(
crate::DispatchProfile::PortBound,
);
let n = MIN_LEAF_ITEMS / 4;
let mut v: Vec<u32> = (0..n as u32).collect();
let plan = JobPlan::new(6, n as u32);
let snap = format!(
"use_smt={} est_pi={:?} explicit={} oversub={:?} global={:?}",
plan.use_smt,
plan.estimated_per_item_ns,
plan.estimated_per_item_ns_explicit,
plan.oversubscription_log2,
crate::sched::adaptive_profile::active_dispatch_profile(),
);
let calling_thread = std::thread::current().id();
let total_processed = AtomicUsize::new(0);
let off_thread_calls = AtomicUsize::new(0);
for_each_chunk(&plan, &mut v, |slice| {
if std::thread::current().id() != calling_thread {
off_thread_calls.fetch_add(1, Ordering::Relaxed);
}
total_processed.fetch_add(slice.len(), Ordering::Relaxed);
for x in slice {
*x += 1000;
}
});
assert_eq!(
off_thread_calls.load(Ordering::Relaxed),
0,
"small input must NOT dispatch to the pool [{snap}]"
);
assert_eq!(
total_processed.load(Ordering::Relaxed),
n,
"all items must be processed exactly once across probe + tail"
);
for (i, &x) in v.iter().enumerate() {
assert_eq!(x, i as u32 + 1000);
}
}
#[test]
fn for_each_fixed_chunk_respects_chunk_size() {
let n = 1000usize;
let chunk = 64;
let mut v: Vec<u32> = vec![0; n];
let plan = JobPlan::new(6, n as u32);
let sizes_seen = Arc::new(std::sync::Mutex::new(Vec::<usize>::new()));
let sizes_clone = Arc::clone(&sizes_seen);
for_each_fixed_chunk(&plan, &mut v, chunk, |slice| {
sizes_clone.lock().unwrap().push(slice.len());
for x in slice {
*x = 7;
}
});
for size in sizes_seen.lock().unwrap().iter() {
assert!(*size <= chunk,
"chunk size {} exceeded the {chunk}-item ceiling", size);
}
assert!(v.iter().all(|&x| x == 7));
}
#[test]
fn for_each_chunk_parallel_sum_matches_serial() {
let n = 50_000usize;
let mut v: Vec<u32> = (0..n as u32).collect();
let counter = Arc::new(AtomicU64::new(0));
let plan = JobPlan::new(6, n as u32);
for_each_chunk(&plan, &mut v, |slice| {
let local: u64 = slice.iter().map(|&x| x as u64).sum();
counter.fetch_add(local, Ordering::Relaxed);
});
let expected: u64 = (0..n as u64).sum();
assert_eq!(counter.load(Ordering::Relaxed), expected,
"parallel sum {} != serial sum {expected}",
counter.load(Ordering::Relaxed));
}
#[test]
fn reduce_chunks_sum_matches_serial() {
let n = 100_000usize;
let v: Vec<u64> = (0..n as u64).collect();
let plan = JobPlan::new(6, n as u32);
let parallel = reduce_chunks(
&plan,
&v,
|| 0u64,
|acc, chunk| acc + chunk.iter().sum::<u64>(),
|a, b| a + b,
);
let serial: u64 = v.iter().sum();
assert_eq!(parallel, serial);
}
#[test]
fn reduce_chunks_large_trivial_reduce_matches_serial() {
let n = 64 * 1024usize;
let v: Vec<u32> = (0..n as u32).collect();
let plan = JobPlan::new(6, n as u32).with_estimated_per_item_ns(1);
let mut last = [0u64; 256];
for _ in 0..5 {
last = reduce_chunks(
&plan, &v,
|| [0u64; 256],
|mut acc, chunk| {
for &x in chunk {
acc[(x & 0xFF) as usize] += 1;
}
acc
},
|mut a, b| {
for i in 0..256 {
a[i] += b[i];
}
a
},
);
}
let mut serial = [0u64; 256];
for &x in &v {
serial[(x & 0xFF) as usize] += 1;
}
assert_eq!(last, serial, "flat-fanout path output must match serial reference");
}
#[test]
fn bench_audit_explicit_heavy_reduce_routes_to_bisect() {
unsafe {
std::env::set_var("FLYNNEL_ENABLE_FLAT_FANOUT", "1");
}
LAST_REDUCE_CHUNKS_PATH.with(|c| c.set(None));
let n = 64 * 1024usize;
let v: Vec<u32> = (0..n as u32).collect();
let plan = JobPlan::new(6, n as u32).with_estimated_per_item_ns(1);
let mut last_path = None;
for _ in 0..8 {
let _result = reduce_chunks(
&plan, &v,
|| 0u64,
|acc, chunk| acc + chunk.iter().map(|&x| x as u64).sum::<u64>(),
|a, b| {
let t0 = read_tsc();
while read_tsc().wrapping_sub(t0) < 150_000 {
std::hint::spin_loop();
}
a.wrapping_add(b)
},
);
last_path = last_reduce_chunks_path();
}
assert_eq!(
last_path,
Some(ReduceChunksPath::Bisect),
"explicit-heavy reducer (>30k-cycle spin) must route to Bisect; got {last_path:?}"
);
}
#[test]
fn reduce_chunks_large_heavy_reduce_matches_serial() {
let n = 64 * 1024usize;
let v: Vec<u32> = (0..n as u32).collect();
let plan = JobPlan::new(6, n as u32).with_estimated_per_item_ns(1);
let mut last_sum: u64 = 0;
for _ in 0..3 {
last_sum = reduce_chunks(
&plan, &v,
|| 0u64,
|acc, chunk| acc + chunk.iter().map(|&x| x as u64).sum::<u64>(),
|a, b| {
let t0 = read_tsc();
while read_tsc().wrapping_sub(t0) < 150_000 {
std::hint::spin_loop();
}
a.wrapping_add(b)
},
);
}
let serial: u64 = v.iter().map(|&x| x as u64).sum();
assert_eq!(last_sum, serial, "bisect path output must match serial reference");
}
#[test]
fn for_each_chunk_records_leaf_time_stats() {
use crate::sched::split_observer::{
acquire_test_lock, reset_leaf_stats, snapshot_leaf_stats,
};
let _stats_lock = acquire_test_lock();
reset_leaf_stats();
let n = 5_000usize;
let mut v: Vec<u32> = (0..n as u32).collect();
let plan = JobPlan::new(6, n as u32);
for_each_chunk(&plan, &mut v, |slice| {
let mut acc: u64 = 0;
for &x in slice.iter() {
acc = acc.wrapping_add((x as u64).wrapping_mul(0x9E3779B97F4A7C15));
}
std::hint::black_box(acc);
});
let stats = snapshot_leaf_stats();
assert!(stats.count >= 1,
"expected at least one leaf recorded, got {}", stats.count);
assert!(stats.sum_ns > 0,
"expected positive total TSC delta, got {}", stats.sum_ns);
reset_leaf_stats();
}
#[test]
fn for_each_chunk_propagates_panic() {
let mut v: Vec<u32> = (0..1000).collect();
let plan = JobPlan::new(6, 1000);
let r = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
for_each_chunk(&plan, &mut v, |slice| {
if slice.first() == Some(&0) {
panic!("intentional panic from first chunk");
}
for x in slice {
*x += 1;
}
});
}));
assert!(r.is_err(), "panic in any chunk must propagate to caller");
}
#[test]
fn par_map_in_place_touches_every_element() {
let mut items: Vec<u64> = (0..256).map(|i| i as u64).collect();
let plan = JobPlan::new(8, 256);
par_map_in_place(&plan, &mut items, |b| *b = b.wrapping_mul(3));
for (i, &b) in items.iter().enumerate() {
assert_eq!(b, (i as u64).wrapping_mul(3));
}
}
#[test]
fn par_zip_apply_pairs_lhs_and_rhs_by_index() {
let mut lhs: Vec<u64> = (0..1024).collect();
let rhs: Vec<u64> = (0..1024).map(|i| i * 7).collect();
let plan = JobPlan::new(8, 1024);
par_zip_apply(&plan, &mut lhs, &rhs, |a, b| *a = a.wrapping_add(*b));
for (i, &value) in lhs.iter().enumerate().take(1024) {
let expected = (i as u64).wrapping_add((i as u64) * 7);
assert_eq!(value, expected, "index {i}");
}
}
#[test]
#[should_panic(expected = "matching slice lengths")]
fn par_zip_apply_panics_on_mismatched_lengths() {
let mut lhs: Vec<u64> = vec![0; 10];
let rhs: Vec<u64> = vec![0; 20];
let plan = JobPlan::new(8, 10);
par_zip_apply(&plan, &mut lhs, &rhs, |_a, _b| {});
}
#[test]
fn par_zip_apply_empty_is_noop() {
let mut lhs: Vec<u64> = Vec::new();
let rhs: Vec<u64> = Vec::new();
let plan = JobPlan::new(8, 0);
par_zip_apply(&plan, &mut lhs, &rhs, |_a, _b| panic!("must not run"));
assert!(lhs.is_empty());
}
#[test]
fn for_each_indexed_visits_every_index_exactly_once() {
let n = 10_000usize;
let seen: Vec<AtomicU64> = (0..n).map(|_| AtomicU64::new(0)).collect();
let plan = JobPlan::new(6, n as u32);
for_each_indexed(&plan, n, 1, |i| {
seen[i].fetch_add(1, Ordering::Relaxed);
});
for (i, s) in seen.iter().enumerate() {
assert_eq!(s.load(Ordering::Relaxed), 1, "index {i} visited {} times", s.load(Ordering::Relaxed));
}
}
#[test]
fn for_each_indexed_empty_is_noop() {
let plan = JobPlan::new(6, 0);
for_each_indexed(&plan, 0, 1, |_| panic!("must not run"));
}
#[test]
fn for_each_chunk_ref_tiles_the_slice_once_at_the_requested_width() {
let n = 4_099usize;
let width = 64usize;
let v: Vec<u32> = (0..n as u32).collect();
let seen: Vec<AtomicU64> = (0..n).map(|_| AtomicU64::new(0)).collect();
let widths = Arc::new(std::sync::Mutex::new(Vec::<(usize, usize)>::new()));
let widths_clone = Arc::clone(&widths);
let plan = JobPlan::new(6, n as u32);
for_each_chunk_ref(&plan, &v, width, |start, chunk| {
widths_clone.lock().unwrap().push((start, chunk.len()));
for (k, &x) in chunk.iter().enumerate() {
assert_eq!(x as usize, start + k, "chunk at {start} holds the wrong items");
seen[start + k].fetch_add(1, Ordering::Relaxed);
}
});
for (i, s) in seen.iter().enumerate() {
assert_eq!(s.load(Ordering::Relaxed), 1, "item {i} covered {} times", s.load(Ordering::Relaxed));
}
let mut widths = widths.lock().unwrap().clone();
widths.sort_unstable();
assert_eq!(widths.len(), n.div_ceil(width), "one chunk per width-sized tile");
for (k, &(start, len)) in widths.iter().enumerate() {
assert_eq!(start, k * width, "chunk {k} starts at the wrong index");
let expected = if k + 1 == widths.len() { n - k * width } else { width };
assert_eq!(len, expected, "chunk {k} has the wrong width");
}
}
#[test]
fn for_each_chunk_ref_empty_is_noop() {
let v: Vec<u32> = Vec::new();
let plan = JobPlan::new(6, 0);
for_each_chunk_ref(&plan, &v, 16, |_, _| panic!("must not run"));
}
}