rudb_encoding/
tally.rs

1//! What each codec cost the process and how often it was kept, for `rudb_codec_metrics()`.
2//!
3//! W1 asks the page builder for no codec that uses over 5% of encode time while being kept in
4//! under 1% of offers. The number that started that rule, four codecs at 62.9% of encode time kept
5//! 7 times in 1,195 offers, came from `cargo xtask encode`, which runs the exhaustive chooser over a
6//! fixture. The writer does not run that chooser. It settles a shape on a sample and replays it, so
7//! what the writer offers is much less than the fixture says, and the rule can only be checked by
8//! counting in the writer.
9//!
10//! # What is counted
11//!
12//! The top level of every cascade and nothing under it. An offer is a candidate the chooser asked
13//! for, kept is the one that came out smallest, and the time is the whole of that candidate's
14//! encode with everything it cascaded into. So the times of one family add up to its encode time
15//! and the share a codec has of it is the share of the writer's encode time its offers cost. A
16//! dictionary's codes going through the integer cascade are inside the dictionary's time rather
17//! than counted again as integers.
18//!
19//! # What it costs
20//!
21//! Two clock readings and three relaxed atomic adds per candidate per chunk, and a chunk is
22//! thousands of values. The counters are process wide and never reset, so a reading is the
23//! difference between two queries, or a fresh process with one load in it.
24
25use std::sync::atomic::{AtomicU64, Ordering};
26use std::time::Instant;
27
28use crate::{integer, string};
29
30/// The counters of one codec.
31struct Counters {
32    offers: AtomicU64,
33    kept: AtomicU64,
34    nanos: AtomicU64,
35}
36
37impl Counters {
38    const fn zero() -> Self {
39        Self { offers: AtomicU64::new(0), kept: AtomicU64::new(0), nanos: AtomicU64::new(0) }
40    }
41}
42
43/// One slot per codec in tag order, and one after them for choosing.
44static INTEGERS: [Counters; 8] = [const { Counters::zero() }; 8];
45static STRINGS: [Counters; 7] = [const { Counters::zero() }; 7];
46
47/// The name of the row that holds the time spent choosing rather than encoding.
48///
49/// That is the questions a family asks of a chunk before it offers anything, like the one pass in
50/// the integer cascade that finds its smallest value, its largest and its runs. It is encode time
51/// no codec spent, so it gets a row of its own rather than going missing from the total.
52pub const CHOOSING: &str = "(choosing)";
53
54/// What one codec has cost the process so far.
55#[derive(Debug, Clone, PartialEq, Eq)]
56pub struct Codec {
57    /// `integer` or `string`.
58    pub family: &'static str,
59    /// The name a report gives the codec, or [`CHOOSING`].
60    pub name: &'static str,
61    /// Top level candidates the chooser asked this codec to encode. Zero for [`CHOOSING`].
62    pub offers: u64,
63    /// Of those, how many came out smallest and were written. Zero for [`CHOOSING`].
64    pub kept: u64,
65    /// The time those offers took, with everything they cascaded into.
66    pub nanos: u64,
67}
68
69/// Every codec of both families, integers first, whether it was offered or not.
70#[must_use]
71pub fn codecs() -> Vec<Codec> {
72    let integers = integer::Kind::ALL.iter().map(|kind| kind.name()).chain([CHOOSING]);
73    let strings = string::Kind::ALL.iter().map(|kind| kind.name()).chain([CHOOSING]);
74    let integers = integers.zip(&INTEGERS).map(|(name, counters)| ("integer", name, counters));
75    let strings = strings.zip(&STRINGS).map(|(name, counters)| ("string", name, counters));
76    integers
77        .chain(strings)
78        .map(|(family, name, counters)| Codec {
79            family,
80            name,
81            offers: counters.offers.load(Ordering::Relaxed),
82            kept: counters.kept.load(Ordering::Relaxed),
83            nanos: counters.nanos.load(Ordering::Relaxed),
84        })
85        .collect()
86}
87
88/// Which family a chunk is being counted into.
89#[derive(Debug, Clone, Copy)]
90pub(crate) enum Family {
91    Integer,
92    String,
93}
94
95impl Family {
96    fn slots(self) -> &'static [Counters] {
97        match self {
98            Self::Integer => &INTEGERS,
99            Self::String => &STRINGS,
100        }
101    }
102}
103
104/// The time between two readings, in nanoseconds.
105fn since(started: Instant) -> u64 {
106    u64::try_from(started.elapsed().as_nanos()).unwrap_or(u64::MAX)
107}
108
109/// Charges the time since `started` to choosing, for a chunk that is about to offer candidates.
110pub(crate) fn chose(family: Family, started: Instant) {
111    if let Some(counters) = family.slots().last() {
112        counters.nanos.fetch_add(since(started), Ordering::Relaxed);
113    }
114}
115
116/// Runs `encode` as one offer of the codec with this tag and charges it the time.
117pub(crate) fn offer<T>(family: Family, tag: u8, encode: impl FnOnce() -> T) -> T {
118    let started = Instant::now();
119    let out = encode();
120    if let Some(counters) = family.slots().get(usize::from(tag)) {
121        counters.offers.fetch_add(1, Ordering::Relaxed);
122        counters.nanos.fetch_add(since(started), Ordering::Relaxed);
123    }
124    out
125}
126
127/// Counts the codec with this tag as the one the chunk was written in.
128pub(crate) fn kept(family: Family, tag: u8) {
129    if let Some(counters) = family.slots().get(usize::from(tag)) {
130        counters.kept.fetch_add(1, Ordering::Relaxed);
131    }
132}
133
134#[cfg(test)]
135mod tests {
136    use super::*;
137
138    fn of(family: &str, name: &str) -> Codec {
139        codecs().into_iter().find(|codec| codec.family == family && codec.name == name).unwrap()
140    }
141
142    #[test]
143    fn a_top_level_chunk_counts_its_offers_and_the_one_it_kept() {
144        let kept = |family: &str| -> u64 {
145            codecs().iter().filter(|codec| codec.family == family).map(|codec| codec.kept).sum()
146        };
147        let before = (of("integer", "FOR+BITPACK"), of("integer", "RLE"), of("string", "PLAIN"));
148        let kept_before = (kept("integer"), kept("string"));
149        let runs: Vec<i64> = (0..4096).map(|at| at / 512).collect();
150        integer::encode(&runs).unwrap();
151        string::encode(&[b"a".as_slice(), b"b", b"c"]).unwrap();
152        let after = (of("integer", "FOR+BITPACK"), of("integer", "RLE"), of("string", "PLAIN"));
153        // Other tests encode on other threads, so this can only say the counts went up.
154        assert!(after.0.offers > before.0.offers);
155        assert!(after.1.offers > before.1.offers);
156        assert!(after.2.offers > before.2.offers);
157        assert!(kept("integer") > kept_before.0);
158        assert!(kept("string") > kept_before.1);
159    }
160
161    #[test]
162    fn every_codec_of_both_families_has_a_row() {
163        let rows = codecs();
164        assert_eq!(rows.len(), integer::Kind::ALL.len() + string::Kind::ALL.len() + 2);
165        assert!(rows.iter().any(|codec| codec.family == "string" && codec.name == "LZ"));
166    }
167}
rudb_encoding/tally.rs

rudb_encoding/
tally.rs
