oxirs_tdb/compression/
benchmark.rs

1//! # Compression Benchmarking
2//!
3//! Measures throughput and compression ratio for different compression algorithms
4//! on TSDB-style data (typically sorted integer sequences).
5//!
6//! ## Usage
7//!
8//! ```rust
9//! use oxirs_tdb::compression::benchmark::{CompressionAlgo, CompressionBenchmark};
10//!
11//! let data = b"hello world hello world hello world";
12//! let result = CompressionBenchmark::benchmark_algorithm(CompressionAlgo::Lz4, data);
13//! println!("Ratio: {:.2}, Speed: {:.1} MB/s", result.ratio, result.compress_mb_s);
14//! ```
15
16use std::time::{Duration, Instant};
17
18use crate::compression::{
19    delta::DeltaEncoder, lz4::Lz4Compressor, run_length::RunLengthEncoder,
20    snappy::SnappyCompressor, zstd_compression::ZstdCompressor, CompressionAlgorithm,
21};
22
23// ─────────────────────────────────────────────────────────────────────────────
24// CompressionAlgo
25// ─────────────────────────────────────────────────────────────────────────────
26
27/// Identifies a compression algorithm for benchmarking purposes.
28#[derive(Debug, Clone, PartialEq, Eq, Hash)]
29pub enum CompressionAlgo {
30    /// Variable-length delta encoding (optimised for sorted integer IDs).
31    Delta,
32    /// Run-length encoding (optimised for repeated values).
33    RunLength,
34    /// LZ4 general-purpose compression (very fast).
35    Lz4,
36    /// Zstandard compression (excellent ratio).
37    Zstd,
38    /// Snappy compression (fast with good ratio).
39    Snappy,
40}
41
42impl std::fmt::Display for CompressionAlgo {
43    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
44        let name = match self {
45            CompressionAlgo::Delta => "Delta",
46            CompressionAlgo::RunLength => "RunLength",
47            CompressionAlgo::Lz4 => "LZ4",
48            CompressionAlgo::Zstd => "Zstd",
49            CompressionAlgo::Snappy => "Snappy",
50        };
51        write!(f, "{}", name)
52    }
53}
54
55// ─────────────────────────────────────────────────────────────────────────────
56// BenchmarkResult
57// ─────────────────────────────────────────────────────────────────────────────
58
59/// Benchmark measurements for a single compression algorithm on a data sample.
60#[derive(Debug, Clone)]
61pub struct BenchmarkResult {
62    /// The algorithm that was benchmarked.
63    pub algo: CompressionAlgo,
64    /// Compression ratio: `compressed_size / original_size` (lower is better).
65    /// A ratio > 1.0 means the data expanded (compression was counter-productive).
66    pub ratio: f64,
67    /// Compression throughput in MB/s.
68    pub compress_mb_s: f64,
69    /// Decompression throughput in MB/s.
70    pub decompress_mb_s: f64,
71    /// Original data size in bytes.
72    pub original_size: usize,
73    /// Compressed data size in bytes.
74    pub compressed_size: usize,
75}
76
77impl BenchmarkResult {
78    /// Return `true` if compression actually shrinks the data.
79    pub fn is_beneficial(&self) -> bool {
80        self.ratio < 1.0
81    }
82
83    /// Space savings as a percentage (0–100).  Negative means data expanded.
84    pub fn space_savings_pct(&self) -> f64 {
85        (1.0 - self.ratio) * 100.0
86    }
87}
88
89impl std::fmt::Display for BenchmarkResult {
90    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
91        write!(
92            f,
93            "{}: ratio={:.3} compress={:.1}MB/s decompress={:.1}MB/s",
94            self.algo, self.ratio, self.compress_mb_s, self.decompress_mb_s
95        )
96    }
97}
98
99// ─────────────────────────────────────────────────────────────────────────────
100// Internal helpers
101// ─────────────────────────────────────────────────────────────────────────────
102
103/// Minimum nanoseconds to report (avoids division by zero on very fast ops).
104const MIN_NS: u128 = 1;
105
106/// Compute MB/s given `data_bytes` and `elapsed` time.
107fn mb_per_second(data_bytes: usize, elapsed: Duration) -> f64 {
108    let ns = elapsed.as_nanos().max(MIN_NS);
109    (data_bytes as f64 / 1_048_576.0) / (ns as f64 / 1_000_000_000.0)
110}
111
112/// Produce a [`BenchmarkResult`] where compression was not available.
113///
114/// Uses original data as compressed data, giving ratio = 1.0 and max speed.
115fn unavailable_result(algo: CompressionAlgo, data: &[u8]) -> BenchmarkResult {
116    BenchmarkResult {
117        algo,
118        ratio: 1.0,
119        compress_mb_s: 0.0,
120        decompress_mb_s: 0.0,
121        original_size: data.len(),
122        compressed_size: data.len(),
123    }
124}
125
126// ─────────────────────────────────────────────────────────────────────────────
127// CompressionBenchmark
128// ─────────────────────────────────────────────────────────────────────────────
129
130/// Measures compression throughput and ratio for different algorithms.
131///
132/// All benchmarks are single-shot (not averaged); for statistical precision
133/// use the `benchmarking` feature with multiple iterations.
134pub struct CompressionBenchmark;
135
136impl CompressionBenchmark {
137    /// Create a new `CompressionBenchmark` instance (stateless).
138    pub fn new() -> Self {
139        Self
140    }
141
142    /// Benchmark a single algorithm on the given data.
143    ///
144    /// Returns a [`BenchmarkResult`] regardless of whether compression succeeds:
145    /// on error, ratio is set to `1.0` and throughputs to `0.0`.
146    pub fn benchmark_algorithm(algo: CompressionAlgo, data: &[u8]) -> BenchmarkResult {
147        if data.is_empty() {
148            return BenchmarkResult {
149                algo,
150                ratio: 1.0,
151                compress_mb_s: 0.0,
152                decompress_mb_s: 0.0,
153                original_size: 0,
154                compressed_size: 0,
155            };
156        }
157
158        match &algo {
159            CompressionAlgo::Delta => Self::bench_delta(data),
160            CompressionAlgo::RunLength => Self::bench_run_length(data),
161            CompressionAlgo::Lz4 => Self::bench_lz4(data),
162            CompressionAlgo::Zstd => Self::bench_zstd(data),
163            CompressionAlgo::Snappy => Self::bench_snappy(data),
164        }
165    }
166
167    /// Benchmark all supported algorithms on the given data.
168    ///
169    /// Results are returned in algorithm order (Delta, RunLength, LZ4, Zstd, Snappy).
170    pub fn benchmark_all(data: &[u8]) -> Vec<BenchmarkResult> {
171        vec![
172            Self::benchmark_algorithm(CompressionAlgo::Delta, data),
173            Self::benchmark_algorithm(CompressionAlgo::RunLength, data),
174            Self::benchmark_algorithm(CompressionAlgo::Lz4, data),
175            Self::benchmark_algorithm(CompressionAlgo::Zstd, data),
176            Self::benchmark_algorithm(CompressionAlgo::Snappy, data),
177        ]
178    }
179
180    /// Return the result with the best compression ratio (lowest ratio value).
181    pub fn best_ratio(results: &[BenchmarkResult]) -> Option<&BenchmarkResult> {
182        results.iter().min_by(|a, b| {
183            a.ratio
184                .partial_cmp(&b.ratio)
185                .unwrap_or(std::cmp::Ordering::Equal)
186        })
187    }
188
189    /// Return the result with the highest compression throughput (MB/s).
190    pub fn best_compress_speed(results: &[BenchmarkResult]) -> Option<&BenchmarkResult> {
191        results.iter().max_by(|a, b| {
192            a.compress_mb_s
193                .partial_cmp(&b.compress_mb_s)
194                .unwrap_or(std::cmp::Ordering::Equal)
195        })
196    }
197
198    /// Return the result with the highest decompression throughput (MB/s).
199    pub fn best_decompress_speed(results: &[BenchmarkResult]) -> Option<&BenchmarkResult> {
200        results.iter().max_by(|a, b| {
201            a.decompress_mb_s
202                .partial_cmp(&b.decompress_mb_s)
203                .unwrap_or(std::cmp::Ordering::Equal)
204        })
205    }
206
207    // ── Private per-algorithm benchmarks ─────────────────────────────────────
208
209    fn bench_delta(data: &[u8]) -> BenchmarkResult {
210        // Treat raw bytes as u64 sequence (chunked by 8 bytes).
211        let values: Vec<u64> = data
212            .chunks_exact(8)
213            .map(|c| u64::from_le_bytes([c[0], c[1], c[2], c[3], c[4], c[5], c[6], c[7]]))
214            .collect();
215
216        if values.is_empty() {
217            // Data too small for u64 chunking; fall back to byte-level encoding
218            let t0 = Instant::now();
219            let enc = DeltaEncoder::encode_byte_sequence(data);
220            let compress_elapsed = t0.elapsed();
221
222            let compressed = match enc {
223                Ok(c) => c,
224                Err(_) => return unavailable_result(CompressionAlgo::Delta, data),
225            };
226
227            let t1 = Instant::now();
228            let _ = DeltaEncoder::decode_byte_sequence(&compressed);
229            let decompress_elapsed = t1.elapsed();
230
231            let ratio = compressed.len() as f64 / data.len() as f64;
232            return BenchmarkResult {
233                algo: CompressionAlgo::Delta,
234                ratio,
235                compress_mb_s: mb_per_second(data.len(), compress_elapsed),
236                decompress_mb_s: mb_per_second(data.len(), decompress_elapsed),
237                original_size: data.len(),
238                compressed_size: compressed.len(),
239            };
240        }
241
242        let t0 = Instant::now();
243        let encoded = DeltaEncoder::encode(&values);
244        let compress_elapsed = t0.elapsed();
245
246        let t1 = Instant::now();
247        let _ = DeltaEncoder::decode(&encoded);
248        let decompress_elapsed = t1.elapsed();
249
250        let ratio = encoded.len() as f64 / data.len() as f64;
251        BenchmarkResult {
252            algo: CompressionAlgo::Delta,
253            ratio,
254            compress_mb_s: mb_per_second(data.len(), compress_elapsed),
255            decompress_mb_s: mb_per_second(data.len(), decompress_elapsed),
256            original_size: data.len(),
257            compressed_size: encoded.len(),
258        }
259    }
260
261    fn bench_run_length(data: &[u8]) -> BenchmarkResult {
262        let t0 = Instant::now();
263        let enc = RunLengthEncoder::encode(data);
264        let compress_elapsed = t0.elapsed();
265
266        let compressed = match enc {
267            Ok(c) => c,
268            Err(_) => return unavailable_result(CompressionAlgo::RunLength, data),
269        };
270
271        let t1 = Instant::now();
272        let _ = RunLengthEncoder::decode(&compressed);
273        let decompress_elapsed = t1.elapsed();
274
275        let ratio = if data.is_empty() {
276            1.0
277        } else {
278            compressed.len() as f64 / data.len() as f64
279        };
280
281        BenchmarkResult {
282            algo: CompressionAlgo::RunLength,
283            ratio,
284            compress_mb_s: mb_per_second(data.len(), compress_elapsed),
285            decompress_mb_s: mb_per_second(data.len(), decompress_elapsed),
286            original_size: data.len(),
287            compressed_size: compressed.len(),
288        }
289    }
290
291    fn bench_lz4(data: &[u8]) -> BenchmarkResult {
292        let compressor = Lz4Compressor::new();
293
294        let t0 = Instant::now();
295        let compressed_data = compressor.compress(data);
296        let compress_elapsed = t0.elapsed();
297
298        let compressed_data = match compressed_data {
299            Ok(c) => c,
300            Err(_) => return unavailable_result(CompressionAlgo::Lz4, data),
301        };
302
303        let t1 = Instant::now();
304        let _ = compressor.decompress(&compressed_data);
305        let decompress_elapsed = t1.elapsed();
306
307        let ratio = compressed_data.data.len() as f64 / data.len() as f64;
308        BenchmarkResult {
309            algo: CompressionAlgo::Lz4,
310            ratio,
311            compress_mb_s: mb_per_second(data.len(), compress_elapsed),
312            decompress_mb_s: mb_per_second(data.len(), decompress_elapsed),
313            original_size: data.len(),
314            compressed_size: compressed_data.data.len(),
315        }
316    }
317
318    fn bench_zstd(data: &[u8]) -> BenchmarkResult {
319        let compressor = ZstdCompressor::new();
320
321        let t0 = Instant::now();
322        let compressed_data = compressor.compress(data);
323        let compress_elapsed = t0.elapsed();
324
325        let compressed_data = match compressed_data {
326            Ok(c) => c,
327            Err(_) => return unavailable_result(CompressionAlgo::Zstd, data),
328        };
329
330        let t1 = Instant::now();
331        let _ = compressor.decompress(&compressed_data);
332        let decompress_elapsed = t1.elapsed();
333
334        let ratio = compressed_data.data.len() as f64 / data.len() as f64;
335        BenchmarkResult {
336            algo: CompressionAlgo::Zstd,
337            ratio,
338            compress_mb_s: mb_per_second(data.len(), compress_elapsed),
339            decompress_mb_s: mb_per_second(data.len(), decompress_elapsed),
340            original_size: data.len(),
341            compressed_size: compressed_data.data.len(),
342        }
343    }
344
345    fn bench_snappy(data: &[u8]) -> BenchmarkResult {
346        let compressor = SnappyCompressor::new();
347
348        let t0 = Instant::now();
349        let compressed_data = compressor.compress(data);
350        let compress_elapsed = t0.elapsed();
351
352        let compressed_data = match compressed_data {
353            Ok(c) => c,
354            Err(_) => return unavailable_result(CompressionAlgo::Snappy, data),
355        };
356
357        let t1 = Instant::now();
358        let _ = compressor.decompress(&compressed_data);
359        let decompress_elapsed = t1.elapsed();
360
361        let ratio = compressed_data.data.len() as f64 / data.len() as f64;
362        BenchmarkResult {
363            algo: CompressionAlgo::Snappy,
364            ratio,
365            compress_mb_s: mb_per_second(data.len(), compress_elapsed),
366            decompress_mb_s: mb_per_second(data.len(), decompress_elapsed),
367            original_size: data.len(),
368            compressed_size: compressed_data.data.len(),
369        }
370    }
371}
372
373impl Default for CompressionBenchmark {
374    fn default() -> Self {
375        Self::new()
376    }
377}
378
379// ─────────────────────────────────────────────────────────────────────────────
380// Tests
381// ─────────────────────────────────────────────────────────────────────────────
382
383#[cfg(test)]
384mod tests {
385    use super::*;
386
387    /// Build a repetitive u64 sequence and flatten to bytes for benchmarking.
388    fn repetitive_u64_data(count: usize) -> Vec<u8> {
389        let values: Vec<u64> = (0..count as u64).map(|i| i / 10).collect();
390        values.iter().flat_map(|v| v.to_le_bytes()).collect()
391    }
392
393    /// Build a sorted ascending u64 sequence as bytes.
394    fn sorted_u64_data(count: usize) -> Vec<u8> {
395        let values: Vec<u64> = (0..count as u64).collect();
396        values.iter().flat_map(|v| v.to_le_bytes()).collect()
397    }
398
399    // ── Individual algorithm benchmarks ──────────────────────────────────────
400
401    #[test]
402    fn test_benchmark_delta_valid_result() {
403        let data = sorted_u64_data(100);
404        let result = CompressionBenchmark::benchmark_algorithm(CompressionAlgo::Delta, &data);
405        assert_eq!(result.algo, CompressionAlgo::Delta);
406        assert!(result.original_size > 0);
407        assert!(result.ratio >= 0.0);
408        assert!(result.compress_mb_s >= 0.0);
409        assert!(result.decompress_mb_s >= 0.0);
410    }
411
412    #[test]
413    fn test_benchmark_run_length_valid_result() {
414        let data = repetitive_u64_data(100);
415        let result = CompressionBenchmark::benchmark_algorithm(CompressionAlgo::RunLength, &data);
416        assert_eq!(result.algo, CompressionAlgo::RunLength);
417        assert!(result.original_size > 0);
418        assert!(result.ratio >= 0.0);
419    }
420
421    #[test]
422    fn test_benchmark_lz4_valid_result() {
423        let data = b"hello world hello world hello world hello world".to_vec();
424        let result = CompressionBenchmark::benchmark_algorithm(CompressionAlgo::Lz4, &data);
425        assert_eq!(result.algo, CompressionAlgo::Lz4);
426        assert!(result.original_size == data.len());
427        assert!(result.ratio >= 0.0);
428    }
429
430    #[test]
431    fn test_benchmark_zstd_valid_result() {
432        let data = b"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".to_vec();
433        let result = CompressionBenchmark::benchmark_algorithm(CompressionAlgo::Zstd, &data);
434        assert_eq!(result.algo, CompressionAlgo::Zstd);
435        assert!(result.ratio >= 0.0);
436    }
437
438    #[test]
439    fn test_benchmark_snappy_valid_result() {
440        let data = b"snappy snappy snappy snappy snappy".to_vec();
441        let result = CompressionBenchmark::benchmark_algorithm(CompressionAlgo::Snappy, &data);
442        assert_eq!(result.algo, CompressionAlgo::Snappy);
443        assert!(result.ratio >= 0.0);
444    }
445
446    // ── benchmark_all ─────────────────────────────────────────────────────────
447
448    #[test]
449    fn test_benchmark_all_returns_five_results() {
450        let data = b"test data for benchmarking all algorithms".to_vec();
451        let results = CompressionBenchmark::benchmark_all(&data);
452        assert_eq!(results.len(), 5);
453    }
454
455    #[test]
456    fn test_benchmark_all_all_algos_present() {
457        let data = sorted_u64_data(50);
458        let results = CompressionBenchmark::benchmark_all(&data);
459        let algos: Vec<&CompressionAlgo> = results.iter().map(|r| &r.algo).collect();
460        assert!(algos.contains(&&CompressionAlgo::Delta));
461        assert!(algos.contains(&&CompressionAlgo::RunLength));
462        assert!(algos.contains(&&CompressionAlgo::Lz4));
463        assert!(algos.contains(&&CompressionAlgo::Zstd));
464        assert!(algos.contains(&&CompressionAlgo::Snappy));
465    }
466
467    // ── best_ratio ────────────────────────────────────────────────────────────
468
469    #[test]
470    fn test_best_ratio_returns_minimum() {
471        let data = repetitive_u64_data(100);
472        let results = CompressionBenchmark::benchmark_all(&data);
473        let best = CompressionBenchmark::best_ratio(&results);
474        assert!(best.is_some());
475        let best = best.unwrap();
476        // Verify it really is the minimum
477        for r in &results {
478            assert!(best.ratio <= r.ratio + f64::EPSILON);
479        }
480    }
481
482    #[test]
483    fn test_best_ratio_empty_returns_none() {
484        let result = CompressionBenchmark::best_ratio(&[]);
485        assert!(result.is_none());
486    }
487
488    // ── best_compress_speed ───────────────────────────────────────────────────
489
490    #[test]
491    fn test_best_compress_speed_returns_maximum() {
492        let data = sorted_u64_data(100);
493        let results = CompressionBenchmark::benchmark_all(&data);
494        let best = CompressionBenchmark::best_compress_speed(&results);
495        assert!(best.is_some());
496        let best = best.unwrap();
497        for r in &results {
498            assert!(best.compress_mb_s >= r.compress_mb_s - f64::EPSILON);
499        }
500    }
501
502    #[test]
503    fn test_best_compress_speed_empty_returns_none() {
504        let result = CompressionBenchmark::best_compress_speed(&[]);
505        assert!(result.is_none());
506    }
507
508    // ── best_decompress_speed ─────────────────────────────────────────────────
509
510    #[test]
511    fn test_best_decompress_speed_returns_maximum() {
512        let data = sorted_u64_data(100);
513        let results = CompressionBenchmark::benchmark_all(&data);
514        let best = CompressionBenchmark::best_decompress_speed(&results);
515        assert!(best.is_some());
516    }
517
518    // ── BenchmarkResult helpers ───────────────────────────────────────────────
519
520    #[test]
521    fn test_benchmark_result_ratio_beneficial() {
522        let r = BenchmarkResult {
523            algo: CompressionAlgo::Lz4,
524            ratio: 0.5,
525            compress_mb_s: 100.0,
526            decompress_mb_s: 200.0,
527            original_size: 1000,
528            compressed_size: 500,
529        };
530        assert!(r.is_beneficial());
531        assert!((r.space_savings_pct() - 50.0).abs() < f64::EPSILON);
532    }
533
534    #[test]
535    fn test_benchmark_result_ratio_not_beneficial() {
536        let r = BenchmarkResult {
537            algo: CompressionAlgo::RunLength,
538            ratio: 1.5,
539            compress_mb_s: 50.0,
540            decompress_mb_s: 80.0,
541            original_size: 100,
542            compressed_size: 150,
543        };
544        assert!(!r.is_beneficial());
545        assert!(r.space_savings_pct() < 0.0);
546    }
547
548    #[test]
549    fn test_benchmark_empty_data() {
550        let result = CompressionBenchmark::benchmark_algorithm(CompressionAlgo::Lz4, &[]);
551        assert_eq!(result.original_size, 0);
552        assert_eq!(result.compressed_size, 0);
553    }
554
555    #[test]
556    fn test_benchmark_result_display() {
557        let r = BenchmarkResult {
558            algo: CompressionAlgo::Zstd,
559            ratio: 0.3,
560            compress_mb_s: 120.0,
561            decompress_mb_s: 400.0,
562            original_size: 1000,
563            compressed_size: 300,
564        };
565        let s = r.to_string();
566        assert!(s.contains("Zstd"));
567        assert!(s.contains("0.300"));
568    }
569
570    #[test]
571    fn test_compression_algo_display() {
572        assert_eq!(CompressionAlgo::Delta.to_string(), "Delta");
573        assert_eq!(CompressionAlgo::RunLength.to_string(), "RunLength");
574        assert_eq!(CompressionAlgo::Lz4.to_string(), "LZ4");
575        assert_eq!(CompressionAlgo::Zstd.to_string(), "Zstd");
576        assert_eq!(CompressionAlgo::Snappy.to_string(), "Snappy");
577    }
578
579    #[test]
580    fn test_delta_compresses_sorted_ids_efficiently() {
581        // Sorted triple IDs with small deltas should compress well
582        let data = sorted_u64_data(200);
583        let result = CompressionBenchmark::benchmark_algorithm(CompressionAlgo::Delta, &data);
584        // Expect better than 50% ratio for sequential IDs (delta=1 → 1 byte via LEB128)
585        assert!(
586            result.ratio < 0.5,
587            "Expected ratio < 0.5, got {}",
588            result.ratio
589        );
590    }
591
592    #[test]
593    fn test_rle_compresses_repetitive_ids_efficiently() {
594        // Highly repetitive data should compress well with RLE
595        let data = vec![42u8; 1000];
596        let result = CompressionBenchmark::benchmark_algorithm(CompressionAlgo::RunLength, &data);
597        assert!(
598            result.ratio < 0.1,
599            "Expected ratio < 0.1 for repetitive data, got {}",
600            result.ratio
601        );
602    }
603}
oxirs_tdb/compression/benchmark.rs

oxirs_tdb/compression/
benchmark.rs
