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;
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    probe: Option<(usize, Goal)>,
182    ceiling: Option<Limit>,
183    floor: Option<Limit>,
184    window: u64,
185}
186
187impl AdaptiveLevel {
188    /// Walks the distinct levels in `range`, starting at the first level not
189    /// below `start`, or at the highest. As in [`CompressContext`], level -8
190    /// runs as -7 and level 0 as the default level.
191    ///
192    /// # Panics
193    ///
194    /// If `range` holds no zrip level.
195    ///
196    /// [`CompressContext`]: crate::context::CompressContext
197    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    /// The level to compress at.
228    pub fn level(&self) -> i32 {
229        self.levels[self.index]
230    }
231
232    /// Records one window at the current level and returns the next level.
233    /// `bottleneck` is `None` when the window shows no clear one; the level
234    /// then holds, though a pending step can still be reverted.
235    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    /// Best fresh level for `goal` within its limit: the lowest of the
310    /// densest levels for ratio, the densest of the fastest levels for speed.
311    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    // zrip on OMQ's benchmark corpus, 1 KiB messages in 32 KiB arenas:
352    // compression speed in MB/s and ratio in hundredths.
353    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    /// A sender compressing at `speed` MB/s per level, behind an optional
357    /// output of `output` MB/s, fed at an optional `input` MB/s.
358    struct Sender {
359        speed: [u64; 11],
360        ratio: [u64; 11],
361        output: Option<u64>,
362        input: Option<u64>,
363        /// Alternating speed error in percent.
364        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        /// One 100 ms window at `level`, with the bottleneck a transport
381        /// would report: output blocked for at least 1/16 of the window, or
382        /// input queued while output blocked under 1/64 of it, or no queue.
383        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            // Input bytes per window that the CPU, output, and input allow.
395            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        // -4 compresses 1.4% worse than -5; 1 compresses worse than -1.
460        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        // Ratio improves with every level, but 3 cannot fill a 45 MB/s output.
480        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        // 1 and 2 compress alike, so the lower level wins.
488        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        // 1 Gbps: -6 keeps up, -7 overflows the output.
495        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        // -7 compresses 4% slower than -6 and much worse.
508        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}