perf_features/perf_features.rs
1//! Per-feature bench: sweeps each opt-in feature (`variable-fingerprint`,
2//! `dynamic`, `concurrent-reads`, `compressed-buckets`) across three filter
3//! sizes, lets `classify_feature` DECIDE the category from the shape of that
4//! sweep, and merge-writes the decision into `../.subms/features/rust.json`.
5//!
6//! A filter's "size" is how many keys it is holding, so the sweep fills to N and
7//! times the lookup path there. A per-op cost that holds steady as N grows is
8//! `hot-path`; one that climbs with N is `structural`. For a cuckoo filter that
9//! is the claim worth measuring: a variant whose lookup starts chasing longer
10//! eviction chains as the table fills does not stay sub-millisecond, and only a
11//! sweep catches it.
12//!
13//! `concurrent-reads` is the one feature that is genuinely two different things:
14//! the SNAPSHOT is an O(N) bucket copy, and lookups against the frozen snapshot
15//! are per-op. The sweep classifies on the snapshot, because that is the part
16//! whose cost depends on size; the per-key lookup p99 still lands in the stage
17//! table.
18//!
19//! The sweep classifies on p50, and the BASELINE is a p50 too. p99 over a few
20//! dozen samples is just the worst one, and a single scheduler slice is large
21//! enough to swamp the size signal. Mixing the two - a p50 sweep point against a
22//! p99 baseline - compares different statistics, and the p50 sits under the p99
23//! almost by construction, so every feature would read as a non-effect.
24//!
25//! This replaces the previous shape, which ran every variant at ONE size and
26//! ASSERTED hot-path via `SubMsStageKind::HotPath`. An asserted category is an
27//! opinion the bench cannot contradict; a sweep measures it, and can disagree.
28//!
29//! These p99 figures describe THIS machine. They are published only when the
30//! manifest is stamped `p99_source: fleet`; a local run leaves the category,
31//! which is machine independent for the SCALING verdict, and no published number.
32//!
33//! Run:
34//! cargo run --release --example perf_features \
35//! --features "harness variable-fingerprint dynamic concurrent-reads compressed-buckets"
36
37use std::collections::BTreeMap;
38use std::io::{self, Write};
39use std::path::PathBuf;
40
41use subms::{SubMsFeatureManifest, SubMsP99Source, SubMsPerfHarness, classify_feature, summarize};
42use subms_cuckoo_filter::CuckooFilter;
43
44/// Key counts the sweep walks.
45const SIZES: [usize; 3] = [4_096, 32_768, 262_144];
46/// Timed repeats for the one-shot snapshot capture.
47const SNAPSHOT_REPS: usize = 32;
48/// UNTIMED captures before them. A whole-table copy pays first-touch on a fresh
49/// heap region, and that cost lands entirely on the SMALLEST sweep point - which
50/// is the denominator of the scaling ratio. Left in, it inflated 4096 to 7100ns
51/// against 3000ns at 32768, a non-monotonic sweep whose min/max ratio read 2.3x
52/// over a 64x size range, so an O(N) memcpy classified hot-path. Warmup has to
53/// be discarded, not merely amortised over a few samples.
54const SNAPSHOT_WARM: usize = 16;
55
56fn keys(n: usize) -> Vec<String> {
57 (0..n).map(|i| format!("key-{i}")).collect()
58}
59
60fn stage_stats(h: &SubMsPerfHarness, name: &str) -> (u64, u64) {
61 summarize(h)
62 .stages
63 .iter()
64 .find(|s| s.name == name)
65 .map_or((0, 0), |s| (s.p50_ns, s.p99_ns))
66}
67
68/// (p50, p99) in ns of `op` run once per key.
69fn keyed(ks: &[String], mut op: impl FnMut(&str)) -> (u64, u64) {
70 let mut h = SubMsPerfHarness::new("cuckoo-feature", "rust");
71 {
72 let st = h.stage("op", ks.len());
73 for k in ks {
74 st.time(|| op(k));
75 }
76 }
77 stage_stats(&h, "op")
78}
79
80fn main() -> io::Result<()> {
81 let canon = SIZES[SIZES.len() - 1];
82 let canon_keys = keys(canon);
83
84 let path = PathBuf::from(env!("CARGO_MANIFEST_DIR"))
85 .join("..")
86 .join(".subms")
87 .join("features")
88 .join("rust.json");
89 let existing = std::fs::read_to_string(&path).unwrap_or_default();
90 let mut manifest = SubMsFeatureManifest::load_str("rust", &existing);
91 // Stamp the box these numbers came from. The bench runs wherever it is
92 // invoked, so an unstamped manifest is indistinguishable from a fleet
93 // capture; the renderer will not publish one it cannot attribute.
94 let (source, instance) = SubMsP99Source::from_env();
95 manifest.set_p99_source(source, instance.as_deref());
96
97 // ---------- base: the baseline, not a feature ----------
98 // Every feature is classified against this. A variant whose lookup lands at
99 // or under the base costs nothing on the hot path, and classify_feature says
100 // so rather than calling it hot-path by default.
101 let base_p50 = {
102 let mut f = CuckooFilter::with_capacity(canon);
103 for k in &canon_keys {
104 f.insert(k);
105 }
106 let (p50, _) = keyed(&canon_keys, |k| {
107 let _ = f.contains(k);
108 });
109 p50
110 };
111
112 // ---------- variable-fingerprint: wider tag, lower FPR ----------
113 #[cfg(feature = "variable-fingerprint")]
114 {
115 use subms_cuckoo_filter::{FingerprintWidth, VariableFpCuckooFilter};
116 let sweep: Vec<(usize, u64)> = SIZES
117 .iter()
118 .map(|&n| {
119 let ks = keys(n);
120 let mut f = VariableFpCuckooFilter::new(n, FingerprintWidth::Sixteen);
121 for k in &ks {
122 f.insert(k);
123 }
124 let (p50, _) = keyed(&ks, |k| {
125 let _ = f.contains(k);
126 });
127 (n, p50)
128 })
129 .collect();
130 let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);
131
132 let mut f = VariableFpCuckooFilter::new(canon, FingerprintWidth::Sixteen);
133 let (_, insert99) = keyed(&canon_keys, |k| {
134 f.insert(k);
135 });
136 let (_, lookup99) = keyed(&canon_keys, |k| {
137 let _ = f.contains(k);
138 });
139 let (_, delete99) = keyed(&canon_keys, |k| {
140 f.delete(k);
141 });
142 let mut p99 = BTreeMap::new();
143 p99.insert("insert".to_string(), insert99);
144 p99.insert("lookup".to_string(), lookup99);
145 p99.insert("delete".to_string(), delete99);
146 manifest.set_feature("variable-fingerprint", cat, &p99, &reason);
147 }
148
149 // ---------- dynamic: grows rather than refusing at load factor ----------
150 #[cfg(feature = "dynamic")]
151 {
152 use subms_cuckoo_filter::DynamicCuckooFilter;
153 let sweep: Vec<(usize, u64)> = SIZES
154 .iter()
155 .map(|&n| {
156 let ks = keys(n);
157 let mut f = DynamicCuckooFilter::new(n);
158 for k in &ks {
159 f.insert(k);
160 }
161 let (p50, _) = keyed(&ks, |k| {
162 let _ = f.contains(k);
163 });
164 (n, p50)
165 })
166 .collect();
167 let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);
168
169 let mut f = DynamicCuckooFilter::new(canon);
170 let (_, insert99) = keyed(&canon_keys, |k| {
171 f.insert(k);
172 });
173 let (_, lookup99) = keyed(&canon_keys, |k| {
174 let _ = f.contains(k);
175 });
176 let (_, delete99) = keyed(&canon_keys, |k| {
177 f.delete(k);
178 });
179 let mut p99 = BTreeMap::new();
180 p99.insert("insert".to_string(), insert99);
181 p99.insert("lookup".to_string(), lookup99);
182 p99.insert("delete".to_string(), delete99);
183 manifest.set_feature("dynamic", cat, &p99, &reason);
184 }
185
186 // ---------- concurrent-reads: a frozen snapshot readers share ----------
187 // Classified on the SNAPSHOT, not the lookup. The snapshot is a whole-table
188 // copy whose cost is the thing that scales; the lookups against it are
189 // per-op and would classify the same as any other read.
190 #[cfg(feature = "concurrent-reads")]
191 {
192 use subms_cuckoo_filter::CuckooSnapshot;
193 let sweep: Vec<(usize, u64)> = SIZES
194 .iter()
195 .map(|&n| {
196 let ks = keys(n);
197 let mut src = CuckooFilter::with_capacity(n);
198 for k in &ks {
199 src.insert(k);
200 }
201 // Several samples, not one. A single timed capture at the
202 // SMALLEST size absorbs the first-touch allocation cost, which
203 // inflates the low end of the sweep and flattens the very ratio
204 // the scaling test reads - a whole-table copy then classifies
205 // hot-path, which is exactly backwards.
206 for _ in 0..SNAPSHOT_WARM {
207 let _ = CuckooSnapshot::capture(&src);
208 }
209 let mut h = SubMsPerfHarness::new("cuckoo-feature", "rust");
210 {
211 let st = h.stage("op", SNAPSHOT_REPS);
212 for _ in 0..SNAPSHOT_REPS {
213 st.time(|| {
214 let _ = CuckooSnapshot::capture(&src);
215 });
216 }
217 }
218 let (p50, _) = stage_stats(&h, "op");
219 (n, p50)
220 })
221 .collect();
222 // PINNED structural, not measured. `CuckooSnapshot::capture` is a
223 // `to_vec()` of the whole bucket array - unambiguously O(N) from the
224 // source - but this sweep cannot demonstrate it on a dev box: even with
225 // warmup discarded the smallest size measures ~7us against ~3us at 8x
226 // the size, a non-monotonic curve whose min/max ratio reads ~2x over a
227 // 64x size range, so the scaling test calls it flat and an O(N) memcpy
228 // classifies hot-path. Recording that would be a false claim about the
229 // one op on this page that genuinely is not per-op, so the category is
230 // pinned and `perfReason` says it was overridden rather than measured.
231 // Revisit on a fleet capture, where the curve should separate.
232 //
233 // No base comparison either: a whole-table copy is not the same kind of
234 // operation as a per-key lookup, so a delta against it means nothing.
235 let (cat, reason) =
236 classify_feature(&sweep, None, Some(subms::SubMsFeatureCategory::Structural));
237
238 let mut src = CuckooFilter::with_capacity(canon);
239 for k in &canon_keys {
240 src.insert(k);
241 }
242 for _ in 0..SNAPSHOT_WARM {
243 let _ = CuckooSnapshot::capture(&src);
244 }
245 let mut h = SubMsPerfHarness::new("cuckoo-feature", "rust");
246 let snap = {
247 let st = h.stage("op", SNAPSHOT_REPS);
248 for _ in 0..SNAPSHOT_REPS - 1 {
249 st.time(|| {
250 let _ = CuckooSnapshot::capture(&src);
251 });
252 }
253 st.time(|| CuckooSnapshot::capture(&src))
254 };
255 let (_, snap99) = stage_stats(&h, "op");
256 let (_, lookup99) = keyed(&canon_keys, |k| {
257 let _ = snap.contains(k);
258 });
259 let mut p99 = BTreeMap::new();
260 p99.insert("snapshot".to_string(), snap99);
261 p99.insert("lookup_on_snapshot".to_string(), lookup99);
262 manifest.set_feature("concurrent-reads", cat, &p99, &reason);
263 }
264
265 // ---------- compressed-buckets: tighter memory per bucket ----------
266 #[cfg(feature = "compressed-buckets")]
267 {
268 use subms_cuckoo_filter::CompressedCuckooFilter;
269 let sweep: Vec<(usize, u64)> = SIZES
270 .iter()
271 .map(|&n| {
272 let ks = keys(n);
273 let mut f = CompressedCuckooFilter::with_capacity(n);
274 for k in &ks {
275 f.insert(k);
276 }
277 let (p50, _) = keyed(&ks, |k| {
278 let _ = f.contains(k);
279 });
280 (n, p50)
281 })
282 .collect();
283 let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);
284
285 let mut f = CompressedCuckooFilter::with_capacity(canon);
286 let (_, insert99) = keyed(&canon_keys, |k| {
287 f.insert(k);
288 });
289 let (_, lookup99) = keyed(&canon_keys, |k| {
290 let _ = f.contains(k);
291 });
292 let (_, delete99) = keyed(&canon_keys, |k| {
293 f.delete(k);
294 });
295 let mut p99 = BTreeMap::new();
296 p99.insert("insert".to_string(), insert99);
297 p99.insert("lookup".to_string(), lookup99);
298 p99.insert("delete".to_string(), delete99);
299 manifest.set_feature("compressed-buckets", cat, &p99, &reason);
300 }
301
302 std::fs::create_dir_all(path.parent().unwrap())?;
303 std::fs::write(&path, manifest.to_json())?;
304 io::stdout().write_all(manifest.to_json().as_bytes())?;
305 Ok(())
306}