use crate::sched::arena::{global_local_arena, join_context};
use crate::sched::plan::JobPlan;
const HEARTBEAT_NS: u64 = 20_000;
#[cfg(target_arch = "x86_64")]
const HEARTBEAT_CYCLES: u64 = 60_000;
#[inline(always)]
fn heartbeat_ticks() -> u64 {
#[cfg(target_arch = "x86_64")]
{
match TSC_PER_NS_16.load(std::sync::atomic::Ordering::Relaxed) {
0 => HEARTBEAT_CYCLES,
rate_16 => HEARTBEAT_NS.saturating_mul(rate_16) >> 4,
}
}
#[cfg(not(target_arch = "x86_64"))]
{
HEARTBEAT_NS
}
}
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"))]
{
static ORIGIN: std::sync::OnceLock<std::time::Instant> = std::sync::OnceLock::new();
ORIGIN
.get_or_init(std::time::Instant::now)
.elapsed()
.as_nanos() as u64
}
}
static TSC_PER_NS_16: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(0);
pub(crate) fn tsc_per_ns_16() -> u64 {
use std::sync::atomic::Ordering;
let installed = TSC_PER_NS_16.load(Ordering::Relaxed);
if installed != 0 {
return installed;
}
let rate = measure_tsc_per_ns_16();
TSC_PER_NS_16.store(rate, Ordering::Relaxed);
rate
}
fn measure_tsc_per_ns_16() -> u64 {
#[cfg(not(target_arch = "x86_64"))]
{
return 16;
}
#[cfg(target_arch = "x86_64")]
{
let mut best = 0u64;
for _ in 0..3 {
let wall_start = std::time::Instant::now();
let tsc_start = read_tsc();
while wall_start.elapsed() < std::time::Duration::from_millis(1) {
std::hint::spin_loop();
}
let ticks = read_tsc().wrapping_sub(tsc_start);
let nanos = wall_start.elapsed().as_nanos() as u64;
if nanos == 0 {
continue;
}
let per_ns_16 = ticks.saturating_mul(16) / nanos;
if per_ns_16 > best {
best = per_ns_16;
}
}
if !(16..=256).contains(&best) {
notice!(
"flynnel: the timestamp counter measured {} ticks per nanosecond in sixteenths, \
which is outside 1 to 16 per nanosecond; leaf times are read as nanoseconds \
instead",
best
);
return 16;
}
best
}
}
#[inline(always)]
fn record_leaf<F: FnOnce() -> R, R>(
site: Option<crate::sched::call_site::SiteRef>,
items: usize,
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, items as u64, None);
});
out
}
#[inline(always)]
fn record_leaf_on_core<F: FnOnce() -> R, R>(
site: Option<crate::sched::call_site::SiteRef>,
items: usize,
body: F,
) -> R {
let (thread_before, _) = crate::sched::occupancy::clock_pair();
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);
let (thread_after, _) = crate::sched::occupancy::clock_pair();
let on_core = match (thread_before.ticks(), thread_after.ticks()) {
(Some(before), Some(after)) => Some(after.saturating_sub(before)),
_ => None,
};
LOCAL_LEAF_BUFFER.with(|cell| {
let mut buf = cell.borrow_mut();
buf.add(site, dt, items as u64, on_core);
});
out
}
#[inline(always)]
fn per_item_square(nanos: u64, items: u64) -> u64 {
(nanos as u128)
.saturating_mul(nanos as u128)
.checked_div((items as u128) << 16)
.unwrap_or(0) as u64
}
#[inline(always)]
pub(crate) fn record_leaf_span_ns(
site: Option<crate::sched::call_site::SiteRef>,
nanos: u64,
items: u64,
) {
if let Some(site) = site {
let scaled = nanos >> 8;
site.get().record_batch_site_only(
nanos,
scaled.saturating_mul(scaled),
1,
items,
per_item_square(nanos, items),
);
}
}
#[inline(always)]
fn record_leaf_span_ticks(site: Option<crate::sched::call_site::SiteRef>, ticks: u64, items: u64) {
if site.is_some() {
let (nanos, _) = LocalLeafBuffer::as_nanos(ticks, 0);
record_leaf_span_ns(site, nanos, items);
}
}
struct LocalLeafBuffer {
global_sum_ns: u64,
global_sumsq_scaled: u64,
global_count: u64,
global_items: u64,
global_sumsq_per_item: u64,
site_sum_ns: u64,
site_sumsq_scaled: u64,
site_count: u64,
site_items: u64,
site_sumsq_per_item: u64,
site_thread_at_start: crate::sched::occupancy::ThreadTicks,
site_wall_at_start: u64,
site_oncore_sum: u64,
site_oncore_sumsq_per_item: u64,
site_oncore_items: 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,
global_items: 0,
global_sumsq_per_item: 0,
site_sum_ns: 0,
site_sumsq_scaled: 0,
site_count: 0,
site_items: 0,
site_sumsq_per_item: 0,
site_thread_at_start: crate::sched::occupancy::ThreadTicks::Absent(
crate::sched::occupancy::NoReading::NoClock,
),
site_wall_at_start: 0,
site_oncore_sum: 0,
site_oncore_sumsq_per_item: 0,
site_oncore_items: 0,
site: core::ptr::null(),
}
}
#[inline(always)]
fn add(
&mut self,
site: Option<crate::sched::call_site::SiteRef>,
nanos: u64,
items: u64,
oncore: Option<u64>,
) {
let scaled = nanos >> 8;
let sq = scaled.saturating_mul(scaled);
let per_item_sq = per_item_square(nanos, items);
self.global_sum_ns = self.global_sum_ns.saturating_add(nanos);
self.global_sumsq_scaled = self.global_sumsq_scaled.saturating_add(sq);
self.global_items = self.global_items.saturating_add(items);
self.global_sumsq_per_item = self.global_sumsq_per_item.saturating_add(per_item_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;
}
if self.site_count == 0 {
let (thread, wall) = crate::sched::occupancy::clock_pair();
self.site_thread_at_start = thread;
self.site_wall_at_start = wall;
}
self.site_sum_ns = self.site_sum_ns.saturating_add(nanos);
self.site_sumsq_scaled = self.site_sumsq_scaled.saturating_add(sq);
self.site_items = self.site_items.saturating_add(items);
self.site_sumsq_per_item = self.site_sumsq_per_item.saturating_add(per_item_sq);
if let Some(ticks) = oncore {
let per_item_oncore = (ticks as u128)
.saturating_mul(ticks as u128)
.checked_div((items as u128) << 16)
.unwrap_or(0) as u64;
self.site_oncore_sum = self.site_oncore_sum.saturating_add(ticks);
self.site_oncore_sumsq_per_item =
self.site_oncore_sumsq_per_item.saturating_add(per_item_oncore);
self.site_oncore_items = self.site_oncore_items.saturating_add(items);
}
self.site_count += 1;
if self.site_count >= Self::FLUSH_THRESHOLD {
self.flush_site();
}
}
}
fn as_nanos(sum_ticks: u64, sumsq_scaled: u64) -> (u64, u64) {
let per_ns_16 = tsc_per_ns_16();
if per_ns_16 == 0 {
return (sum_ticks, sumsq_scaled);
}
let sum_ns = sum_ticks.saturating_mul(16) / per_ns_16;
let sumsq_ns = sumsq_scaled
.saturating_mul(256)
/ per_ns_16.saturating_mul(per_ns_16).max(1);
(sum_ns, sumsq_ns)
}
fn flush_global(&mut self) {
if self.global_count == 0 {
return;
}
let (sum_ns, sumsq_scaled) =
Self::as_nanos(self.global_sum_ns, self.global_sumsq_scaled);
let (_, sumsq_per_item) = Self::as_nanos(0, self.global_sumsq_per_item);
crate::sched::split_observer::record_leaf_batch(
sum_ns,
sumsq_scaled,
self.global_count,
self.global_items,
sumsq_per_item,
);
self.global_sum_ns = 0;
self.global_sumsq_scaled = 0;
self.global_count = 0;
self.global_items = 0;
self.global_sumsq_per_item = 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 };
let (thread, wall) = crate::sched::occupancy::clock_pair();
let weight = if let (Some(start), Some(end)) =
(self.site_thread_at_start.ticks(), thread.ticks())
{
let on_core = end.saturating_sub(start);
let elapsed = wall.saturating_sub(self.site_wall_at_start);
site.add_pool_ticks(on_core, elapsed);
crate::sched::levers::batch_weight()
.then(|| crate::sched::call_site::batch_weight_per_mille(on_core, elapsed))
.flatten()
} else {
None
};
let (sum_ns, sumsq_scaled) =
Self::as_nanos(self.site_sum_ns, self.site_sumsq_scaled);
let (_, sumsq_per_item) = Self::as_nanos(0, self.site_sumsq_per_item);
site.record_batch_weighted(
sum_ns,
sumsq_scaled,
self.site_count,
self.site_items,
sumsq_per_item,
weight,
);
site.record_oncore_batch(
self.site_oncore_sum,
self.site_oncore_sumsq_per_item,
self.site_oncore_items,
);
self.site_oncore_sum = 0;
self.site_oncore_sumsq_per_item = 0;
self.site_oncore_items = 0;
self.site_sum_ns = 0;
self.site_sumsq_scaled = 0;
self.site_count = 0;
self.site_items = 0;
self.site_sumsq_per_item = 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 RecordRoutingArm {
site: Option<crate::sched::call_site::SiteRef>,
arm: Option<crate::sched::call_site::PolicyArm>,
started: std::time::Instant,
}
impl RecordRoutingArm {
fn start(
site: Option<crate::sched::call_site::SiteRef>,
arm: Option<crate::sched::call_site::PolicyArm>,
) -> Self {
Self { site, arm, started: std::time::Instant::now() }
}
}
impl Drop for RecordRoutingArm {
fn drop(&mut self) {
let Some(site) = self.site else {
return;
};
let Some(arm) = self.arm else {
return;
};
site.get()
.record_routing_arm(arm, self.started.elapsed().as_nanos() as u64);
}
}
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_LEAF_WORK_NS: u64 = 1_000_000;
static SEED_HYSTERESIS: std::sync::atomic::AtomicBool =
std::sync::atomic::AtomicBool::new(true);
static STABILIZERS_FROM_ENV: std::sync::Once = std::sync::Once::new();
fn stabilizers_from_env() {
STABILIZERS_FROM_ENV.call_once(|| {
let off = matches!(
std::env::var_os("FLYNNEL_SEED_HYSTERESIS").as_deref(),
Some(v) if v == "0"
);
SEED_HYSTERESIS.store(!off, std::sync::atomic::Ordering::Relaxed);
});
}
pub fn seed_hysteresis() -> bool {
stabilizers_from_env();
SEED_HYSTERESIS.load(std::sync::atomic::Ordering::Relaxed)
}
fn seed_depth_reporting() -> bool {
static ON: std::sync::OnceLock<bool> = std::sync::OnceLock::new();
*ON.get_or_init(|| std::env::var_os("FLYNNEL_SEED_DEPTH").is_some())
}
pub fn set_seed_hysteresis(on: bool) -> bool {
stabilizers_from_env();
SEED_HYSTERESIS.swap(on, std::sync::atomic::Ordering::Relaxed)
}
#[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 estimate_ns = plan.estimated_per_item_ns;
let target_leaf_count = match estimate_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;
let depth = depth.max(workers_log2);
let depth = match plan.site {
Some(site) if seed_hysteresis() => site.get().stabilize_seed_depth(depth),
_ => depth,
};
let depth = if plan.oversubscription_log2_explicit {
let items_log2 = (items as u64).next_power_of_two().trailing_zeros() as usize;
depth
.saturating_add(plan.effective_oversubscription_log2() as usize)
.min(items_log2)
} else {
depth
};
if let Some(site) = plan.site {
site.get().record_seed_depth(depth);
}
if seed_depth_reporting() {
static LAST_SHAPE: core::sync::atomic::AtomicU64 =
core::sync::atomic::AtomicU64::new(u64::MAX);
let ns = plan.estimated_per_item_ns.unwrap_or(0);
let key = ((items as u64) << 32) | ns as u64;
if LAST_SHAPE.swap(key, core::sync::atomic::Ordering::Relaxed) != key {
notice!(
"seed depth: items {items} per_item_ns {:?} effective_ns {:?} \
workers {workers} target_leaves {target_leaf_count} \
seeded_leaves {} depth {depth}",
plan.estimated_per_item_ns,
estimate_ns,
1usize << depth
);
}
}
depth
}
#[inline]
fn adaptive_min_leaf(plan: &JobPlan, caller_floor: usize) -> usize {
if !plan.estimated_per_item_ns_explicit {
if let Some(site) = plan.site
&& let Some(per_item_ns) = site.get().per_item_ns()
&& per_item_ns > 0
{
let from_cost = (pool_dispatch_cost_ns() / per_item_ns).max(1) as usize;
return from_cost.min(caller_floor);
}
if plan.use_smt {
return 1;
}
return caller_floor;
}
match plan.estimated_per_item_ns {
Some(ns) if ns > 0 => {
let raw = (pool_dispatch_cost_ns() / ns as u64).max(1) as usize;
raw.min(caller_floor)
}
_ => caller_floor,
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct HostDispatchProfile {
pub dispatch_cost_ns: u64,
pub collapse_threshold_ns: u64,
pub jec_wake_threshold_ns: u64,
}
static HOST_DISPATCH_COST_NS: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(0);
static HOST_COLLAPSE_THRESHOLD_NS: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(0);
static HOST_JEC_WAKE_THRESHOLD_NS: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(0);
pub(crate) fn installed_dispatch_cost_ns() -> u64 {
use std::sync::atomic::Ordering;
if HOST_COLLAPSE_THRESHOLD_NS.load(Ordering::Acquire) == 0 {
return 0;
}
HOST_DISPATCH_COST_NS.load(Ordering::Relaxed)
}
pub fn host_dispatch_profile() -> HostDispatchProfile {
use std::sync::atomic::Ordering;
let collapse = HOST_COLLAPSE_THRESHOLD_NS.load(Ordering::Acquire);
if collapse != 0 {
return HostDispatchProfile {
dispatch_cost_ns: HOST_DISPATCH_COST_NS.load(Ordering::Relaxed),
collapse_threshold_ns: collapse,
jec_wake_threshold_ns: HOST_JEC_WAKE_THRESHOLD_NS.load(Ordering::Relaxed),
};
}
if CALIBRATING
.compare_exchange(false, true, Ordering::AcqRel, Ordering::Acquire)
.is_ok()
{
let _in_flight = CalibrationInFlight;
return calibrate_host_dispatch();
}
if !crate::sched::arena_local::current_worker_ctx().is_null() {
return HostDispatchProfile {
dispatch_cost_ns: 0,
collapse_threshold_ns: 0,
jec_wake_threshold_ns: 0,
};
}
let mut spins = 0u32;
loop {
let collapse = HOST_COLLAPSE_THRESHOLD_NS.load(Ordering::Acquire);
if collapse != 0 {
return HostDispatchProfile {
dispatch_cost_ns: HOST_DISPATCH_COST_NS.load(Ordering::Relaxed),
collapse_threshold_ns: collapse,
jec_wake_threshold_ns: HOST_JEC_WAKE_THRESHOLD_NS.load(Ordering::Relaxed),
};
}
if CALIBRATING
.compare_exchange(false, true, Ordering::AcqRel, Ordering::Acquire)
.is_ok()
{
let _in_flight = CalibrationInFlight;
return calibrate_host_dispatch();
}
if spins < 1_000 {
spins += 1;
std::hint::spin_loop();
} else {
std::thread::yield_now();
}
}
}
static CALIBRATING: std::sync::atomic::AtomicBool = std::sync::atomic::AtomicBool::new(false);
struct CalibrationInFlight;
impl Drop for CalibrationInFlight {
fn drop(&mut self) {
CALIBRATING.store(false, std::sync::atomic::Ordering::Release);
}
}
pub fn inline_collapse_threshold_ns() -> u64 {
host_dispatch_profile().collapse_threshold_ns
}
pub fn pool_dispatch_cost_ns() -> u64 {
host_dispatch_profile().dispatch_cost_ns
}
pub fn measured_collapse_threshold_ns() -> Option<u64> {
match HOST_COLLAPSE_THRESHOLD_NS.load(std::sync::atomic::Ordering::Relaxed) {
0 => None,
ns => Some(ns),
}
}
pub fn jec_wake_threshold_ns() -> u64 {
host_dispatch_profile().jec_wake_threshold_ns
}
pub fn calibrate_host_dispatch() -> HostDispatchProfile {
use std::sync::atomic::Ordering;
let p = match pinned_host_profile() {
Some(pinned) => pinned,
None => stored_or_measured(),
};
HOST_DISPATCH_COST_NS.store(p.dispatch_cost_ns, Ordering::Relaxed);
HOST_JEC_WAKE_THRESHOLD_NS.store(p.jec_wake_threshold_ns, Ordering::Relaxed);
HOST_COLLAPSE_THRESHOLD_NS.store(p.collapse_threshold_ns, Ordering::Release);
p
}
#[cfg(feature = "persisted-calibration")]
fn stored_or_measured() -> HostDispatchProfile {
use crate::sched::calibration_store::{
CalibrationStore, CpuCalibration, HostStamp, StoreError, calibration_dir,
};
let Some(dir) = calibration_dir() else {
return draw_host_dispatch().profile;
};
let stamp = HostStamp::detect();
let store = match CalibrationStore::open_or_create(&dir, &stamp) {
Ok(s) => s,
Err(e) => {
notice!(
"flynnel: the calibration table under {} is unusable ({e:?}); \
this process measures its own dispatch profile",
dir.display()
);
return draw_host_dispatch().profile;
}
};
if let Some((cpu, _accel)) = store.read()
&& stored_record_serves(&cpu, configured_max_age_s(), now_unix_s())
{
if std::env::var_os("FLYNNEL_OCCUPANCY").is_some() {
let age_s = now_unix_s().saturating_sub(cpu.measured_unix_s);
let lasts = match configured_max_age_s() {
Some(bound) if bound > 0 => format!("serves until it is {bound} s old"),
_ => "serves until the layout version changes".to_string(),
};
notice!(
"flynnel: host profile {},{},{} READ from the stored record, not \
measured; it was drawn {age_s} s ago at {} per mille occupancy with \
spread {} per mille and {lasts}",
cpu.dispatch_cost_ns,
cpu.collapse_threshold_ns,
cpu.jec_wake_threshold_ns,
cpu.occupancy().map_or_else(|| "an unrecorded".to_string(), |o| o.to_string()),
cpu.spread_per_mille,
);
}
return HostDispatchProfile {
dispatch_cost_ns: cpu.dispatch_cost_ns,
collapse_threshold_ns: cpu.collapse_threshold_ns,
jec_wake_threshold_ns: cpu.jec_wake_threshold_ns,
};
}
let Draw { profile, spread, occupancy: drawn_at, publishable } = draw_host_dispatch();
if std::env::var_os("FLYNNEL_OCCUPANCY").is_some() {
notice!(
"flynnel: host profile {},{},{}",
profile.dispatch_cost_ns,
profile.collapse_threshold_ns,
profile.jec_wake_threshold_ns,
);
match drawn_at {
Some(share) => notice!(
"flynnel: host calibration ran at {share} per mille occupancy, \
spread {spread} per mille",
),
None => notice!(
"flynnel: host calibration measured no occupancy on this platform, \
spread {spread} per mille",
),
}
}
if !publishable {
notice!(
"flynnel: this draw was taken on a pool worker, whose joins time its own inline \
pass rather than a dispatch, so it routes this process and is not stored"
);
return profile;
}
match store.try_acquire_writer() {
Ok(writer) => {
writer.beat();
let outcome = writer.publish_if_better(
&CpuCalibration::new(
profile.dispatch_cost_ns,
profile.collapse_threshold_ns,
profile.jec_wake_threshold_ns,
spread,
SAMPLES as u32,
drawn_at,
),
&[],
);
use crate::sched::calibration_store::PublishOutcome;
match outcome {
PublishOutcome::KeptIncumbent { incumbent, offered, confirmations } => {
notice!(
"flynnel: this host's stored calibration dispatches in {incumbent} \
ns and this one in {offered}; the cheaper record stands and this \
process uses what it measured. It carries {confirmations} \
agreeing draw(s){}",
if confirmations == 0 {
", so it stays provisional and the next start measures again"
} else {
" and serves the next start"
}
);
}
PublishOutcome::Published { confirmations: 0 } => notice!(
"flynnel: this draw is stored and provisional; nothing has agreed \
with it yet, so the next start measures again and the two are \
compared"
),
PublishOutcome::Published { confirmations } => notice!(
"flynnel: this draw is stored with {confirmations} agreeing draw(s) \
and serves the next start"
),
}
}
Err(StoreError::WriterActive) => {}
Err(e) => notice!(
"flynnel: measured this host but could not publish it ({e:?}); \
the next process measures again"
),
}
profile
}
#[cfg(feature = "persisted-calibration")]
fn stored_record_serves(
cpu: &crate::sched::calibration_store::CpuCalibration,
max_age_s: Option<u64>,
now_s: u64,
) -> bool {
if !crate::sched::levers::serve_policy().admits(cpu) {
return false;
}
match max_age_s {
None | Some(0) => true,
Some(max) => now_s.saturating_sub(cpu.measured_unix_s) <= max,
}
}
#[cfg(feature = "persisted-calibration")]
pub const DEFAULT_CALIBRATION_MAX_AGE_S: u64 = 86_400;
#[cfg(feature = "persisted-calibration")]
fn configured_max_age_s() -> Option<u64> {
let Some(raw) = std::env::var_os("FLYNNEL_CALIBRATION_MAX_AGE_S") else {
return Some(DEFAULT_CALIBRATION_MAX_AGE_S);
};
let Some(text) = raw.to_str() else {
notice!(
"flynnel: FLYNNEL_CALIBRATION_MAX_AGE_S is not valid UTF-8; using the \
default of {DEFAULT_CALIBRATION_MAX_AGE_S}s"
);
return Some(DEFAULT_CALIBRATION_MAX_AGE_S);
};
match text.trim().parse::<u64>() {
Ok(v) => Some(v),
Err(e) => {
notice!(
"flynnel: FLYNNEL_CALIBRATION_MAX_AGE_S wants a whole number of \
seconds and got {text:?} ({e}); using the default of \
{DEFAULT_CALIBRATION_MAX_AGE_S}s"
);
Some(DEFAULT_CALIBRATION_MAX_AGE_S)
}
}
}
#[cfg(feature = "persisted-calibration")]
fn now_unix_s() -> u64 {
match std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH) {
Ok(d) => d.as_secs(),
Err(e) => {
notice!(
"flynnel: this host's clock reads before the epoch ({e}), so a stored \
calibration's age cannot be taken and it stands"
);
0
}
}
}
#[cfg(not(feature = "persisted-calibration"))]
fn stored_or_measured() -> HostDispatchProfile {
draw_host_dispatch().profile
}
#[cfg_attr(
not(feature = "persisted-calibration"),
expect(dead_code, reason = "only the persisted path stores a draw, so only it reads these")
)]
struct Draw {
profile: HostDispatchProfile,
spread: u32,
occupancy: Option<u32>,
publishable: bool,
}
fn draw_host_dispatch() -> Draw {
use std::sync::atomic::{AtomicBool, Ordering};
let ctx_ptr = crate::sched::arena_local::current_worker_ctx();
if ctx_ptr.is_null() {
return draw_on_this_thread(true);
}
let ctx = unsafe { &*ctx_ptr };
let ended = AtomicBool::new(false);
std::thread::scope(|scope| {
let spawned = std::thread::Builder::new()
.name("flynnel-calibration".to_string())
.spawn_scoped(scope, || {
let _ended = SetOnDrop(&ended);
draw_on_this_thread(true)
});
let helper = match spawned {
Ok(helper) => helper,
Err(e) => {
notice!(
"flynnel: could not start a thread to calibrate outside the pool ({e}); \
this worker draws on itself, so its dispatch cost times its own inline \
pass, and the draw is not stored"
);
return draw_on_this_thread(false);
}
};
let mut idle_rounds = 0u32;
while !ended.load(Ordering::Acquire) {
match ctx.find_work() {
Some(job) => {
unsafe { job.execute() };
idle_rounds = 0;
}
None if idle_rounds < 1_000 => {
idle_rounds += 1;
std::hint::spin_loop();
}
None => std::thread::yield_now(),
}
}
match helper.join() {
Ok(draw) => draw,
Err(panic) => std::panic::resume_unwind(panic),
}
})
}
fn draw_on_this_thread(publishable: bool) -> Draw {
let window = crate::sched::occupancy::OccupancyWindow::start();
let (profile, spread) = measure_host_dispatch();
Draw { profile, spread, occupancy: window.sample().per_mille(), publishable }
}
struct SetOnDrop<'a>(&'a std::sync::atomic::AtomicBool);
impl Drop for SetOnDrop<'_> {
fn drop(&mut self) {
self.0.store(true, std::sync::atomic::Ordering::Release);
}
}
fn interpolate_crossover(prev: Option<(u64, i64)>, a: u64, diff: i64) -> u64 {
match prev {
Some((a_prev, d_prev)) if d_prev > diff && a > a_prev => {
let span = (a - a_prev) as f64;
let frac = d_prev as f64 / (d_prev - diff) as f64;
a_prev + (span * frac) as u64
}
_ => a,
}
}
pub fn calibrate_inline_collapse_threshold() -> u64 {
calibrate_host_dispatch().collapse_threshold_ns
}
fn pinned_host_profile() -> Option<HostDispatchProfile> {
let raw = std::env::var_os("FLYNNEL_HOST_PROFILE_NS")?;
match raw.to_str() {
Some(text) => parse_pinned_profile(text),
None => {
notice!(
"flynnel: FLYNNEL_HOST_PROFILE_NS is not valid UTF-8; measuring this host instead"
);
None
}
}
}
fn parse_pinned_profile(text: &str) -> Option<HostDispatchProfile> {
let mut fields = text.split(',');
let mut take = |what: &str| -> Option<u64> {
let Some(field) = fields.next() else {
notice!(
"flynnel: FLYNNEL_HOST_PROFILE_NS wants dispatch,collapse,wake in ns; the {what} field is missing, so measuring this host instead"
);
return None;
};
match field.trim().parse::<u64>() {
Ok(0) => {
notice!(
"flynnel: FLYNNEL_HOST_PROFILE_NS {what} is zero, which marks an uncalibrated profile; measuring this host instead"
);
None
}
Ok(ns) => Some(ns),
Err(e) => {
notice!(
"flynnel: FLYNNEL_HOST_PROFILE_NS {what} field {field:?} is not a nanosecond count ({e}); measuring this host instead"
);
None
}
}
};
let dispatch_cost_ns = take("dispatch")?;
let collapse_threshold_ns = take("collapse")?;
let jec_wake_threshold_ns = take("wake")?;
if fields.next().is_some() {
notice!(
"flynnel: FLYNNEL_HOST_PROFILE_NS takes exactly dispatch,collapse,wake; measuring this host instead"
);
return None;
}
Some(HostDispatchProfile {
dispatch_cost_ns,
collapse_threshold_ns,
jec_wake_threshold_ns,
})
}
struct ReportOccupancy {
thread_at_start: u64,
wall_at_start: u64,
site: crate::sched::call_site::SiteRef,
}
impl ReportOccupancy {
fn start(site: crate::sched::call_site::SiteRef) -> Self {
let (thread_at_start, wall_at_start) = site.get().pool_ticks();
Self { thread_at_start, wall_at_start, site }
}
}
impl Drop for ReportOccupancy {
fn drop(&mut self) {
let (thread, wall) = self.site.get().pool_ticks();
let elapsed = wall.saturating_sub(self.wall_at_start);
if elapsed == 0 {
return;
}
let on_core = thread.saturating_sub(self.thread_at_start);
let pct = on_core.saturating_mul(100) / elapsed;
self.site.get().record_occupancy(pct.min(100) as u32);
}
}
const SAMPLES: usize = 9;
fn measure_host_dispatch() -> (HostDispatchProfile, u32) {
const LEAF: usize = 256;
const MAX_ITEMS: usize = 1 << 17;
const DIRECT_SAMPLES: usize = 1024;
fn fastest<F: FnMut()>(mut f: F) -> u64 {
let mut samples = [0u64; SAMPLES];
for slot in &mut samples {
let t0 = std::time::Instant::now();
f();
*slot = t0.elapsed().as_nanos() as u64;
}
samples.sort_unstable();
if std::env::var_os("FLYNNEL_PROFILE_SAMPLES").is_some() {
notice!(
"profile point: min {} median {} max {} samples {samples:?}",
samples[0],
samples[SAMPLES / 2],
samples[SAMPLES - 1]
);
}
samples[0]
}
fn body(items: &mut [u64]) {
for x in items.iter_mut() {
let mut v = *x;
for _ in 0..8 {
v = v.wrapping_mul(0x9E37_79B9_7F4A_7C15).rotate_left(13);
}
*x = v;
}
std::hint::black_box(&*items);
}
fn dispatched(plan: &JobPlan, items: &mut [u64]) {
if items.len() <= LEAF {
body(items);
return;
}
let mid = items.len() >> 1;
let (lo, hi) = items.split_at_mut(mid);
join_context(plan, |_| dispatched(plan, lo), |_| dispatched(plan, hi));
}
fn sweep<A, B>(v: &mut [u64], mut first: A, mut second: B) -> u64
where
A: FnMut(&JobPlan, &mut [u64]),
B: FnMut(&JobPlan, &mut [u64]),
{
let mut n = 4 * LEAF;
let mut prev: Option<(u64, i64)> = None;
loop {
let plan = JobPlan::new(0, n as u32);
let a = fastest(|| first(&plan, &mut v[..n]));
let b = fastest(|| second(&plan, &mut v[..n]));
let diff = b as i64 - a as i64;
if diff <= 0 {
return interpolate_crossover(prev, a, diff);
}
if n >= v.len() {
return a;
}
prev = Some((a, diff));
n <<= 1;
}
}
fn median_sweep<F: FnMut() -> u64>(mut sweep_once: F) -> (u64, u32) {
let mut samples = [0u64; SAMPLES];
for slot in &mut samples {
*slot = sweep_once();
}
samples.sort_unstable();
if std::env::var_os("FLYNNEL_PROFILE_SAMPLES").is_some() {
notice!(
"profile sweep: min {} median {} max {} spread {} iqr {} per mille samples {samples:?}",
samples[0],
samples[SAMPLES / 2],
samples[SAMPLES - 1],
sample_spread_per_mille(&samples),
sample_iqr_per_mille(&samples),
);
}
(samples[SAMPLES / 2], sample_spread_per_mille(&samples))
}
let mut v: Vec<u64> = (0..MAX_ITEMS as u64).collect();
let warm = JobPlan::new(0, (4 * LEAF) as u32);
for _ in 0..16 {
dispatched(&warm, &mut v[..4 * LEAF]);
}
body(&mut v);
let plan_two = JobPlan::new(0, 2);
let mut samples = [0u64; DIRECT_SAMPLES];
for slot in &mut samples {
let (lo, hi) = v[..2].split_at_mut(1);
let t0 = std::time::Instant::now();
join_context(&plan_two, |_| body(lo), |_| body(hi));
*slot = t0.elapsed().as_nanos() as u64;
}
samples.sort_unstable();
let dispatch_cost_ns = samples[DIRECT_SAMPLES / 2].max(1);
let serial_vs_pool = |v: &mut [u64]| {
sweep(v, |_, items| body(items), dispatched)
};
let (collapse_median, collapse_spread) = median_sweep(|| serial_vs_pool(&mut v));
let collapse_threshold_ns = collapse_median.max(dispatch_cost_ns);
let polling_vs_wake = |v: &mut [u64]| {
sweep(
v,
|plan, items| {
let _scope = crate::sched::arena_local::DispatchScope::new_if_change(false);
dispatched(plan, items);
},
|plan, items| {
let _scope = crate::sched::arena_local::DispatchScope::new_if_change(true);
dispatched(plan, items);
},
)
};
let (jec_wake_threshold_ns, wake_spread) = median_sweep(|| polling_vs_wake(&mut v));
(
HostDispatchProfile { dispatch_cost_ns, collapse_threshold_ns, jec_wake_threshold_ns },
collapse_spread.max(wake_spread),
)
}
pub fn sample_spread_per_mille(sorted: &[u64]) -> u32 {
if sorted.len() < 2 {
return 0;
}
let median = sorted[sorted.len() / 2].max(1);
let span = sorted[sorted.len() - 1].saturating_sub(sorted[0]);
(span.saturating_mul(1000) / median).min(u32::MAX as u64) as u32
}
pub fn sample_iqr_per_mille(sorted: &[u64]) -> u32 {
if sorted.len() < 4 {
return 0;
}
let median = sorted[sorted.len() / 2].max(1);
let q1 = sorted[sorted.len() / 4];
let q3 = sorted[(sorted.len() * 3) / 4];
(q3.saturating_sub(q1).saturating_mul(1000) / median).min(u32::MAX as u64) as u32
}
#[inline]
fn capped_to_caller(plan: &JobPlan) -> bool {
plan.capped_to_caller()
}
#[inline]
fn runs_on_caller(plan: &JobPlan, n: usize) -> bool {
capped_to_caller(plan) || collapses_inline(plan, n)
}
#[inline]
fn collapses_inline(plan: &JobPlan, n: usize) -> bool {
if plan.site.is_some_and(|s| s.get().collapse_overran()) {
return false;
}
plan.estimated_per_item_ns_explicit
&& plan.effective_ns_per_elem().is_some_and(|per| {
(per as u64).saturating_mul(n as u64) < inline_collapse_threshold_ns()
})
}
#[inline]
fn run_on_caller<R>(plan: &JobPlan, items: usize, body: impl FnOnce() -> R) -> R {
let t0 = std::time::Instant::now();
let out = record_leaf(plan.site, items, body);
if !capped_to_caller(plan)
&& let Some(site) = plan.site
{
site.get()
.note_collapsed_body(t0.elapsed().as_nanos() as u64, inline_collapse_threshold_ns());
}
out
}
#[track_caller]
pub fn for_each_chunk<T, F>(plan: &JobPlan, items: &mut [T], op: F)
where
T: Send,
F: Fn(&mut [T]) + Sync,
{
for_each_chunk_min_leaf(plan, items, MIN_LEAF_ITEMS, op)
}
#[track_caller]
pub fn for_each_chunk_min_leaf<T, F>(
plan: &JobPlan,
items: &mut [T],
min_leaf: usize,
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, routing_arm) = plan
.with_site_if_none(crate::sched::call_site::caller_site())
.apply_site_class_measured();
let _routing = RecordRoutingArm::start(plan_owned.site, routing_arm);
let plan = &plan_owned;
let _occupancy = plan.site.map(ReportOccupancy::start);
let _flush_on_exit = FlushLeafStatsOnExit;
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 >= jec_wake_threshold_ns();
let _jec_scope = crate::sched::arena_local::DispatchScope::new_if_change(use_jec_wake);
if runs_on_caller(plan, n) {
run_on_caller(plan, items.len(), || op(items));
return;
}
let workers = plan.effective_workers(global_local_arena().total_workers());
let effective_min_leaf = adaptive_min_leaf(plan, min_leaf.max(1));
if seed_depth_reporting() {
static LAST_FLOOR_SHAPE: core::sync::atomic::AtomicU64 =
core::sync::atomic::AtomicU64::new(u64::MAX);
let ns = plan.estimated_per_item_ns.unwrap_or(0);
let key = ((n as u64) << 32)
^ ((ns as u64) << 8)
^ effective_min_leaf as u64;
if LAST_FLOOR_SHAPE.swap(key, core::sync::atomic::Ordering::Relaxed) != key {
notice!(
"leaf floor: items {n} per_item_ns {:?} explicit {} \
use_smt {} caller_floor {} effective_floor {effective_min_leaf}",
plan.estimated_per_item_ns,
plan.estimated_per_item_ns_explicit,
plan.use_smt,
min_leaf.max(1)
);
}
}
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, first.len(), || 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, more.len(), || 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 = inline_collapse_threshold_ns();
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, one.len(), || 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, confirm.len(), || 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, tail.len(), || op(tail));
return;
}
let leaves_per_worker = plan.effective_leaves_per_worker();
let max_budget = workers.saturating_mul(leaves_per_worker).max(1);
let probe_min_leaf = pool_dispatch_cost_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, routing_arm) = plan
.with_site_if_none(crate::sched::call_site::caller_site())
.apply_site_class_measured();
let _routing = RecordRoutingArm::start(plan_owned.site, routing_arm);
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, n as u64);
return;
}
if capped_to_caller(plan) {
run_on_caller(plan, n, || {
for c in items.chunks_mut(chunk) {
op(c);
}
});
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, items.len(), || op(items));
return;
}
let cur_splits = if migrated { max_budget } else { splits };
if cur_splits <= 1 {
record_leaf(plan.site, items.len(), || 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, items.len(), || op(items));
return;
}
let cur_splits = if migrated {
workers_floor.max(splits / 2)
} else {
splits
};
if cur_splits <= 1 {
record_leaf(plan.site, items.len(), || 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>,
items: usize,
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 {
if crate::sched::levers::oncore_spread() {
record_leaf_on_core(site, items, body)
} else {
record_leaf(site, items, body)
}
} else {
crate::sched::trace::emit(crate::sched::trace::TraceEvent::LeafStart, 0);
let out = body();
crate::sched::trace::emit(crate::sched::trace::TraceEvent::LeafEnd, 0);
out
}
}
#[inline(always)]
fn advance_bracket_tick(prev: u32) -> (u32, bool) {
let v = prev.wrapping_add(1);
let take = v >= LEAF_SAMPLE_STRIDE;
(if take { 0 } else { v }, take)
}
#[inline]
fn record_leaf_bracket_sampled<F: FnOnce() -> R, R>(
site: Option<crate::sched::call_site::SiteRef>,
items: usize,
body: F,
) -> R {
thread_local! {
static BRACKET_TICK: std::cell::Cell<u32> = const { std::cell::Cell::new(0) };
}
if !crate::sched::levers::oncore_spread() {
return record_leaf(site, items, body);
}
let bracket = BRACKET_TICK.with(|c| {
let (next, take) = advance_bracket_tick(c.get());
c.set(next);
take
});
if bracket {
record_leaf_on_core(site, items, body)
} else {
record_leaf(site, items, 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, items.len(), || 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, items.len(), || 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)
}
fn model_leaf(plan: &JobPlan, n: usize) -> Option<usize> {
if !plan.estimated_per_item_ns_explicit || plan.task_overhead_ns.is_none() {
report_unreachable_model(plan, n);
return None;
}
let chunks = plan.optimal_chunk_count_for(plan.resolved_workers(), n)? as usize;
Some(n.div_ceil(chunks.max(1)))
}
fn report_unreachable_model(plan: &JobPlan, n: usize) {
if plan.task_overhead_ns.is_none() || !model_reporting() {
return;
}
static LAST_SHAPE: core::sync::atomic::AtomicU64 = core::sync::atomic::AtomicU64::new(u64::MAX);
let key = ((n as u64) << 32) ^ u64::from(plan.task_overhead_ns.unwrap_or(0));
if LAST_SHAPE.swap(key, core::sync::atomic::Ordering::Relaxed) != key {
notice!(
"tiny-tasks model not consulted: items {n} task_overhead_ns {:?} \
estimated_per_item_ns {:?} stated {}. The model needs a per-item \
cost the caller stated or the entry probe measured, so the \
overhead sized nothing and the split used the caller's min_leaf.",
plan.task_overhead_ns, plan.estimated_per_item_ns, plan.estimated_per_item_ns_explicit
);
}
}
fn model_reporting() -> bool {
static ON: std::sync::OnceLock<bool> = std::sync::OnceLock::new();
*ON.get_or_init(|| std::env::var_os("FLYNNEL_MODEL_REPORT").is_some())
}
#[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, routing_arm) = plan
.with_site_if_none(crate::sched::call_site::caller_site())
.apply_site_class_measured();
let _routing = RecordRoutingArm::start(plan_owned.site, routing_arm);
let plan = &plan_owned;
if runs_on_caller(plan, n) {
run_on_caller(plan, out.len(), || op(out, a, b));
return;
}
let leaf = min_leaf.max(1);
let workers = plan.effective_workers(global_local_arena().total_workers());
let dispatch_leaf = model_leaf(plan, n).map_or(leaf, |derived| leaf.max(derived));
let max_budget = workers.saturating_mul(plan.effective_leaves_per_worker()).max(1);
bisect_triple(plan, out, a, b, &op, dispatch_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_bracket_sampled(plan.site, out.len(), || op(out, a, b));
return;
}
let cur_splits = if migrated { max_budget } else { splits };
if cur_splits <= 1 {
record_leaf_bracket_sampled(plan.site, out.len(), || 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, routing_arm) = plan
.with_site_if_none(crate::sched::call_site::caller_site())
.apply_site_class_measured();
let _routing = RecordRoutingArm::start(plan_owned.site, routing_arm);
let plan = &plan_owned;
let _flush_on_exit = FlushLeafStatsOnExit;
if runs_on_caller(plan, n) {
run_on_caller(plan, items.len(), || op(0, items));
return;
}
let leaf = min_leaf.max(1);
let workers = plan.effective_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, first_n, || 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, more.len(), || 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;
}
let dispatch_leaf = model_leaf(effective_plan, items_to_dispatch.len())
.map_or(leaf, |derived| leaf.max(derived));
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, dispatch_leaf, seed_depth, 0,
);
return;
}
let max_budget = workers
.saturating_mul(effective_plan.effective_leaves_per_worker())
.max(1);
bisect_indexed(
effective_plan,
items_to_dispatch,
start_offset,
&op,
dispatch_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_bracket_sampled(plan.site, items.len(), || 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_bracket_sampled(plan.site, items.len(), || 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_bracket_sampled(plan.site, items.len(), || op(start, items));
return;
}
let cur_splits = if migrated { max_budget } else { splits };
if cur_splits <= 1 {
record_leaf_bracket_sampled(plan.site, items.len(), || 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, routing_arm) = plan
.with_site_if_none(crate::sched::call_site::caller_site())
.apply_site_class_measured();
let _routing = RecordRoutingArm::start(plan_owned.site, routing_arm);
let plan = &plan_owned;
let _flush_on_exit = FlushLeafStatsOnExit;
if capped_to_caller(plan) {
return run_on_caller(plan, n, || (0..n).map(&f).collect());
}
let leaf = min_leaf.max(1);
let workers = plan.effective_workers(global_local_arena().total_workers());
let max_budget = workers.saturating_mul(plan.effective_leaves_per_worker()).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, first_n, || {
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, extra, || {
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, items.len(), || fill_leaf(items, start, f));
return;
}
let cur_splits = if migrated { max_budget } else { splits };
if cur_splits <= 1 {
record_leaf(plan.site, items.len(), || 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, routing_arm) = plan
.with_site_if_none(crate::sched::call_site::caller_site())
.apply_site_class_measured();
let _routing = RecordRoutingArm::start(plan_owned.site, routing_arm);
let plan = &plan_owned;
if capped_to_caller(plan) {
return run_on_caller(plan, n, || (0..n).map(&f).collect());
}
if plan.estimated_per_item_ns_explicit
&& let Some(total_ns) = plan.estimated_total_ns()
{
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 arm = heartbeat_arm(site.get(), cv2, n);
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()) }
}
fn heartbeat_arm(
site: &crate::sched::call_site::CallSiteState,
cv2: Option<u64>,
n: usize,
) -> crate::sched::call_site::PolicyArm {
use crate::sched::call_site::PolicyArm;
let cv2_high = crate::sched::adaptive_profile::class_thresholds()
.cv2_high_per_mille
.load(std::sync::atomic::Ordering::Relaxed);
match cv2 {
Some(c) if c < cv2_high => PolicyArm::Default,
Some(_) => site.choose_arm(n >= HEARTBEAT_MIN_ITEMS),
None if site.leaves_under_spread_unit() => PolicyArm::Default,
None if n < HEARTBEAT_GATE_ITEMS => PolicyArm::Default,
None => PolicyArm::Alternative,
}
}
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, n as u64);
return;
}
let base = items.as_mut_ptr() as *mut R;
let quantum = heartbeat_ticks();
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) >= quantum {
record_leaf_span_ticks(plan.site, now.wrapping_sub(span_t0), i as u64);
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_ticks(plan.site, read_tsc().wrapping_sub(span_t0), n as u64);
}
#[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, routing_arm) = plan
.with_site_if_none(crate::sched::call_site::caller_site())
.apply_site_class_measured();
let _routing = RecordRoutingArm::start(plan_owned.site, routing_arm);
let plan = &plan_owned;
if capped_to_caller(plan) {
return run_on_caller(plan, n, || (0..n).map(&f).collect());
}
if plan.estimated_per_item_ns_explicit
&& let Some(total_ns) = plan.estimated_total_ns()
{
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();
}
if capped_to_caller(plan) {
return collect_indexed(plan, n, 1, f);
}
let workers = plan.effective_workers(global_local_arena().total_workers());
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 quantum = heartbeat_ticks();
let mut last_tick = read_tsc();
let span_t0 = last_tick;
let mut tokens_since_check: u64 = 0;
let workers = plan.effective_workers(global_local_arena().total_workers());
let max_budget = workers.saturating_mul(plan.effective_leaves_per_worker()).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
&& read_tsc().wrapping_sub(last_tick) >= quantum;
if (token_trip || tick_trip) && i + 1 < n {
let remaining = n - i;
if remaining >= 2 {
record_leaf_span_ticks(plan.site, read_tsc().wrapping_sub(span_t0), i as u64);
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_ticks(plan.site, read_tsc().wrapping_sub(span_t0), n as u64);
}
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, items.len(), || op(items));
return;
}
let cur_splits = if migrated { max_budget } else { splits };
if cur_splits <= 1 {
record_leaf(plan.site, items.len(), || 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;
if capped_to_caller(plan) {
record_reduce_chunks_path(ReduceChunksPath::Caller);
return run_on_caller(plan, items.len(), || fold(init(), items));
}
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 = plan.effective_workers(global_local_arena().total_workers());
let multiplier = plan.effective_leaves_per_worker();
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,
Caller,
}
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 crossover_interpolation_survives_unordered_timings() {
let placed = interpolate_crossover(Some((100, 40)), 200, -40);
assert!(
(100..=200).contains(&placed),
"an ordered pair interpolates between its two costs, got {placed}"
);
assert_eq!(
interpolate_crossover(Some((200, 40)), 100, -40),
100,
"an unordered pair has no crossover to place and must report the \
measurement rather than subtract past zero"
);
assert_eq!(interpolate_crossover(Some((100, 40)), 100, -40), 100);
assert_eq!(interpolate_crossover(Some((100, -40)), 200, -40), 200);
assert_eq!(interpolate_crossover(None, 175, -1), 175);
}
#[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};
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).with_estimated_per_item_ns(1);
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,
"an explicit estimate under the collapse threshold 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_chunk_small_input_without_an_estimate() {
use std::sync::atomic::{AtomicUsize, Ordering};
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 total_processed = AtomicUsize::new(0);
for_each_chunk(&plan, &mut v, |slice| {
total_processed.fetch_add(slice.len(), Ordering::Relaxed);
for x in slice {
*x += 1000;
}
});
assert_eq!(
total_processed.load(Ordering::Relaxed),
n,
"every item is processed exactly once across probe and tail, on whichever thread"
);
for (i, &x) in v.iter().enumerate() {
assert_eq!(x, i as u32 + 1000, "item {i} processed exactly once");
}
}
#[test]
fn one_outlier_moves_the_range_and_leaves_the_iqr_alone() {
let tight: Vec<u64> = vec![100, 101, 102, 103, 104, 105, 106, 107, 108];
assert!(
sample_spread_per_mille(&tight) < 100,
"samples that agree report a small range"
);
let mut hiccup = tight.clone();
hiccup[8] = 900;
assert!(
sample_spread_per_mille(&hiccup) > 7_000,
"one sample nine times the rest sets the whole range"
);
assert!(
sample_iqr_per_mille(&hiccup) < 100,
"the middle half is untouched by it, which is what the median keeps"
);
let scattered: Vec<u64> = vec![20, 50, 90, 140, 200, 260, 330, 410, 500];
assert!(sample_spread_per_mille(&scattered) > 2_000);
assert!(
sample_iqr_per_mille(&scattered) > 1_000,
"a spread that is real reaches the middle half too"
);
}
#[cfg(feature = "persisted-calibration")]
#[test]
fn a_record_that_serves_is_one_the_refusal_will_never_be_offered() {
use crate::sched::calibration_store::CpuCalibration;
let now = 1_000_000u64;
let mut passes = CpuCalibration::new(1_000, 70_000, 40_000, 41, 9, Some(990));
passes.confirmations = 1;
assert!(
stored_record_serves(&passes, None, now),
"with no age bound a trustworthy record is returned, so nothing offers it"
);
let provisional = CpuCalibration::new(1_000, 70_000, 40_000, 41, 9, Some(990));
assert!(
!stored_record_serves(&provisional, None, now),
"a record nothing has agreed with is measured over, and a record in that \
state is the only kind the refusal is ever offered"
);
}
#[cfg(feature = "persisted-calibration")]
#[test]
fn the_default_bound_is_a_day_and_the_comparison_includes_it() {
use crate::sched::calibration_store::CpuCalibration;
assert_eq!(
DEFAULT_CALIBRATION_MAX_AGE_S,
24 * 60 * 60,
"this bound is how long a contended draw can keep routing, so a change \
to it fails here rather than passing quietly"
);
let now = 2_000_000_000u64;
let bound = Some(DEFAULT_CALIBRATION_MAX_AGE_S);
let mut at_the_bound = CpuCalibration::new(1_000, 70_000, 40_000, 41, 9, Some(990));
at_the_bound.measured_unix_s = now - DEFAULT_CALIBRATION_MAX_AGE_S;
at_the_bound.confirmations = 1;
assert!(
stored_record_serves(&at_the_bound, bound, now),
"a record exactly the bound's age serves, so the comparison is inclusive"
);
let mut past_it = CpuCalibration::new(1_000, 70_000, 40_000, 41, 9, Some(990));
past_it.measured_unix_s = now - DEFAULT_CALIBRATION_MAX_AGE_S - 1;
past_it.confirmations = 1;
assert!(
!stored_record_serves(&past_it, bound, now),
"a second past it is drawn again"
);
}
#[cfg(feature = "persisted-calibration")]
#[test]
fn an_age_bound_is_what_lets_a_trustworthy_record_be_drawn_again() {
use crate::sched::calibration_store::CpuCalibration;
let drawn_at = 1_000_000u64;
let now = drawn_at + 3_600;
let mut aged = CpuCalibration::new(1_000, 70_000, 40_000, 41, 9, Some(990));
aged.measured_unix_s = drawn_at;
aged.confirmations = 1;
assert!(
stored_record_serves(&aged, Some(7_200), now),
"inside the bound it stands"
);
assert!(
!stored_record_serves(&aged, Some(1_800), now),
"past the bound it is drawn again, which is the only way a trustworthy \
record is ever displaced short of a layout change"
);
assert!(
stored_record_serves(&aged, Some(0), now),
"zero is read as no bound rather than as re-measure always"
);
let mut future = CpuCalibration::new(1_000, 70_000, 40_000, 41, 9, Some(990));
future.measured_unix_s = now + 10_000;
future.confirmations = 1;
assert!(
stored_record_serves(&future, Some(60), now),
"a record stamped in the future ages to nothing and stands"
);
}
#[test]
fn a_pinned_profile_parses_all_three_fields_or_none() {
let p = parse_pinned_profile("1000,5000,20000").expect("three counts parse");
assert_eq!(p.dispatch_cost_ns, 1000);
assert_eq!(p.collapse_threshold_ns, 5000);
assert_eq!(p.jec_wake_threshold_ns, 20000);
assert_eq!(
parse_pinned_profile(" 1000 , 5000 , 20000 ").expect("spacing is tolerated"),
p,
"a value spaced out for readability pins the same profile"
);
assert!(parse_pinned_profile("1000,5000").is_none(), "a missing field is refused");
assert!(
parse_pinned_profile("1000,5000,20000,7").is_none(),
"a fourth field is refused rather than ignored"
);
assert!(
parse_pinned_profile("0,5000,20000").is_none(),
"zero marks an uncalibrated profile and cannot be pinned"
);
assert!(
parse_pinned_profile("1000,0,20000").is_none(),
"zero is refused in the collapse field too"
);
assert!(parse_pinned_profile("1000,fast,20000").is_none(), "a non-count is refused");
assert!(parse_pinned_profile("").is_none(), "an empty value is refused");
}
#[test]
fn the_sampled_path_reaches_the_site_with_an_on_core_reading() {
static SITE: crate::sched::call_site::CallSiteState =
crate::sched::call_site::CallSiteState::new();
let site = crate::sched::call_site::SiteRef::new(&SITE);
assert_eq!(SITE.oncore_items(), 0, "a fresh site has taken no reading");
let mut sink = 0u64;
for i in 0..(LocalLeafBuffer::FLUSH_THRESHOLD as usize * 4) {
sink = sink.wrapping_add(record_leaf_on_core(Some(site), 64, || {
let mut acc = 0u64;
for k in 0..4_096u64 {
acc = acc.wrapping_add(std::hint::black_box(k ^ i as u64));
}
acc
}));
}
std::hint::black_box(sink);
let (thread, _) = crate::sched::occupancy::clock_pair();
if thread.ticks().is_some() {
assert!(
SITE.oncore_items() > 0,
"this platform has a thread clock, so the sampled path must have \
carried a reading to the site"
);
assert!(
SITE.per_item_oncore_cv2_per_mille().is_some(),
"items were recorded, so a spread is computable from them"
);
} else {
assert_eq!(
SITE.oncore_items(),
0,
"with no thread clock the site must hold no on-core items rather \
than a zero that reads as a measurement"
);
assert_eq!(SITE.per_item_oncore_cv2_per_mille(), None);
}
}
#[test]
fn one_call_in_the_stride_takes_the_bracket_and_the_rest_do_not() {
let rounds = LEAF_SAMPLE_STRIDE as usize * 10;
let mut tick = 0u32;
let mut taken_at = Vec::new();
for call in 0..rounds {
let (next, take) = advance_bracket_tick(tick);
tick = next;
if take {
taken_at.push(call);
}
}
assert_eq!(
taken_at.len(),
10,
"one call in {LEAF_SAMPLE_STRIDE} over {rounds} calls is 10 brackets, \
got {} at {taken_at:?}",
taken_at.len()
);
for pair in taken_at.windows(2) {
assert_eq!(
pair[1] - pair[0],
LEAF_SAMPLE_STRIDE as usize,
"brackets at {taken_at:?} are not one stride apart"
);
}
}
#[test]
fn the_indexed_path_times_every_leaf_and_leaves_the_bracket_to_the_switch() {
static SITE: crate::sched::call_site::CallSiteState =
crate::sched::call_site::CallSiteState::new();
let site = crate::sched::call_site::SiteRef::new(&SITE);
let n = 4 * MIN_LEAF_ITEMS;
let mut v: Vec<u64> = (0..n as u64).collect();
let bound = LocalLeafBuffer::FLUSH_THRESHOLD as usize * 64;
let mut dispatches = 0usize;
while dispatches < bound && SITE.oncore_items() == 0 {
let plan = JobPlan::new(0, n as u32)
.with_site(site)
.with_estimated_per_item_ns(5_000);
for_each_chunk_indexed_min_leaf(&plan, &mut v, MIN_LEAF_ITEMS, |_start, chunk| {
for slot in chunk.iter_mut() {
let mut acc = *slot;
for _ in 0..64 {
acc = acc.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1);
}
*slot = std::hint::black_box(acc);
}
});
dispatches += 1;
}
assert!(
SITE.leaf_count() > 0,
"the indexed entry records every leaf, so the site must have counts"
);
assert!(
SITE.oncore_items() > 0,
"the indexed entry reaches the bracket, which `oncore_spread` leaves on by \
default; no bracketed leaf reached the site in {dispatches} dispatches, so \
the recorder never takes it"
);
assert!(SITE.per_item_oncore_cv2_per_mille().is_some());
}
#[test]
fn the_triple_path_times_every_leaf_and_leaves_the_bracket_to_the_switch() {
static SITE: crate::sched::call_site::CallSiteState =
crate::sched::call_site::CallSiteState::new();
let site = crate::sched::call_site::SiteRef::new(&SITE);
let n = 4 * MIN_LEAF_ITEMS;
let a: Vec<u64> = (0..n as u64).collect();
let b: Vec<u64> = (0..n as u64).map(|x| x ^ 0x5DEE_CE66).collect();
let mut out: Vec<u64> = vec![0; n];
let bound = LocalLeafBuffer::FLUSH_THRESHOLD as usize * 64;
let mut dispatches = 0usize;
while dispatches < bound && SITE.oncore_items() == 0 {
let plan = JobPlan::new(0, n as u32)
.with_site(site)
.with_estimated_per_item_ns(5_000);
for_each_chunk_triple_min_leaf(
&plan,
&mut out,
&a,
&b,
MIN_LEAF_ITEMS,
|out, a, b| {
for i in 0..out.len() {
let mut acc = a[i] ^ b[i];
for _ in 0..64 {
acc = acc.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1);
}
out[i] = std::hint::black_box(acc);
}
},
);
dispatches += 1;
}
assert!(
SITE.leaf_count() > 0,
"the triple entry records every leaf, so the site must have counts"
);
assert!(
SITE.oncore_items() > 0,
"the triple entry reaches the bracket, which `oncore_spread` leaves on by \
default; no bracketed leaf reached the site in {dispatches} dispatches, so \
the recorder never takes it"
);
assert!(SITE.per_item_oncore_cv2_per_mille().is_some());
}
#[test]
fn host_dispatch_profile_is_measured_and_cached() {
let t0 = std::time::Instant::now();
let p = calibrate_host_dispatch();
let cost = t0.elapsed();
assert!(
p.dispatch_cost_ns > 100,
"a dispatch cost of {} ns is a failed measurement, not a fast pool",
p.dispatch_cost_ns
);
assert!(p.collapse_threshold_ns >= p.dispatch_cost_ns, "the collapse threshold is floored at the dispatch cost");
assert!(p.jec_wake_threshold_ns > 0, "a measured wake threshold is positive");
assert_eq!(host_dispatch_profile(), p, "the query hands out the installed profile");
assert_eq!(inline_collapse_threshold_ns(), p.collapse_threshold_ns);
eprintln!(
"host dispatch profile: dispatch cost {} ns, collapse threshold {} ns, wake threshold {} ns (measured in {cost:?})",
p.dispatch_cost_ns, p.collapse_threshold_ns, p.jec_wake_threshold_ns
);
}
#[test]
fn triple_min_leaf_small_explicit_estimate_runs_on_the_caller() {
use std::sync::atomic::{AtomicUsize, Ordering};
let n = 200usize;
let a: Vec<u32> = (0..n as u32).collect();
let b: Vec<u32> = vec![1; n];
let mut out = vec![0u32; n];
let plan = JobPlan::new(6, n as u32).with_estimated_per_item_ns(1);
let caller = std::thread::current().id();
let off_thread = AtomicUsize::new(0);
let calls = AtomicUsize::new(0);
for_each_chunk_triple_min_leaf(&plan, &mut out, &a, &b, 64, |o, x, y| {
if std::thread::current().id() != caller {
off_thread.fetch_add(1, Ordering::Relaxed);
}
calls.fetch_add(1, Ordering::Relaxed);
for ((o, x), y) in o.iter_mut().zip(x).zip(y) {
*o = x + y;
}
});
assert_eq!(off_thread.load(Ordering::Relaxed), 0, "must not dispatch to the pool");
assert_eq!(calls.load(Ordering::Relaxed), 1, "one body call over the whole slice");
assert!(out.iter().enumerate().all(|(i, &v)| v == i as u32 + 1));
}
#[test]
fn indexed_min_leaf_small_explicit_estimate_runs_on_the_caller() {
use std::sync::atomic::{AtomicUsize, Ordering};
let n = 200usize;
let mut v: Vec<u32> = vec![0; n];
let plan = JobPlan::new(6, n as u32).with_estimated_per_item_ns(1);
let caller = std::thread::current().id();
let off_thread = AtomicUsize::new(0);
let calls = AtomicUsize::new(0);
for_each_chunk_indexed_min_leaf(&plan, &mut v, 1, |start, chunk| {
if std::thread::current().id() != caller {
off_thread.fetch_add(1, Ordering::Relaxed);
}
calls.fetch_add(1, Ordering::Relaxed);
for (i, x) in chunk.iter_mut().enumerate() {
*x = (start + i) as u32;
}
});
assert_eq!(off_thread.load(Ordering::Relaxed), 0, "must not dispatch to the pool");
assert_eq!(calls.load(Ordering::Relaxed), 1, "one body call over the whole slice");
assert!(v.iter().enumerate().all(|(i, &x)| x == i as u32));
}
#[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);
use std::sync::atomic::AtomicUsize;
let widest = Arc::new(AtomicUsize::new(0));
let widest_clone = Arc::clone(&widest);
for_each_fixed_chunk(&plan, &mut v, chunk, |slice| {
widest_clone.fetch_max(slice.len(), Ordering::Relaxed);
for x in slice {
*x = 7;
}
});
let widest = widest.load(Ordering::Relaxed);
assert!(
widest <= chunk,
"chunk size {widest} exceeded the {chunk}-item ceiling"
);
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 a_measured_fine_grain_site_keeps_its_floor_while_its_class_holds_smt_on() {
use crate::sched::call_site::{CallSiteState, SiteRef};
static FINE: CallSiteState = CallSiteState::new();
const PER_ITEM_NS: u64 = 5;
const ITEMS: u64 = 4_096;
let leaf_ns = PER_ITEM_NS * ITEMS;
let scaled = leaf_ns >> 8;
let sq = scaled.saturating_mul(scaled);
let per_item_sq = (leaf_ns as u128)
.saturating_mul(leaf_ns as u128)
.checked_div((ITEMS as u128) << 16)
.unwrap_or(0) as u64;
for _ in 0..4 {
FINE.record_batch_site_only(leaf_ns * 8, sq * 8, 8, ITEMS * 8, per_item_sq * 8);
}
assert_eq!(
FINE.per_item_ns(),
Some(PER_ITEM_NS),
"the site measured its own per-item cost"
);
let caller_floor = MIN_LEAF_ITEMS;
let plan = JobPlan::bare(6, 65_536)
.with_smt()
.with_site(SiteRef::new(&FINE));
assert!(plan.use_smt, "the arrangement under test has SMT on");
assert!(
!plan.estimated_per_item_ns_explicit,
"no caller hint, so the floor has only the site to read"
);
let dispatch_ns = pool_dispatch_cost_ns();
let measured_floor = adaptive_min_leaf(&plan, caller_floor);
assert!(
measured_floor > 1,
"a site measuring {PER_ITEM_NS} ns an item must not collapse to one item per \
leaf, which would hand each of them a dispatch; got {measured_floor}"
);
assert!(
measured_floor <= caller_floor,
"the floor never rises above the caller's {caller_floor}; got {measured_floor}"
);
assert!(
measured_floor == caller_floor
|| (measured_floor as u64 + 1) * PER_ITEM_NS > dispatch_ns,
"a leaf carries about one dispatch of work unless the caller's floor caps it \
first, so one item fewer would not cover it: {measured_floor} items at \
{PER_ITEM_NS} ns against a dispatch measured at {dispatch_ns} ns"
);
static UNMEASURED: CallSiteState = CallSiteState::new();
let bare = JobPlan::bare(6, 8).with_smt().with_site(SiteRef::new(&UNMEASURED));
assert_eq!(
adaptive_min_leaf(&bare, caller_floor),
1,
"with nothing measured, use_smt still stands in for a per-item figure"
);
}
#[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::snapshot_leaf_stats;
static SITE: crate::sched::call_site::CallSiteState =
crate::sched::call_site::CallSiteState::new();
let site = crate::sched::call_site::SiteRef::new(&SITE);
let n = 8 * MIN_LEAF_ITEMS;
let mut v: Vec<u32> = (0..n as u32).collect();
let plan = JobPlan::new(6, n as u32).with_site(site).with_workers(1);
let dispatches = LocalLeafBuffer::FLUSH_THRESHOLD as usize * 4;
let before = snapshot_leaf_stats();
let dispatch_start = std::time::Instant::now();
for _ in 0..dispatches {
for_each_chunk_indexed_min_leaf(&plan, &mut v, MIN_LEAF_ITEMS, |_start, slice| {
for x in slice.iter_mut() {
let mut acc = *x as u64;
for _ in 0..64 {
acc = acc.wrapping_mul(0x9E37_79B9_7F4A_7C15).wrapping_add(1);
}
*x = std::hint::black_box(acc) as u32;
}
});
}
let dispatch_ns = dispatch_start.elapsed().as_nanos() as u64;
let after = snapshot_leaf_stats();
let count = SITE.leaf_count();
assert!(
count >= LocalLeafBuffer::FLUSH_THRESHOLD,
"{dispatches} single-leaf dispatches should have flushed at least one batch to \
the site, which holds {count} leaves"
);
let sum_ns = SITE.leaf_sum_ns();
assert!(
sum_ns > 0,
"expected a positive total leaf time in nanoseconds at the site"
);
let ceiling = dispatch_ns.saturating_mul(2).max(1);
assert!(
sum_ns <= ceiling,
"{} ns of leaf time over {} leaves ({} ns each) on one thread inside {} ns of wall \
time, ceiling {}: the leaf clock and the wall clock are not sharing a unit",
sum_ns,
count,
sum_ns / count.max(1),
dispatch_ns,
ceiling
);
let global_count = after.count.wrapping_sub(before.count);
assert!(
global_count + LocalLeafBuffer::FLUSH_THRESHOLD > count,
"the global counters rose by {global_count} leaves while the site recorded {count}"
);
assert!(
after.sum_ns.wrapping_sub(before.sum_ns) > 0,
"the global leaf time did not rise while the site recorded {sum_ns} ns"
);
}
fn span_test_item(i: usize) -> u64 {
let mut acc = i as u64;
for _ in 0..256 {
acc = acc.wrapping_mul(0x9E37_79B9_7F4A_7C15).wrapping_add(1);
}
std::hint::black_box(acc)
}
fn assert_span_in_nanoseconds(
site: &crate::sched::call_site::CallSiteState,
rate_16: u64,
wall_ns: u64,
inner_ns: u64,
) {
assert_eq!(
site.leaf_count(),
1,
"a fill that cannot promote records one span"
);
let span_ns = site.leaf_sum_ns();
assert!(
span_ns <= wall_ns.saturating_mul(2),
"a {span_ns} ns span inside {wall_ns} ns of wall time, with the counter at \
{rate_16} sixteenths of a tick a nanosecond: the span is in counter ticks"
);
assert!(
span_ns >= inner_ns / 2,
"a {span_ns} ns span around {inner_ns} ns of items, with the counter at \
{rate_16} sixteenths of a tick a nanosecond: the span was converted twice"
);
}
#[test]
fn a_heartbeat_span_reaches_its_site_in_nanoseconds() {
use std::sync::atomic::{AtomicU64, Ordering};
static SITE: crate::sched::call_site::CallSiteState =
crate::sched::call_site::CallSiteState::new();
let site = crate::sched::call_site::SiteRef::new(&SITE);
let plan = JobPlan::new(6, 1).with_site(site);
let rate_16 = tsc_per_ns_16();
let n = 2 * MIN_LEAF_ITEMS;
let mut buf: Vec<std::mem::MaybeUninit<u64>> = Vec::with_capacity(n);
buf.resize_with(n, std::mem::MaybeUninit::uninit);
let base = std::time::Instant::now();
let first_ns = AtomicU64::new(0);
let last_ns = AtomicU64::new(0);
let item = |i: usize| {
if i == 0 {
first_ns.store(base.elapsed().as_nanos() as u64, Ordering::Relaxed);
}
let out = span_test_item(i);
if i == n - 1 {
last_ns.store(base.elapsed().as_nanos() as u64, Ordering::Relaxed);
}
out
};
let t0 = std::time::Instant::now();
heartbeat_fill(&plan, &mut buf[..], 0, &item);
let wall_ns = t0.elapsed().as_nanos() as u64;
let inner_ns = last_ns.load(Ordering::Relaxed) - first_ns.load(Ordering::Relaxed);
assert_span_in_nanoseconds(&SITE, rate_16, wall_ns, inner_ns);
}
#[test]
fn a_heartbeat_site_of_unreadably_short_leaves_takes_slaw_at_any_size() {
use crate::sched::call_site::{CallSiteState, PolicyArm};
static SHORT: CallSiteState = CallSiteState::new();
SHORT.record_batch_site_only(16 * 200, 0, 16, 0, 0);
assert_eq!(SHORT.cv2_per_mille(), None);
let big = 4 * HEARTBEAT_GATE_ITEMS;
assert_eq!(
heartbeat_arm(&SHORT, SHORT.cv2_per_mille(), big),
PolicyArm::Default
);
static FRESH: CallSiteState = CallSiteState::new();
assert_eq!(heartbeat_arm(&FRESH, None, big), PolicyArm::Alternative);
assert_eq!(
heartbeat_arm(&FRESH, None, HEARTBEAT_GATE_ITEMS - 1),
PolicyArm::Default
);
}
#[test]
fn a_token_bucket_span_reaches_its_site_in_nanoseconds() {
use std::sync::atomic::{AtomicU64, Ordering};
static SITE: crate::sched::call_site::CallSiteState =
crate::sched::call_site::CallSiteState::new();
let site = crate::sched::call_site::SiteRef::new(&SITE);
let plan = JobPlan::new(6, 1).with_site(site);
let rate_16 = tsc_per_ns_16();
let n = POLL_MASK;
let mut buf: Vec<std::mem::MaybeUninit<u64>> = Vec::with_capacity(n);
buf.resize_with(n, std::mem::MaybeUninit::uninit);
let base = std::time::Instant::now();
let first_ns = AtomicU64::new(0);
let last_ns = AtomicU64::new(0);
let item = |i: usize| {
if i == 0 {
first_ns.store(base.elapsed().as_nanos() as u64, Ordering::Relaxed);
}
let out = span_test_item(i);
if i == n - 1 {
last_ns.store(base.elapsed().as_nanos() as u64, Ordering::Relaxed);
}
out
};
let t0 = std::time::Instant::now();
token_bucket_fill(&plan, &mut buf[..], 0, &item, &|_: usize| 0u32);
let wall_ns = t0.elapsed().as_nanos() as u64;
let inner_ns = last_ns.load(Ordering::Relaxed) - first_ns.load(Ordering::Relaxed);
assert_span_in_nanoseconds(&SITE, rate_16, wall_ns, inner_ns);
}
fn assert_spans_carry_items(
site: &crate::sched::call_site::CallSiteState,
spans: u64,
items: u64,
) {
assert_eq!(
site.leaf_count(),
spans,
"each fill that cannot promote records one span"
);
let per_item = site
.per_item_ns()
.expect("spans that carry their items give the site a per-item mean");
let covered = spans * items;
let sum_ns = site.leaf_sum_ns();
assert!(
per_item.abs_diff(sum_ns / covered) <= 1,
"{per_item} ns an item from {sum_ns} ns over {covered} items: the spans' time is \
not divided by the items they covered"
);
}
#[test]
fn a_span_carries_the_items_it_covered() {
use crate::sched::call_site::{CallSiteState, SiteRef};
const SPANS: u64 = 4;
static HEARTBEAT: CallSiteState = CallSiteState::new();
let plan = JobPlan::new(6, 1).with_site(SiteRef::new(&HEARTBEAT));
let n = 2 * MIN_LEAF_ITEMS;
for _ in 0..SPANS {
let mut buf: Vec<std::mem::MaybeUninit<u64>> = Vec::with_capacity(n);
buf.resize_with(n, std::mem::MaybeUninit::uninit);
heartbeat_fill(&plan, &mut buf[..], 0, &span_test_item);
}
assert_spans_carry_items(&HEARTBEAT, SPANS, n as u64);
static SERIAL: CallSiteState = CallSiteState::new();
let plan = JobPlan::new(6, 1).with_site(SiteRef::new(&SERIAL));
let n = MIN_LEAF_ITEMS;
for _ in 0..SPANS {
let mut buf: Vec<std::mem::MaybeUninit<u64>> = Vec::with_capacity(n);
buf.resize_with(n, std::mem::MaybeUninit::uninit);
heartbeat_fill(&plan, &mut buf[..], 0, &span_test_item);
}
assert_spans_carry_items(&SERIAL, SPANS, n as u64);
static BUCKET: CallSiteState = CallSiteState::new();
let plan = JobPlan::new(6, 1).with_site(SiteRef::new(&BUCKET));
let n = POLL_MASK;
for _ in 0..SPANS {
let mut buf: Vec<std::mem::MaybeUninit<u64>> = Vec::with_capacity(n);
buf.resize_with(n, std::mem::MaybeUninit::uninit);
token_bucket_fill(&plan, &mut buf[..], 0, &span_test_item, &|_: usize| 0u32);
}
assert_spans_carry_items(&BUCKET, SPANS, n as u64);
static FIXED: CallSiteState = CallSiteState::new();
let plan = JobPlan::new(6, 1).with_site(SiteRef::new(&FIXED));
let n = 64;
for _ in 0..SPANS {
let mut v: Vec<u64> = (0..n as u64).collect();
for_each_fixed_chunk(&plan, &mut v, n, |slice| {
for x in slice.iter_mut() {
*x = span_test_item(*x as usize);
}
});
}
assert_spans_carry_items(&FIXED, SPANS, n as u64);
}
#[test]
fn a_token_bucket_fill_with_no_tokens_promotes_once_a_quantum_has_passed() {
use std::sync::atomic::{AtomicUsize, Ordering};
let item = |i: usize| {
let mut acc = i as u64;
for _ in 0..32 {
acc = acc.wrapping_mul(0x9E37_79B9_7F4A_7C15).wrapping_add(1);
}
std::hint::black_box(acc)
};
let n = 1usize << 16;
let asked = AtomicUsize::new(0);
let tokens = |_: usize| {
asked.fetch_add(1, Ordering::Relaxed);
0u32
};
let plan = JobPlan::new(6, 1);
let mut buf: Vec<std::mem::MaybeUninit<u64>> = Vec::with_capacity(n);
buf.resize_with(n, std::mem::MaybeUninit::uninit);
token_bucket_fill(&plan, &mut buf[..], 0, &item, &tokens);
let serial = asked.load(Ordering::Relaxed);
assert!(
serial < n,
"a fill of {n} items with no tokens stayed serial throughout: the time trip never \
fired, so it is not counting from the span's start"
);
for (i, slot) in buf.iter().enumerate() {
assert_eq!(unsafe { slot.assume_init_read() }, item(i));
}
}
#[test]
fn the_heartbeat_quantum_is_its_stated_nanoseconds_once_the_rate_is_known() {
let rate_16 = tsc_per_ns_16();
let ticks = heartbeat_ticks();
let (nanos, _) = LocalLeafBuffer::as_nanos(ticks, 0);
assert!(
nanos.abs_diff(HEARTBEAT_NS) <= HEARTBEAT_NS / 100,
"the quantum is {ticks} ticks, {nanos} ns through the leaf path's conversion at \
{rate_16} sixteenths of a tick a nanosecond, where it is stated as {HEARTBEAT_NS} ns"
);
}
#[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();
use std::sync::atomic::AtomicUsize;
let tiles = n.div_ceil(width);
let lens: Vec<AtomicUsize> = (0..tiles).map(|_| AtomicUsize::new(0)).collect();
let plan = JobPlan::new(6, n as u32);
for_each_chunk_ref(&plan, &v, width, |start, chunk| {
assert_eq!(start % width, 0, "chunk at {start} does not begin a tile");
let prior = lens[start / width].swap(chunk.len() + 1, Ordering::Relaxed);
assert_eq!(prior, 0, "tile {} was covered twice", start / width);
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));
}
for (k, slot) in lens.iter().enumerate() {
let stored = slot.load(Ordering::Relaxed);
assert_ne!(stored, 0, "tile {k} was never covered");
let expected = if k + 1 == tiles { n - k * width } else { width };
assert_eq!(stored - 1, 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"));
}
#[test]
fn a_worker_cap_of_one_keeps_every_entry_on_the_calling_thread() {
use std::sync::atomic::AtomicUsize;
let caller = std::thread::current().id();
let bodies = AtomicUsize::new(0);
let elsewhere = AtomicUsize::new(0);
let note = || {
bodies.fetch_add(1, Ordering::Relaxed);
if std::thread::current().id() != caller {
elsewhere.fetch_add(1, Ordering::Relaxed);
}
};
let n = 4096usize;
let a: Vec<u32> = vec![1; n];
let b: Vec<u32> = vec![2; n];
let estimated = JobPlan::new(6, n as u32).with_workers(1).with_estimated_per_item_ns(5_000);
let bare = JobPlan::new(6, n as u32).with_workers(1);
let mut ran = 0usize;
let mut idle: Vec<String> = Vec::new();
let mut left: Vec<String> = Vec::new();
for (label, plan) in [("estimated", &estimated), ("bare", &bare)] {
let entries: [(&str, &dyn Fn()); 16] = [
("for_each_chunk", &|| {
let mut v = a.clone();
for_each_chunk(plan, &mut v, |c| {
note();
c.iter_mut().for_each(|x| *x += 1);
});
}),
("for_each_chunk_min_leaf", &|| {
let mut v = a.clone();
for_each_chunk_min_leaf(plan, &mut v, 1, |c| {
note();
c.iter_mut().for_each(|x| *x += 1);
});
}),
("for_each_fixed_chunk", &|| {
let mut v = a.clone();
for_each_fixed_chunk(plan, &mut v, 64, |c| {
note();
c.iter_mut().for_each(|x| *x += 1);
});
}),
("for_each_chunk_triple", &|| {
let mut out = vec![0u32; n];
for_each_chunk_triple(plan, &mut out, &a, &b, |o, x, y| {
note();
for ((o, x), y) in o.iter_mut().zip(x).zip(y) {
*o = x + y;
}
});
assert_eq!(out[n - 1], 3, "the triple entry still computed its output");
}),
("for_each_chunk_triple_min_leaf", &|| {
let mut out = vec![0u32; n];
for_each_chunk_triple_min_leaf(plan, &mut out, &a, &b, 1, |o, x, y| {
note();
for ((o, x), y) in o.iter_mut().zip(x).zip(y) {
*o = x + y;
}
});
assert_eq!(out[0], 3, "the triple entry still computed its output");
}),
("for_each_chunk_indexed", &|| {
let mut idx = vec![0u32; n];
for_each_chunk_indexed(plan, &mut idx, |start, chunk| {
note();
for (k, slot) in chunk.iter_mut().enumerate() {
*slot = (start + k) as u32;
}
});
assert_eq!(idx[n - 1], (n - 1) as u32, "the indexed entry filled its output");
}),
("for_each_chunk_indexed_min_leaf", &|| {
let mut idx = vec![0u32; n];
for_each_chunk_indexed_min_leaf(plan, &mut idx, 1, |start, chunk| {
note();
for (k, slot) in chunk.iter_mut().enumerate() {
*slot = (start + k) as u32;
}
});
assert_eq!(idx[n - 1], (n - 1) as u32, "the indexed entry filled its output");
}),
("for_each_indexed", &|| {
for_each_indexed(plan, n, 1, |_i| note());
}),
("for_each_chunk_ref", &|| {
for_each_chunk_ref(plan, &a, 64, |_start, _chunk| note());
}),
("collect_indexed", &|| {
let got: Vec<usize> = collect_indexed(plan, n, 1, |i| {
note();
i
});
assert_eq!(got[n - 1], n - 1, "collect_indexed kept its order");
}),
("collect_indexed_heartbeat", &|| {
let got: Vec<usize> = collect_indexed_heartbeat(plan, n, |i| {
note();
i
});
assert_eq!(got[n - 1], n - 1, "the heartbeat collect kept its order");
}),
("collect_indexed_token_bucket", &|| {
let got: Vec<usize> = collect_indexed_token_bucket(
plan,
n,
|_i| 1_000,
|i| {
note();
i
},
);
assert_eq!(got[n - 1], n - 1, "the token-bucket collect kept its order");
}),
("collect_indexed_tiny_tasks", &|| {
let got: Vec<usize> = collect_indexed_tiny_tasks(plan, n, |i| {
note();
i
});
assert_eq!(got[n - 1], n - 1, "the tiny-tasks collect kept its order");
}),
("reduce_chunks", &|| {
let sum = reduce_chunks(
plan,
&a,
|| 0u64,
|acc, s| {
note();
acc + s.iter().map(|&x| u64::from(x)).sum::<u64>()
},
|x, y| x + y,
);
assert_eq!(sum, n as u64, "reduce_chunks folded every element");
assert_eq!(last_reduce_chunks_path(), Some(ReduceChunksPath::Caller));
}),
("par_map_in_place", &|| {
let mut v = a.clone();
par_map_in_place(plan, &mut v, |x| {
note();
*x += 1;
});
}),
("par_zip_apply", &|| {
let mut v = a.clone();
par_zip_apply(plan, &mut v, &b, |x, y| {
note();
*x += y;
});
assert_eq!(v[n - 1], 3, "par_zip_apply paired every index");
}),
];
for (name, run) in entries {
let bodies_before = bodies.load(Ordering::Relaxed);
let elsewhere_before = elsewhere.load(Ordering::Relaxed);
run();
ran += 1;
if bodies.load(Ordering::Relaxed) == bodies_before {
idle.push(format!("{name} ({label})"));
}
if elsewhere.load(Ordering::Relaxed) != elsewhere_before {
left.push(format!("{name} ({label})"));
}
}
}
assert_eq!(ran, 32, "every entry ran under both plans");
assert!(idle.is_empty(), "these entries never ran their body: {idle:?}");
assert!(
left.is_empty(),
"a worker cap of one must not leave the caller, and these did: {left:?}"
);
}
#[test]
fn a_capped_body_past_the_collapse_threshold_leaves_the_latch_alone() {
static SITE: crate::sched::call_site::CallSiteState =
crate::sched::call_site::CallSiteState::new();
let site = crate::sched::call_site::SiteRef::new(&SITE);
let limit = inline_collapse_threshold_ns();
let n = 64usize;
let mut v = vec![0u64; n];
let plan = JobPlan::new(6, n as u32)
.with_site(site)
.with_workers(1)
.with_estimated_per_item_ns(1);
for_each_chunk_indexed_min_leaf(&plan, &mut v, 1, |start, chunk| {
let t0 = std::time::Instant::now();
while (t0.elapsed().as_nanos() as u64) <= limit {
std::hint::spin_loop();
}
for (k, slot) in chunk.iter_mut().enumerate() {
*slot = (start + k) as u64;
}
});
assert_eq!(v[n - 1], (n - 1) as u64, "the capped body ran");
assert!(
!SITE.collapse_overran(),
"a body the cap put on the caller ran past {limit} ns and latched the site"
);
}
#[test]
fn an_explicit_oversubscription_factor_shifts_the_seed_depth() {
const ITEMS: usize = 65_536;
const ITEMS_LOG2: usize = 16;
const WORKERS: usize = 24;
let bare = JobPlan::new(6, ITEMS as u32).with_estimated_per_item_ns(500);
assert!(!bare.oversubscription_log2_explicit);
let plain = adaptive_seed_depth(&bare, ITEMS, WORKERS);
for log2 in 0..=3u8 {
let pinned = JobPlan::new(6, ITEMS as u32)
.with_estimated_per_item_ns(500)
.with_oversubscription_log2(log2);
assert!(pinned.oversubscription_log2_explicit);
assert_eq!(
adaptive_seed_depth(&pinned, ITEMS, WORKERS),
(plain + log2 as usize).min(ITEMS_LOG2),
"a factor of {log2} shifts the depth by {log2}",
);
}
let profiled = JobPlan::set_profile(
6,
ITEMS as u32,
crate::dispatch_profile::DispatchProfile::LatencyBound,
)
.with_estimated_per_item_ns(500);
assert!(profiled.oversubscription_log2.is_some());
assert_eq!(adaptive_seed_depth(&profiled, ITEMS, WORKERS), plain);
}
#[test]
fn an_explicit_oversubscription_factor_sets_the_split_budget() {
let plan = JobPlan::new(6, 1024);
assert!(!plan.oversubscription_log2_explicit, "a bare plan defers to the observer");
let observer = crate::sched::split_observer::split_multiplier() as usize;
assert_eq!(plan.effective_leaves_per_worker(), observer.max(1));
for log2 in 0..=3u8 {
let pinned = JobPlan::new(6, 1024).with_oversubscription_log2(log2);
assert!(pinned.oversubscription_log2_explicit);
assert_eq!(pinned.effective_leaves_per_worker(), 1usize << log2,
"an explicit factor of {log2} means {} leaves per worker", 1usize << log2);
}
let profiled = JobPlan::set_profile(
6, 1024, crate::dispatch_profile::DispatchProfile::LatencyBound);
assert!(profiled.oversubscription_log2.is_some(), "the profile carries a default");
assert!(!profiled.oversubscription_log2_explicit, "but the caller set nothing");
assert_eq!(profiled.effective_leaves_per_worker(), observer.max(1));
use crate::sched::workload_shape::WorkloadShape;
for shape in [
WorkloadShape::Streaming,
WorkloadShape::ProducerFast { burst: 64 },
WorkloadShape::WorkSteal { n_consumers: 8, batch_size: 1024 },
WorkloadShape::Cooperative { n_cores: 8 },
WorkloadShape::VariantRace { n_variants: 3 },
] {
let shaped = JobPlan::new(6, 1024).with_workload_shape(shape);
match shape.hints().oversubscription_log2 {
Some(log2) => {
assert!(shaped.oversubscription_log2_explicit,
"{shape:?} carries a factor, so it is the caller's");
assert_eq!(shaped.effective_leaves_per_worker(), 1usize << log2,
"{shape:?} sets the split budget");
}
None => assert!(!shaped.oversubscription_log2_explicit,
"{shape:?} carries no factor, so the observer still decides"),
}
}
}
#[test]
fn a_collapsed_body_that_overruns_stops_its_site_collapsing() {
use crate::sched::call_site::{CallSiteState, SiteRef};
static SITE: CallSiteState = CallSiteState::new();
let site = SiteRef::new(&SITE);
let threshold = host_dispatch_profile().collapse_threshold_ns;
assert!(threshold > 0, "measured by the query above");
assert!(!SITE.collapse_overran(), "a fresh site has not overrun");
let n = 64usize;
let mut items = vec![0u8; n];
let plan = JobPlan::new(0, n as u32)
.with_site(site)
.with_estimated_per_item_ns(1);
assert!(collapses_inline(&plan, n), "the estimate admits it inline");
let over = std::time::Duration::from_nanos(threshold.saturating_mul(4));
for_each_chunk(&plan, &mut items, |chunk| {
std::thread::sleep(over);
for x in chunk.iter_mut() {
*x = x.wrapping_add(1);
}
});
assert!(SITE.collapse_overran(), "the overrun latched the site");
assert!(!collapses_inline(&plan, n),
"the same plan no longer collapses at this site");
}
#[test]
fn a_plan_without_both_hints_has_no_model_width_and_keeps_the_caller_floor() {
let n = 4096usize;
assert_eq!(model_leaf(&JobPlan::new(6, n as u32), n), None);
assert_eq!(
model_leaf(&JobPlan::new(6, n as u32).with_estimated_per_item_ns(50), n),
None,
"a per-item cost alone leaves the model without a fixed cost"
);
assert_eq!(
model_leaf(&JobPlan::new(6, n as u32).with_task_overhead_ns(500), n),
None,
"an overhead alone leaves the model without work to spread"
);
}
#[test]
fn an_overhead_alone_is_inert_and_a_per_item_cost_alone_is_not() {
let n = 4096usize;
let overhead_only = JobPlan::new(6, n as u32).with_task_overhead_ns(500);
assert_eq!(model_leaf(&overhead_only, n), None);
assert!(
!overhead_only.estimated_per_item_ns_explicit,
"an overhead alone leaves the cost unstated, which is the reported case"
);
let cost_only = JobPlan::new(6, n as u32).with_estimated_per_item_ns(50);
assert_eq!(model_leaf(&cost_only, n), None);
assert!(
cost_only.task_overhead_ns.is_none(),
"a cost alone leaves no overhead, which is not reported: the cost \
still steers the tier pick, the collapse decision and the leaf floor"
);
assert!(cost_only.estimated_total_ns().is_some());
}
#[test]
fn a_classifier_default_cost_is_not_a_stated_one_and_yields_no_model_width() {
let n = 4096usize;
let plan = JobPlan::set_profile(
6,
n as u32,
crate::dispatch_profile::DispatchProfile::MemoryBound,
)
.with_task_overhead_ns(500);
assert!(
plan.estimated_per_item_ns.is_some(),
"the profile supplies a default, which is what makes this the interesting case"
);
assert!(!plan.estimated_per_item_ns_explicit);
assert_eq!(model_leaf(&plan, n), None);
assert!(model_leaf(&plan.with_estimated_per_item_ns(50), n).is_some());
}
#[test]
fn the_model_width_grows_with_overhead_and_shrinks_with_per_item_cost() {
let n = 4096usize;
let width = |per_item: u32, overhead: u32| {
model_leaf(
&JobPlan::new(6, n as u32)
.with_estimated_per_item_ns(per_item)
.with_task_overhead_ns(overhead),
n,
)
.expect("both hints are set")
};
assert!(width(50, 5_000) > width(50, 500));
assert!(width(500, 500) < width(50, 500));
let with_span = model_leaf(
&JobPlan::new(6, n as u32)
.with_estimated_per_item_ns(50)
.with_task_overhead_ns(500)
.with_task_span_ns(4_500),
n,
)
.expect("both hints are set");
assert_eq!(with_span, width(50, 5_000));
}
#[test]
fn a_fixed_cost_that_swamps_the_work_collapses_the_width_to_the_whole_run() {
let n = 64usize;
let one_chunk = model_leaf(
&JobPlan::new(6, n as u32)
.with_estimated_per_item_ns(100_000)
.with_task_overhead_ns(u32::MAX),
n,
)
.expect("both hints are set");
assert_eq!(one_chunk, n, "one chunk over n items is n items wide");
let per_item = model_leaf(
&JobPlan::new(6, n as u32)
.with_estimated_per_item_ns(100_000)
.with_task_overhead_ns(1),
n,
)
.expect("both hints are set");
assert_eq!(per_item, 1);
}
}