subms_hyperloglog/
recipe.rs

1//! `SubMsRecipe` impl. Behind the `harness` feature.
2
3use subms::{
4    SubMsBenchParams, SubMsLcg, SubMsPerfHarness, SubMsRecipe, SubMsStageKind, SubMsTimer,
5};
6
7use crate::HyperLogLog;
8
9/// Stages: `add`, `estimate`.
10pub struct HyperLogLogRecipe;
11
12/// Samples for the `estimate` stage. The harness takes p99 as
13/// `sorted[floor(0.99 * n)]`, so at n <= 100 that index is `n - 1` and the
14/// reported p99 is whichever single call caught a scheduler hiccup. 2000 puts
15/// 19 samples above the p99 index and 1 above p999. Do not lower it.
16const ESTIMATE_SAMPLES: usize = 2_000;
17
18/// Untimed `estimate` reps before the timed loop. One fold of the register
19/// array is far above the per-key budget, so it needs its own warm-up rather
20/// than inheriting the one `add` did.
21const ESTIMATE_WARM: usize = 64;
22
23impl SubMsRecipe for HyperLogLogRecipe {
24    fn name(&self) -> &str {
25        "hyperloglog"
26    }
27
28    fn run(&self, h: &mut SubMsPerfHarness, params: &SubMsBenchParams) {
29        let entries = params.entries;
30        let warmup = params.warmup;
31        let seed = params.seed;
32        let mut hll = HyperLogLog::new(14);
33
34        // Warm-up
35        let mut rng = SubMsLcg::new(seed);
36        for _ in 0..warmup {
37            hll.add(&format!("warm{}", rng.next_u32()));
38        }
39
40        let s_add = h.stage("add", entries).with_kind(SubMsStageKind::HotPath);
41        let mut rng = SubMsLcg::new(seed.wrapping_add(1));
42        for _ in 0..entries {
43            let key = format!("k{}", rng.next_u32());
44            let t0 = SubMsTimer::tick();
45            hll.add(&key);
46            s_add.record(t0.elapsed_ns());
47        }
48
49        for _ in 0..ESTIMATE_WARM {
50            std::hint::black_box(hll.estimate());
51        }
52        let s_est = h
53            .stage("estimate", ESTIMATE_SAMPLES)
54            .with_kind(SubMsStageKind::HotPath);
55        for _ in 0..ESTIMATE_SAMPLES {
56            let t0 = SubMsTimer::tick();
57            // estimate() is pure and in-crate, so dropping the result lets LLVM
58            // delete the whole 16k-register scan and time an empty region.
59            std::hint::black_box(hll.estimate());
60            s_est.record(t0.elapsed_ns());
61        }
62
63        h.add_meta("precision", "14");
64        h.add_meta("registers", &hll.register_count().to_string());
65        h.add_meta("estimate", &(hll.estimate() as u64).to_string());
66    }
67}
subms_hyperloglog/recipe.rs

subms_hyperloglog/
recipe.rs
