diff --git a/Cargo.lock b/Cargo.lock index a07734f089b466440c3ae6fc1087ce85fc24ce62..1a96b62ec0a40c61587e5eec105ac6929db5237b 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -11,6 +11,12 @@ dependencies = [ "memchr", ] +[[package]] +name = "anes" +version = "0.1.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4b46cbb362ab8752921c97e041f5e366ee6297bd428a31275b9fcf1e380f7299" + [[package]] name = "anstream" version = "0.6.21" @@ -93,6 +99,12 @@ version = "1.1.2" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "1505bd5d3d116872e7271a6d4e16d81d0c8570876c8de68093a09ac269d8aac0" +[[package]] +name = "autocfg" +version = "1.5.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f2032f911046de80f0a198e0901378627c33f59ea0ac00e363d481118bd70a53" + [[package]] name = "axum" version = "0.7.9" @@ -224,6 +236,12 @@ version = "1.11.1" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "1e748733b7cbc798e1434b6ac524f0c1ff2ab456fe201501e6497c8417a4fc33" +[[package]] +name = "cast" +version = "0.3.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "37b2a672a2cb129a2e41c10b1224bb368f9f37a2b16b612598138befd7b37eb5" + [[package]] name = "cc" version = "1.2.56" @@ -246,6 +264,33 @@ version = "0.2.1" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "613afe47fcd5fac7ccf1db93babcb082c5994d996f20b8b159f2ad1658eb5724" +[[package]] +name = "ciborium" +version = "0.2.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "42e69ffd6f0917f5c029256a24d0161db17cea3997d185db0d35926308770f0e" +dependencies = [ + "ciborium-io", + "ciborium-ll", + "serde", +] + +[[package]] +name = "ciborium-io" +version = "0.2.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "05afea1e0a06c9be33d539b876f1ce3692f4afea2cb41f740e7743225ed1c757" + +[[package]] +name = "ciborium-ll" +version = "0.2.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "57663b653d948a338bfb3eeba9bb2fd5fcfaecb9e199e87e1eda4d9e8b240fd9" +dependencies = [ + "ciborium-io", + "half", +] + [[package]] name = "clap" version = "4.5.60" @@ -347,12 +392,79 @@ dependencies = [ "libc", ] +[[package]] +name = "criterion" +version = "0.5.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f2b12d017a929603d80db1831cd3a24082f8137ce19c69e6447f54f5fc8d692f" +dependencies = [ + "anes", + "cast", + "ciborium", + "clap", + "criterion-plot", + "is-terminal", + "itertools", + "num-traits", + "once_cell", + "oorandom", + "plotters", + "rayon", + "regex", + "serde", + "serde_derive", + "serde_json", + "tinytemplate", + "walkdir", +] + +[[package]] +name = "criterion-plot" +version = "0.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6b50826342786a51a89e2da3a28f1c32b06e387201bc2d19791f622c673706b1" +dependencies = [ + "cast", + "itertools", +] + [[package]] name = "critical-section" version = "1.2.0" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "790eea4361631c5e7d22598ecd5723ff611904e3344ce8720784c93e3d83d40b" +[[package]] +name = "crossbeam-deque" +version = "0.8.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5181e0de7b61eb03a81e347d6dd8797bae9da5146707b51077e2d71a54ec0ceb" +dependencies = [ + "crossbeam-epoch", + "crossbeam-utils", +] + +[[package]] +name = "crossbeam-epoch" +version = "0.9.20" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "2d6914041f254d6e9176c01941b21115dcfb7089e55135a35411081bd106ef3f" +dependencies = [ + "crossbeam-utils", +] + +[[package]] +name = "crossbeam-utils" +version = "0.8.22" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "61803da095bee82a81bb1a452ecc25d3b2f1416d1897eb86430c6159ef717c17" + +[[package]] +name = "crunchy" +version = "0.2.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "460fbee9c2c2f33933d720630a6a0bac33ba7053db5344fac858d4b8952d77d5" + [[package]] name = "crypto-common" version = "0.1.7" @@ -393,6 +505,12 @@ dependencies = [ "syn", ] +[[package]] +name = "either" +version = "1.17.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9e5e8f6c15a24b9a3ee5efec809ccd006d3b30e8b3bb63c39af737c7f87daa1d" + [[package]] name = "embedded-io" version = "0.4.0" @@ -610,6 +728,17 @@ dependencies = [ "tracing", ] +[[package]] +name = "half" +version = "2.7.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6ea2d84b969582b4b1864a92dc5d27cd2b77b622a8d79306834f1be5ba20d84b" +dependencies = [ + "cfg-if", + "crunchy", + "zerocopy", +] + [[package]] name = "hash32" version = "0.2.1" @@ -654,6 +783,12 @@ version = "0.5.0" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "2304e00983f87ffb38b55b444b5e3b60a884b5d30c0fca7d82fe33449bbe55ea" +[[package]] +name = "hermit-abi" +version = "0.5.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "fc0fef456e4baa96da950455cd02c081ca953b141298e41db3fc7e36b1da849c" + [[package]] name = "http" version = "1.4.0" @@ -923,12 +1058,32 @@ dependencies = [ "serde", ] +[[package]] +name = "is-terminal" +version = "0.4.17" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3640c1c38b8e4e43584d8df18be5fc6b0aa314ce6ebf51b53313d4306cca8e46" +dependencies = [ + "hermit-abi", + "libc", + "windows-sys 0.61.2", +] + [[package]] name = "is_terminal_polyfill" version = "1.70.2" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "a6cb138bb79a146c1bd460005623e142ef0181e3d0219cb493e02f7d08a35695" +[[package]] +name = "itertools" +version = "0.10.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b0fd2260e829bddf4cb6ea802289de2f86d6a7a690192fbe91b3f46e0f2c8473" +dependencies = [ + "either", +] + [[package]] name = "itoa" version = "1.0.17" @@ -1123,6 +1278,15 @@ version = "0.2.0" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "cf97ec579c3c42f953ef76dbf8d55ac91fb219dde70e49aa4a6b7d74e9919050" +[[package]] +name = "num-traits" +version = "0.2.19" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "071dfc062690e90b734c0b2273ce72ad0ffa95f0c74596bc250dcfd960262841" +dependencies = [ + "autocfg", +] + [[package]] name = "once_cell" version = "1.21.3" @@ -1135,6 +1299,12 @@ version = "1.70.2" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "384b8ab6d37215f3c5301a95a4accb5d64aa607f1fcb26a11b5303878451b4fe" +[[package]] +name = "oorandom" +version = "11.1.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d6790f58c7ff633d8771f42965289203411a5e5c68388703c06e14f24770b41e" + [[package]] name = "openssl" version = "0.10.75" @@ -1203,6 +1373,34 @@ version = "0.3.32" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "7edddbd0b52d732b21ad9a5fab5c704c14cd949e5e9a1ec5929a24fded1b904c" +[[package]] +name = "plotters" +version = "0.3.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5aeb6f403d7a4911efb1e33402027fc44f29b5bf6def3effcc22d7bb75f2b747" +dependencies = [ + "num-traits", + "plotters-backend", + "plotters-svg", + "wasm-bindgen", + "web-sys", +] + +[[package]] +name = "plotters-backend" +version = "0.3.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "df42e13c12958a16b3f7f4386b9ab1f3e7933914ecea48da7139435263a4172a" + +[[package]] +name = "plotters-svg" +version = "0.3.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "51bae2ac328883f7acdfea3d66a7c35751187f870bc81f94563733a154d7a670" +dependencies = [ + "plotters-backend", +] + [[package]] name = "postcard" version = "1.1.3" @@ -1412,6 +1610,38 @@ dependencies = [ "getrandom 0.3.4", ] +[[package]] +name = "rayon" +version = "1.12.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "fb39b166781f92d482534ef4b4b1b2568f42613b53e5b6c160e24cfbfa30926d" +dependencies = [ + "either", + "rayon-core", +] + +[[package]] +name = "rayon-core" +version = "1.13.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "22e18b0f0062d30d4230b2e85ff77fdfe4326feb054b9783a3460d8435c8ab91" +dependencies = [ + "crossbeam-deque", + "crossbeam-utils", +] + +[[package]] +name = "regex" +version = "1.12.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e10754a14b9137dd7b1e3e5b0493cc9171fdd105e0ab477f51b72e7f3ac0e276" +dependencies = [ + "aho-corasick", + "memchr", + "regex-automata", + "regex-syntax", +] + [[package]] name = "regex-automata" version = "0.4.14" @@ -1575,6 +1805,15 @@ version = "1.0.23" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "9774ba4a74de5f7b1c1451ed6cd5285a32eddb5cccb8cc655a4e50009e06477f" +[[package]] +name = "same-file" +version = "1.0.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "93fc1dc3aaa9bfed95e02e6eadabb4baf7e3078b0bd1b4d7b6b0b68378900502" +dependencies = [ + "winapi-util", +] + [[package]] name = "schannel" version = "0.1.28" @@ -1785,6 +2024,7 @@ dependencies = [ "axum-extra", "base64", "bytes", + "criterion", "futures-util", "http", "maud", @@ -2019,6 +2259,16 @@ dependencies = [ "zerovec", ] +[[package]] +name = "tinytemplate" +version = "1.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "be4d6b5f19ff7664e8c98d03e2139cb510db9b0a60b55f8e8709b689d939b6bc" +dependencies = [ + "serde", + "serde_json", +] + [[package]] name = "tinyvec" version = "1.10.0" @@ -2337,6 +2587,16 @@ version = "0.9.5" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "0b928f33d975fc6ad9f86c8f283853ad26bdd5b10b7f1542aa2fa15e2289105a" +[[package]] +name = "walkdir" +version = "2.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "29790946404f91d9c5d06f9874efddea1dc06c5efe94541a7d6863108e3a5e4b" +dependencies = [ + "same-file", + "winapi-util", +] + [[package]] name = "want" version = "0.3.1" @@ -2492,6 +2752,15 @@ dependencies = [ "rustls-pki-types", ] +[[package]] +name = "winapi-util" +version = "0.1.11" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c2a7b1c03c876122aa43f3020e6c3c3ee5c05081c9a00739faf7503aeba10d22" +dependencies = [ + "windows-sys 0.61.2", +] + [[package]] name = "windows-link" version = "0.2.1" diff --git a/server/Cargo.toml b/server/Cargo.toml index 0d9cdcd21d94751babdf769e118d2c89d6a009d8..7de0c944b4a8c7e3123b818432fce82f09e6aeca 100644 --- a/server/Cargo.toml +++ b/server/Cargo.toml @@ -35,5 +35,18 @@ urlencoding = "2" tempfile = "3" http = "1" quinn-proto = "0.11.14" # pin: RUSTSEC-2026-0008 +criterion = { version = "0.5", features = ["html_reports"] } + +[[bench]] +name = "ranking_kernel" +harness = false + +[[bench]] +name = "garden_render" +harness = false + +[[bench]] +name = "ingest_replay" +harness = false diff --git a/server/benches/common/mod.rs b/server/benches/common/mod.rs new file mode 100644 index 0000000000000000000000000000000000000000..0efccef671e849359cf1925dbd3d215c3286e161 --- /dev/null +++ b/server/benches/common/mod.rs @@ -0,0 +1,276 @@ +//! Synthetic graph + ingest generators shared by the ranking benchmarks. +//! +//! Everything here is deterministic (xorshift PRNG, fixed seeds) so successive +//! criterion runs compare like for like. + +#![allow(dead_code)] + +use slugsocial_server::events::{Event, Ingest}; +use slugsocial_server::path_types::ItemId; +use slugsocial_server::reducer::{ContentState, GroupState, ReducerState, VoteData}; + +/// Deterministic xorshift64* so benchmarks never depend on `rand` seeding. +pub struct Rng(u64); + +impl Rng { + pub fn new(seed: u64) -> Self { + Rng(seed | 1) + } + + pub fn next_u64(&mut self) -> u64 { + let mut x = self.0; + x ^= x >> 12; + x ^= x << 25; + x ^= x >> 27; + self.0 = x; + x.wrapping_mul(0x2545_F491_4F6C_DD1D) + } + + pub fn below(&mut self, n: usize) -> usize { + (self.next_u64() % n as u64) as usize + } +} + +/// Comparison-graph shapes. Each stresses a different term in the cost model: +/// `Clique` maximizes edge count `E`, `Chain` maximizes the number of power +/// iterations (spectral gap shrinks as `1/n^2`), `ManyComponents` maximizes the +/// component count `C` that scoped ranking loops over. +#[derive(Clone, Copy, Debug)] +pub enum Topology { + /// Path graph `0-1-2-…-(n-1)`. Worst-case mixing time. + Chain, + /// One hub compared against every other node. Sparse, fast mixing. + Star, + /// Every pair compared. `E = n(n-1)`, dense but well conditioned. + Clique, + /// `n` nodes, `degree * n / 2` random pairs. Realistic sparse graph. + RandomSparse { degree: usize }, + /// `components` disjoint chains of `size` nodes each. + ManyComponents { components: usize, size: usize }, +} + +impl Topology { + pub fn label(&self) -> String { + match self { + Topology::Chain => "chain".into(), + Topology::Star => "star".into(), + Topology::Clique => "clique".into(), + Topology::RandomSparse { degree } => format!("sparse-d{degree}"), + Topology::ManyComponents { components, size } => { + format!("comps{components}x{size}") + } + } + } + + /// Unordered pairs (i, j) with i < j that should receive a vote. + pub fn pairs(&self, n: usize) -> Vec<(usize, usize)> { + let mut out = Vec::new(); + match *self { + Topology::Chain => { + for i in 0..n.saturating_sub(1) { + out.push((i, i + 1)); + } + } + Topology::Star => { + for i in 1..n { + out.push((0, i)); + } + } + Topology::Clique => { + for i in 0..n { + for j in (i + 1)..n { + out.push((i, j)); + } + } + } + Topology::RandomSparse { degree } => { + let mut rng = Rng::new(0xC0FFEE ^ n as u64); + // Spanning chain first so the graph stays one component, then + // random chords up to the requested average degree. + for i in 0..n.saturating_sub(1) { + out.push((i, i + 1)); + } + let extra = degree.saturating_sub(2) * n / 2; + for _ in 0..extra { + let a = rng.below(n); + let b = rng.below(n); + if a != b { + out.push((a.min(b), a.max(b))); + } + } + } + Topology::ManyComponents { components, size } => { + for c in 0..components { + let base = c * size; + for i in 0..size.saturating_sub(1) { + out.push((base + i, base + i + 1)); + } + } + } + } + out + } + + /// Total node count implied by the topology for a nominal size `n`. + pub fn node_count(&self, n: usize) -> usize { + match *self { + Topology::ManyComponents { components, size } => components * size, + _ => n, + } + } +} + +pub fn item_name(i: usize) -> String { + format!("~/bench/i{i:06}") +} + +pub fn item_id(i: usize) -> ItemId { + ItemId::parse(&item_name(i)).expect("valid item id") +} + +pub fn vote_data(a: usize, b: usize, ratio_left: i32, ratio_right: i32, ts: i64) -> VoteData { + VoteData { + ts, + a: item_id(a), + b: item_id(b), + ratio_left, + ratio_right, + body: "synthetic".to_string(), + principal: "bench".to_string(), + delegate: None, + thread_tag: "bench".to_string(), + } +} + +/// Build a `GroupState` directly (skips DSL parsing) for kernel benchmarks. +/// +/// Every node is registered up front so `idx_to_item` order matches the +/// topology's node numbering, then one vote is applied per pair. Ratios vary +/// slightly so the stationary distribution is non-degenerate. +pub fn build_group(topo: Topology, n: usize) -> GroupState { + let total = topo.node_count(n); + let mut g = GroupState::new(); + for i in 0..total { + g.ensure_item_pub(&item_name(i)); + } + for (k, (i, j)) in topo.pairs(total).into_iter().enumerate() { + let left = 2 + (k % 5) as i32; + g.apply_vote(vote_data(i, j, left, 1, k as i64)); + } + g +} + +/// A `ContentState` whose `ranking_group` matches `build_group` and whose +/// `item_children` puts every node under a single parent (`~/bench`), which is +/// what garden pages resolve when rendering a scope. +pub fn build_content(topo: Topology, n: usize) -> ContentState { + let total = topo.node_count(n); + let mut content = ContentState::default(); + content.ranking_group = build_group(topo, n); + let parent = ItemId::parse("~/bench").expect("parent"); + let children = content.item_children.entry(parent).or_default(); + for i in 0..total { + children.insert(item_id(i)); + } + for i in 0..total { + content.items.insert(item_id(i)); + content + .item_bodies + .insert(item_id(i), format!("body of item {i}")); + } + content +} + +pub fn bench_parent() -> ItemId { + ItemId::parse("~/bench").expect("parent") +} + +/// All nodes of the topology as an explicit scope list. +pub fn scope_items(topo: Topology, n: usize) -> Vec { + (0..topo.node_count(n)).map(item_id).collect() +} + +// --------------------------------------------------------------------------- +// DSL-level generators (exercise parse + reducer, not just the kernel) +// --------------------------------------------------------------------------- + +/// Render a `.sorter` document declaring `items` and casting `votes`. +pub fn synth_document(item_idxs: &[usize], vote_pairs: &[(usize, usize)]) -> String { + let mut s = String::with_capacity(item_idxs.len() * 48 + vote_pairs.len() * 64); + s.push_str("#bench\n\n"); + for &i in item_idxs { + s.push_str(&format!("{} {{ synthetic item {i} }}\n", item_name(i))); + } + s.push('\n'); + for (k, &(a, b)) in vote_pairs.iter().enumerate() { + let left = 2 + (k % 5); + s.push_str(&format!( + "{{ synthetic comparison {k} }}\n{} {left}:1 {}\n", + item_name(a), + item_name(b) + )); + } + s +} + +pub fn ingest_event(id: usize, raw: String) -> Event { + Event::Ingest(Ingest { + ts: 1_700_000_000_000 + id as i64, + id: format!("bench-{id:06}"), + raw, + principal: "bench".to_string(), + delegate: None, + room_id: "public".to_string(), + thread_tag: "bench".to_string(), + }) +} + +/// A stream of ingests that grows one garden: each post declares `votes_per_post` +/// new comparisons over a pool of `n` items, chained so the graph stays connected. +/// +/// This mirrors the real durable path — every post appends to `events.jsonl` and +/// is replayed through `ReducerState::apply_event` on boot. +pub fn synth_ingest_stream(posts: usize, votes_per_post: usize, n: usize) -> Vec { + let mut events = Vec::with_capacity(posts); + let mut rng = Rng::new(0xBEEF); + let mut next_new_item = 0usize; + + for p in 0..posts { + let mut items = Vec::new(); + let mut pairs = Vec::new(); + for _ in 0..votes_per_post { + // Bias toward introducing fresh items until the pool is full, then + // compare existing ones — the shape a real garden fills in over time. + let a = if next_new_item < n { + let a = next_new_item; + next_new_item += 1; + items.push(a); + a + } else { + rng.below(n) + }; + let b = if next_new_item < n { + let b = next_new_item; + next_new_item += 1; + items.push(b); + b + } else { + rng.below(n) + }; + if a != b { + pairs.push((a, b)); + } + } + events.push(ingest_event(p, synth_document(&items, &pairs))); + } + events +} + +/// Replay a prebuilt event stream into a fresh reducer, exactly as boot does. +pub fn replay(events: &[Event]) -> ReducerState { + let mut state = ReducerState::default(); + for e in events { + state.apply_event(e.clone()); + } + state +} diff --git a/server/benches/garden_render.rs b/server/benches/garden_render.rs new file mode 100644 index 0000000000000000000000000000000000000000..be9b40837e5e6dadd1923f702f00cd3078b6b7de --- /dev/null +++ b/server/benches/garden_render.rs @@ -0,0 +1,109 @@ +//! Page-render benchmarks: what a single `GET /~/bench` costs. +//! +//! Garden pages call `scope_rank::build_children_rankings` synchronously on every +//! request with no caching (see AGENTS.md durability matrix — the reducer +//! projection is derived, and scoped rankings are not memoized at all). +//! +//! Cost model for `build_rankings_for_item_set(content, items)` with `S` items in +//! scope, `C` connected components among them, `E` directed edges and `P` voted +//! pairs in the *whole* group: +//! +//! component split = O(S + P) +//! per component = O(E) — `ranked_items_subset` filters all of `group.edges` +//! + O(P) — the `pairs` count re-scans all of `voted_pairs` +//! + O(T*(n_c + e_c)) +//! total = O(S + C * (E + P) + Σ_c T_c * (n_c + e_c)) +//! +//! The `C * (E + P)` term is the problem: it is independent of component size, so +//! a scope of 5000 items split into 2500 pairwise components costs 2500 full scans +//! of the group's edge and pair maps. `component_fanout` isolates that term by +//! holding total item count fixed while varying how it is partitioned. + +use criterion::{criterion_group, criterion_main, BenchmarkId, Criterion, Throughput}; +use std::hint::black_box; + +use slugsocial_server::scope_rank::{build_children_rankings, build_rankings_for_item_set}; + +mod common; +use common::{bench_parent, build_content, scope_items, Topology}; + +/// One connected scope of growing size — the "healthy garden" case. +fn single_component_scope(c: &mut Criterion) { + let mut g = c.benchmark_group("render/single_component"); + g.sample_size(10); + + for n in [256usize, 1024, 4096] { + let content = build_content(Topology::RandomSparse { degree: 6 }, n); + let parent = bench_parent(); + g.throughput(Throughput::Elements(n as u64)); + g.bench_with_input(BenchmarkId::from_parameter(n), &content, |b, content| { + b.iter(|| black_box(build_children_rankings(content, &parent).component_rankings.len())) + }); + } + g.finish(); +} + +/// Fixed 4096 items in scope, partitioned into ever more components. +/// +/// Total power-iteration work *falls* as components shrink, so any growth in +/// wall time is pure `C * (E + P)` overhead from the per-component rescans. +fn component_fanout(c: &mut Criterion) { + let mut g = c.benchmark_group("render/component_fanout"); + g.sample_size(10); + + const TOTAL: usize = 4096; + for size in [1024usize, 256, 64, 16, 4, 2] { + let components = TOTAL / size; + let topo = Topology::ManyComponents { components, size }; + let content = build_content(topo, TOTAL); + let parent = bench_parent(); + g.throughput(Throughput::Elements(components as u64)); + g.bench_with_input( + BenchmarkId::new("components", components), + &content, + |b, content| { + b.iter(|| { + black_box(build_children_rankings(content, &parent).component_rankings.len()) + }) + }, + ); + } + g.finish(); +} + +/// Chain components: worst mixing *and* high component count together. This is +/// the shape a real garden drifts toward — many small, weakly-connected clusters +/// of siblings that were each compared a handful of times. +fn worst_case_scope(c: &mut Criterion) { + let mut g = c.benchmark_group("render/worst_case"); + g.sample_size(10); + + for (components, size) in [(500usize, 8usize), (2000, 8), (2000, 32)] { + let topo = Topology::ManyComponents { components, size }; + let content = build_content(topo, components * size); + let items = scope_items(topo, components * size); + g.throughput(Throughput::Elements((components * size) as u64)); + g.bench_with_input( + BenchmarkId::new(format!("{components}x{size}"), components * size), + &(content, items), + |b, (content, items)| { + b.iter(|| { + black_box( + build_rankings_for_item_set(content, items) + .component_rankings + .len(), + ) + }) + }, + ); + } + g.finish(); +} + +criterion_group!( + benches, + single_component_scope, + component_fanout, + worst_case_scope +); +criterion_main!(benches); diff --git a/server/benches/ingest_replay.rs b/server/benches/ingest_replay.rs new file mode 100644 index 0000000000000000000000000000000000000000..fdbe77eba8ee07715e35af1addb2c2d72072aad1 --- /dev/null +++ b/server/benches/ingest_replay.rs @@ -0,0 +1,176 @@ +//! Write-path and boot-replay benchmarks — the slowest thing the server does. +//! +//! `ReducerState::apply_ingest_to_content` recomputes rankings twice per post +//! (once before applying votes to capture "before" ranks for rank history, once +//! after) and, for each of the `U` distinct items mentioned in a vote, calls both +//! `scope_rank_of` and `global_rank_of` on each side of that pair. +//! +//! Per ingest, with `N` items / `E` edges / `P` voted pairs / `C` components in +//! the group and `T` power iterations: +//! +//! 2 × compute_group_ranking = O(E + T·(N + E)) +//! 2U × scope_rank_of = O(U · (P + E + T·(n_s + e_s))) +//! 2U × global_rank_of = O(U · C · (E + P)) + O(U · T · (N + E)) +//! ──────────────────────────────────────────────────────────────────── +//! per ingest ≈ O(U · C · E) +//! +//! `global_rank_of` is the dominant term: to find one item's position it ranks +//! *every* connected component in the group from scratch, and each of those calls +//! rescans the full edge map. It is called 2U times per post and its result is a +//! single integer written into `rank_history`. +//! +//! Boot replay is `Σ` of that over every post in `events.jsonl`, and because `C`, +//! `E` and `N` all grow with the number of posts, replay of `M` posts is +//! super-quadratic in `M` — this is the ~20s benchmark below. + +use criterion::{criterion_group, criterion_main, BenchmarkId, Criterion, Throughput}; +use std::hint::black_box; + +use slugsocial_server::reducer::ReducerState; + +mod common; +use common::{ingest_event, replay, synth_document, synth_ingest_stream, Rng}; + +/// One post applied to an already-large garden. Isolates the per-write cost that +/// a user waits on when submitting through `POST /api/v0/rpc`. +fn single_ingest_into_existing_garden(c: &mut Criterion) { + let mut g = c.benchmark_group("ingest/single_post"); + g.sample_size(10); + + // Kept small on purpose: building each base garden is itself a replay, and + // replay is super-quadratic, so a 3200-post base would take hours to set up. + for existing_posts in [50usize, 100, 135] { + let warmup = synth_ingest_stream(existing_posts, 4, existing_posts * 2); + let base = replay(&warmup); + + // The new post compares two items already present in the garden. + let raw = synth_document(&[], &[(0, 1)]); + let event = ingest_event(existing_posts, raw); + + g.throughput(Throughput::Elements(1)); + g.bench_with_input( + BenchmarkId::from_parameter(existing_posts), + &(base, event), + |b, (base, event)| { + b.iter_batched( + || base.clone(), + |mut state| { + state.apply_event(event.clone()); + black_box(state.public().ranking_group.idx_to_item.len()) + }, + criterion::BatchSize::LargeInput, + ) + }, + ); + } + g.finish(); +} + +/// A single post carrying many votes. Shows the `U` factor: rank history is +/// recomputed per voted item, so a bulk import post pays `global_rank_of` once +/// per item it touches rather than once for the post. +fn votes_per_post_scaling(c: &mut Criterion) { + let mut g = c.benchmark_group("ingest/votes_per_post"); + g.sample_size(10); + + const POOL: usize = 200; + let warmup = synth_ingest_stream(100, 4, POOL); + let base = replay(&warmup); + + for votes in [1usize, 4, 16, 64] { + let mut rng = Rng::new(0x5EED ^ votes as u64); + let pairs: Vec<(usize, usize)> = (0..votes) + .map(|_| { + let a = rng.below(POOL); + let b = (a + 1 + rng.below(POOL - 1)) % POOL; + (a, b) + }) + .collect(); + let event = ingest_event(9999, synth_document(&[], &pairs)); + + g.throughput(Throughput::Elements(votes as u64)); + g.bench_with_input( + BenchmarkId::from_parameter(votes), + &(base.clone(), event), + |b, (base, event)| { + b.iter_batched( + || base.clone(), + |mut state| { + state.apply_event(event.clone()); + black_box(state.public().ranking_group.edges.len()) + }, + criterion::BatchSize::LargeInput, + ) + }, + ); + } + g.finish(); +} + +/// Cold boot: replay the whole event log. `server/src/main.rs` does exactly this +/// before the process starts serving, so this benchmark *is* startup latency. +/// +/// Scaling sweep — the per-post cost grows with log length, so wall time grows +/// faster than linearly in `posts`. +fn boot_replay_scaling(c: &mut Criterion) { + let mut g = c.benchmark_group("replay/scaling"); + g.sample_size(10); + + for posts in [25usize, 50, 75, 100] { + let events = synth_ingest_stream(posts, 4, posts * 2); + g.throughput(Throughput::Elements(posts as u64)); + g.bench_with_input(BenchmarkId::from_parameter(posts), &events, |b, events| { + b.iter(|| { + let mut state = ReducerState::default(); + for e in events { + state.apply_event(e.clone()); + } + black_box(state.public().ranking_group.idx_to_item.len()) + }) + }); + } + g.finish(); +} + +/// The slow path, sized so one iteration costs roughly 20 seconds. +/// +/// 135 posts × 4 votes builds a garden of only 270 items and 536 compared pairs +/// — a genuinely small instance. Nothing here is adversarial: ordinary ratios, +/// four votes per post, one parent scope, no redactions. Override the size with +/// `SLUG_BENCH_REPLAY_POSTS` (cost scales ≈ M^2.5, so 200 posts ≈ 50s). +/// +/// Criterion runs 10 samples, so budget ~4 minutes of wall clock for this group. +fn boot_replay_slow_path(c: &mut Criterion) { + let mut g = c.benchmark_group("replay/slow_path"); + g.sample_size(10); + g.sampling_mode(criterion::SamplingMode::Flat); + g.measurement_time(std::time::Duration::from_secs(300)); + g.warm_up_time(std::time::Duration::from_secs(1)); + + let posts = std::env::var("SLUG_BENCH_REPLAY_POSTS") + .ok() + .and_then(|v| v.parse::().ok()) + .unwrap_or(135); + let events = synth_ingest_stream(posts, 4, posts * 2); + + g.throughput(Throughput::Elements(posts as u64)); + g.bench_function(BenchmarkId::new("posts", posts), |b| { + b.iter(|| { + let mut state = ReducerState::default(); + for e in &events { + state.apply_event(e.clone()); + } + black_box(state.public().ranking_group.idx_to_item.len()) + }) + }); + g.finish(); +} + +criterion_group!( + benches, + single_ingest_into_existing_garden, + votes_per_post_scaling, + boot_replay_scaling, + boot_replay_slow_path +); +criterion_main!(benches); diff --git a/server/benches/ranking_kernel.rs b/server/benches/ranking_kernel.rs new file mode 100644 index 0000000000000000000000000000000000000000..4d5c6824e7abc828957bbf39677200ab3eea2999 --- /dev/null +++ b/server/benches/ranking_kernel.rs @@ -0,0 +1,168 @@ +//! Kernel-level benchmarks for Rank Centrality power iteration. +//! +//! Cost model for `ranking::compute_scores_from_edges(n, edges, K, tol)`: +//! +//! setup = O(E) — raw collect, pairwise normalize, adjacency build +//! iterate= O(T * (n + E)) — T = iterations actually run, capped at K = 10_000 +//! total = O(E + T * (n + E)) +//! +//! `T` is governed by the spectral gap of the Markov chain, not by `n` directly. +//! For a path graph the gap is Θ(1/n²), so T ≈ Θ(n² · log(1/tol)) and the 10k cap +//! binds at surprisingly small n. For a star or clique the gap is Θ(1) and T is +//! a few dozen. `topology_convergence` is the group that shows this split. + +use criterion::{criterion_group, criterion_main, BenchmarkId, Criterion, Throughput}; +use std::hint::black_box; + +use slugsocial_server::ranking::{ + compute_group_ranking, connected_components_from_voted_pairs, ranked_items_subset, +}; + +mod common; +use common::{build_group, Topology}; + +const MAX_ITERS: usize = 10_000; +const TOL: f64 = 1e-8; + +/// How the graph shape (not just its size) drives iteration count. +fn topology_convergence(c: &mut Criterion) { + let mut g = c.benchmark_group("kernel/topology"); + g.sample_size(20); + + for n in [64usize, 256, 1024] { + for topo in [ + Topology::Chain, + Topology::Star, + Topology::RandomSparse { degree: 6 }, + ] { + let base = build_group(topo, n); + g.throughput(Throughput::Elements(n as u64)); + g.bench_with_input( + BenchmarkId::new(topo.label(), n), + &base, + |b, base| { + b.iter_batched_ref( + || base.clone(), + |group| { + group.dirty = true; + compute_group_ranking(group, MAX_ITERS, TOL); + black_box(group.cached_scores.len()) + }, + criterion::BatchSize::SmallInput, + ) + }, + ); + } + } + g.finish(); +} + +/// Dense graphs: E grows as n², so per-iteration cost dominates. +fn dense_graphs(c: &mut Criterion) { + let mut g = c.benchmark_group("kernel/clique"); + g.sample_size(10); + + for n in [64usize, 128, 256] { + let base = build_group(Topology::Clique, n); + let edges = base.edges.len() as u64; + g.throughput(Throughput::Elements(edges)); + g.bench_with_input(BenchmarkId::from_parameter(n), &base, |b, base| { + b.iter_batched_ref( + || base.clone(), + |group| { + group.dirty = true; + compute_group_ranking(group, MAX_ITERS, TOL); + black_box(group.cached_scores.len()) + }, + criterion::BatchSize::SmallInput, + ) + }); + } + g.finish(); +} + +/// `ranked_items_subset` filters the *whole* `group.edges` map on every call, so +/// ranking a 2-node component inside a 100k-edge group still pays O(E). +/// +/// The two arms below rank the same tiny subset out of groups of growing size. +/// Flat-ish per-element cost here would mean the filter is cheap; it is not. +fn subset_pays_full_edge_scan(c: &mut Criterion) { + let mut g = c.benchmark_group("kernel/subset_edge_scan"); + g.sample_size(20); + + for n in [1024usize, 4096, 16384] { + let group = build_group(Topology::RandomSparse { degree: 6 }, n); + let tiny: Vec = vec![0, 1]; + g.throughput(Throughput::Elements(group.edges.len() as u64)); + g.bench_with_input( + BenchmarkId::new("rank_2_of_n", n), + &(group, tiny), + |b, (group, idxs)| { + b.iter(|| black_box(ranked_items_subset(group, idxs, MAX_ITERS, TOL).len())) + }, + ); + } + g.finish(); +} + +/// Undirected BFS over voted pairs: O(n + P). This one is honest. +fn connected_components(c: &mut Criterion) { + let mut g = c.benchmark_group("kernel/connected_components"); + g.sample_size(50); + + for n in [1024usize, 16384, 131072] { + let group = build_group(Topology::RandomSparse { degree: 6 }, n); + g.throughput(Throughput::Elements(group.voted_pairs.len() as u64)); + g.bench_with_input(BenchmarkId::from_parameter(n), &group, |b, group| { + b.iter(|| { + let (comps, isolates) = connected_components_from_voted_pairs( + group.idx_to_item.len(), + group.voted_pairs.iter().copied(), + ); + black_box(comps.len() + isolates.len()) + }) + }); + } + g.finish(); +} + +/// The `dirty` flag is the only cache in the system. Confirms a warm read is free +/// and quantifies exactly what a single spurious invalidation costs. +fn cache_hit_vs_miss(c: &mut Criterion) { + let mut g = c.benchmark_group("kernel/cache"); + g.sample_size(20); + + let base = build_group(Topology::RandomSparse { degree: 6 }, 4096); + + let mut warm = base.clone(); + compute_group_ranking(&mut warm, MAX_ITERS, TOL); + g.bench_function("hit", |b| { + b.iter(|| { + compute_group_ranking(black_box(&mut warm), MAX_ITERS, TOL); + black_box(warm.cached_scores.len()) + }) + }); + + g.bench_function("miss", |b| { + b.iter_batched_ref( + || base.clone(), + |group| { + group.dirty = true; + compute_group_ranking(group, MAX_ITERS, TOL); + black_box(group.cached_scores.len()) + }, + criterion::BatchSize::SmallInput, + ) + }); + g.finish(); +} + +criterion_group!( + benches, + topology_convergence, + dense_graphs, + subset_pays_full_edge_scan, + connected_components, + cache_hit_vs_miss +); +criterion_main!(benches); diff --git a/server/examples/bench_probe.rs b/server/examples/bench_probe.rs new file mode 100644 index 0000000000000000000000000000000000000000..74fc324542807dd9d1c90806be368a268c4b1f82 --- /dev/null +++ b/server/examples/bench_probe.rs @@ -0,0 +1,412 @@ +//! Sizing probe for the ranking benchmarks: prints graph shape and wall time for +//! boot replay at several log lengths so bench parameters can be calibrated. +//! +//! Run: `cargo run --release -p slugsocial-server --example bench_probe` + +use std::time::Instant; + +use slugsocial_server::ranking::{ + compute_group_ranking, connected_components_from_voted_pairs, ranked_items_subset, +}; +use slugsocial_server::reducer::{GroupState, ReducerState, VoteData}; +use slugsocial_server::scope_rank::build_rankings_for_item_set; +use slugsocial_server::path_types::ItemId; +use slugsocial_server::events::{Event, Ingest}; + +fn item_name(i: usize) -> String { + format!("~/bench/i{i:06}") +} + +fn item_id(i: usize) -> ItemId { + ItemId::parse(&item_name(i)).unwrap() +} + +struct Rng(u64); +impl Rng { + fn new(s: u64) -> Self { + Rng(s | 1) + } + fn next_u64(&mut self) -> u64 { + let mut x = self.0; + x ^= x >> 12; + x ^= x << 25; + x ^= x >> 27; + self.0 = x; + x.wrapping_mul(0x2545_F491_4F6C_DD1D) + } + fn below(&mut self, n: usize) -> usize { + (self.next_u64() % n as u64) as usize + } +} + +fn vote(a: usize, b: usize, l: i32, ts: i64) -> VoteData { + VoteData { + ts, + a: item_id(a), + b: item_id(b), + ratio_left: l, + ratio_right: 1, + body: "synthetic".into(), + principal: "bench".into(), + delegate: None, + thread_tag: "bench".into(), + } +} + +fn chain_group(n: usize) -> GroupState { + let mut g = GroupState::new(); + for i in 0..n { + g.ensure_item_pub(&item_name(i)); + } + for i in 0..n - 1 { + g.apply_vote(vote(i, i + 1, 2, i as i64)); + } + g +} + +fn sparse_group(n: usize, degree: usize) -> GroupState { + let mut g = GroupState::new(); + let mut rng = Rng::new(0xC0FFEE ^ n as u64); + for i in 0..n { + g.ensure_item_pub(&item_name(i)); + } + let mut ts = 0i64; + for i in 0..n - 1 { + g.apply_vote(vote(i, i + 1, 2, ts)); + ts += 1; + } + for _ in 0..(degree.saturating_sub(2) * n / 2) { + let a = rng.below(n); + let b = rng.below(n); + if a != b { + g.apply_vote(vote(a, b, 3, ts)); + ts += 1; + } + } + g +} + +/// Pure random pairing with no spanning backbone — matches what the replay +/// workload actually builds once the item pool is full. +fn random_group(n: usize, votes: usize) -> GroupState { + let mut g = GroupState::new(); + let mut rng = Rng::new(0xD00D ^ n as u64); + for i in 0..n { + g.ensure_item_pub(&item_name(i)); + } + for ts in 0..votes { + let a = rng.below(n); + let b = rng.below(n); + if a != b { + g.apply_vote(vote(a, b, 2, ts as i64)); + } + } + g +} + +fn synth_document(items: &[usize], pairs: &[(usize, usize)]) -> String { + let mut s = String::from("#bench\n\n"); + for &i in items { + s.push_str(&format!("{} {{ synthetic item {i} }}\n", item_name(i))); + } + s.push('\n'); + for (k, &(a, b)) in pairs.iter().enumerate() { + let left = 2 + (k % 5); + s.push_str(&format!( + "{{ synthetic comparison {k} }}\n{} {left}:1 {}\n", + item_name(a), + item_name(b) + )); + } + s +} + +fn stream(posts: usize, votes_per_post: usize, n: usize) -> Vec { + let mut rng = Rng::new(0xBEEF); + let mut next_new = 0usize; + let mut out = Vec::with_capacity(posts); + for p in 0..posts { + let mut items = Vec::new(); + let mut pairs = Vec::new(); + for _ in 0..votes_per_post { + let a = if next_new < n { + let a = next_new; + next_new += 1; + items.push(a); + a + } else { + rng.below(n) + }; + let b = if next_new < n { + let b = next_new; + next_new += 1; + items.push(b); + b + } else { + rng.below(n) + }; + if a != b { + pairs.push((a, b)); + } + } + out.push(Event::Ingest(Ingest { + ts: 1_700_000_000_000 + p as i64, + id: format!("bench-{p:06}"), + raw: synth_document(&items, &pairs), + principal: "bench".into(), + delegate: None, + room_id: "public".into(), + thread_tag: "bench".into(), + })); + } + out +} + +fn main() { + println!("== iteration counts (power iteration convergence) =="); + for n in [16usize, 32, 64, 128, 256, 512, 1024] { + let mut g = chain_group(n); + let t = Instant::now(); + compute_group_ranking(&mut g, 10_000, 1e-8); + let chain_ms = t.elapsed().as_secs_f64() * 1000.0; + + let mut s = sparse_group(n, 6); + let t = Instant::now(); + compute_group_ranking(&mut s, 10_000, 1e-8); + let sparse_ms = t.elapsed().as_secs_f64() * 1000.0; + + println!( + "n={n:6} chain: {chain_ms:9.3} ms (E={:6}) sparse-d6: {sparse_ms:9.3} ms (E={:6})", + g.edges.len(), + s.edges.len() + ); + } + + // `max_iters` is a parameter, so sweeping it reveals where the loop actually + // stops: once wall time stops growing with the cap, the tolerance was met. + // If time keeps growing all the way to 10_000, the cap is binding and the + // returned scores are NOT converged. + println!("\n== where does power iteration actually stop? (time vs max_iters cap) =="); + println!("{:<28} {:>9} {:>9} {:>9} {:>9} {:>9}", "graph", "k=10", "k=100", "k=1000", "k=10000", "verdict"); + for (label, g) in [ + ("chain n=256", chain_group(256)), + ("chain n=1024", chain_group(1024)), + ("sparse d6 n=1024", sparse_group(1024, 6)), + ("random n=280 v=550 (replay)", random_group(280, 550)), + ("random n=400 v=800 (replay)", random_group(400, 800)), + ("clique n=128", { + let mut g = GroupState::new(); + for i in 0..128 { + g.ensure_item_pub(&item_name(i)); + } + let mut ts = 0i64; + for i in 0..128 { + for j in (i + 1)..128 { + g.apply_vote(vote(i, j, 2, ts)); + ts += 1; + } + } + g + }), + ] { + let idxs: Vec = (0..g.idx_to_item.len()).collect(); + let mut times = Vec::new(); + for k in [10usize, 100, 1000, 10_000] { + let t = Instant::now(); + let reps = if k >= 1000 { 3 } else { 20 }; + for _ in 0..reps { + let _ = ranked_items_subset(&g, &idxs, k, 1e-8); + } + times.push(t.elapsed().as_secs_f64() * 1000.0 / reps as f64); + } + // Still growing between k=1000 and k=10000 means the cap binds. + let saturated = times[3] > times[2] * 3.0; + println!( + "{label:<28} {:>8.2}ms {:>8.2}ms {:>8.2}ms {:>8.2}ms {}", + times[0], + times[1], + times[2], + times[3], + if saturated { "CAP BINDS (not converged)" } else { "converged early" } + ); + } + + println!("\n== subset ranking pays full edge scan =="); + for n in [1024usize, 4096, 16384, 65536] { + let g = sparse_group(n, 6); + let t = Instant::now(); + for _ in 0..100 { + let _ = ranked_items_subset(&g, &[0, 1], 10_000, 1e-8); + } + let us = t.elapsed().as_secs_f64() * 1e6 / 100.0; + println!( + "group n={n:6} E={:7} rank 2 items: {us:10.1} us", + g.edges.len() + ); + } + + println!("\n== garden page render: fixed 4096 items, varying component count =="); + for size in [1024usize, 256, 64, 16, 4, 2] { + let comps = 4096 / size; + let mut content = slugsocial_server::reducer::ContentState::default(); + let mut g = GroupState::new(); + for i in 0..4096 { + g.ensure_item_pub(&item_name(i)); + } + let mut ts = 0i64; + for c in 0..comps { + let base = c * size; + for i in 0..size - 1 { + g.apply_vote(vote(base + i, base + i + 1, 2, ts)); + ts += 1; + } + } + content.ranking_group = g; + let parent = ItemId::parse("~/bench").unwrap(); + let children = content.item_children.entry(parent).or_default(); + for i in 0..4096 { + children.insert(item_id(i)); + } + let items: Vec = (0..4096).map(item_id).collect(); + + let t = Instant::now(); + let r = build_rankings_for_item_set(&content, &items); + let ms = t.elapsed().as_secs_f64() * 1000.0; + println!( + "components={comps:5} size={size:5} render: {ms:10.3} ms (got {} comps)", + r.component_rankings.len() + ); + } + + println!("\n== connected components (honest O(n+P)) =="); + for n in [16384usize, 65536, 262144] { + let g = sparse_group(n, 6); + let t = Instant::now(); + let (c, i) = connected_components_from_voted_pairs( + g.idx_to_item.len(), + g.voted_pairs.iter().copied(), + ); + let ms = t.elapsed().as_secs_f64() * 1000.0; + println!("n={n:7} P={:8} cc: {ms:9.3} ms ({} comps, {} isolates)", g.voted_pairs.len(), c.len(), i.len()); + } + + // Attribute the per-post cost: replay the same 135 posts with the vote lines + // stripped (items only), then rebuild the identical vote graph directly into + // a GroupState. Whatever is left over is the rank-history machinery. + println!("\n== cost attribution for a 135-post replay =="); + { + let posts = 135usize; + let events = stream(posts, 4, posts * 2); + + let t = Instant::now(); + let mut full = ReducerState::default(); + for e in &events { + full.apply_event(e.clone()); + } + let full_s = t.elapsed().as_secs_f64(); + + // Items only: same item declarations, zero votes -> zero ranking work. + // Regenerated (not line-filtered) so the documents stay well formed. + let items_only: Vec = events + .iter() + .enumerate() + .map(|(p, e)| { + let Event::Ingest(i) = e else { unreachable!() }; + let declared: Vec = i + .raw + .lines() + .filter_map(|l| l.strip_prefix("~/bench/i")) + .filter_map(|rest| rest.split_whitespace().next()) + .filter_map(|num| num.parse::().ok()) + .collect(); + let _ = p; + Event::Ingest(Ingest { + raw: synth_document(&declared, &[]), + ..i.clone() + }) + }) + .collect(); + let t = Instant::now(); + let mut novote = ReducerState::default(); + for e in &items_only { + novote.apply_event(e.clone()); + } + let parse_s = t.elapsed().as_secs_f64(); + + // Raw graph construction only. + let g_final = full.public().ranking_group.clone(); + let t = Instant::now(); + let mut g = GroupState::new(); + for (idx, it) in g_final.idx_to_item.iter().enumerate() { + let _ = idx; + g.ensure_item_pub(it.as_str()); + } + for (k, (i, j)) in g_final.voted_pairs.iter().enumerate() { + g.apply_vote(vote(*i, *j, 2, k as i64)); + } + let graph_s = t.elapsed().as_secs_f64(); + + println!("full replay : {full_s:8.3} s"); + println!(" DSL parse + item bookkeeping : {parse_s:8.3} s ({:5.1}%)", parse_s / full_s * 100.0); + println!(" raw vote-graph construction : {graph_s:8.3} s ({:5.1}%)", graph_s / full_s * 100.0); + println!( + " ranking + rank-history : {:8.3} s ({:5.1}%)", + full_s - parse_s - graph_s, + (full_s - parse_s - graph_s) / full_s * 100.0 + ); + + // How much of that is component fan-out inside global_rank_of? + let (comps, iso) = connected_components_from_voted_pairs( + g_final.idx_to_item.len(), + g_final.voted_pairs.iter().copied(), + ); + let sizes: Vec = { + let mut s: Vec = comps.iter().map(|c| c.len()).collect(); + s.sort_unstable_by(|a, b| b.cmp(a)); + s + }; + println!( + "final graph: N={} E={} P={} components={} (largest {:?}) isolates={}", + g_final.idx_to_item.len(), + g_final.edges.len(), + g_final.voted_pairs.len(), + comps.len(), + &sizes[..sizes.len().min(5)], + iso.len() + ); + + // One global_rank_of-equivalent: rank every component from scratch. + let t = Instant::now(); + for c in &comps { + let _ = ranked_items_subset(&g_final, c, 10_000, 1e-8); + } + let one_global = t.elapsed().as_secs_f64() * 1000.0; + println!( + "one global_rank_of at final size: {one_global:.2} ms; ingest calls it 2 x (distinct voted items) = up to 16 x per post" + ); + } + + println!("\n== boot replay scaling (the slow path) =="); + let sweep: Vec = std::env::args() + .nth(1) + .map(|a| a.split(',').filter_map(|s| s.parse().ok()).collect()) + .unwrap_or_else(|| vec![135]); + for posts in sweep { + let events = stream(posts, 4, posts * 2); + let t = Instant::now(); + let mut state = ReducerState::default(); + for e in &events { + state.apply_event(e.clone()); + } + let secs = t.elapsed().as_secs_f64(); + let pub_ = state.public(); + println!( + "posts={posts:6} replay: {secs:9.3} s N={:6} E={:7} P={:7} ({:.2} ms/post)", + pub_.ranking_group.idx_to_item.len(), + pub_.ranking_group.edges.len(), + pub_.ranking_group.voted_pairs.len(), + secs * 1000.0 / posts as f64 + ); + std::io::Write::flush(&mut std::io::stdout()).ok(); + } +}