use std::num::NonZeroU32;
use super::Frontier;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Imbalance {
pub per_mille: u32,
pub over_generations: u32,
}
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct PlanInputs {
pub width: u32,
pub barrier_ns: f64,
pub rebalance_fixed_ns: f64,
pub copy_ns_per_id: f64,
pub pending_ids: f64,
pub generation_ns: f64,
pub imbalance: Option<Imbalance>,
}
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Plan {
pub frontier: Frontier,
pub cost_per_generation_ns: f64,
pub global_cost_ns: f64,
}
fn growth(imbalance: Imbalance) -> f64 {
let r = (f64::from(imbalance.per_mille) / 1000.0).max(1.0);
let n = f64::from(imbalance.over_generations.max(1));
r.powf(1.0 / n)
}
fn partition_cost(inputs: &PlanInputs, g: f64, n: f64) -> f64 {
let rebalance = inputs.rebalance_fixed_ns + inputs.copy_ns_per_id * inputs.pending_ids;
let r = g.powf(n).min(f64::from(inputs.width.max(1)));
rebalance / n + inputs.generation_ns * (1.0 - 1.0 / r) / 2.0
}
pub fn plan(inputs: &PlanInputs) -> Plan {
let global_cost_ns = inputs.barrier_ns;
let global = Plan {
frontier: Frontier::Global,
cost_per_generation_ns: global_cost_ns,
global_cost_ns,
};
let Some(imbalance) = inputs.imbalance else {
return global;
};
let width = f64::from(inputs.width.max(1));
if inputs.width <= 1 {
return Plan {
frontier: Frontier::Partition { rebalance_every: None },
cost_per_generation_ns: 0.0,
global_cost_ns,
};
}
let g = growth(imbalance);
let never_cost = if g <= 1.0 {
0.0
} else {
inputs.generation_ns * (1.0 - 1.0 / width) / 2.0
};
let mut best = Plan {
frontier: Frontier::Partition { rebalance_every: None },
cost_per_generation_ns: never_cost,
global_cost_ns,
};
if g > 1.0 {
let reach = (width.ln() / g.ln()).max(1.0);
let (mut lo, mut hi) = (1.0f64, reach);
for _step in 0..100 {
let a = lo + (hi - lo) / 3.0;
let b = hi - (hi - lo) / 3.0;
if partition_cost(inputs, g, a) <= partition_cost(inputs, g, b) {
hi = b;
} else {
lo = a;
}
}
let center = (lo + hi) / 2.0;
for n in [center.floor(), center.ceil(), 1.0, reach.floor().max(1.0)] {
if n < 1.0 || n > f64::from(u32::MAX) {
continue;
}
let cost = partition_cost(inputs, g, n);
if cost < best.cost_per_generation_ns {
best = Plan {
frontier: Frontier::Partition { rebalance_every: NonZeroU32::new(n as u32) },
cost_per_generation_ns: cost,
global_cost_ns,
};
}
}
}
if best.frontier == (Frontier::Partition { rebalance_every: NonZeroU32::new(1) }) {
return global;
}
if best.cost_per_generation_ns < global_cost_ns { best } else { global }
}
#[cfg(test)]
mod tests {
use super::*;
fn inputs(barrier_ns: f64, generation_ns: f64, imbalance: Option<Imbalance>) -> PlanInputs {
PlanInputs {
width: 32,
barrier_ns,
rebalance_fixed_ns: 2.0 * barrier_ns,
copy_ns_per_id: 2.0,
pending_ids: 10_000.0,
generation_ns,
imbalance,
}
}
#[test]
fn with_nothing_observed_the_plan_is_a_global_frontier() {
let p = plan(&inputs(500.0, 250_000.0, None));
assert_eq!(p.frontier, Frontier::Global);
}
#[test]
fn a_program_that_never_diverges_never_rebalances() {
let balanced = Imbalance { per_mille: 1000, over_generations: 4 };
let p = plan(&inputs(500.0, 250_000.0, Some(balanced)));
assert_eq!(p.frontier, Frontier::Partition { rebalance_every: None });
assert_eq!(p.cost_per_generation_ns, 0.0);
}
#[test]
fn a_cheap_barrier_against_fast_divergence_keeps_a_global_frontier() {
let fast = Imbalance { per_mille: 2000, over_generations: 1 };
let p = plan(&inputs(2_000.0, 250_000.0, Some(fast)));
assert_eq!(p.frontier, Frontier::Global, "{p:?}");
}
#[test]
fn an_expensive_barrier_against_slow_divergence_rebalances_at_an_interval() {
let slow = Imbalance { per_mille: 1100, over_generations: 10 };
let p = plan(&inputs(200_000.0, 250_000.0, Some(slow)));
let Frontier::Partition { rebalance_every: Some(n) } = p.frontier else {
panic!("expected a finite rebalance interval, got {p:?}");
};
assert!(n.get() > 1, "{p:?}");
assert!(p.cost_per_generation_ns < p.global_cost_ns);
let g = growth(slow);
let at = |k: f64| partition_cost(&inputs(200_000.0, 250_000.0, Some(slow)), g, k);
let chosen = at(f64::from(n.get()));
assert!(chosen <= at(1.0), "the interval chosen is no worse than every generation");
}
#[test]
fn an_interval_of_one_generation_is_a_global_frontier() {
let doubling = Imbalance { per_mille: 2000, over_generations: 1 };
let mut every = inputs(1_000_000.0, 250_000.0, Some(doubling));
every.rebalance_fixed_ns = 1.0;
every.copy_ns_per_id = 0.0;
let g = growth(doubling);
assert!(
partition_cost(&every, g, 1.0) < partition_cost(&every, g, 2.0),
"these inputs price rebalancing every generation cheapest"
);
assert_eq!(plan(&every).frontier, Frontier::Global);
}
#[test]
fn a_single_block_has_nothing_to_rebalance() {
let mut one = inputs(500.0, 250_000.0, Some(Imbalance { per_mille: 3000, over_generations: 1 }));
one.width = 1;
assert_eq!(plan(&one).frontier, Frontier::Partition { rebalance_every: None });
}
}