pub(crate) const FLOOR: u64 = 1;
const PROBE_EVERY: u64 = 8;
const RISE_AFTER: u32 = 3;
const RISE_PCT: u64 = 125;
const HALVE_PCT: u64 = 140;
fn over(p99: u64, of: u64, pct: u64) -> bool {
u128::from(p99) * 100 > u128::from(of) * u128::from(pct)
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) struct Tuner {
budget: u64,
ceiling: u64,
closed: u64,
floor: Option<u64>,
streak: u32,
at_floor: bool,
}
impl Tuner {
pub(crate) fn new(ceiling: u64) -> Self {
Self {
budget: FLOOR,
ceiling: ceiling.max(FLOOR),
closed: 0,
floor: None,
streak: 0,
at_floor: true,
}
}
pub(crate) fn current(&self) -> u64 {
if self.at_floor { FLOOR } else { self.budget }
}
pub(crate) fn budget(&self) -> u64 {
self.budget
}
pub(crate) fn at_floor(&self) -> bool {
self.at_floor
}
pub(crate) fn floor_p99(&self) -> Option<u64> {
self.floor
}
pub(crate) fn lower_ceiling(&mut self, ceiling: u64) {
self.ceiling = self.ceiling.min(ceiling.max(FLOOR));
self.budget = self.budget.min(self.ceiling);
}
pub(crate) fn close(&mut self, p99: u64) -> u64 {
let mut reprobe = false;
match (self.at_floor, self.floor) {
(true, prev) => {
reprobe = prev.is_some_and(|f| over(p99, f, RISE_PCT));
self.floor = Some(p99);
}
(false, Some(f)) => {
if over(p99, f, HALVE_PCT) {
self.budget = (self.budget / 2).max(FLOOR);
self.streak = 0;
reprobe = true;
} else if over(p99, f, RISE_PCT) {
self.streak = 0;
} else {
self.streak += 1;
if self.streak >= RISE_AFTER {
self.budget = (self.budget + 1).min(self.ceiling);
self.streak = 0;
}
}
}
(false, None) => reprobe = true,
}
self.closed += 1;
self.at_floor = reprobe || self.closed % PROBE_EVERY == 0;
self.current()
}
}
#[cfg(test)]
mod tests {
use super::*;
fn run(t: &mut Tuner, p99s: &[u64]) -> Vec<u64> {
p99s.iter().map(|&p| t.close(p)).collect()
}
fn good(t: &mut Tuner, n: usize) {
for _ in 0..n {
let _ = t.close(1000);
}
}
#[test]
fn test_the_first_window_runs_at_the_floor() {
let t = Tuner::new(8);
assert!(t.at_floor());
assert_eq!(
(t.current(), t.budget(), t.floor_p99()),
(FLOOR, FLOOR, None)
);
}
#[test]
fn test_three_windows_within_the_rise_line_raise_the_budget_by_one() {
let mut t = Tuner::new(8);
assert_eq!(t.close(1000), 1, "window 1, the floor, closes");
assert!(!t.at_floor(), "window 2 runs at the budget");
assert_eq!(run(&mut t, &[1000, 1250]), [1, 1]);
assert_eq!(t.close(1100), 2, "window 4, the third within the line");
assert_eq!(run(&mut t, &[1000, 1000]), [2, 2]);
assert_eq!(t.close(1000), 3, "window 7");
}
#[test]
fn test_a_window_between_the_lines_holds_the_budget_and_restarts_the_count() {
let mut t = Tuner::new(8);
let _ = t.close(1000);
assert_eq!(run(&mut t, &[1000, 1000, 1251]), [1, 1, 1]);
assert_eq!(run(&mut t, &[1000, 1000]), [1, 1]);
assert_eq!(t.close(1000), 2, "window 7, the third since window 4");
assert_eq!(t.close(1400), FLOOR);
assert!(t.at_floor());
assert_eq!(t.budget(), 2, "held, not halved");
}
#[test]
fn test_a_window_over_the_halving_line_halves_at_once_and_reprobes_the_floor() {
let mut t = Tuner::new(8);
let _ = t.close(1000);
good(&mut t, 10);
assert_eq!((t.budget(), t.at_floor()), (4, false), "{t:?}");
assert_eq!(
t.close(1401),
FLOOR,
"window 12 over 1.4x: window 13 at the floor"
);
assert!(t.at_floor());
assert_eq!(t.budget(), 2);
assert_eq!(t.close(1000), 2);
}
#[test]
fn test_an_odd_budget_halves_down() {
let mut t = Tuner::new(8);
let _ = t.close(1000);
good(&mut t, 13);
assert_eq!((t.budget(), t.at_floor()), (5, false), "{t:?}");
let _ = t.close(1500);
assert_eq!(t.budget(), 2);
}
#[test]
fn test_a_halving_restarts_the_count_toward_a_rise() {
let mut t = Tuner::new(8);
let _ = t.close(1000);
assert_eq!(run(&mut t, &[1000, 1000, 1000]), [1, 1, 2]);
assert_eq!(run(&mut t, &[1000, 1000]), [2, 2]);
assert_eq!(t.close(1500), FLOOR);
assert_eq!(t.budget(), 1);
assert_eq!(t.close(1000), FLOOR);
assert!(t.at_floor());
assert_eq!(t.close(1000), 1, "the probe closes");
assert_eq!(run(&mut t, &[1000, 1000]), [1, 1]);
assert_eq!(t.close(1000), 2, "window 12, the third since the halving");
}
#[test]
fn test_a_count_toward_a_rise_carries_across_a_probe() {
let mut t = Tuner::new(8);
let _ = t.close(1000);
good(&mut t, 7);
assert_eq!((t.budget(), t.at_floor()), (3, true), "window 9 is a probe");
assert_eq!(t.close(1000), 3, "the probe closes");
assert_eq!(t.close(1000), 3, "window 10: two toward the rise");
assert_eq!(t.close(1000), 4, "window 11: three (window 8 counted)");
}
#[test]
fn test_a_slow_floor_window_is_measured_again_and_never_halves() {
let mut t = Tuner::new(8);
let _ = t.close(1000);
good(&mut t, 7);
assert!(t.at_floor(), "window 9: a probe");
assert_eq!(t.close(1500), FLOOR);
assert!(t.at_floor());
assert_eq!((t.budget(), t.floor_p99()), (3, Some(1500)));
assert_eq!(t.close(1000), 3);
assert_eq!(t.floor_p99(), Some(1000));
let mut u = Tuner::new(8);
let _ = u.close(1000);
good(&mut u, 7);
assert_eq!(u.close(1250), u.budget());
assert!(!u.at_floor());
}
#[test]
fn test_windows_are_judged_against_the_latest_floor() {
let mut t = Tuner::new(8);
let _ = t.close(2000);
assert_eq!(
run(&mut t, &[2400, 2400, 2400, 2400, 2400, 2400]),
[1, 1, 2, 2, 2, 3]
);
let _ = t.close(2400);
assert!(t.at_floor(), "window 9: a probe");
assert_eq!(t.close(1000), 3);
assert_eq!(t.close(2400), FLOOR, "window 10 halves");
assert_eq!(t.budget(), 1);
}
#[test]
fn test_every_eighth_window_runs_at_the_floor() {
let mut t = Tuner::new(8);
for closed in 1..=24u64 {
let _ = t.close(1000);
let next = closed + 1;
assert_eq!(t.at_floor(), next % 8 == 1, "window {next}");
}
}
#[test]
fn test_the_budget_never_halves_below_the_floor_nor_rises_past_its_ceiling() {
let mut t = Tuner::new(2);
let _ = t.close(1000);
assert_eq!(t.close(5000), FLOOR);
assert!(t.at_floor(), "a halving at the floor still re-measures it");
assert_eq!(t.budget(), FLOOR);
good(&mut t, 21);
assert_eq!(t.budget(), 2);
assert_eq!(
Tuner::new(0).current(),
FLOOR,
"a ceiling of 0 is the floor"
);
let mut z = Tuner::new(0);
good(&mut z, 11);
assert_eq!(z.budget(), FLOOR);
}
#[test]
fn test_a_lowered_ceiling_takes_the_budget_down_and_is_never_raised() {
let mut t = Tuner::new(8);
let _ = t.close(1000);
good(&mut t, 6);
assert_eq!(t.budget(), 3);
t.lower_ceiling(2);
assert_eq!(t.budget(), 2);
t.lower_ceiling(5);
good(&mut t, 20);
assert_eq!(t.budget(), 2, "the ceiling stays the lowest asked for");
t.lower_ceiling(0);
assert_eq!(t.budget(), FLOOR);
}
#[test]
fn test_over_compares_exactly_and_never_overflows() {
assert!(!over(1250, 1000, 125));
assert!(over(1251, 1000, 125));
assert!(!over(1400, 1000, 140));
assert!(over(1401, 1000, 140));
assert!(over(u64::MAX, u64::MAX / 2, 140));
assert!(!over(u64::MAX, u64::MAX, 125));
}
}