pleat 0.1.0

Ribbon filters with pleated (partition-instead-of-sort) construction: build at Bloom-filter speed, verify by checksum.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

//! Query throughput: scalar vs. batch, both filter families, plus a measured false-positive
//! rate. Complements the construction benchmark.
use criterion::{criterion_group, criterion_main, BenchmarkId, Criterion, Throughput};
use pleat::filter::{RibbonFilter, StdRibbon};

fn mix64(mut z: u64) -> u64 {
    z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
    z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
    z ^ (z >> 31)
}
fn keys(n: usize, seed: u64) -> Vec<u64> {
    let mut s = seed;
    (0..n)
        .map(|_| {
            s = s.wrapping_add(0x9e37_79b9_7f4a_7c15);
            mix64(s)
        })
        .collect()
}

fn bench(c: &mut Criterion) {
    let n = 10_000_000usize;
    let members = keys(n, 0xA11CE);
    let probes = keys(1_000_000, 0xD15EA5E); // absent (miss-dominated)
    let hf = RibbonFilter::from_keys_pleated(&members);
    let sf = StdRibbon::<7>::from_keys_pleated(&members).unwrap();

    // Report measured FPR alongside (printed once).
    let fp_h = probes.iter().filter(|&&k| hf.contains(k)).count();
    let fp_s = probes.iter().filter(|&&k| sf.contains(k)).count();
    eprintln!(
        "measured FPR @ r=7: homogeneous {:.3}%, standard {:.3}% (theory 0.781%)",
        100.0 * fp_h as f64 / probes.len() as f64,
        100.0 * fp_s as f64 / probes.len() as f64
    );

    let mut out = vec![false; probes.len()];
    let mut g = c.benchmark_group("query_miss");
    g.throughput(Throughput::Elements(probes.len() as u64));
    g.sample_size(20);
    g.bench_function(BenchmarkId::from_parameter("homog/scalar"), |b| {
        b.iter(|| {
            let mut acc = 0u64;
            for &k in &probes {
                acc += hf.contains(std::hint::black_box(k)) as u64;
            }
            acc
        })
    });
    g.bench_function(BenchmarkId::from_parameter("homog/batch"), |b| {
        b.iter(|| hf.contains_batch(std::hint::black_box(&probes), &mut out))
    });
    g.bench_function(BenchmarkId::from_parameter("std/scalar"), |b| {
        b.iter(|| {
            let mut acc = 0u64;
            for &k in &probes {
                acc += sf.contains(std::hint::black_box(k)) as u64;
            }
            acc
        })
    });
    g.bench_function(BenchmarkId::from_parameter("std/batch"), |b| {
        b.iter(|| sf.contains_batch(std::hint::black_box(&probes), &mut out))
    });
    g.finish();
}
criterion_group!(benches, bench);
criterion_main!(benches);