perf_features/
perf_features.rs

1//! Feature classification bench. Each feature's representative op is swept
2//! across three tree sizes, `classify_feature` DECIDES the category from the
3//! shape of that sweep, and the decision plus a measured `p99ByStage` is
4//! merge-written into `.subms/features/rust.json`.
5//!
6//! A treap's ops are O(log n) expected, so on a 64x size sweep a per-op feature
7//! should rise by well under 2x - flat, by the classifier's reading. Anything
8//! that walks the tree instead of descending it rises with n, and that is the
9//! line the sweep is here to draw. `split` looks like the former and is the
10//! latter.
11//!
12//! Run:
13//!   cargo run --release --example perf_features \
14//!       --features "harness range-query persistent merge-split concurrent-reads"
15
16use std::collections::BTreeMap;
17use std::io::{self, Write};
18use std::path::PathBuf;
19
20use subms::{SubMsFeatureManifest, SubMsP99Source, SubMsPerfHarness, classify_feature, summarize};
21use subms_treap::Treap;
22
23const SIZES: [usize; 3] = [4_096, 32_768, 262_144];
24const CANON: usize = SIZES[SIZES.len() - 1];
25const SEED: u64 = 0;
26/// Keyed ops per measurement. Fixed across the sweep so a slope has one cause.
27const OPS: usize = 20_000;
28/// Samples per bulk op. A whole-structure call is far above the per-key budget,
29/// so a distribution needs repeats rather than one shot. 256 is a FLOOR, not a
30/// preference: the harness takes p99 as `sorted[floor(0.99 * n)]`, so at n <= 100
31/// that index IS `n - 1` and the "p99" is the single worst sample. A structural
32/// verdict then turns on whichever rep caught a page fault. 256 puts two samples
33/// above the index and makes it a real percentile. Do not lower it.
34const BULK_REPS: usize = 256;
35const BULK_WARM: usize = 8;
36const KEY_SPACE: u64 = 1_000_000_007;
37
38/// Scattered rather than ascending, so a descent cannot be predicted away.
39fn key_at(i: usize) -> u64 {
40    ((i as u64).wrapping_mul(2_654_435_761)) % 1_000_000_007
41}
42
43fn build(n: usize) -> Treap<u64, u64> {
44    let mut t = Treap::new(SEED);
45    for i in 0..n {
46        t.insert(key_at(i), i as u64);
47    }
48    t
49}
50
51fn stat(h: &SubMsPerfHarness, median: bool) -> u64 {
52    summarize(h)
53        .stages
54        .iter()
55        .find(|s| s.name == "op")
56        .map_or(0, |s| if median { s.p50_ns } else { s.p99_ns })
57}
58
59/// p50/p99 (ns) of `op` over a fixed OPS of keys drawn from a tree of size `n`.
60fn keyed(n: usize, mut op: impl FnMut(usize), median: bool) -> u64 {
61    let mut h = SubMsPerfHarness::new("treap-feature", "rust");
62    let st = h.stage("op", OPS);
63    for i in 0..OPS {
64        let idx = (i * 7919) % n;
65        st.time(|| op(idx));
66    }
67    stat(&h, median)
68}
69
70/// A whole-tree op. `setup` runs OUTSIDE the timed region and the first
71/// `BULK_WARM` reps are discarded: measured cold, a bulk op lands its
72/// first-touch cost on whichever sweep point runs first, which reads as a curve
73/// that FALLS with size - the opposite of the structural signal.
74fn bulk<T>(mut setup: impl FnMut() -> T, mut op: impl FnMut(&mut T), median: bool) -> u64 {
75    let mut input = setup();
76    for _ in 0..BULK_WARM {
77        op(&mut input);
78    }
79    let mut h = SubMsPerfHarness::new("treap-feature", "rust");
80    let st = h.stage("op", BULK_REPS);
81    for _ in 0..BULK_REPS {
82        st.time(|| op(&mut input));
83    }
84    stat(&h, median)
85}
86
87/// Sweeps and PRINTS the curve. A non-monotonic or ratio-compressed sweep
88/// classifies flat, and the only way to catch one is to look at the rows.
89fn sweep(label: &str, mut at: impl FnMut(usize) -> u64) -> Vec<(usize, u64)> {
90    let rows: Vec<(usize, u64)> = SIZES.iter().map(|&n| (n, at(n))).collect();
91    eprintln!("sweep {label}: {rows:?}");
92    rows
93}
94
95fn main() -> io::Result<()> {
96    let path = PathBuf::from(env!("CARGO_MANIFEST_DIR"))
97        .join("..")
98        .join(".subms")
99        .join("features")
100        .join("rust.json");
101    let existing = std::fs::read_to_string(&path).unwrap_or_default();
102    let mut manifest = SubMsFeatureManifest::load_str("rust", &existing);
103    // Stamp the box these numbers came from. The bench runs wherever it is
104    // invoked, so an unstamped manifest is indistinguishable from a fleet
105    // capture; the renderer will not publish one it cannot attribute.
106    let (source, instance) = SubMsP99Source::from_env();
107    manifest.set_p99_source(source, instance.as_deref());
108
109    // The baseline: a base-treap lookup at the canonical size. A feature landing
110    // at or under this costs nothing on the read path.
111    let base = build(CANON);
112    let base_p50 = keyed(CANON, |i| _ = base.get(&key_at(i)), true);
113    eprintln!("base get p50: {base_p50}ns");
114
115    // ---------- persistent: path-copying insert, old version stays valid ----------
116    #[cfg(feature = "persistent")]
117    {
118        use subms_treap::PersistentTreap;
119        // `insert` returns a NEW treap sharing everything off the copied path,
120        // so the cost is the path length - O(log n), which should read flat.
121        let sw = sweep("persistent/insert", |n| {
122            let mut p = PersistentTreap::new(SEED);
123            for i in 0..n {
124                p = p.insert(key_at(i), i as u64);
125            }
126            keyed(n, |i| _ = p.insert(key_at(i), i as u64), true)
127        });
128        let (cat, reason) = classify_feature(&sw, Some(base_p50), None);
129
130        let mut p = PersistentTreap::new(SEED);
131        for i in 0..CANON {
132            p = p.insert(key_at(i), i as u64);
133        }
134        let mut p99 = BTreeMap::new();
135        p99.insert(
136            "insert".to_string(),
137            keyed(CANON, |i| _ = p.insert(key_at(i), i as u64), false),
138        );
139        p99.insert(
140            "get".to_string(),
141            keyed(CANON, |i| _ = p.get(&key_at(i)), false),
142        );
143        p99.insert(
144            "remove".to_string(),
145            keyed(CANON, |i| _ = p.remove(&key_at(i)), false),
146        );
147        manifest.set_feature("persistent", cat, &p99, &reason);
148    }
149
150    // ---------- merge-split: split at a pivot, merge two ordered halves ----------
151    #[cfg(feature = "merge-split")]
152    {
153        use subms_treap::SplittableTreap;
154        // Timed as a split-then-merge ROUND TRIP, because `split` consumes the
155        // treap: rebuilding one per rep would put an O(n log n) build inside the
156        // timed region and the figure would be the build. A round trip restores
157        // the original, so the input is set up once and every rep does identical
158        // work.
159        //
160        // The sweep classifies this structural, and the reason is in `split`
161        // rather than in `split_node`: the descent is O(log n), but split then
162        // calls `count()` on BOTH halves to fill in their lengths, and that is a
163        // full traversal. An O(log n) op with an O(n) bookkeeping tail.
164        let make = |n: usize| {
165            let mut t = SplittableTreap::new(SEED);
166            for i in 0..n {
167                t.insert(key_at(i), i as u64);
168            }
169            Some(t)
170        };
171        let round_trip = |slot: &mut Option<SplittableTreap<u64, u64>>| {
172            let t = slot.take().expect("round trip restores the treap");
173            let (l, r) = t.split(&(KEY_SPACE / 2));
174            *slot = Some(SplittableTreap::merge(l, r));
175        };
176        let sw = sweep("merge-split/split+merge", |n| {
177            bulk(|| make(n), round_trip, true)
178        });
179        let (cat, reason) = classify_feature(&sw, Some(base_p50), None);
180
181        let mut p99 = BTreeMap::new();
182        p99.insert(
183            "split_merge".to_string(),
184            bulk(|| make(CANON), round_trip, false),
185        );
186        manifest.set_feature("merge-split", cat, &p99, &reason);
187    }
188
189    // ---------- concurrent-reads: a flattened immutable snapshot ----------
190    #[cfg(feature = "concurrent-reads")]
191    {
192        use subms_treap::TreapSnapshot;
193        // `from_treap` flattens the tree into a sorted Vec, so it is O(n) and the
194        // sweep says so. Lookups on the result are a binary search over that Vec,
195        // which is the point: readers pay O(log n) with no tree pointers and no
196        // coordination with the writer.
197        let sw = sweep("concurrent-reads/snapshot", |n| {
198            let t = build(n);
199            bulk(|| (), |()| _ = TreapSnapshot::from_treap(&t), true)
200        });
201        let (cat, reason) = classify_feature(&sw, Some(base_p50), None);
202
203        let t = build(CANON);
204        let snap = TreapSnapshot::from_treap(&t);
205        let mut p99 = BTreeMap::new();
206        p99.insert(
207            "snapshot".to_string(),
208            bulk(|| (), |()| _ = TreapSnapshot::from_treap(&t), false),
209        );
210        p99.insert(
211            "lookup_on_snapshot".to_string(),
212            keyed(CANON, |i| _ = snap.get(&key_at(i)), false),
213        );
214        manifest.set_feature("concurrent-reads", cat, &p99, &reason);
215    }
216
217    std::fs::create_dir_all(path.parent().unwrap())?;
218    std::fs::write(&path, manifest.to_json())?;
219    io::stdout().write_all(manifest.to_json().as_bytes())?;
220    Ok(())
221}
perf_features/perf_features.rs

perf_features/
perf_features.rs
