#![allow(clippy::missing_errors_doc)]
use core::sync::atomic::{AtomicBool, AtomicPtr, AtomicU8, AtomicU32, AtomicU64, Ordering};
use crate::sched::adaptive_profile::{
WorkloadClass, class_tag_decode, class_tag_encode, classify_window,
};
const TAG_UNINIT: u8 = 0xFF;
const SITE_CLASSIFY_QUANTUM: u64 = 16;
const SITE_MIGRATION_HYSTERESIS: u32 = 2;
fn per_item_cv2(sumsq_per_item: u64, mean: u64, items: u64) -> Option<u64> {
let mean_sq = (mean as u128).saturating_mul(mean as u128);
let expected = mean_sq.saturating_mul(items as u128);
if expected == 0 {
return None;
}
let total = (sumsq_per_item as u128) << 16;
let spread = total.saturating_sub(expected);
Some((spread.saturating_mul(1000) / expected) as u64)
}
fn publish_min(slot: &AtomicU64, value: u64) {
if value < slot.load(Ordering::Relaxed) {
slot.store(value, Ordering::Relaxed);
}
}
fn publish_max(slot: &AtomicU64, value: u64) {
if value > slot.load(Ordering::Relaxed) {
slot.store(value, Ordering::Relaxed);
}
}
fn publish_count(slot: &AtomicU64) {
slot.store(
slot.load(Ordering::Relaxed).wrapping_add(1),
Ordering::Relaxed,
);
}
const FULL_WEIGHT: u64 = 1000;
pub(crate) fn batch_weight_per_mille(on_core_ticks: u64, wall_ticks: u64) -> Option<u64> {
if wall_ticks == 0 {
return None;
}
let share = (on_core_ticks as u128).saturating_mul(FULL_WEIGHT as u128)
/ (wall_ticks as u128);
Some((share as u64).min(FULL_WEIGHT))
}
const ARM_TRIAL_CADENCE: u32 = 16;
const ARM_MIN_SAMPLES: u32 = 3;
const PLACEMENT_REPROBE_CADENCE: u32 = 32;
pub const PLACEMENT_BUCKETS: usize = 40;
const EWMA_COUNT_SHIFT: u32 = 56;
const EWMA_VALUE_MASK: u64 = (1u64 << EWMA_COUNT_SHIFT) - 1;
const EWMA_ALPHA_RECIP: u64 = 8;
const EWMA_WARM_SAMPLES: u64 = EWMA_ALPHA_RECIP;
#[inline]
fn ewma_update(cell: &AtomicU64, sample_ns: u64) {
let packed = cell.load(Ordering::Relaxed);
let count = packed >> EWMA_COUNT_SHIFT;
let old = packed & EWMA_VALUE_MASK;
let sample = sample_ns.max(1) & EWMA_VALUE_MASK;
let (new, count) = if count == 0 {
(sample, 1)
} else if count < EWMA_WARM_SAMPLES {
((old * count + sample) / (count + 1), count + 1)
} else {
(
(old - old / EWMA_ALPHA_RECIP).saturating_add(sample / EWMA_ALPHA_RECIP),
count,
)
};
cell.store((count << EWMA_COUNT_SHIFT) | (new.max(1) & EWMA_VALUE_MASK), Ordering::Relaxed);
}
#[inline]
fn ewma_value(cell: &AtomicU64) -> u64 {
cell.load(Ordering::Relaxed) & EWMA_VALUE_MASK
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PolicyArm {
Default,
Alternative,
}
impl PolicyArm {
#[inline]
fn idx(self) -> usize {
match self {
PolicyArm::Default => 0,
PolicyArm::Alternative => 1,
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Placement {
Cpu,
Backend,
Race,
}
pub struct CallSiteState {
active_tag: AtomicU8,
pending_tag: AtomicU8,
pending_run: AtomicU32,
leaf_count: AtomicU64,
leaf_sum_ns: AtomicU64,
leaf_sumsq_scaled: AtomicU64,
leaf_items: AtomicU64,
leaf_sumsq_per_item: AtomicU64,
leaf_weight_sum: AtomicU64,
leaf_oncore_items: AtomicU64,
leaf_oncore_sum: AtomicU64,
leaf_oncore_sumsq_per_item: AtomicU64,
last_count: AtomicU64,
last_sum_ns: AtomicU64,
last_sumsq: AtomicU64,
last_items: AtomicU64,
last_sumsq_per_item: AtomicU64,
last_weight_sum: AtomicU64,
last_oncore_items: AtomicU64,
last_oncore_sum: AtomicU64,
last_oncore_sumsq_per_item: AtomicU64,
window_mean_ns: AtomicU64,
window_cv2: AtomicU64,
window_ticks: AtomicU64,
window_spread_ticks: AtomicU64,
window_cv2_min: AtomicU64,
window_cv2_max: AtomicU64,
window_wall_cv2: AtomicU64,
window_wall_cv2_min: AtomicU64,
window_wall_cv2_max: AtomicU64,
window_wall_ticks: AtomicU64,
window_oncore_cv2: AtomicU64,
window_oncore_cv2_min: AtomicU64,
window_oncore_cv2_max: AtomicU64,
window_oncore_ticks: AtomicU64,
arm_ewma_ns: [AtomicU64; 2],
arm_samples: [AtomicU32; 2],
arm_calls: AtomicU32,
routing_ewma_ns: [AtomicU64; 2],
routing_samples: [AtomicU32; 2],
routing_calls: AtomicU32,
place_cpu_ns: [AtomicU64; PLACEMENT_BUCKETS],
place_backend_ns: [AtomicU64; PLACEMENT_BUCKETS],
place_calls: [AtomicU32; PLACEMENT_BUCKETS],
split_cpu_ns_per_item: AtomicU64,
split_backend_ns_per_item: AtomicU64,
split_cpu_ns_per_item_by_size: [AtomicU64; PLACEMENT_BUCKETS],
split_backend_ns_per_item_by_size: [AtomicU64; PLACEMENT_BUCKETS],
reduce_cost_sum_cycles: AtomicU64,
reduce_cost_samples: AtomicU32,
collapse_overran: AtomicBool,
active_depth: AtomicU32,
pending_depth: AtomicU32,
depth_run: AtomicU32,
recent_occupancy_pct: AtomicU32,
pool_thread_ticks: AtomicU64,
pool_wall_ticks: AtomicU64,
last_seed_depth: AtomicU32,
seed_depth_flips: AtomicU32,
}
const DEPTH_UNSET: u32 = u32::MAX;
const OCCUPANCY_UNREPORTED: u32 = u32::MAX;
pub const SEED_DEPTH_HYSTERESIS: u32 = 2;
impl CallSiteState {
#[allow(clippy::new_without_default)]
pub const fn new() -> Self {
Self {
active_tag: AtomicU8::new(TAG_UNINIT),
pending_tag: AtomicU8::new(TAG_UNINIT),
pending_run: AtomicU32::new(0),
leaf_count: AtomicU64::new(0),
leaf_sum_ns: AtomicU64::new(0),
leaf_sumsq_scaled: AtomicU64::new(0),
leaf_items: AtomicU64::new(0),
leaf_sumsq_per_item: AtomicU64::new(0),
leaf_weight_sum: AtomicU64::new(0),
leaf_oncore_items: AtomicU64::new(0),
leaf_oncore_sum: AtomicU64::new(0),
leaf_oncore_sumsq_per_item: AtomicU64::new(0),
last_oncore_items: AtomicU64::new(0),
last_oncore_sum: AtomicU64::new(0),
last_oncore_sumsq_per_item: AtomicU64::new(0),
last_count: AtomicU64::new(0),
last_sum_ns: AtomicU64::new(0),
last_sumsq: AtomicU64::new(0),
last_items: AtomicU64::new(0),
last_sumsq_per_item: AtomicU64::new(0),
last_weight_sum: AtomicU64::new(0),
window_mean_ns: AtomicU64::new(0),
window_cv2: AtomicU64::new(0),
window_ticks: AtomicU64::new(0),
window_spread_ticks: AtomicU64::new(0),
window_cv2_min: AtomicU64::new(u64::MAX),
window_cv2_max: AtomicU64::new(0),
window_wall_cv2: AtomicU64::new(0),
window_wall_cv2_min: AtomicU64::new(u64::MAX),
window_wall_cv2_max: AtomicU64::new(0),
window_wall_ticks: AtomicU64::new(0),
window_oncore_cv2: AtomicU64::new(0),
window_oncore_cv2_min: AtomicU64::new(u64::MAX),
window_oncore_cv2_max: AtomicU64::new(0),
window_oncore_ticks: AtomicU64::new(0),
arm_ewma_ns: [const { AtomicU64::new(0) }; 2],
arm_samples: [const { AtomicU32::new(0) }; 2],
arm_calls: AtomicU32::new(0),
routing_ewma_ns: [const { AtomicU64::new(0) }; 2],
routing_samples: [const { AtomicU32::new(0) }; 2],
routing_calls: AtomicU32::new(0),
place_cpu_ns: [const { AtomicU64::new(0) }; PLACEMENT_BUCKETS],
place_backend_ns: [const { AtomicU64::new(0) }; PLACEMENT_BUCKETS],
place_calls: [const { AtomicU32::new(0) }; PLACEMENT_BUCKETS],
split_cpu_ns_per_item: AtomicU64::new(0),
split_backend_ns_per_item: AtomicU64::new(0),
split_cpu_ns_per_item_by_size: [const { AtomicU64::new(0) }; PLACEMENT_BUCKETS],
split_backend_ns_per_item_by_size: [const { AtomicU64::new(0) }; PLACEMENT_BUCKETS],
reduce_cost_sum_cycles: AtomicU64::new(0),
reduce_cost_samples: AtomicU32::new(0),
collapse_overran: AtomicBool::new(false),
active_depth: AtomicU32::new(DEPTH_UNSET),
pending_depth: AtomicU32::new(DEPTH_UNSET),
depth_run: AtomicU32::new(0),
recent_occupancy_pct: AtomicU32::new(OCCUPANCY_UNREPORTED),
pool_thread_ticks: AtomicU64::new(0),
pool_wall_ticks: AtomicU64::new(0),
last_seed_depth: AtomicU32::new(DEPTH_UNSET),
seed_depth_flips: AtomicU32::new(0),
}
}
pub fn reset(&self) {
let Self {
active_tag,
pending_tag,
pending_run,
leaf_count,
leaf_sum_ns,
leaf_sumsq_scaled,
leaf_items,
leaf_sumsq_per_item,
leaf_weight_sum,
leaf_oncore_items,
leaf_oncore_sum,
leaf_oncore_sumsq_per_item,
last_count,
last_sum_ns,
last_sumsq,
last_items,
last_sumsq_per_item,
last_weight_sum,
last_oncore_items,
last_oncore_sum,
last_oncore_sumsq_per_item,
window_mean_ns,
window_cv2,
window_ticks,
window_spread_ticks,
window_cv2_min,
window_cv2_max,
window_wall_cv2,
window_wall_cv2_min,
window_wall_cv2_max,
window_wall_ticks,
window_oncore_cv2,
window_oncore_cv2_min,
window_oncore_cv2_max,
window_oncore_ticks,
arm_ewma_ns,
arm_samples,
arm_calls,
routing_ewma_ns,
routing_samples,
routing_calls,
place_cpu_ns,
place_backend_ns,
place_calls,
split_cpu_ns_per_item,
split_backend_ns_per_item,
split_cpu_ns_per_item_by_size,
split_backend_ns_per_item_by_size,
reduce_cost_sum_cycles,
reduce_cost_samples,
collapse_overran,
active_depth,
pending_depth,
depth_run,
recent_occupancy_pct,
pool_thread_ticks,
pool_wall_ticks,
last_seed_depth,
seed_depth_flips,
} = self;
for tag in [active_tag, pending_tag] {
tag.store(TAG_UNINIT, Ordering::Relaxed);
}
for counter in [
leaf_count,
leaf_sum_ns,
leaf_sumsq_scaled,
leaf_items,
leaf_sumsq_per_item,
leaf_weight_sum,
leaf_oncore_items,
leaf_oncore_sum,
leaf_oncore_sumsq_per_item,
last_count,
last_sum_ns,
last_sumsq,
last_items,
last_sumsq_per_item,
last_weight_sum,
last_oncore_items,
last_oncore_sum,
last_oncore_sumsq_per_item,
window_mean_ns,
window_cv2,
window_ticks,
window_spread_ticks,
window_cv2_max,
window_wall_cv2,
window_wall_cv2_max,
window_wall_ticks,
window_oncore_cv2,
window_oncore_cv2_max,
window_oncore_ticks,
split_cpu_ns_per_item,
split_backend_ns_per_item,
reduce_cost_sum_cycles,
pool_thread_ticks,
pool_wall_ticks,
] {
counter.store(0, Ordering::Relaxed);
}
for counter in [
pending_run,
arm_calls,
routing_calls,
reduce_cost_samples,
depth_run,
seed_depth_flips,
] {
counter.store(0, Ordering::Relaxed);
}
for depth in [active_depth, pending_depth, last_seed_depth] {
depth.store(DEPTH_UNSET, Ordering::Relaxed);
}
for bank in [
&arm_ewma_ns[..],
&routing_ewma_ns[..],
&place_cpu_ns[..],
&place_backend_ns[..],
&split_cpu_ns_per_item_by_size[..],
&split_backend_ns_per_item_by_size[..],
] {
for cell in bank {
cell.store(0, Ordering::Relaxed);
}
}
for bank in [&arm_samples[..], &routing_samples[..], &place_calls[..]] {
for cell in bank {
cell.store(0, Ordering::Relaxed);
}
}
for min in [window_cv2_min, window_wall_cv2_min, window_oncore_cv2_min] {
min.store(u64::MAX, Ordering::Relaxed);
}
recent_occupancy_pct.store(OCCUPANCY_UNREPORTED, Ordering::Relaxed);
collapse_overran.store(false, Ordering::Relaxed);
}
pub fn record_seed_depth(&self, depth: usize) {
let d = depth as u32;
let previous = self.last_seed_depth.swap(d, Ordering::Relaxed);
if previous != DEPTH_UNSET && previous != d {
self.seed_depth_flips.fetch_add(1, Ordering::Relaxed);
}
}
pub fn seed_depth_flips(&self) -> u32 {
self.seed_depth_flips.load(Ordering::Relaxed)
}
pub(crate) fn add_pool_ticks(&self, thread_ticks: u64, wall_ticks: u64) {
self.pool_thread_ticks
.fetch_add(thread_ticks, Ordering::Relaxed);
self.pool_wall_ticks.fetch_add(wall_ticks, Ordering::Relaxed);
}
pub(crate) fn pool_ticks(&self) -> (u64, u64) {
(
self.pool_thread_ticks.load(Ordering::Relaxed),
self.pool_wall_ticks.load(Ordering::Relaxed),
)
}
pub fn record_occupancy(&self, percent: u32) {
self.recent_occupancy_pct
.store(percent.min(100), Ordering::Relaxed);
}
pub fn recent_occupancy(&self) -> Option<u32> {
match self.recent_occupancy_pct.load(Ordering::Relaxed) {
OCCUPANCY_UNREPORTED => None,
pct => Some(pct),
}
}
pub fn stabilize_seed_depth(&self, observed: usize) -> usize {
let obs = observed as u32;
let active = self.active_depth.load(Ordering::Relaxed);
if active == DEPTH_UNSET {
self.active_depth.store(obs, Ordering::Relaxed);
return observed;
}
if obs == active {
self.depth_run.store(0, Ordering::Relaxed);
return observed;
}
let previous_pending = self.pending_depth.swap(obs, Ordering::Relaxed);
let run = if previous_pending == obs {
self.depth_run
.fetch_add(1, Ordering::Relaxed)
.saturating_add(1)
} else {
self.depth_run.store(1, Ordering::Relaxed);
1
};
if run >= SEED_DEPTH_HYSTERESIS {
self.active_depth.store(obs, Ordering::Relaxed);
self.depth_run.store(0, Ordering::Relaxed);
return observed;
}
active as usize
}
pub fn seeded_depth(&self) -> Option<u32> {
match self.active_depth.load(Ordering::Relaxed) {
DEPTH_UNSET => None,
d => Some(d),
}
}
#[inline]
pub fn collapse_overran(&self) -> bool {
self.collapse_overran.load(Ordering::Relaxed)
}
#[inline]
pub fn note_collapsed_body(&self, elapsed_ns: u64, threshold_ns: u64) {
if elapsed_ns > threshold_ns {
self.collapse_overran.store(true, Ordering::Relaxed);
}
}
#[inline]
pub fn learned_class(&self) -> Option<WorkloadClass> {
class_tag_decode(self.active_tag.load(Ordering::Acquire))
}
pub fn record_batch(
&'static self,
sum_ns: u64,
sumsq_scaled: u64,
count: u64,
items: u64,
sumsq_per_item: u64,
) {
crate::sched::split_observer::record_leaf_batch(
sum_ns,
sumsq_scaled,
count,
items,
sumsq_per_item,
);
self.record_batch_site_only(sum_ns, sumsq_scaled, count, items, sumsq_per_item);
}
pub(crate) fn record_batch_site_only(
&'static self,
sum_ns: u64,
sumsq_scaled: u64,
count: u64,
items: u64,
sumsq_per_item: u64,
) {
self.record_batch_weighted(sum_ns, sumsq_scaled, count, items, sumsq_per_item, None)
}
pub(crate) fn record_batch_weighted(
&'static self,
sum_ns: u64,
sumsq_scaled: u64,
count: u64,
items: u64,
sumsq_per_item: u64,
weight_per_mille: Option<u64>,
) {
let w = weight_per_mille.unwrap_or(FULL_WEIGHT).min(FULL_WEIGHT);
let scale = |v: u64| v.saturating_mul(w);
self.leaf_sum_ns.fetch_add(scale(sum_ns), Ordering::Relaxed);
self.leaf_sumsq_scaled
.fetch_add(scale(sumsq_scaled), Ordering::Relaxed);
self.leaf_items.fetch_add(scale(items), Ordering::Relaxed);
self.leaf_sumsq_per_item
.fetch_add(scale(sumsq_per_item), Ordering::Relaxed);
self.leaf_weight_sum
.fetch_add(scale(count), Ordering::Relaxed);
let prior = self.leaf_count.fetch_add(count, Ordering::Relaxed);
let new_total = prior.wrapping_add(count);
if (prior / SITE_CLASSIFY_QUANTUM) != (new_total / SITE_CLASSIFY_QUANTUM) {
self.tick();
}
}
pub(crate) fn record_oncore_batch(
&'static self,
oncore_sum: u64,
oncore_sumsq_per_item: u64,
items: u64,
) {
if items == 0 {
return;
}
self.leaf_oncore_sum.fetch_add(oncore_sum, Ordering::Relaxed);
self.leaf_oncore_sumsq_per_item
.fetch_add(oncore_sumsq_per_item, Ordering::Relaxed);
self.leaf_oncore_items.fetch_add(items, Ordering::Relaxed);
}
pub fn per_item_oncore_cv2_per_mille(&self) -> Option<u64> {
let items = self.leaf_oncore_items.load(Ordering::Relaxed);
if items == 0 {
return None;
}
let mean = self.leaf_oncore_sum.load(Ordering::Relaxed) / items;
let sumsq = self.leaf_oncore_sumsq_per_item.load(Ordering::Relaxed);
per_item_cv2(sumsq, mean, items)
}
pub fn oncore_items(&self) -> u64 {
self.leaf_oncore_items.load(Ordering::Relaxed)
}
pub fn cv2_per_mille(&self) -> Option<u64> {
let n = self.leaf_count.load(Ordering::Relaxed);
if n < 4 {
return None;
}
let sum = self.leaf_sum_ns.load(Ordering::Relaxed);
let sumsq = self.leaf_sumsq_scaled.load(Ordering::Relaxed);
let n = self.leaf_weight_sum.load(Ordering::Relaxed).max(1);
let mean_scaled = (sum >> 8) / n;
if mean_scaled == 0 {
return None;
}
let sumsq_per_n = sumsq / n;
let mean_sq = mean_scaled.saturating_mul(mean_scaled);
let var = sumsq_per_n.saturating_sub(mean_sq);
Some(var.saturating_mul(1000) / mean_sq)
}
pub(crate) fn leaves_under_spread_unit(&self) -> bool {
if self.leaf_count.load(Ordering::Relaxed) < 4 {
return false;
}
let n = self.leaf_weight_sum.load(Ordering::Relaxed).max(1);
(self.leaf_sum_ns.load(Ordering::Relaxed) >> 8) / n == 0
}
#[inline]
pub fn leaf_count(&self) -> u64 {
self.leaf_count.load(Ordering::Relaxed)
}
pub fn leaf_sum_ns(&self) -> u64 {
let weight = self.leaf_weight_sum.load(Ordering::Relaxed);
if weight == 0 {
return 0;
}
let mean = self.leaf_sum_ns.load(Ordering::Relaxed) / weight;
mean.saturating_mul(self.leaf_count.load(Ordering::Relaxed))
}
pub fn per_item_ns(&self) -> Option<u64> {
if self.leaf_count.load(Ordering::Relaxed) < 4 {
return None;
}
let items = self.leaf_items.load(Ordering::Relaxed);
if items == 0 {
return None;
}
Some(self.leaf_sum_ns.load(Ordering::Relaxed) / items)
}
pub fn per_item_cv2_per_mille(&self) -> Option<u64> {
let leaves = self.leaf_count.load(Ordering::Relaxed);
if leaves < 4 {
return None;
}
let items = self.leaf_items.load(Ordering::Relaxed);
if items == 0 {
return None;
}
let mean_ns = self.leaf_sum_ns.load(Ordering::Relaxed) / items;
let sumsq_per_item = self.leaf_sumsq_per_item.load(Ordering::Relaxed);
per_item_cv2(sumsq_per_item, mean_ns, items)
}
pub fn window_mean_ns(&self) -> Option<u64> {
if self.window_ticks.load(Ordering::Relaxed) == 0 {
None
} else {
Some(self.window_mean_ns.load(Ordering::Relaxed))
}
}
pub fn window_cv2_per_mille(&self) -> Option<u64> {
if self.window_spread_ticks.load(Ordering::Relaxed) == 0 {
None
} else {
Some(self.window_cv2.load(Ordering::Relaxed))
}
}
pub fn window_ticks(&self) -> u64 {
self.window_ticks.load(Ordering::Relaxed)
}
pub fn window_spread_ticks(&self) -> u64 {
self.window_spread_ticks.load(Ordering::Relaxed)
}
pub fn window_cv2_range_per_mille(&self) -> Option<(u64, u64)> {
if self.window_spread_ticks.load(Ordering::Relaxed) == 0 {
None
} else {
Some((
self.window_cv2_min.load(Ordering::Relaxed),
self.window_cv2_max.load(Ordering::Relaxed),
))
}
}
pub fn window_wall_cv2_per_mille(&self) -> Option<u64> {
if self.window_wall_ticks.load(Ordering::Relaxed) == 0 {
None
} else {
Some(self.window_wall_cv2.load(Ordering::Relaxed))
}
}
pub fn window_wall_cv2_range_per_mille(&self) -> Option<(u64, u64)> {
if self.window_wall_ticks.load(Ordering::Relaxed) == 0 {
None
} else {
Some((
self.window_wall_cv2_min.load(Ordering::Relaxed),
self.window_wall_cv2_max.load(Ordering::Relaxed),
))
}
}
pub fn window_wall_ticks(&self) -> u64 {
self.window_wall_ticks.load(Ordering::Relaxed)
}
pub fn window_oncore_cv2_per_mille(&self) -> Option<u64> {
if self.window_oncore_ticks.load(Ordering::Relaxed) == 0 {
None
} else {
Some(self.window_oncore_cv2.load(Ordering::Relaxed))
}
}
pub fn window_oncore_cv2_range_per_mille(&self) -> Option<(u64, u64)> {
if self.window_oncore_ticks.load(Ordering::Relaxed) == 0 {
None
} else {
Some((
self.window_oncore_cv2_min.load(Ordering::Relaxed),
self.window_oncore_cv2_max.load(Ordering::Relaxed),
))
}
}
pub fn window_oncore_ticks(&self) -> u64 {
self.window_oncore_ticks.load(Ordering::Relaxed)
}
fn tick(&self) {
let count = self.leaf_count.load(Ordering::Relaxed);
let sum = self.leaf_sum_ns.load(Ordering::Relaxed);
let sumsq = self.leaf_sumsq_scaled.load(Ordering::Relaxed);
let prev_count = self.last_count.load(Ordering::Relaxed);
let dcount = count.saturating_sub(prev_count);
if dcount < 4 {
return;
}
let items = self.leaf_items.load(Ordering::Relaxed);
let sumsq_per_item = self.leaf_sumsq_per_item.load(Ordering::Relaxed);
let dsum = sum.saturating_sub(self.last_sum_ns.load(Ordering::Relaxed));
let dsumsq = sumsq.saturating_sub(self.last_sumsq.load(Ordering::Relaxed));
let ditems = items.saturating_sub(self.last_items.load(Ordering::Relaxed));
let dsumsq_per_item =
sumsq_per_item.saturating_sub(self.last_sumsq_per_item.load(Ordering::Relaxed));
let weight_sum = self.leaf_weight_sum.load(Ordering::Relaxed);
let dweight = weight_sum
.saturating_sub(self.last_weight_sum.load(Ordering::Relaxed))
.max(1);
self.last_weight_sum.store(weight_sum, Ordering::Relaxed);
self.last_count.store(count, Ordering::Relaxed);
self.last_sum_ns.store(sum, Ordering::Relaxed);
self.last_sumsq.store(sumsq, Ordering::Relaxed);
self.last_items.store(items, Ordering::Relaxed);
self.last_sumsq_per_item.store(sumsq_per_item, Ordering::Relaxed);
let oncore_items = self.leaf_oncore_items.load(Ordering::Relaxed);
let oncore_sum = self.leaf_oncore_sum.load(Ordering::Relaxed);
let oncore_sumsq = self.leaf_oncore_sumsq_per_item.load(Ordering::Relaxed);
let d_oncore_items =
oncore_items.saturating_sub(self.last_oncore_items.load(Ordering::Relaxed));
let d_oncore_sum =
oncore_sum.saturating_sub(self.last_oncore_sum.load(Ordering::Relaxed));
let d_oncore_sumsq = oncore_sumsq
.saturating_sub(self.last_oncore_sumsq_per_item.load(Ordering::Relaxed));
self.last_oncore_items.store(oncore_items, Ordering::Relaxed);
self.last_oncore_sum.store(oncore_sum, Ordering::Relaxed);
self.last_oncore_sumsq_per_item
.store(oncore_sumsq, Ordering::Relaxed);
let oncore_cv2 = d_oncore_sum
.checked_div(d_oncore_items)
.and_then(|mean| per_item_cv2(d_oncore_sumsq, mean, d_oncore_items));
let per_item = dsum.checked_div(ditems);
let (mean_ns, wall_cv2) = if let Some(mean) = per_item {
(mean, per_item_cv2(dsumsq_per_item, mean, ditems))
} else {
let mean = dsum / dweight;
let scaled_mean = (dsum >> 8) / dweight;
let spread = (scaled_mean > 0).then(|| {
let sumsq_per_n = dsumsq / dweight;
let mean_sq = scaled_mean.saturating_mul(scaled_mean);
let var = sumsq_per_n.saturating_sub(mean_sq);
var.saturating_mul(1000) / mean_sq
});
(mean, spread)
};
let oncore_used = oncore_cv2.filter(|_| per_item.is_some());
let cv2 = oncore_used.or(wall_cv2);
self.window_mean_ns.store(mean_ns, Ordering::Relaxed);
publish_count(&self.window_ticks);
if let Some(cv2) = cv2 {
self.window_cv2.store(cv2, Ordering::Relaxed);
publish_min(&self.window_cv2_min, cv2);
publish_max(&self.window_cv2_max, cv2);
publish_count(&self.window_spread_ticks);
}
if let Some(wall) = wall_cv2 {
self.window_wall_cv2.store(wall, Ordering::Relaxed);
publish_min(&self.window_wall_cv2_min, wall);
publish_max(&self.window_wall_cv2_max, wall);
publish_count(&self.window_wall_ticks);
}
if let Some(oncore) = oncore_used {
self.window_oncore_cv2.store(oncore, Ordering::Relaxed);
publish_min(&self.window_oncore_cv2_min, oncore);
publish_max(&self.window_oncore_cv2_max, oncore);
publish_count(&self.window_oncore_ticks);
}
let Some(observed) = classify_window(mean_ns, cv2) else {
return;
};
let observed_tag = class_tag_encode(observed);
let active = class_tag_decode(self.active_tag.load(Ordering::Relaxed));
match active {
None => {
self.active_tag.store(observed_tag, Ordering::Release);
self.pending_tag.store(observed_tag, Ordering::Relaxed);
self.pending_run.store(0, Ordering::Relaxed);
}
Some(active_class) if active_class != observed => {
if crate::sched::adaptive_profile::class_bucket_distance(
active_class, observed,
) >= 2
&& dcount >= 64
{
self.active_tag.store(observed_tag, Ordering::Release);
self.pending_tag.store(observed_tag, Ordering::Relaxed);
self.pending_run.store(0, Ordering::Relaxed);
return;
}
let pending = self.pending_tag.load(Ordering::Relaxed);
if pending == observed_tag {
let run = self
.pending_run
.fetch_add(1, Ordering::Relaxed)
.saturating_add(1);
if run >= SITE_MIGRATION_HYSTERESIS {
self.active_tag.store(observed_tag, Ordering::Release);
}
} else {
self.pending_tag.store(observed_tag, Ordering::Relaxed);
self.pending_run.store(1, Ordering::Relaxed);
}
}
Some(_) => {
self.pending_tag.store(observed_tag, Ordering::Relaxed);
self.pending_run.store(0, Ordering::Relaxed);
}
}
}
pub fn choose_arm(&self, alternative_allowed: bool) -> PolicyArm {
if !alternative_allowed {
return PolicyArm::Default;
}
let calls = self.arm_calls.fetch_add(1, Ordering::Relaxed);
let s0 = self.arm_samples[0].load(Ordering::Relaxed);
let s1 = self.arm_samples[1].load(Ordering::Relaxed);
if s0 < ARM_MIN_SAMPLES || s1 < ARM_MIN_SAMPLES {
return if s1 < s0 {
PolicyArm::Alternative
} else {
PolicyArm::Default
};
}
let e0 = ewma_value(&self.arm_ewma_ns[0]);
let e1 = ewma_value(&self.arm_ewma_ns[1]);
let best = if e1 < e0 {
PolicyArm::Alternative
} else {
PolicyArm::Default
};
if calls % ARM_TRIAL_CADENCE == ARM_TRIAL_CADENCE - 1 {
return match best {
PolicyArm::Default => PolicyArm::Alternative,
PolicyArm::Alternative => PolicyArm::Default,
};
}
best
}
pub fn choose_routing_arm(&self) -> PolicyArm {
let calls = self.routing_calls.fetch_add(1, Ordering::Relaxed);
let s0 = self.routing_samples[0].load(Ordering::Relaxed);
let s1 = self.routing_samples[1].load(Ordering::Relaxed);
if s0 < ARM_MIN_SAMPLES || s1 < ARM_MIN_SAMPLES {
return if s1 < s0 {
PolicyArm::Alternative
} else {
PolicyArm::Default
};
}
let e0 = ewma_value(&self.routing_ewma_ns[0]);
let e1 = ewma_value(&self.routing_ewma_ns[1]);
let best = if e1 < e0 {
PolicyArm::Alternative
} else {
PolicyArm::Default
};
if calls % ARM_TRIAL_CADENCE == ARM_TRIAL_CADENCE - 1 {
return match best {
PolicyArm::Default => PolicyArm::Alternative,
PolicyArm::Alternative => PolicyArm::Default,
};
}
best
}
pub fn record_routing_arm(&self, arm: PolicyArm, wall_ns: u64) {
let i = arm.idx();
ewma_update(&self.routing_ewma_ns[i], wall_ns);
self.routing_samples[i].fetch_add(1, Ordering::Relaxed);
}
pub fn routing_ewmas(&self) -> (u64, u64) {
(
ewma_value(&self.routing_ewma_ns[0]),
ewma_value(&self.routing_ewma_ns[1]),
)
}
pub fn record_arm(&self, arm: PolicyArm, wall_ns: u64) {
let i = arm.idx();
ewma_update(&self.arm_ewma_ns[i], wall_ns);
self.arm_samples[i].fetch_add(1, Ordering::Relaxed);
}
pub fn arm_ewmas(&self) -> (u64, u64) {
(
ewma_value(&self.arm_ewma_ns[0]),
ewma_value(&self.arm_ewma_ns[1]),
)
}
#[inline]
fn bucket(batch: u32) -> usize {
(63 - (batch.max(1) as u64).leading_zeros() as usize).min(PLACEMENT_BUCKETS - 1)
}
pub fn choose_placement(&self, batch: u32) -> Placement {
let b = Self::bucket(batch);
let calls = self.place_calls[b].fetch_add(1, Ordering::Relaxed);
let cpu = ewma_value(&self.place_cpu_ns[b]);
let dev = ewma_value(&self.place_backend_ns[b]);
if cpu == 0 || dev == 0 {
return Placement::Race;
}
if calls % PLACEMENT_REPROBE_CADENCE == PLACEMENT_REPROBE_CADENCE - 1 {
return Placement::Race;
}
if cpu <= dev { Placement::Cpu } else { Placement::Backend }
}
pub fn record_placement(
&self,
batch: u32,
cpu_ns: Option<u64>,
backend_ns: Option<u64>,
) {
let b = Self::bucket(batch);
if let Some(ns) = cpu_ns {
ewma_update(&self.place_cpu_ns[b], ns);
}
if let Some(ns) = backend_ns {
ewma_update(&self.place_backend_ns[b], ns);
}
}
pub fn placement_ewmas(&self, batch: u32) -> (u64, u64) {
let b = Self::bucket(batch);
(
ewma_value(&self.place_cpu_ns[b]),
ewma_value(&self.place_backend_ns[b]),
)
}
pub fn split_cpu_share_per_mille(&self) -> u32 {
let c = ewma_value(&self.split_cpu_ns_per_item);
let g = ewma_value(&self.split_backend_ns_per_item);
if c == 0 || g == 0 {
return 500;
}
let total = c.saturating_add(g).max(1);
((g.saturating_mul(1000)) / total).clamp(50, 950) as u32
}
pub fn record_split(
&self,
cpu_items: usize,
cpu_ns: u64,
backend_items: usize,
backend_ns: u64,
) {
if cpu_items > 0 {
ewma_update(
&self.split_cpu_ns_per_item,
(cpu_ns / cpu_items as u64).max(1),
);
}
if backend_items > 0 {
ewma_update(
&self.split_backend_ns_per_item,
(backend_ns / backend_items as u64).max(1),
);
}
}
pub fn split_cpu_share_per_mille_for(&self, n: u32) -> u32 {
let b = Self::bucket(n);
let c = ewma_value(&self.split_cpu_ns_per_item_by_size[b]);
let g = ewma_value(&self.split_backend_ns_per_item_by_size[b]);
if c == 0 || g == 0 {
return self.split_cpu_share_per_mille();
}
let total = c.saturating_add(g).max(1);
((g.saturating_mul(1000)) / total).clamp(50, 950) as u32
}
pub fn record_split_for(
&self,
n: u32,
cpu_items: usize,
cpu_ns: u64,
backend_items: usize,
backend_ns: u64,
) {
let b = Self::bucket(n);
if cpu_items > 0 {
ewma_update(
&self.split_cpu_ns_per_item_by_size[b],
(cpu_ns / cpu_items as u64).max(1),
);
}
if backend_items > 0 {
ewma_update(
&self.split_backend_ns_per_item_by_size[b],
(backend_ns / backend_items as u64).max(1),
);
}
self.record_split(cpu_items, cpu_ns, backend_items, backend_ns);
}
pub fn reduce_cost_wants_sample(&self) -> bool {
self.reduce_cost_samples.load(Ordering::Relaxed) < REDUCE_COST_MAX_SAMPLES
}
pub fn record_reduce_cost_sample(&self, cycles: u64) {
self.reduce_cost_sum_cycles.fetch_add(cycles, Ordering::Relaxed);
self.reduce_cost_samples.fetch_add(1, Ordering::Relaxed);
}
pub fn reduce_cost_avg_cycles(&self) -> Option<u64> {
let n = self.reduce_cost_samples.load(Ordering::Relaxed);
if n < REDUCE_COST_MIN_SAMPLES {
return None;
}
Some(self.reduce_cost_sum_cycles.load(Ordering::Relaxed) / n as u64)
}
}
const REDUCE_COST_MAX_SAMPLES: u32 = 16;
const REDUCE_COST_MIN_SAMPLES: u32 = 4;
impl core::fmt::Debug for CallSiteState {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
f.debug_struct("CallSiteState")
.field("learned_class", &self.learned_class())
.field("leaf_count", &self.leaf_count())
.field("cv2_per_mille", &self.cv2_per_mille())
.finish()
}
}
#[derive(Clone, Copy)]
pub struct SiteRef(&'static CallSiteState);
impl SiteRef {
#[inline]
pub const fn new(site: &'static CallSiteState) -> Self {
Self(site)
}
#[inline]
pub fn get(self) -> &'static CallSiteState {
self.0
}
}
impl PartialEq for SiteRef {
#[inline]
fn eq(&self, other: &Self) -> bool {
core::ptr::eq(self.0, other.0)
}
}
impl Eq for SiteRef {}
impl core::hash::Hash for SiteRef {
#[inline]
fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
(self.0 as *const CallSiteState as usize).hash(state);
}
}
impl core::fmt::Debug for SiteRef {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
write!(f, "SiteRef({:p})", self.0 as *const CallSiteState)
}
}
struct SiteNode {
key: u64,
location: &'static std::panic::Location<'static>,
state: &'static CallSiteState,
}
const SITE_SLOTS: usize = 2048;
static SITE_TABLE: [AtomicPtr<SiteNode>; SITE_SLOTS] =
[const { AtomicPtr::new(core::ptr::null_mut()) }; SITE_SLOTS];
static SITE_TABLE_OVERFLOW: AtomicU64 = AtomicU64::new(0);
trait TableNode: 'static {
fn key(&self) -> u64;
fn state(&self) -> &'static CallSiteState;
}
impl TableNode for SiteNode {
fn key(&self) -> u64 {
self.key
}
fn state(&self) -> &'static CallSiteState {
self.state
}
}
fn table_lookup<N: TableNode>(
table: &'static [AtomicPtr<N>],
start: usize,
key: u64,
) -> Option<&'static N> {
let mask = table.len() - 1;
let mut idx = start & mask;
for _ in 0..table.len() {
let p = table[idx].load(Ordering::Acquire);
if p.is_null() {
return None;
}
let node = unsafe { &*p };
if node.key() == key {
return Some(node);
}
idx = (idx + 1) & mask;
}
None
}
fn table_insert<N: TableNode>(
table: &'static [AtomicPtr<N>],
start: usize,
key: u64,
build: impl Fn() -> N,
) -> Option<&'static CallSiteState> {
let mut prepared: Option<&'static N> = None;
let mask = table.len() - 1;
let mut idx = start & mask;
for _ in 0..table.len() {
let p = table[idx].load(Ordering::Acquire);
if p.is_null() {
let node = *prepared.get_or_insert_with(|| &*Box::leak(Box::new(build())));
let fresh = node as *const N as *mut N;
match table[idx].compare_exchange(
core::ptr::null_mut(),
fresh,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => return Some(node.state()),
Err(taken) => {
let other = unsafe { &*taken };
if other.key() == key {
return Some(other.state());
}
}
}
} else {
let node = unsafe { &*p };
if node.key() == key {
return Some(node.state());
}
}
idx = (idx + 1) & mask;
}
None
}
fn site_lookup(key: u64) -> Option<&'static SiteNode> {
table_lookup(&SITE_TABLE, key as usize, key)
}
fn site_insert(key: u64, loc: &'static std::panic::Location<'static>) -> &'static CallSiteState {
let inserted = table_insert(&SITE_TABLE, key as usize, key, || SiteNode {
key,
location: loc,
state: Box::leak(Box::new(CallSiteState::new())),
});
match inserted {
Some(state) => state,
None => {
SITE_TABLE_OVERFLOW.fetch_add(1, Ordering::Relaxed);
Box::leak(Box::new(CallSiteState::new()))
}
}
}
struct KeyNode {
key: u64,
state: &'static CallSiteState,
}
impl TableNode for KeyNode {
fn key(&self) -> u64 {
self.key
}
fn state(&self) -> &'static CallSiteState {
self.state
}
}
const KEY_SLOTS: usize = 4096;
static KEY_TABLE: [AtomicPtr<KeyNode>; KEY_SLOTS] =
[const { AtomicPtr::new(core::ptr::null_mut()) }; KEY_SLOTS];
static KEY_TABLE_OVERFLOW: AtomicU64 = AtomicU64::new(0);
static KEY_OVERFLOW_SITE: CallSiteState = CallSiteState::new();
fn key_slot(key: u64) -> usize {
(key.wrapping_mul(0x9E37_79B9_7F4A_7C15) >> 32) as usize
}
pub fn site_for_key(key: u64) -> SiteRef {
let slot = key_slot(key);
if let Some(node) = table_lookup(&KEY_TABLE, slot, key) {
return SiteRef::new(node.state);
}
let inserted = table_insert(&KEY_TABLE, slot, key, || KeyNode {
key,
state: Box::leak(Box::new(CallSiteState::new())),
});
match inserted {
Some(state) => SiteRef::new(state),
None => {
KEY_TABLE_OVERFLOW.fetch_add(1, Ordering::Relaxed);
SiteRef::new(&KEY_OVERFLOW_SITE)
}
}
}
pub fn keyed_site_table_overflow() -> u64 {
KEY_TABLE_OVERFLOW.load(Ordering::Relaxed)
}
pub fn site_table_overflow() -> u64 {
SITE_TABLE_OVERFLOW.load(Ordering::Relaxed)
}
fn location_key(loc: &'static std::panic::Location<'static>) -> u64 {
use core::hash::{Hash, Hasher};
let mut h = std::hash::DefaultHasher::new();
loc.file().hash(&mut h);
loc.line().hash(&mut h);
loc.column().hash(&mut h);
h.finish()
}
#[track_caller]
#[inline]
pub fn caller_site() -> SiteRef {
site_for_location(std::panic::Location::caller())
}
pub fn site_for_location(loc: &'static std::panic::Location<'static>) -> SiteRef {
thread_local! {
static LAST: core::cell::Cell<(usize, usize)> = const { core::cell::Cell::new((0, 0)) };
}
let loc_addr = loc as *const _ as usize;
let cached = LAST.with(|c| c.get());
if cached.0 == loc_addr && cached.1 != 0 {
return SiteRef::new(unsafe { &*(cached.1 as *const CallSiteState) });
}
let key = location_key(loc);
let site: &'static CallSiteState = match site_lookup(key) {
Some(node) => node.state,
None => site_insert(key, loc),
};
LAST.with(|c| c.set((loc_addr, site as *const CallSiteState as usize)));
SiteRef::new(site)
}
#[cfg(test)]
pub(crate) fn registry_len() -> usize {
site_nodes().count()
}
fn site_nodes() -> impl Iterator<Item = &'static SiteNode> {
table_nodes(&SITE_TABLE)
}
fn table_nodes<N: TableNode>(table: &'static [AtomicPtr<N>]) -> impl Iterator<Item = &'static N> {
table.iter().filter_map(|slot| {
let p = slot.load(Ordering::Acquire);
if p.is_null() {
None
} else {
Some(unsafe { &*p })
}
})
}
#[derive(Copy, Clone, Debug)]
pub struct RegisteredSite {
pub location: &'static std::panic::Location<'static>,
pub site: SiteRef,
}
pub fn registered_sites() -> Vec<RegisteredSite> {
site_nodes()
.map(|node| RegisteredSite {
location: node.location,
site: SiteRef::new(node.state),
})
.collect()
}
#[derive(Copy, Clone, Debug)]
pub struct RegisteredKeyedSite {
pub key: u64,
pub site: SiteRef,
}
pub fn registered_keyed_sites() -> Vec<RegisteredKeyedSite> {
table_nodes(&KEY_TABLE)
.map(|node| RegisteredKeyedSite {
key: node.key,
site: SiteRef::new(node.state),
})
.collect()
}
pub fn reset_all_sites() -> usize {
let mut swept = 0;
for node in site_nodes() {
node.state.reset();
swept += 1;
}
for node in table_nodes(&KEY_TABLE) {
node.state.reset();
swept += 1;
}
if keyed_site_table_overflow() > 0 {
KEY_OVERFLOW_SITE.reset();
swept += 1;
}
swept
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn a_batch_that_held_its_cores_weighs_a_whole_batch() {
assert_eq!(batch_weight_per_mille(8_000, 8_000), Some(FULL_WEIGHT));
assert_eq!(batch_weight_per_mille(4_800, 8_000), Some(600));
}
#[test]
fn a_weight_resolves_a_single_part_per_mille() {
assert_eq!(batch_weight_per_mille(1, 1_000), Some(1));
assert_eq!(batch_weight_per_mille(999, 1_000), Some(999));
}
#[test]
fn a_boosted_clock_pair_weighs_one_batch_and_not_more() {
assert_eq!(batch_weight_per_mille(12_000, 8_000), Some(FULL_WEIGHT));
}
#[test]
fn an_interval_that_never_elapsed_has_no_weight_rather_than_none_of_one() {
assert_eq!(batch_weight_per_mille(0, 0), None);
assert_eq!(batch_weight_per_mille(5_000, 0), None);
assert_eq!(batch_weight_per_mille(0, 8_000), Some(0));
}
#[test]
fn the_range_keeps_a_tick_the_latest_reading_has_already_lost() {
static S: CallSiteState = CallSiteState::new();
const ITEMS: u64 = 1024;
let sq = |ns: u64| (ns >> 8).saturating_mul(ns >> 8);
let per_item_sq =
|ns: u64| ((ns as u128).saturating_mul(ns as u128) / ((ITEMS as u128) << 16)) as u64;
let (fast, slow) = (1280u64 * ITEMS, 1920u64 * ITEMS);
S.record_batch_site_only(
8 * fast + 8 * slow,
8 * sq(fast) + 8 * sq(slow),
16,
16 * ITEMS,
8 * per_item_sq(fast) + 8 * per_item_sq(slow),
);
let spread_tick = S.window_cv2_per_mille().expect("a window was classified");
assert!(spread_tick > 0, "the first window carries a spread");
let flat = 1600u64 * ITEMS;
S.record_batch_site_only(
16 * flat,
16 * sq(flat),
16,
16 * ITEMS,
16 * per_item_sq(flat),
);
assert_eq!(
S.window_cv2_per_mille(),
Some(0),
"the latest reading is the flat window and says nothing of the first"
);
let (lo, hi) = S.window_cv2_range_per_mille().expect("two windows were classified");
assert_eq!(lo, 0, "the flat window is the smallest seen");
assert_eq!(hi, spread_tick, "and the spread one survives in the range");
}
#[test]
fn a_per_item_spread_is_read_at_its_own_value() {
static S: CallSiteState = CallSiteState::new();
const ITEMS: u64 = 1024;
let (fast, slow) = (1280u64 * ITEMS, 1920u64 * ITEMS);
let sq = |ns: u64| (ns >> 8).saturating_mul(ns >> 8);
let per_item_sq = |ns: u64| {
((ns as u128).saturating_mul(ns as u128) / ((ITEMS as u128) << 16)) as u64
};
S.record_batch_site_only(
8 * fast + 8 * slow,
8 * sq(fast) + 8 * sq(slow),
16,
16 * ITEMS,
8 * per_item_sq(fast) + 8 * per_item_sq(slow),
);
assert_eq!(S.window_mean_ns(), Some(1600));
assert_eq!(S.per_item_ns(), Some(1600));
assert_eq!(S.window_cv2_per_mille(), Some(40));
assert_eq!(S.per_item_cv2_per_mille(), Some(40));
let low = crate::sched::adaptive_profile::class_thresholds()
.cv2_low_per_mille
.load(Ordering::Relaxed);
if 40 < low {
assert_eq!(S.learned_class(), Some(WorkloadClass::Streaming));
}
}
#[test]
fn a_window_reports_its_spread_on_each_clock() {
static S: CallSiteState = CallSiteState::new();
const ITEMS: u64 = 1024;
let (fast, slow) = (1280u64 * ITEMS, 1920u64 * ITEMS);
let flat = 1600u64 * ITEMS;
let sq = |ns: u64| (ns >> 8).saturating_mul(ns >> 8);
let per_item_sq =
|ns: u64| ((ns as u128).saturating_mul(ns as u128) / ((ITEMS as u128) << 16)) as u64;
S.record_oncore_batch(16 * flat, 16 * per_item_sq(flat), 16 * ITEMS);
S.record_batch_site_only(
8 * fast + 8 * slow,
8 * sq(fast) + 8 * sq(slow),
16,
16 * ITEMS,
8 * per_item_sq(fast) + 8 * per_item_sq(slow),
);
assert_eq!(S.window_wall_cv2_per_mille(), Some(40));
assert_eq!(S.window_oncore_cv2_per_mille(), Some(0));
assert_eq!(
S.window_cv2_per_mille(),
Some(0),
"the classifier used the on-core spread"
);
assert_eq!(S.window_oncore_ticks(), 1);
assert_eq!(S.window_wall_cv2_range_per_mille(), Some((40, 40)));
assert_eq!(S.window_oncore_cv2_range_per_mille(), Some((0, 0)));
S.reset();
assert_eq!(S.window_wall_cv2_per_mille(), None);
assert_eq!(S.window_oncore_cv2_per_mille(), None);
assert_eq!(S.window_oncore_ticks(), 0);
S.record_batch_site_only(
16 * flat,
16 * sq(flat),
16,
16 * ITEMS,
16 * per_item_sq(flat),
);
assert_eq!(S.window_wall_cv2_range_per_mille(), Some((0, 0)));
}
#[test]
fn a_window_with_no_oncore_timing_reads_none_on_that_clock() {
static S: CallSiteState = CallSiteState::new();
const ITEMS: u64 = 1024;
let (fast, slow) = (1280u64 * ITEMS, 1920u64 * ITEMS);
let sq = |ns: u64| (ns >> 8).saturating_mul(ns >> 8);
let per_item_sq =
|ns: u64| ((ns as u128).saturating_mul(ns as u128) / ((ITEMS as u128) << 16)) as u64;
S.record_batch_site_only(
8 * fast + 8 * slow,
8 * sq(fast) + 8 * sq(slow),
16,
16 * ITEMS,
8 * per_item_sq(fast) + 8 * per_item_sq(slow),
);
assert_eq!(S.window_wall_cv2_per_mille(), Some(40));
assert_eq!(
S.window_cv2_per_mille(),
Some(40),
"wall time is all the window had"
);
assert_eq!(S.window_oncore_cv2_per_mille(), None);
assert_eq!(S.window_oncore_cv2_range_per_mille(), None);
assert_eq!(S.window_oncore_ticks(), 0);
}
#[test]
fn a_window_of_leaves_under_the_unit_has_a_mean_and_no_spread() {
static S: CallSiteState = CallSiteState::new();
let leaf = 200u64;
S.record_batch_site_only(16 * leaf, 0, 16, 0, 0);
assert_eq!(S.window_ticks(), 1);
assert_eq!(S.window_mean_ns(), Some(leaf));
assert_eq!(S.window_spread_ticks(), 0);
assert_eq!(S.window_cv2_per_mille(), None);
assert_eq!(S.window_cv2_range_per_mille(), None);
assert_eq!(S.window_wall_ticks(), 0);
assert_eq!(S.window_wall_cv2_per_mille(), None);
assert_eq!(S.window_wall_cv2_range_per_mille(), None);
assert_eq!(S.cv2_per_mille(), None);
assert!(S.leaves_under_spread_unit());
assert!(S.learned_class().is_some());
}
#[test]
fn items_under_a_nanosecond_have_no_per_item_spread_while_their_leaves_do() {
static S: CallSiteState = CallSiteState::new();
const ITEMS: u64 = 1024;
let leaf = 512u64;
let sq = |ns: u64| (ns >> 8).saturating_mul(ns >> 8);
S.record_batch_site_only(16 * leaf, 16 * sq(leaf), 16, 16 * ITEMS, 0);
assert_eq!(S.per_item_ns(), Some(0));
assert_eq!(S.per_item_cv2_per_mille(), None);
assert_eq!(S.window_cv2_per_mille(), None);
assert_eq!(S.window_spread_ticks(), 0);
assert_eq!(S.cv2_per_mille(), Some(0));
assert!(!S.leaves_under_spread_unit());
}
#[test]
fn a_window_with_no_spread_keeps_the_last_one_that_had_one() {
static S: CallSiteState = CallSiteState::new();
const ITEMS: u64 = 1024;
let (fast, slow) = (1280u64 * ITEMS, 1920u64 * ITEMS);
let sq = |ns: u64| (ns >> 8).saturating_mul(ns >> 8);
let per_item_sq =
|ns: u64| ((ns as u128).saturating_mul(ns as u128) / ((ITEMS as u128) << 16)) as u64;
S.record_batch_site_only(
8 * fast + 8 * slow,
8 * sq(fast) + 8 * sq(slow),
16,
16 * ITEMS,
8 * per_item_sq(fast) + 8 * per_item_sq(slow),
);
S.record_batch_site_only(16 * 200, 0, 16, 0, 0);
assert_eq!(S.window_ticks(), 2);
assert_eq!(S.window_spread_ticks(), 1);
assert_eq!(S.window_wall_ticks(), 1);
assert_eq!(S.window_mean_ns(), Some(200));
assert_eq!(S.window_cv2_per_mille(), Some(40));
assert_eq!(S.window_cv2_range_per_mille(), Some((40, 40)));
assert_eq!(S.window_wall_cv2_per_mille(), Some(40));
}
#[test]
fn caller_site_is_distinct_per_call_site_and_stable_per_site() {
let a = caller_site();
let b = caller_site();
assert_ne!(a, b, "distinct call sites must get distinct states");
let mut repeats = Vec::new();
for _ in 0..3 {
repeats.push(caller_site());
}
assert_eq!(repeats[0], repeats[1]);
assert_eq!(repeats[1], repeats[2]);
assert_ne!(repeats[0], a);
assert_ne!(repeats[0], b);
assert!(registry_len() >= 3, "registry materializes one state per site");
}
#[test]
fn fresh_site_is_unclassified() {
static S: CallSiteState = CallSiteState::new();
assert_eq!(S.learned_class(), None);
assert_eq!(S.cv2_per_mille(), None);
assert_eq!(S.leaf_count(), 0);
}
#[test]
fn a_reset_site_reads_as_a_fresh_one() {
static S: CallSiteState = CallSiteState::new();
S.record_seed_depth(3);
S.record_seed_depth(5);
assert_eq!(S.seed_depth_flips(), 1, "the site must have learned something first");
S.reset();
assert_eq!(S.seed_depth_flips(), 0);
assert_eq!(S.learned_class(), None);
assert_eq!(S.cv2_per_mille(), None);
assert_eq!(S.leaf_count(), 0);
S.record_seed_depth(9);
assert_eq!(S.seed_depth_flips(), 0, "the first depth after a reset flips nothing");
}
#[test]
fn the_registry_says_where_each_site_is() {
let mine = caller_site();
let sites = registered_sites();
let found = sites
.iter()
.find(|r| r.site == mine)
.expect("a site resolved through caller_site is in the registry");
assert!(
found.location.file().ends_with("call_site.rs"),
"the location is this file, not the binding's: {}",
found.location.file()
);
assert!(found.location.line() > 0);
}
#[test]
fn resetting_every_site_covers_the_ones_just_made() {
let mine = caller_site();
mine.get().record_seed_depth(2);
mine.get().record_seed_depth(7);
assert_eq!(mine.get().seed_depth_flips(), 1);
let keyed = site_for_key(0x5EED_0004);
keyed.get().record_seed_depth(2);
keyed.get().record_seed_depth(7);
assert_eq!(keyed.get().seed_depth_flips(), 1);
let swept = reset_all_sites();
assert!(swept >= 2, "the sweep counts the located and keyed sites it reset");
assert_eq!(mine.get().seed_depth_flips(), 0);
assert_eq!(keyed.get().seed_depth_flips(), 0);
}
#[test]
fn one_key_is_one_site_and_two_keys_are_two() {
let a = site_for_key(0x5EED_0001);
assert_eq!(site_for_key(0x5EED_0001), a, "a key resolves to the site it made");
assert_ne!(site_for_key(0x5EED_0002), a, "two keys learn apart");
}
#[test]
fn a_key_never_names_a_location_site() {
let here = caller_site();
let found = registered_sites()
.into_iter()
.find(|r| r.site == here)
.expect("a site resolved through caller_site is in the registry");
let keyed = site_for_key(location_key(found.location));
assert_ne!(keyed, here, "a key equal to a location's hash is a site of its own");
}
#[test]
fn the_registry_lists_each_keyed_site_by_its_key() {
let key = 0x5EED_0003;
let site = site_for_key(key);
let listed = registered_keyed_sites()
.into_iter()
.find(|r| r.key == key)
.expect("a keyed site is listed with its key");
assert_eq!(listed.site, site);
assert!(
registered_sites().iter().all(|r| r.site != site),
"a keyed site is not listed among the located ones"
);
}
#[test]
fn site_classifies_uniform_streaming_leaves() {
static S: CallSiteState = CallSiteState::new();
for _ in 0..4 {
let per = 1_000_000u64;
let scaled = per >> 8;
S.record_batch_site_only(per * 16, scaled * scaled * 16, 16, 0, 0);
}
assert_eq!(S.learned_class(), Some(WorkloadClass::Streaming));
}
#[test]
fn two_sites_classify_independently() {
static LIGHT: CallSiteState = CallSiteState::new();
static HEAVY: CallSiteState = CallSiteState::new();
for _ in 0..4 {
let l = 20u64; LIGHT.record_batch_site_only(l * 16, 0, 16, 0, 0);
let h = 1_000_000u64; let hs = h >> 8;
HEAVY.record_batch_site_only(h * 16, hs * hs * 16, 16, 0, 0);
}
assert_eq!(LIGHT.learned_class(), Some(WorkloadClass::FineGrain));
assert_eq!(HEAVY.learned_class(), Some(WorkloadClass::Streaming));
}
#[test]
fn cv2_reflects_site_spread() {
static UNIFORM: CallSiteState = CallSiteState::new();
static SPREAD: CallSiteState = CallSiteState::new();
let per = 10_000u64;
let scaled = per >> 8;
UNIFORM.record_batch_site_only(per * 8, scaled * scaled * 8, 8, 0, 0);
let a = 1_000u64;
let b = 100_000u64;
let asc = a >> 8;
let bsc = b >> 8;
SPREAD.record_batch_site_only(a * 4 + b * 4, asc * asc * 4 + bsc * bsc * 4, 8, 0, 0);
assert!(UNIFORM.cv2_per_mille().unwrap() < 20);
assert!(SPREAD.cv2_per_mille().unwrap() >= 500);
}
#[test]
fn a_seed_depth_change_needs_corroboration() {
static S: CallSiteState = CallSiteState::new();
assert_eq!(S.seeded_depth(), None, "a fresh site has seeded nothing");
assert_eq!(
S.stabilize_seed_depth(5),
5,
"the first dispatch takes the depth its estimate asks for"
);
assert_eq!(
S.stabilize_seed_depth(6),
5,
"one estimate the far side of a boundary does not move the depth"
);
assert_eq!(
S.stabilize_seed_depth(6),
6,
"a second consecutive call asking the same thing does"
);
assert_eq!(S.seeded_depth(), Some(6));
}
#[test]
fn a_run_toward_a_new_depth_restarts_when_a_third_value_intervenes() {
static S: CallSiteState = CallSiteState::new();
assert_eq!(S.stabilize_seed_depth(5), 5);
assert_eq!(S.stabilize_seed_depth(6), 5);
assert_eq!(
S.stabilize_seed_depth(7),
5,
"a different candidate breaks the run toward 6"
);
assert_eq!(
S.stabilize_seed_depth(6),
5,
"so 6 starts its run again rather than arriving already seconded"
);
assert_eq!(S.stabilize_seed_depth(6), 6);
}
#[test]
fn a_depth_the_site_already_holds_clears_a_pending_run() {
static S: CallSiteState = CallSiteState::new();
assert_eq!(S.stabilize_seed_depth(5), 5);
assert_eq!(S.stabilize_seed_depth(6), 5);
assert_eq!(
S.stabilize_seed_depth(5),
5,
"asking for what is already in force is not a change"
);
assert_eq!(
S.stabilize_seed_depth(6),
5,
"and it broke the run, so 6 needs two agreeing calls again"
);
assert_eq!(S.stabilize_seed_depth(6), 6);
}
#[test]
fn a_class_survives_the_same_work_split_into_different_leaf_sizes() {
static S: CallSiteState = CallSiteState::new();
const PER_ITEM_NS: u64 = 1_000;
let record = |items: u64, leaves: u64| {
let leaf_ns = PER_ITEM_NS * items;
let scaled = leaf_ns >> 8;
let sq = scaled.saturating_mul(scaled);
S.record_batch_site_only(
leaf_ns * leaves,
sq * leaves,
leaves,
items * leaves,
(sq / items) * leaves,
);
};
for _ in 0..8 {
record(1_024, 16);
}
let uniform = S.learned_class();
assert!(uniform.is_some(), "a site fed 128 leaves has classified");
for _ in 0..8 {
record(1, 8);
record(64, 4);
record(512, 4);
}
assert_eq!(
S.learned_class(),
uniform,
"the same work in leaves of 1 to 512 items must hold the class the 1024-item \
leaves produced; per-item cost never changed"
);
assert_eq!(
S.per_item_ns(),
Some(PER_ITEM_NS),
"per-item cost reads the same whatever the leaves came out at"
);
let per_item_cv2 = S.per_item_cv2_per_mille().expect("items were recorded");
let low = crate::sched::adaptive_profile::class_thresholds()
.cv2_low_per_mille
.load(Ordering::Relaxed);
assert!(
per_item_cv2 < low,
"per-item spread {per_item_cv2} must read as uniform, under {low}, on work whose \
per-item cost never changed"
);
}
#[test]
fn routing_arm_adopts_the_caller_plan_when_the_class_routing_is_slower() {
static S: CallSiteState = CallSiteState::new();
for _ in 0..4 {
S.record_routing_arm(PolicyArm::Default, 900_000);
S.record_routing_arm(PolicyArm::Alternative, 300_000);
}
let calls = 2 * ARM_TRIAL_CADENCE;
let mut caller_plan = 0;
let mut class_routing = 0;
for _ in 0..calls {
match S.choose_routing_arm() {
PolicyArm::Alternative => caller_plan += 1,
PolicyArm::Default => class_routing += 1,
}
}
assert!(
caller_plan > class_routing,
"the faster arm must win the routing: caller plan {caller_plan}, class routing \
{class_routing} over {calls} calls"
);
assert_eq!(
class_routing, 2,
"the slower arm runs once per cadence of {ARM_TRIAL_CADENCE} and no more often, \
so a routing that becomes the better one again is found without paying for it \
every dispatch"
);
let (default_ns, alternative_ns) = S.routing_ewmas();
assert!(
alternative_ns < default_ns,
"the arms report what they cost: class routing {default_ns} ns, caller plan \
{alternative_ns} ns"
);
}
#[test]
fn policy_arm_explores_then_adopts_faster_arm() {
static S: CallSiteState = CallSiteState::new();
for _ in 0..4 {
S.record_arm(PolicyArm::Default, 1_000_000);
S.record_arm(PolicyArm::Alternative, 100_000);
}
let mut alt = 0;
for _ in 0..12 {
if S.choose_arm(true) == PolicyArm::Alternative {
alt += 1;
}
}
assert!(alt >= 10, "faster arm must dominate; got {alt}/12");
assert_eq!(S.choose_arm(false), PolicyArm::Default);
}
#[test]
fn placement_races_cold_then_picks_faster_side() {
static S: CallSiteState = CallSiteState::new();
let batch = 4096u32;
assert_eq!(S.choose_placement(batch), Placement::Race);
S.record_placement(batch, Some(50_000), Some(5_000_000));
let mut cpu = 0;
for _ in 0..8 {
if S.choose_placement(batch) == Placement::Cpu {
cpu += 1;
}
}
assert!(cpu >= 7, "CPU side must dominate; got {cpu}/8");
assert_eq!(S.choose_placement(2), Placement::Race);
}
#[test]
fn split_share_tracks_throughput_ratio() {
static S: CallSiteState = CallSiteState::new();
assert_eq!(S.split_cpu_share_per_mille(), 500);
S.record_split(1000, 10_000, 1000, 30_000);
let share = S.split_cpu_share_per_mille();
assert!((700..=800).contains(&share), "share {share}");
}
#[test]
fn split_share_outgrows_a_cold_first_sample_within_eight() {
static S: CallSiteState = CallSiteState::new();
S.record_split(512, 512 * 32_000, 512, 512 * 18_000);
assert!(S.split_cpu_share_per_mille() < 400, "cold share {}", S.split_cpu_share_per_mille());
for _ in 0..7 {
S.record_split(500, 500 * 10_000, 500, 500 * 25_000);
}
let share = S.split_cpu_share_per_mille();
assert!((620..=700).contains(&share), "share {share}");
for _ in 0..8 {
S.record_split(500, 500 * 10_000, 500, 500 * 25_000);
}
assert!(S.split_cpu_share_per_mille() > share, "share {}", S.split_cpu_share_per_mille());
}
#[test]
fn site_ref_identity_semantics() {
static A: CallSiteState = CallSiteState::new();
static B: CallSiteState = CallSiteState::new();
assert_eq!(SiteRef::new(&A), SiteRef::new(&A));
assert_ne!(SiteRef::new(&A), SiteRef::new(&B));
}
}