lseq/research/benches/lseq_benchmarks.rs

use criterion::{black_box, criterion_group, criterion_main, Criterion, BenchmarkId};
use peoplesgrocers_lseq_research::ReferenceLSEQ;
use peoplesgrocers_lseq::{SortKey, LSEQ};
use peoplesgrocers_lseq_research::algorithms::lseq_base64::{LSEQBase64, SortKeyBase64};
use rand::{Rng, rngs::StdRng, SeedableRng};
use std::collections::VecDeque;
// Add lseq crate from crates.io (uses arbitrary precision arithmetic)
// This crate does not compile on arm
#[cfg(target_arch = "x86_64")]
use lseq::{LSEQ as LSEQArbitraryPrecision, Ident};

fn benchmark_sequential_insertions(c: &mut Criterion) {
    let mut group = c.benchmark_group("sequential_insertions");
    
    for size in [100, 1000, 5000].iter() {
        // Benchmark original paper reference implementation
        group.bench_with_input(
            BenchmarkId::new("original", size),
            size,
            |b, &size| {
                b.iter(|| {
                    let mut lseq = ReferenceLSEQ::new(StdRng::seed_from_u64(42));
                    let mut keys = Vec::new();
                    
                    for _ in 0..size {
                        let before = keys.last();
                        let key = lseq.allocate(before, None).unwrap();
                        keys.push(key);
                    }
                    
                    black_box(keys);
                });
            },
        );
        
        // Benchmark published implementation
        group.bench_with_input(
            BenchmarkId::new("published", size),
            size,
            |b, &size| {
                b.iter(|| {
                    let mut lseq = LSEQ::new(StdRng::seed_from_u64(42));
                    let mut keys = Vec::new();
                    
                    for _ in 0..size {
                        let before = keys.last();
                        let key = lseq.alloc(before, None);
                        keys.push(key);
                    }
                    
                    black_box(keys);
                });
            },
        );
        
        // Benchmark Base64 implementation
        group.bench_with_input(
            BenchmarkId::new("base64", size),
            size,
            |b, &size| {
                b.iter(|| {
                    let mut lseq = LSEQBase64::new(StdRng::seed_from_u64(42));
                    let mut keys = Vec::new();
                    
                    for _ in 0..size {
                        let before = keys.last();
                        let key = lseq.allocate(before, None).unwrap();
                        keys.push(key);
                    }
                    
                    black_box(keys);
                });
            },
        );
        
        // Benchmark lseq crate from crates.io (arbitrary precision arithmetic)
        #[cfg(target_arch = "x86_64")]
        group.bench_with_input(
            BenchmarkId::new("arbitrary_precision", size),
            size,
            |b, &size| {
                b.iter(|| {
                    let mut lseq = LSEQArbitraryPrecision::new();
                    let mut keys = Vec::new();
                    
                    for _ in 0..size {
                        let before = keys.last();
                        let after = None;
                        let key = lseq.allocate(before, after);
                        keys.push(key);
                    }
                    
                    black_box(keys);
                });
            },
        );
    }
    
    group.finish();
}

fn benchmark_random_insertions(c: &mut Criterion) {
    let mut group = c.benchmark_group("random_insertions");
    
    for size in [100, 1000, 5000].iter() {
        // Benchmark original paper reference implementation
        group.bench_with_input(
            BenchmarkId::new("original", size),
            size,
            |b, &size| {
                b.iter(|| {
                    let mut lseq = ReferenceLSEQ::new(StdRng::seed_from_u64(42));
                    let mut keys = Vec::new();
                    let mut rng = StdRng::seed_from_u64(123);
                    
                    for _ in 0..size {
                        if keys.is_empty() {
                            let key = lseq.allocate(None, None).unwrap();
                            keys.push(key);
                        } else {
                            let idx = rng.random_range(0..keys.len());
                            let before = if idx == 0 { None } else { Some(&keys[idx - 1]) };
                            let after = if idx == keys.len() { None } else { Some(&keys[idx]) };
                            
                            let key = lseq.allocate(before, after).unwrap();
                            keys.insert(idx, key);
                        }
                    }
                    
                    black_box(keys);
                });
            },
        );
        
        // Benchmark published implementation
        group.bench_with_input(
            BenchmarkId::new("published", size),
            size,
            |b, &size| {
                b.iter(|| {
                    let mut lseq = LSEQ::new(StdRng::seed_from_u64(42));
                    let mut keys = Vec::new();
                    let mut rng = StdRng::seed_from_u64(123);
                    
                    for _ in 0..size {
                        if keys.is_empty() {
                            let key = lseq.alloc(None, None);
                            keys.push(key);
                        } else {
                            let idx = rng.random_range(0..keys.len());
                            let before = if idx == 0 { None } else { Some(&keys[idx - 1]) };
                            let after = if idx == keys.len() { None } else { Some(&keys[idx]) };
                            
                            let key = lseq.alloc(before, after);
                            keys.insert(idx, key);
                        }
                    }
                    
                    black_box(keys);
                });
            },
        );
        
        // Benchmark Base64 implementation
        group.bench_with_input(
            BenchmarkId::new("base64", size),
            size,
            |b, &size| {
                b.iter(|| {
                    let mut lseq = LSEQBase64::new(StdRng::seed_from_u64(42));
                    let mut keys = Vec::new();
                    let mut rng = StdRng::seed_from_u64(123);
                    
                    for _ in 0..size {
                        if keys.is_empty() {
                            let key = lseq.allocate(None, None).unwrap();
                            keys.push(key);
                        } else {
                            let idx = rng.random_range(0..keys.len());
                            let before = if idx == 0 { None } else { Some(&keys[idx - 1]) };
                            let after = if idx == keys.len() { None } else { Some(&keys[idx]) };
                            
                            let key = lseq.allocate(before, after).unwrap();
                            keys.insert(idx, key);
                        }
                    }
                    
                    black_box(keys);
                });
            },
        );
        
        // Benchmark lseq crate from crates.io (arbitrary precision arithmetic)
        #[cfg(target_arch = "x86_64")]
        group.bench_with_input(
            BenchmarkId::new("arbitrary_precision", size),
            size,
            |b, &size| {
                b.iter(|| {
                    let mut lseq = LSEQArbitraryPrecision::new();
                    let mut keys = Vec::new();
                    let mut rng = StdRng::seed_from_u64(123);
                    
                    for _ in 0..size {
                        if keys.is_empty() {
                            let key = lseq.allocate(None, None);
                            keys.push(key);
                        } else {
                            let idx = rng.random_range(0..keys.len());
                            let before = if idx == 0 { None } else { Some(&keys[idx - 1]) };
                            let after = if idx == keys.len() { None } else { Some(&keys[idx]) };
                            
                            let key = lseq.allocate(before, after);
                            keys.insert(idx, key);
                        }
                    }
                    
                    black_box(keys);
                });
            },
        );
    }
    
    group.finish();
}

criterion_group!(
    benches,
    benchmark_sequential_insertions,
    benchmark_random_insertions,
);
criterion_main!(benches);