1use core::ops::RangeInclusive;
28use core::time::Duration;
29
30use crate::strategy::{DEFAULT_LEVEL, MAX_LEVEL, MIN_LEVEL};
31
32pub const MIN_WINDOW_BYTES: u64 = 256 * 1024;
35
36const LADDER: usize = 11;
38const RETRY_WINDOWS: u64 = 32;
40const RATIO_STEP: (u128, u128) = (102, 100);
42const RATIO_TIE: (u128, u128) = (1005, 1000);
44const SPEED_STEP: (u128, u128) = (90, 100);
46const SPEED_TIE: (u128, u128) = (95, 100);
48
49#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
51pub struct CompressStats {
52 pub plain: u64,
54 pub compressed: u64,
56 pub busy: Duration,
58}
59
60impl CompressStats {
61 pub fn record(&mut self, plain: usize, compressed: usize, busy: Duration) {
63 self.plain += plain as u64;
64 self.compressed += compressed as u64;
65 self.busy += busy;
66 }
67
68 pub fn merge(&mut self, other: Self) {
70 self.plain += other.plain;
71 self.compressed += other.compressed;
72 self.busy += other.busy;
73 }
74}
75
76#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
78pub enum Bottleneck {
79 Output,
81 Cpu,
83 Input,
85}
86
87impl Bottleneck {
88 fn goal(self) -> Goal {
90 match self {
91 Self::Output | Self::Input => Goal::Ratio,
92 Self::Cpu => Goal::Speed,
93 }
94 }
95}
96
97#[derive(Clone, Copy, Debug, PartialEq, Eq)]
98enum Goal {
99 Ratio,
100 Speed,
101}
102
103impl Goal {
104 fn kept(self, previous: Sample, current: Sample, bottleneck: Option<Bottleneck>) -> bool {
108 match self {
109 Self::Ratio => {
110 bottleneck != Some(Bottleneck::Cpu) && current.ratio_within(previous, RATIO_STEP)
111 }
112 Self::Speed => {
113 bottleneck != Some(Bottleneck::Output) && current.speed_within(previous, SPEED_STEP)
114 }
115 }
116 }
117}
118
119#[derive(Clone, Copy, Debug)]
121struct Sample {
122 plain: u128,
123 compressed: u128,
124 busy: u128,
125 window: u64,
126}
127
128impl Sample {
129 fn new(stats: CompressStats, window: u64) -> Option<Self> {
130 let busy = stats.busy.as_nanos();
131 (stats.plain > 0 && busy > 0).then(|| Self {
132 plain: u128::from(stats.plain),
133 compressed: u128::from(stats.compressed),
134 busy,
135 window,
136 })
137 }
138
139 fn decay_into(self, older: Self) -> Self {
140 Self {
141 plain: older.plain / 2 + self.plain,
142 compressed: older.compressed / 2 + self.compressed,
143 busy: older.busy / 2 + self.busy,
144 window: self.window,
145 }
146 }
147
148 fn ratio_within(self, other: Self, (num, den): (u128, u128)) -> bool {
150 self.compressed * other.plain * den <= other.compressed * self.plain * num
151 }
152
153 fn speed_within(self, other: Self, (num, den): (u128, u128)) -> bool {
155 self.plain * other.busy * den >= other.plain * self.busy * num
156 }
157
158 fn denser(self, other: Self) -> bool {
159 self.compressed * other.plain < other.compressed * self.plain
160 }
161
162 fn faster(self, other: Self) -> bool {
163 self.plain * other.busy > other.plain * self.busy
164 }
165}
166
167#[derive(Clone, Copy, Debug)]
169struct Limit {
170 index: usize,
171 until: u64,
172}
173
174#[derive(Clone, Debug)]
176pub struct AdaptiveLevel {
177 levels: [i32; LADDER],
178 len: usize,
179 samples: [Option<Sample>; LADDER],
180 index: usize,
181 probe: Option<(usize, Goal)>,
183 ceiling: Option<Limit>,
185 floor: Option<Limit>,
187 window: u64,
189}
190
191impl AdaptiveLevel {
192 pub fn new(range: RangeInclusive<i32>, start: i32) -> Self {
202 let mut levels = [0; LADDER];
203 let mut len = 0;
204 for level in (MIN_LEVEL..=MAX_LEVEL).filter(|level| *level != 0) {
205 if range.contains(&level)
206 || (level == MIN_LEVEL && range.contains(&-8))
207 || (level == DEFAULT_LEVEL && range.contains(&0))
208 {
209 levels[len] = level;
210 len += 1;
211 }
212 }
213 assert!(len > 0, "{range:?} holds no zrip level");
214 let index = levels[..len]
215 .iter()
216 .position(|level| *level >= start)
217 .unwrap_or(len - 1);
218
219 Self {
220 levels,
221 len,
222 samples: [None; LADDER],
223 index,
224 probe: None,
225 ceiling: None,
226 floor: None,
227 window: 0,
228 }
229 }
230
231 pub fn level(&self) -> i32 {
233 self.levels[self.index]
234 }
235
236 pub fn update(&mut self, stats: CompressStats, bottleneck: Option<Bottleneck>) -> i32 {
240 self.window += 1;
241 let Some(mut sample) = Sample::new(stats, self.window) else {
242 return self.level();
243 };
244 if let Some(older) = self.fresh(self.index) {
245 sample = sample.decay_into(older);
246 }
247 self.samples[self.index] = Some(sample);
248
249 if let Some((from, goal)) = self.probe.take()
250 && let Some(previous) = self.samples[from]
251 && !goal.kept(previous, sample, bottleneck)
252 {
253 self.set_limit(goal, from);
254 self.index = from;
255 return self.level();
256 }
257
258 let Some(goal) = bottleneck.map(Bottleneck::goal) else {
259 return self.level();
260 };
261 if let Some(next) = self.next(goal) {
262 self.probe = Some((self.index, goal));
263 self.index = next;
264 } else {
265 let settled = self.settle(goal);
266 if settled != self.index || self.limit(goal).is_none() {
267 self.set_limit(goal, settled);
268 }
269 self.index = settled;
270 }
271 self.level()
272 }
273
274 fn fresh(&self, index: usize) -> Option<Sample> {
276 self.samples[index].filter(|sample| self.window - sample.window < RETRY_WINDOWS)
277 }
278
279 fn limit(&self, goal: Goal) -> Option<Limit> {
280 let limit = match goal {
281 Goal::Ratio => self.ceiling,
282 Goal::Speed => self.floor,
283 };
284 limit.filter(|limit| self.window < limit.until)
285 }
286
287 fn set_limit(&mut self, goal: Goal, index: usize) {
288 let limit = Some(Limit {
289 index,
290 until: self.window + RETRY_WINDOWS,
291 });
292 match goal {
293 Goal::Ratio => self.ceiling = limit,
294 Goal::Speed => self.floor = limit,
295 }
296 }
297
298 fn next(&self, goal: Goal) -> Option<usize> {
301 let limit = self.limit(goal);
302 match goal {
303 Goal::Ratio => {
304 let next = self.index + 1;
305 let blocked = limit.is_some_and(|limit| next > limit.index);
306 (next < self.len && !blocked).then_some(next)
307 }
308 Goal::Speed => {
309 let next = self.index.checked_sub(1)?;
310 let blocked = limit.is_some_and(|limit| next < limit.index);
311 (!blocked).then_some(next)
312 }
313 }
314 }
315
316 fn settle(&self, goal: Goal) -> usize {
319 let limit = self.limit(goal);
320 let fresh = || {
321 (0..self.len)
322 .filter(move |index| match (goal, limit) {
323 (Goal::Ratio, Some(limit)) => *index <= limit.index,
324 (Goal::Speed, Some(limit)) => *index >= limit.index,
325 (_, None) => true,
326 })
327 .filter_map(|index| Some((index, self.fresh(index)?)))
328 };
329 let best = |better: fn(Sample, Sample) -> bool| {
330 fresh()
331 .map(|(_, sample)| sample)
332 .reduce(|best, sample| if better(sample, best) { sample } else { best })
333 };
334
335 let settled = match goal {
336 Goal::Ratio => best(Sample::denser).and_then(|densest| {
337 fresh().find(|(_, sample)| sample.ratio_within(densest, RATIO_TIE))
338 }),
339 Goal::Speed => best(Sample::faster).and_then(|fastest| {
340 fresh()
341 .filter(|(_, sample)| sample.speed_within(fastest, SPEED_TIE))
342 .reduce(|best, entry| if entry.1.denser(best.1) { entry } else { best })
343 }),
344 };
345 settled.map_or(self.index, |(index, _)| index)
346 }
347}
348
349#[cfg(test)]
350mod tests {
351 extern crate std;
352
353 use super::*;
354 use core::cell::Cell;
355 use std::vec::Vec;
356
357 const LEVELS: [i32; 11] = [-7, -6, -5, -4, -3, -2, -1, 1, 2, 3, 4];
358 const SPEED: [u64; 11] = [286, 298, 234, 226, 221, 225, 220, 197, 197, 154, 154];
361 const RATIO: [u64; 11] = [186, 255, 289, 285, 294, 322, 365, 351, 351, 336, 337];
362
363 struct Sender {
366 speed: [u64; 11],
367 ratio: [u64; 11],
368 output: Option<u64>,
369 input: Option<u64>,
370 jitter: u64,
372 windows: Cell<u64>,
373 }
374
375 impl Sender {
376 const fn cpu() -> Self {
377 Self {
378 speed: SPEED,
379 ratio: RATIO,
380 output: None,
381 input: None,
382 jitter: 0,
383 windows: Cell::new(0),
384 }
385 }
386
387 fn window(&self, level: i32) -> (CompressStats, Option<Bottleneck>) {
391 let index = LEVELS.iter().position(|l| *l == level).unwrap();
392 self.windows.set(self.windows.get() + 1);
393 let error = if self.windows.get().is_multiple_of(2) {
394 100 + self.jitter
395 } else {
396 100 - self.jitter
397 };
398 let speed = self.speed[index] * error / 100;
399 let ratio = self.ratio[index];
400
401 let cpu = speed * 100_000;
403 let output = self.output.map_or(u64::MAX, |output| output * 1000 * ratio);
404 let input = self.input.map_or(u64::MAX, |input| input * 100_000);
405 let plain = cpu.min(output).min(input);
406 let blocked_us = if output < cpu.min(input) {
407 100_000 - plain * 100_000 / cpu
408 } else {
409 0
410 };
411 let queued = input > plain;
412 let bottleneck = if blocked_us > 0 && blocked_us * 16 >= 100_000 {
413 Some(Bottleneck::Output)
414 } else if queued {
415 (blocked_us * 64 < 100_000).then_some(Bottleneck::Cpu)
416 } else {
417 Some(Bottleneck::Input)
418 };
419 let stats = CompressStats {
420 plain,
421 compressed: plain * 100 / ratio,
422 busy: Duration::from_micros(plain / speed),
423 };
424 (stats, bottleneck)
425 }
426
427 fn run(&self, adaptive: &mut AdaptiveLevel, windows: usize) -> Vec<i32> {
428 (0..windows)
429 .map(|_| {
430 let (stats, bottleneck) = self.window(adaptive.level());
431 adaptive.update(stats, bottleneck)
432 })
433 .collect()
434 }
435 }
436
437 fn settled(levels: &[i32], level: i32) -> bool {
438 levels.iter().all(|l| *l == level)
439 }
440
441 #[test]
442 fn ladder_skips_zero_and_runs_minus_eight_as_minus_seven() {
443 let adaptive = AdaptiveLevel::new(-8..=4, -1);
444 assert_eq!(&adaptive.levels[..adaptive.len], LEVELS);
445 assert_eq!(adaptive.level(), -1);
446 assert_eq!(AdaptiveLevel::new(1..=4, -1).level(), 1);
447 assert_eq!(AdaptiveLevel::new(-7..=-3, -1).level(), -3);
448 assert_eq!(AdaptiveLevel::new(0..=0, -1).level(), 1);
449 assert_eq!(AdaptiveLevel::new(-8..=-8, -1).level(), -7);
450 }
451
452 #[test]
453 #[should_panic(expected = "holds no zrip level")]
454 fn range_without_levels_panics() {
455 AdaptiveLevel::new(5..=9, 5);
456 }
457
458 #[test]
459 fn slow_output_climbs_across_dips_to_the_best_ratio() {
460 let sender = Sender {
461 output: Some(1),
462 ..Sender::cpu()
463 };
464 let mut adaptive = AdaptiveLevel::new(-7..=4, -7);
465 let levels = sender.run(&mut adaptive, 30);
466 assert_eq!(&levels[..8], &[-6, -5, -4, -3, -2, -1, 1, -1]);
468 assert!(settled(&levels[8..], -1), "{levels:?}");
469 }
470
471 #[test]
472 fn slow_output_climbs_to_the_top_when_it_compresses_best() {
473 let sender = Sender {
474 ratio: [186, 255, 289, 295, 300, 322, 365, 380, 390, 400, 410],
475 output: Some(1),
476 ..Sender::cpu()
477 };
478 let mut adaptive = AdaptiveLevel::new(-7..=4, -1);
479 let levels = sender.run(&mut adaptive, 30);
480 assert_eq!(&levels[..4], &[1, 2, 3, 4]);
481 assert!(settled(&levels[4..], 4), "{levels:?}");
482 }
483
484 #[test]
485 fn output_climb_stops_where_compression_falls_behind() {
486 let sender = Sender {
488 ratio: [186, 255, 289, 295, 300, 322, 365, 380, 380, 400, 410],
489 output: Some(45),
490 ..Sender::cpu()
491 };
492 let mut adaptive = AdaptiveLevel::new(-7..=4, -1);
493 let levels = sender.run(&mut adaptive, 30);
494 assert_eq!(&levels[..5], &[1, 2, 3, 2, 1]);
496 assert!(settled(&levels[5..], 1), "{levels:?}");
497 }
498
499 #[test]
500 fn fast_output_drops_to_the_fastest_level_that_fits() {
501 let sender = Sender {
503 output: Some(125),
504 ..Sender::cpu()
505 };
506 let mut adaptive = AdaptiveLevel::new(-7..=4, 4);
507 let levels = sender.run(&mut adaptive, 30);
508 assert_eq!(&levels[..11], &[3, 2, 1, -1, -2, -3, -4, -5, -6, -7, -6]);
509 assert!(settled(&levels[11..], -6), "{levels:?}");
510 }
511
512 #[test]
513 fn unlimited_output_prefers_the_denser_of_tied_fast_levels() {
514 let sender = Sender::cpu();
516 let mut adaptive = AdaptiveLevel::new(-7..=4, -1);
517 let levels = sender.run(&mut adaptive, 30);
518 assert_eq!(&levels[..7], &[-2, -3, -4, -5, -6, -7, -6]);
519 assert!(settled(&levels[7..], -6), "{levels:?}");
520 }
521
522 #[test]
523 fn measurement_noise_does_not_move_a_settled_level() {
524 for output in [None, Some(1), Some(125)] {
525 let sender = Sender {
526 output,
527 jitter: 4,
528 ..Sender::cpu()
529 };
530 let mut adaptive = AdaptiveLevel::new(-7..=4, -1);
531 let levels = sender.run(&mut adaptive, 30);
532 let last = levels[15];
533 assert!(settled(&levels[15..], last), "{output:?}: {levels:?}");
534 }
535 }
536
537 #[test]
538 fn idle_input_climbs_and_unclear_windows_hold() {
539 let sender = Sender {
540 input: Some(10),
541 ..Sender::cpu()
542 };
543 let mut adaptive = AdaptiveLevel::new(-3..=4, -3);
544 let levels = sender.run(&mut adaptive, 12);
545 assert_eq!(&levels[..4], &[-2, -1, 1, -1]);
546 assert!(settled(&levels[4..], -1), "{levels:?}");
547
548 let (stats, _) = Sender::cpu().window(-1);
549 assert_eq!(adaptive.update(stats, None), -1);
550 }
551
552 #[test]
553 fn limits_expire_and_the_walk_probes_again() {
554 let sender = Sender {
555 output: Some(1),
556 ..Sender::cpu()
557 };
558 let mut adaptive = AdaptiveLevel::new(-2..=1, -1);
559 let windows = 2 + usize::try_from(RETRY_WINDOWS).unwrap();
560 let levels = sender.run(&mut adaptive, windows);
561 assert_eq!(&levels[..2], &[1, -1]);
562 assert!(settled(&levels[2..windows - 1], -1), "{levels:?}");
563 assert_eq!(levels.last(), Some(&1));
564 }
565
566 #[test]
567 fn empty_windows_keep_the_level() {
568 let mut adaptive = AdaptiveLevel::new(-7..=4, -1);
569 assert_eq!(
570 adaptive.update(CompressStats::default(), Some(Bottleneck::Cpu)),
571 -1
572 );
573 let (stats, _) = Sender::cpu().window(-1);
574 assert_eq!(adaptive.update(stats, None), -1);
575 }
576
577 #[test]
578 fn stats_record_and_merge() {
579 let mut stats = CompressStats::default();
580 stats.record(100, 40, Duration::from_micros(3));
581 let mut other = CompressStats::default();
582 other.record(50, 30, Duration::from_micros(2));
583 stats.merge(other);
584 assert_eq!(
585 stats,
586 CompressStats {
587 plain: 150,
588 compressed: 70,
589 busy: Duration::from_micros(5),
590 }
591 );
592 }
593}