Skip to main content

zrip_encode/
adaptive.rs

1//! Compression level adaptation for a sender whose bottleneck moves.
2//!
3//! The caller compresses in windows, records each frame's work in
4//! [`CompressStats`], and names what limited the window, like C zstd's
5//! `--adapt`. A blocked output or idle input asks for ratio. Queued input
6//! with free output asks for compression speed. The level walks one step at
7//! a time toward the goal, crossing small dips, and reverts a step that
8//! clearly hurts. Neither ratio nor speed is monotonic in the level for every
9//! input, so a finished walk settles on the best recently measured level.
10//!
11//! Speed is input bytes per second spent compressing. End-to-end throughput
12//! varies too much between short windows to rank levels.
13//!
14//! ```
15//! use core::time::Duration;
16//! use zrip::adaptive::{AdaptiveLevel, Bottleneck, CompressStats};
17//!
18//! let mut adaptive = AdaptiveLevel::new(-7..=4, -1);
19//! let mut stats = CompressStats::default();
20//! // After each frame: input bytes, frame bytes, and time spent compressing.
21//! stats.record(64 * 1024, 20 * 1024, Duration::from_micros(300));
22//! // After each window of at least `MIN_WINDOW_BYTES` input:
23//! let level = adaptive.update(stats, Some(Bottleneck::Output));
24//! assert_eq!(level, 1);
25//! ```
26
27use core::ops::RangeInclusive;
28use core::time::Duration;
29
30use crate::strategy::{DEFAULT_LEVEL, MAX_LEVEL, MIN_LEVEL};
31
32/// Input a window should cover at least. Smaller windows rank levels by
33/// measurement noise.
34pub const MIN_WINDOW_BYTES: u64 = 256 * 1024;
35
36/// Distinct zrip levels: -7 to 4 without 0.
37const LADDER: usize = 11;
38/// Windows a limit holds and a measurement stays fresh.
39const RETRY_WINDOWS: u64 = 32;
40/// A step toward ratio may lose up to 2% of it to cross a dip.
41const RATIO_STEP: (u128, u128) = (102, 100);
42/// Ratios within 0.5% tie; the lower level wins.
43const RATIO_TIE: (u128, u128) = (1005, 1000);
44/// A step toward speed may lose up to 10% of it to cross a plateau.
45const SPEED_STEP: (u128, u128) = (90, 100);
46/// Speeds within 5% tie; the better ratio wins.
47const SPEED_TIE: (u128, u128) = (95, 100);
48
49/// Compression work done in one window.
50#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
51pub struct CompressStats {
52    /// Input bytes.
53    pub plain: u64,
54    /// Compressed bytes.
55    pub compressed: u64,
56    /// Time spent compressing, summed over threads.
57    pub busy: Duration,
58}
59
60impl CompressStats {
61    /// Adds one frame.
62    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    /// Adds work recorded elsewhere, such as on another thread.
69    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/// What limited the sender during one window.
77#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
78pub enum Bottleneck {
79    /// The output refused bytes. Compress harder.
80    Output,
81    /// Input waited while the output kept up. Compress faster.
82    Cpu,
83    /// Nothing waited. Spare time goes to ratio.
84    Input,
85}
86
87impl Bottleneck {
88    /// Blocked output or spare time asks for ratio; a busy CPU for speed.
89    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    /// A step fails when it clearly loses its goal, or when it moves the
105    /// bottleneck to the other side: CPU after a ratio step, output after a
106    /// speed step.
107    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/// Compression at one level, decayed by half per window at that level.
120#[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    /// Compressed bytes per input byte at most `num / den` times `other`'s.
149    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    /// Speed at least `num / den` times `other`'s.
154    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/// A finished walk blocks steps past `index` until window `until`.
168#[derive(Clone, Copy, Debug)]
169struct Limit {
170    index: usize,
171    until: u64,
172}
173
174/// Hill climb over the distinct zrip levels of one range.
175#[derive(Clone, Debug)]
176pub struct AdaptiveLevel {
177    levels: [i32; LADDER],
178    len: usize,
179    samples: [Option<Sample>; LADDER],
180    index: usize,
181    /// The step under test: the index it left, and its goal.
182    probe: Option<(usize, Goal)>,
183    /// Highest index a step toward ratio may reach while it holds.
184    ceiling: Option<Limit>,
185    /// Lowest index a step toward speed may reach while it holds.
186    floor: Option<Limit>,
187    /// Windows seen so far.
188    window: u64,
189}
190
191impl AdaptiveLevel {
192    /// Walks the distinct levels in `range`, starting at the first level not
193    /// below `start`, or at the highest. As in [`CompressContext`], level -8
194    /// runs as -7 and level 0 as the default level.
195    ///
196    /// # Panics
197    ///
198    /// If `range` holds no zrip level.
199    ///
200    /// [`CompressContext`]: crate::context::CompressContext
201    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    /// The level to compress at.
232    pub fn level(&self) -> i32 {
233        self.levels[self.index]
234    }
235
236    /// Records one window at the current level and returns the next level.
237    /// `bottleneck` is `None` when the window shows no clear one; the level
238    /// then holds, though a pending step can still be reverted.
239    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    /// The sample at `index`, if taken within the last `RETRY_WINDOWS`.
275    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    /// The next index toward `goal`, unless at the end of the ladder or past
299    /// its limit.
300    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    /// Best fresh level for `goal` within its limit: the lowest of the
317    /// densest levels for ratio, the densest of the fastest levels for speed.
318    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    // zrip on OMQ's benchmark corpus, 1 KiB messages in 32 KiB arenas:
359    // compression speed in MB/s and ratio in hundredths.
360    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    /// A sender compressing at `speed` MB/s per level, behind an optional
364    /// output of `output` MB/s, fed at an optional `input` MB/s.
365    struct Sender {
366        speed: [u64; 11],
367        ratio: [u64; 11],
368        output: Option<u64>,
369        input: Option<u64>,
370        /// Alternating speed error in percent.
371        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        /// One 100 ms window at `level`, with the bottleneck a transport
388        /// would report: output blocked for at least 1/16 of the window, or
389        /// input queued while output blocked under 1/64 of it, or no queue.
390        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            // Input bytes per window that the CPU, output, and input allow.
402            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        // -4 compresses 1.4% worse than -5; 1 compresses worse than -1.
467        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        // Ratio improves with every level, but 3 cannot fill a 45 MB/s output.
487        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        // 1 and 2 compress alike, so the lower level wins.
495        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        // 1 Gbps: -6 keeps up, -7 overflows the output.
502        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        // -7 compresses 4% slower than -6 and much worse.
515        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}