1use core::ops::RangeInclusive;
28use core::time::Duration;
29
30use crate::strategy::DEFAULT_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)>,
182 ceiling: Option<Limit>,
183 floor: Option<Limit>,
184 window: u64,
185}
186
187impl AdaptiveLevel {
188 pub fn new(range: RangeInclusive<i32>, start: i32) -> Self {
198 let mut levels = [0; LADDER];
199 let mut len = 0;
200 for level in (-7..=4).filter(|level| *level != 0) {
201 if range.contains(&level)
202 || (level == -7 && range.contains(&-8))
203 || (level == DEFAULT_LEVEL && range.contains(&0))
204 {
205 levels[len] = level;
206 len += 1;
207 }
208 }
209 assert!(len > 0, "{range:?} holds no zrip level");
210 let index = levels[..len]
211 .iter()
212 .position(|level| *level >= start)
213 .unwrap_or(len - 1);
214
215 Self {
216 levels,
217 len,
218 samples: [None; LADDER],
219 index,
220 probe: None,
221 ceiling: None,
222 floor: None,
223 window: 0,
224 }
225 }
226
227 pub fn level(&self) -> i32 {
229 self.levels[self.index]
230 }
231
232 pub fn update(&mut self, stats: CompressStats, bottleneck: Option<Bottleneck>) -> i32 {
236 self.window += 1;
237 let Some(mut sample) = Sample::new(stats, self.window) else {
238 return self.level();
239 };
240 if let Some(older) = self.fresh(self.index) {
241 sample = sample.decay_into(older);
242 }
243 self.samples[self.index] = Some(sample);
244
245 if let Some((from, goal)) = self.probe.take()
246 && let Some(previous) = self.samples[from]
247 && !goal.kept(previous, sample, bottleneck)
248 {
249 self.set_limit(goal, from);
250 self.index = from;
251 return self.level();
252 }
253
254 let Some(goal) = bottleneck.map(Bottleneck::goal) else {
255 return self.level();
256 };
257 if let Some(next) = self.next(goal) {
258 self.probe = Some((self.index, goal));
259 self.index = next;
260 } else {
261 let settled = self.settle(goal);
262 if settled != self.index || self.limit(goal).is_none() {
263 self.set_limit(goal, settled);
264 }
265 self.index = settled;
266 }
267 self.level()
268 }
269
270 fn fresh(&self, index: usize) -> Option<Sample> {
271 self.samples[index].filter(|sample| self.window - sample.window < RETRY_WINDOWS)
272 }
273
274 fn limit(&self, goal: Goal) -> Option<Limit> {
275 let limit = match goal {
276 Goal::Ratio => self.ceiling,
277 Goal::Speed => self.floor,
278 };
279 limit.filter(|limit| self.window < limit.until)
280 }
281
282 fn set_limit(&mut self, goal: Goal, index: usize) {
283 let limit = Some(Limit {
284 index,
285 until: self.window + RETRY_WINDOWS,
286 });
287 match goal {
288 Goal::Ratio => self.ceiling = limit,
289 Goal::Speed => self.floor = limit,
290 }
291 }
292
293 fn next(&self, goal: Goal) -> Option<usize> {
294 let limit = self.limit(goal);
295 match goal {
296 Goal::Ratio => {
297 let next = self.index + 1;
298 let blocked = limit.is_some_and(|limit| next > limit.index);
299 (next < self.len && !blocked).then_some(next)
300 }
301 Goal::Speed => {
302 let next = self.index.checked_sub(1)?;
303 let blocked = limit.is_some_and(|limit| next < limit.index);
304 (!blocked).then_some(next)
305 }
306 }
307 }
308
309 fn settle(&self, goal: Goal) -> usize {
312 let limit = self.limit(goal);
313 let fresh = || {
314 (0..self.len)
315 .filter(move |index| match (goal, limit) {
316 (Goal::Ratio, Some(limit)) => *index <= limit.index,
317 (Goal::Speed, Some(limit)) => *index >= limit.index,
318 (_, None) => true,
319 })
320 .filter_map(|index| Some((index, self.fresh(index)?)))
321 };
322 let best = |better: fn(Sample, Sample) -> bool| {
323 fresh()
324 .map(|(_, sample)| sample)
325 .reduce(|best, sample| if better(sample, best) { sample } else { best })
326 };
327
328 let settled = match goal {
329 Goal::Ratio => best(Sample::denser).and_then(|densest| {
330 fresh().find(|(_, sample)| sample.ratio_within(densest, RATIO_TIE))
331 }),
332 Goal::Speed => best(Sample::faster).and_then(|fastest| {
333 fresh()
334 .filter(|(_, sample)| sample.speed_within(fastest, SPEED_TIE))
335 .reduce(|best, entry| if entry.1.denser(best.1) { entry } else { best })
336 }),
337 };
338 settled.map_or(self.index, |(index, _)| index)
339 }
340}
341
342#[cfg(test)]
343mod tests {
344 extern crate std;
345
346 use super::*;
347 use core::cell::Cell;
348 use std::vec::Vec;
349
350 const LEVELS: [i32; 11] = [-7, -6, -5, -4, -3, -2, -1, 1, 2, 3, 4];
351 const SPEED: [u64; 11] = [286, 298, 234, 226, 221, 225, 220, 197, 197, 154, 154];
354 const RATIO: [u64; 11] = [186, 255, 289, 285, 294, 322, 365, 351, 351, 336, 337];
355
356 struct Sender {
359 speed: [u64; 11],
360 ratio: [u64; 11],
361 output: Option<u64>,
362 input: Option<u64>,
363 jitter: u64,
365 windows: Cell<u64>,
366 }
367
368 impl Sender {
369 const fn cpu() -> Self {
370 Self {
371 speed: SPEED,
372 ratio: RATIO,
373 output: None,
374 input: None,
375 jitter: 0,
376 windows: Cell::new(0),
377 }
378 }
379
380 fn window(&self, level: i32) -> (CompressStats, Option<Bottleneck>) {
384 let index = LEVELS.iter().position(|l| *l == level).unwrap();
385 self.windows.set(self.windows.get() + 1);
386 let error = if self.windows.get().is_multiple_of(2) {
387 100 + self.jitter
388 } else {
389 100 - self.jitter
390 };
391 let speed = self.speed[index] * error / 100;
392 let ratio = self.ratio[index];
393
394 let cpu = speed * 100_000;
396 let output = self.output.map_or(u64::MAX, |output| output * 1000 * ratio);
397 let input = self.input.map_or(u64::MAX, |input| input * 100_000);
398 let plain = cpu.min(output).min(input);
399 let blocked_us = if output < cpu.min(input) {
400 100_000 - plain * 100_000 / cpu
401 } else {
402 0
403 };
404 let queued = input > plain;
405 let bottleneck = if blocked_us > 0 && blocked_us * 16 >= 100_000 {
406 Some(Bottleneck::Output)
407 } else if queued {
408 (blocked_us * 64 < 100_000).then_some(Bottleneck::Cpu)
409 } else {
410 Some(Bottleneck::Input)
411 };
412 let stats = CompressStats {
413 plain,
414 compressed: plain * 100 / ratio,
415 busy: Duration::from_micros(plain / speed),
416 };
417 (stats, bottleneck)
418 }
419
420 fn run(&self, adaptive: &mut AdaptiveLevel, windows: usize) -> Vec<i32> {
421 (0..windows)
422 .map(|_| {
423 let (stats, bottleneck) = self.window(adaptive.level());
424 adaptive.update(stats, bottleneck)
425 })
426 .collect()
427 }
428 }
429
430 fn settled(levels: &[i32], level: i32) -> bool {
431 levels.iter().all(|l| *l == level)
432 }
433
434 #[test]
435 fn ladder_skips_zero_and_runs_minus_eight_as_minus_seven() {
436 let adaptive = AdaptiveLevel::new(-8..=4, -1);
437 assert_eq!(&adaptive.levels[..adaptive.len], LEVELS);
438 assert_eq!(adaptive.level(), -1);
439 assert_eq!(AdaptiveLevel::new(1..=4, -1).level(), 1);
440 assert_eq!(AdaptiveLevel::new(-7..=-3, -1).level(), -3);
441 assert_eq!(AdaptiveLevel::new(0..=0, -1).level(), 1);
442 assert_eq!(AdaptiveLevel::new(-8..=-8, -1).level(), -7);
443 }
444
445 #[test]
446 #[should_panic(expected = "holds no zrip level")]
447 fn range_without_levels_panics() {
448 AdaptiveLevel::new(5..=9, 5);
449 }
450
451 #[test]
452 fn slow_output_climbs_across_dips_to_the_best_ratio() {
453 let sender = Sender {
454 output: Some(1),
455 ..Sender::cpu()
456 };
457 let mut adaptive = AdaptiveLevel::new(-7..=4, -7);
458 let levels = sender.run(&mut adaptive, 30);
459 assert_eq!(&levels[..8], &[-6, -5, -4, -3, -2, -1, 1, -1]);
461 assert!(settled(&levels[8..], -1), "{levels:?}");
462 }
463
464 #[test]
465 fn slow_output_climbs_to_the_top_when_it_compresses_best() {
466 let sender = Sender {
467 ratio: [186, 255, 289, 295, 300, 322, 365, 380, 390, 400, 410],
468 output: Some(1),
469 ..Sender::cpu()
470 };
471 let mut adaptive = AdaptiveLevel::new(-7..=4, -1);
472 let levels = sender.run(&mut adaptive, 30);
473 assert_eq!(&levels[..4], &[1, 2, 3, 4]);
474 assert!(settled(&levels[4..], 4), "{levels:?}");
475 }
476
477 #[test]
478 fn output_climb_stops_where_compression_falls_behind() {
479 let sender = Sender {
481 ratio: [186, 255, 289, 295, 300, 322, 365, 380, 380, 400, 410],
482 output: Some(45),
483 ..Sender::cpu()
484 };
485 let mut adaptive = AdaptiveLevel::new(-7..=4, -1);
486 let levels = sender.run(&mut adaptive, 30);
487 assert_eq!(&levels[..5], &[1, 2, 3, 2, 1]);
489 assert!(settled(&levels[5..], 1), "{levels:?}");
490 }
491
492 #[test]
493 fn fast_output_drops_to_the_fastest_level_that_fits() {
494 let sender = Sender {
496 output: Some(125),
497 ..Sender::cpu()
498 };
499 let mut adaptive = AdaptiveLevel::new(-7..=4, 4);
500 let levels = sender.run(&mut adaptive, 30);
501 assert_eq!(&levels[..11], &[3, 2, 1, -1, -2, -3, -4, -5, -6, -7, -6]);
502 assert!(settled(&levels[11..], -6), "{levels:?}");
503 }
504
505 #[test]
506 fn unlimited_output_prefers_the_denser_of_tied_fast_levels() {
507 let sender = Sender::cpu();
509 let mut adaptive = AdaptiveLevel::new(-7..=4, -1);
510 let levels = sender.run(&mut adaptive, 30);
511 assert_eq!(&levels[..7], &[-2, -3, -4, -5, -6, -7, -6]);
512 assert!(settled(&levels[7..], -6), "{levels:?}");
513 }
514
515 #[test]
516 fn measurement_noise_does_not_move_a_settled_level() {
517 for output in [None, Some(1), Some(125)] {
518 let sender = Sender {
519 output,
520 jitter: 4,
521 ..Sender::cpu()
522 };
523 let mut adaptive = AdaptiveLevel::new(-7..=4, -1);
524 let levels = sender.run(&mut adaptive, 30);
525 let last = levels[15];
526 assert!(settled(&levels[15..], last), "{output:?}: {levels:?}");
527 }
528 }
529
530 #[test]
531 fn idle_input_climbs_and_unclear_windows_hold() {
532 let sender = Sender {
533 input: Some(10),
534 ..Sender::cpu()
535 };
536 let mut adaptive = AdaptiveLevel::new(-3..=4, -3);
537 let levels = sender.run(&mut adaptive, 12);
538 assert_eq!(&levels[..4], &[-2, -1, 1, -1]);
539 assert!(settled(&levels[4..], -1), "{levels:?}");
540
541 let (stats, _) = Sender::cpu().window(-1);
542 assert_eq!(adaptive.update(stats, None), -1);
543 }
544
545 #[test]
546 fn limits_expire_and_the_walk_probes_again() {
547 let sender = Sender {
548 output: Some(1),
549 ..Sender::cpu()
550 };
551 let mut adaptive = AdaptiveLevel::new(-2..=1, -1);
552 let windows = 2 + usize::try_from(RETRY_WINDOWS).unwrap();
553 let levels = sender.run(&mut adaptive, windows);
554 assert_eq!(&levels[..2], &[1, -1]);
555 assert!(settled(&levels[2..windows - 1], -1), "{levels:?}");
556 assert_eq!(levels.last(), Some(&1));
557 }
558
559 #[test]
560 fn empty_windows_keep_the_level() {
561 let mut adaptive = AdaptiveLevel::new(-7..=4, -1);
562 assert_eq!(
563 adaptive.update(CompressStats::default(), Some(Bottleneck::Cpu)),
564 -1
565 );
566 let (stats, _) = Sender::cpu().window(-1);
567 assert_eq!(adaptive.update(stats, None), -1);
568 }
569
570 #[test]
571 fn stats_record_and_merge() {
572 let mut stats = CompressStats::default();
573 stats.record(100, 40, Duration::from_micros(3));
574 let mut other = CompressStats::default();
575 other.record(50, 30, Duration::from_micros(2));
576 stats.merge(other);
577 assert_eq!(
578 stats,
579 CompressStats {
580 plain: 150,
581 compressed: 70,
582 busy: Duration::from_micros(5),
583 }
584 );
585 }
586}