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/agents.md b/agents.md index 18dc65564f2c48937ffffa7632c9141d73b21eef..66e8d6614d90b939b0a52452c00e677fa7f8d1ad 100644 --- a/agents.md +++ b/agents.md @@ -69,6 +69,7 @@ Strict **CSP** that blocks `eval` would break the current app. Other projects ma | **`RoomMintInvite` links** | **RAM only** | `AppState.invites` — not appended as `InviteMinted` today; **lost on restart** (`server/src/state.rs`, `server/src/api/rpc.rs`). Event types `InviteMinted` / `InviteRedeemed` exist for replay and a possible future persisted mint (`server/src/reducer.rs`). | | **OAuth / pending sessions** | **RAM only** | `AppState.pending_sessions` (`server/src/state.rs`, `server/src/api/auth.rs`) | | **External resolver cooldowns** | **RAM only** | `AppState.resolver_runs` — debounce/rate-limit guard for on-demand resolver buttons (`SLUG_GITHUB_RESOLVER_COOLDOWN_MS`, default 15s). Resolver results themselves are durable synthetic `Ingest` / `PostRedacted` events in `events.jsonl`. | +| **Rank-position memo** | **RAM only / derived** | `ContentState.rank_position_cache` — generation-keyed global and per-parent rank positions used to reuse one ingest's “after” ordering as the next ingest's “before” ordering. Rebuilt lazily during event replay; never persisted. | | **Reducer projection** | **Derived** | Rebuilt from log on startup; not separately persisted | If you add a new ephemeral map or start persisting something that was RAM-only, **update this table and the code comments** (`server/src/state.rs` is a good anchor). 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..c63e37619cf9cf3ffa81b78a8696478470d89f81 --- /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 full global ordering at final size: {one_global:.2} ms; memoized ingest computes it once after voting" + ); + } + + 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(); + } +} diff --git a/server/src/api/rpc.rs b/server/src/api/rpc.rs index d40778129ec3c1c14f80cc7f9090e70dcede3d31..5b1cc059f431123dfb7076421a07bc00881a95fc 100644 --- a/server/src/api/rpc.rs +++ b/server/src/api/rpc.rs @@ -18,7 +18,7 @@ use crate::{ events::{Event, Ingest, ThreadCapability}, identity::{parse_agent, parse_username}, path_types::ItemId, - ranking::{connected_components_from_voted_pairs, ranked_items_subset}, + ranking::{connected_components_from_voted_pairs, rank_partition, ranked_items_subset}, reducer::{scope_from_room_wire, ReducerState, ScopeId}, scope_rank::suggest_next_pair_in_pool, state::{AppState, InviteState}, @@ -1292,8 +1292,8 @@ pub async fn handle_rpc_batch( let offset = offset.unwrap_or(0); let want_percent = percent.unwrap_or(false); let reduced = state.reduced.read().await; - let mut content = content_for_room(&reduced, &room).clone(); - let group = &mut content.ranking_group; + let content = content_for_room(&reduced, &room); + let group = &content.ranking_group; let n = group.idx_to_item.len(); let (mut comps, _) = connected_components_from_voted_pairs( n, group.voted_pairs.iter().copied(), @@ -1301,8 +1301,7 @@ pub async fn handle_rpc_batch( comps.sort_by_key(|b| std::cmp::Reverse(b.len())); let mut ranked: Vec = Vec::new(); - for comp in &comps { - let items = ranked_items_subset(group, comp, 10000, 1e-8); + for items in rank_partition(group, &comps, 10000, 1e-8) { let top = items.first().map(|r| r.score).unwrap_or(1.0); let bot = items.last().map(|r| r.score).unwrap_or(0.0); let range = (top - bot).max(1e-12); diff --git a/server/src/ranking.rs b/server/src/ranking.rs index 38e6d09b4370e5f8cbae09c0e5760b4e7f1ef7db..06d09c55820a2fc113970bc8113abf42d8ea831b 100644 --- a/server/src/ranking.rs +++ b/server/src/ranking.rs @@ -247,6 +247,80 @@ pub fn ranked_items_subset(group: &GroupState, idxs: &[usize], max_iters: usize, items } +/// Rank several disjoint node groups with a **single** pass over the edge map. +/// +/// `groups[k]` holds indices into `group.idx_to_item`. Edges are bucketed by +/// group in one O(E) scan, so the total cost is +/// `O(N + E + Σ_k T_k·(n_k + e_k))` instead of the `O(K·E)` you get from calling +/// [`ranked_items_subset`] once per group — the filter inside that function walks +/// the whole edge map regardless of how few nodes it was asked about. +/// +/// Groups are expected to be disjoint; if a node appears in several, the last +/// group claiming it wins. Edges crossing groups are dropped, which matches the +/// induced-subgraph semantics of [`ranked_items_subset`], so ranking each +/// connected component through either path gives identical results. +pub fn rank_partition( + group: &GroupState, + groups: &[Vec], + max_iters: usize, + tol: f64, +) -> Vec> { + const UNASSIGNED: u32 = u32::MAX; + + let n = group.idx_to_item.len(); + let mut slot_group: Vec = vec![UNASSIGNED; n]; + let mut slot_local: Vec = vec![UNASSIGNED; n]; + for (gi, nodes) in groups.iter().enumerate() { + for (li, &node) in nodes.iter().enumerate() { + if node < n { + slot_group[node] = gi as u32; + slot_local[node] = li as u32; + } + } + } + + let mut buckets: Vec> = vec![Vec::new(); groups.len()]; + for (&(src, dst), &w) in &group.edges { + if src >= n || dst >= n { + continue; + } + let gi = slot_group[src]; + if gi == UNASSIGNED || gi != slot_group[dst] { + continue; + } + buckets[gi as usize].push(( + (slot_local[src] as usize, slot_local[dst] as usize), + w, + )); + } + + groups + .iter() + .zip(buckets) + .map(|(nodes, edges)| { + let scores = + compute_scores_from_edges(nodes.len(), edges.into_iter(), max_iters, tol); + let mut items: Vec = nodes + .iter() + .enumerate() + .filter_map(|(local, &global)| { + let item = group.idx_to_item.get(global)?.clone(); + Some(RankedItem { + item, + score: *scores.get(local).unwrap_or(&0.0), + }) + }) + .collect(); + items.sort_by(|a, b| { + b.score + .partial_cmp(&a.score) + .unwrap_or(std::cmp::Ordering::Equal) + }); + items + }) + .collect() +} + pub fn group_summary_scores( group: &mut GroupState, max_iters: usize, @@ -363,6 +437,63 @@ mod tests { assert_eq!(comp1, vec!["https://slug.social/c", "https://slug.social/d"]); } + /// `rank_partition` exists purely to avoid the O(components x edges) cost of + /// calling `ranked_items_subset` in a loop, so the two must stay identical. + #[test] + fn rank_partition_matches_per_component_subset_ranking() { + let mut g = mk_group(); + // Three components of different shapes: a chain, a star, and a lone pair. + g.apply_vote(vote(1, "a", "b", 3, 1)); + g.apply_vote(vote(2, "b", "c", 2, 1)); + g.apply_vote(vote(3, "c", "d", 5, 2)); + g.apply_vote(vote(4, "hub", "s1", 2, 1)); + g.apply_vote(vote(5, "hub", "s2", 4, 1)); + g.apply_vote(vote(6, "hub", "s3", 1, 3)); + g.apply_vote(vote(7, "x", "y", 7, 2)); + + let (comps, _) = connected_components_from_voted_pairs( + g.idx_to_item.len(), + g.voted_pairs.iter().copied(), + ); + assert_eq!(comps.len(), 3); + + let batched = rank_partition(&g, &comps, 10000, 1e-8); + assert_eq!(batched.len(), comps.len()); + for (comp, got) in comps.iter().zip(&batched) { + let want = ranked_items_subset(&g, comp, 10000, 1e-8); + assert_eq!(got.len(), want.len()); + for (a, b) in got.iter().zip(&want) { + assert_eq!(a.item, b.item, "ordering diverged for component {comp:?}"); + assert!( + (a.score - b.score).abs() < 1e-12, + "score diverged for {}: {} vs {}", + a.item.as_str(), + a.score, + b.score + ); + } + } + } + + /// Edges leaving a group are dropped, so a partition that splits a connected + /// component ranks each piece on its induced subgraph only. + #[test] + fn rank_partition_drops_cross_group_edges() { + let mut g = mk_group(); + g.apply_vote(vote(1, "a", "b", 3, 1)); + g.apply_vote(vote(2, "b", "c", 3, 1)); + + let idx = |s: &str| g.item_to_idx[&ItemId::parse(s).unwrap()]; + let groups = vec![vec![idx("a"), idx("b")], vec![idx("c")]]; + let out = rank_partition(&g, &groups, 10000, 1e-8); + + assert_eq!(out[0].len(), 2); + assert_eq!(out[0][0].item.as_str(), "https://slug.social/a"); + // A lone node carries the whole mass of its own subgraph. + assert_eq!(out[1].len(), 1); + assert!((out[1][0].score - 1.0).abs() < 1e-12); + } + #[test] fn subset_ranking_ranks_within_component_only() { let mut g = mk_group(); diff --git a/server/src/reducer.rs b/server/src/reducer.rs index 85b984b5ed71fa1aac25443c1360d285a9b58fef..e82e581996d6ffaac04d027ad082440af08b6e81 100644 --- a/server/src/reducer.rs +++ b/server/src/reducer.rs @@ -52,6 +52,9 @@ pub struct GroupState { pub dirty: bool, pub cached_scores: Vec, pub recent_votes: VecDeque, + /// Monotonic in-memory version of the vote graph. Derived caches use this + /// to detect whether their rankings still describe the current edges. + pub generation: u64, } impl Default for GroupState { @@ -70,6 +73,7 @@ impl GroupState { dirty: true, cached_scores: Vec::new(), recent_votes: VecDeque::with_capacity(200), + generation: 0, } } @@ -129,6 +133,10 @@ impl GroupState { while self.recent_votes.len() > 200 { self.recent_votes.pop_back(); } + self.generation = self + .generation + .checked_add(1) + .expect("vote graph generation overflow"); } } @@ -204,6 +212,15 @@ pub struct ForumThreadState { } +#[derive(Debug, Clone)] +pub(crate) struct RankPositionCache { + generation: u64, + global: HashMap, + by_parent: HashMap>, + #[cfg(test)] + recomputations: usize, +} + #[derive(Debug, Clone, Default)] pub struct ContentState { pub ranking_group: GroupState, @@ -219,6 +236,15 @@ pub struct ContentState { pub item_threads: HashMap>, /// Per-item rank history, oldest first. pub rank_history: HashMap>, + /// RAM-only memo of rank positions at `ranking_group.generation`. + /// + /// The next vote ingest's "before" positions are exactly the previous vote + /// ingest's "after" positions. Keeping the complete global ordering and + /// lazily populated parent-scope orderings avoids recomputing both before + /// every ingest. A vote bumps the generation and forces one fresh "after" + /// computation; item-only ingests do not invalidate it because isolates do + /// not affect any ranked component. + pub(crate) rank_position_cache: Option, } #[derive(Debug, Clone)] @@ -419,77 +445,152 @@ impl ReducerState { ItemId::parse(item) } - /// 1-indexed rank of `item` within its connected component in the parent scope. - /// 0 if the item has no votes connecting it to siblings (unranked). - fn scope_rank_of( + /// 1-indexed rank within its own connected component, for every child of + /// `scope`. Items with no votes connecting them to a sibling are absent. + fn scope_positions( group: &GroupState, - item: &ItemId, + scope: &ItemId, item_children: &HashMap>, - ) -> usize { - let scope = match item.parent() { - Some(p) => p, - None => return 0, - }; - let children = match item_children.get(&scope) { - None => return 0, - Some(c) => c, - }; - let &item_global_idx = match group.item_to_idx.get(item) { - None => return 0, - Some(i) => i, + ) -> HashMap { + let Some(children) = item_children.get(scope) else { + return HashMap::new(); }; - // Map scope children to compact local indices. - let sibling_idxs: Vec = children.iter() + let sibling_idxs: Vec = children + .iter() .filter_map(|c| group.item_to_idx.get(c).copied()) .collect(); - let global_to_local: HashMap = sibling_idxs.iter() - .enumerate().map(|(l, &g)| (g, l)).collect(); - let item_local = match global_to_local.get(&item_global_idx) { - None => return 0, - Some(&l) => l, - }; - // Connected components within scope. + let global_to_local: HashMap = sibling_idxs + .iter() + .enumerate() + .map(|(l, &g)| (g, l)) + .collect(); let (comps, _) = crate::ranking::connected_components_from_voted_pairs( sibling_idxs.len(), group.voted_pairs.iter().filter_map(|(a, b)| { - Some((global_to_local.get(a).copied()?, global_to_local.get(b).copied()?)) + Some(( + global_to_local.get(a).copied()?, + global_to_local.get(b).copied()?, + )) }), ); - // Find the component containing this item. - let comp_local = match comps.iter().find(|c| c.contains(&item_local)) { - None => return 0, - Some(c) => c, - }; - let comp_global: Vec = comp_local.iter() - .filter_map(|&l| sibling_idxs.get(l).copied()) + let comps_global: Vec> = comps + .iter() + .map(|c| c.iter().filter_map(|&l| sibling_idxs.get(l).copied()).collect()) .collect(); - let ranked = crate::ranking::ranked_items_subset(group, &comp_global, 10000, 1e-8); - ranked.iter().position(|r| &r.item == item).map(|i| i + 1).unwrap_or(0) - } - /// 1-indexed position of `item` in the component-aware global flat list. - /// Components sorted largest-first; items ranked within each component. - /// 0 if the item is not in the ranking group. - fn global_rank_of(group: &GroupState, item: &ItemId) -> usize { - if !group.item_to_idx.contains_key(item) { - return 0; + let mut out = HashMap::new(); + for ranked in crate::ranking::rank_partition(group, &comps_global, 10000, 1e-8) { + for (i, r) in ranked.into_iter().enumerate() { + out.insert(r.item, i + 1); + } } - let n = group.idx_to_item.len(); + out + } + + /// 1-indexed position in the component-aware global flat list, for every + /// ranked item. Components largest-first, items ranked within each component. + /// Items outside any component (isolates, unvoted) are absent. + fn global_positions(group: &GroupState) -> HashMap { let (mut comps, _) = crate::ranking::connected_components_from_voted_pairs( - n, group.voted_pairs.iter().copied(), + group.idx_to_item.len(), + group.voted_pairs.iter().copied(), ); comps.sort_by_key(|b| std::cmp::Reverse(b.len())); + + let mut out = HashMap::new(); let mut pos = 1usize; - for comp in &comps { - let ranked = crate::ranking::ranked_items_subset(group, comp, 10000, 1e-8); - for r in &ranked { - if &r.item == item { - return pos; - } + for ranked in crate::ranking::rank_partition(group, &comps, 10000, 1e-8) { + for r in ranked { + out.insert(r.item, pos); pos += 1; } } - 0 + out + } + + /// `(scope_rank, global_rank)` for each of `items`, 0 where unranked. + /// + /// Rank history needs these for every item an ingest votes on. Resolving them + /// one item at a time means re-ranking the entire graph per item — the whole + /// global ordering is computed here once, and each distinct parent scope once, + /// no matter how many items the post touches. + fn rank_positions_for( + content: &mut ContentState, + items: &[ItemId], + ) -> HashMap { + if items.is_empty() { + return HashMap::new(); + } + + let generation = content.ranking_group.generation; + let stale = content + .rank_position_cache + .as_ref() + .map_or(true, |cache| cache.generation != generation); + if stale { + let global = Self::global_positions(&content.ranking_group); + #[cfg(test)] + let recomputations = content + .rank_position_cache + .as_ref() + .map_or(1, |cache| cache.recomputations + 1); + content.rank_position_cache = Some(RankPositionCache { + generation, + global, + by_parent: HashMap::new(), + #[cfg(test)] + recomputations, + }); + } + + let parents: HashSet = items.iter().filter_map(ItemId::parent).collect(); + let missing_parents: Vec = parents + .into_iter() + .filter(|parent| { + !content + .rank_position_cache + .as_ref() + .expect("cache initialized") + .by_parent + .contains_key(parent) + }) + .collect(); + for parent in missing_parents { + let positions = Self::scope_positions( + &content.ranking_group, + &parent, + &content.item_children, + ); + content + .rank_position_cache + .as_mut() + .expect("cache initialized") + .by_parent + .insert(parent, positions); + } + + let cache = content + .rank_position_cache + .as_ref() + .expect("cache initialized"); + let mut content_positions = HashMap::with_capacity(items.len()); + for item in items { + let scope = item + .parent() + .and_then(|parent| { + cache + .by_parent + .get(&parent) + .and_then(|positions| positions.get(item).copied()) + }) + .unwrap_or(0); + let global = cache.global.get(item).copied().unwrap_or(0); + // This explicit loop keeps the cache borrowed once and avoids + // rebuilding any ranking while extracting the requested subset. + // The map is small (at most the distinct voted items in one post). + content_positions.insert(item.clone(), (scope, global)); + } + content_positions } /// Apply one ingest's DSL effects to `content` (votes, items, snippets, rank history). @@ -518,18 +619,7 @@ impl ReducerState { let before: HashMap = if !voted_items.is_empty() { crate::ranking::compute_group_ranking(&mut content.ranking_group, 10000, 1e-8); - voted_items - .iter() - .map(|it| { - ( - it.clone(), - ( - Self::scope_rank_of(&content.ranking_group, it, &content.item_children), - Self::global_rank_of(&content.ranking_group, it), - ), - ) - }) - .collect() + Self::rank_positions_for(content, &voted_items) } else { HashMap::new() }; @@ -611,9 +701,9 @@ impl ReducerState { if !voted_items.is_empty() { crate::ranking::compute_group_ranking(&mut content.ranking_group, 10000, 1e-8); let thread = canonical_thread.clone(); + let after = Self::rank_positions_for(content, &voted_items); for item in &voted_items { - let after_scope = Self::scope_rank_of(&content.ranking_group, item, &content.item_children); - let after_global = Self::global_rank_of(&content.ranking_group, item); + let (after_scope, after_global) = after.get(item).copied().unwrap_or((0, 0)); let score = content .ranking_group .item_to_idx @@ -917,3 +1007,66 @@ impl Default for ReducerState { } } } + +#[cfg(test)] +mod rank_position_cache_tests { + use super::*; + + fn ingest(id: &str, raw: &str) -> Ingest { + Ingest { + ts: 1, + id: id.to_string(), + raw: raw.to_string(), + principal: "tester".to_string(), + delegate: None, + room_id: "public".to_string(), + thread_tag: "bench".to_string(), + } + } + + #[test] + fn reuses_previous_after_positions_as_next_before_positions() { + let mut content = ContentState::default(); + ReducerState::apply_ingest_to_content( + &mut content, + &ingest( + "first", + "~/memo/a { a }\n~/memo/b { b }\n{ a wins }\n~/memo/a 2:1 ~/memo/b", + ), + ) + .unwrap(); + + let cache = content.rank_position_cache.as_ref().unwrap(); + assert_eq!(cache.generation, content.ranking_group.generation); + // Initial empty "before", then the first vote's "after". + assert_eq!(cache.recomputations, 2); + + ReducerState::apply_ingest_to_content( + &mut content, + &ingest("items-only", "~/memo/c { c }"), + ) + .unwrap(); + assert_eq!( + content + .rank_position_cache + .as_ref() + .unwrap() + .recomputations, + 2, + "adding an isolate must not invalidate ranked positions" + ); + + ReducerState::apply_ingest_to_content( + &mut content, + &ingest("second", "{ b beats c }\n~/memo/b 2:1 ~/memo/c"), + ) + .unwrap(); + let cache = content.rank_position_cache.as_ref().unwrap(); + assert_eq!(cache.generation, content.ranking_group.generation); + assert_eq!( + cache.recomputations, 3, + "the second ingest must reuse its before positions and recompute only after voting" + ); + assert_eq!(content.rank_history[&ItemId::parse("~/memo/b").unwrap()].len(), 2); + } +} diff --git a/server/src/scope_rank.rs b/server/src/scope_rank.rs index 3a019ebba45eb78c54db539c8259b514c8b0c389..0dd3590a9ef6f56b203a68b20721f2cb44e6dca0 100644 --- a/server/src/scope_rank.rs +++ b/server/src/scope_rank.rs @@ -4,7 +4,7 @@ use std::collections::{HashMap, HashSet}; use crate::path_types::ItemId; -use crate::ranking::{connected_components_from_voted_pairs, ranked_items_subset, RankedItem}; +use crate::ranking::{connected_components_from_voted_pairs, rank_partition, RankedItem}; use crate::reducer::{ContentState, GroupState}; #[derive(Debug, Clone)] @@ -114,24 +114,44 @@ pub fn build_rankings_for_item_set( comps_local.sort_by(|a, b| b.len().cmp(&a.len()).then_with(|| a.cmp(b))); - let component_rankings: Vec = comps_local + // Rank every component in one pass over the edge map, and count each + // component's pairs in one pass over `voted_pairs`. Doing either per + // component costs O(components x edges), which dominates page render time + // once a scope fragments into many small clusters. + let comps_global: Vec> = comps_local .iter() .map(|comp_local| { - let comp_global: Vec = comp_local + comp_local .iter() .filter_map(|li| local_to_global.get(*li).copied()) - .collect(); - let comp_set: HashSet = comp_global.iter().copied().collect(); - let ranked = ranked_items_subset(group, &comp_global, 10000, 1e-8); - let pairs = group - .voted_pairs - .iter() - .filter(|(i, j)| comp_set.contains(i) && comp_set.contains(j)) - .count(); - ScopedComponent { pairs, ranked } + .collect() }) .collect(); + let mut comp_of_local: Vec> = vec![None; scoped_idxs.len()]; + for (ci, comp_local) in comps_local.iter().enumerate() { + for &li in comp_local { + comp_of_local[li] = Some(ci); + } + } + let mut pair_counts: Vec = vec![0; comps_local.len()]; + for (i, j) in &group.voted_pairs { + let (Some(&li), Some(&lj)) = (global_to_local.get(i), global_to_local.get(j)) else { + continue; + }; + if let (Some(ci), Some(cj)) = (comp_of_local[li], comp_of_local[lj]) { + if ci == cj { + pair_counts[ci] += 1; + } + } + } + + let component_rankings: Vec = rank_partition(group, &comps_global, 10000, 1e-8) + .into_iter() + .zip(pair_counts) + .map(|(ranked, pairs)| ScopedComponent { pairs, ranked }) + .collect(); + let mut unranked_items: Vec = isolate_local_idxs .into_iter() .filter_map(|li| local_to_global.get(li).copied()) @@ -284,6 +304,7 @@ mod tests { item_snippets: HashMap::new(), item_threads: HashMap::new(), rank_history: HashMap::new(), + rank_position_cache: None, } } @@ -366,6 +387,7 @@ mod tests { item_snippets: HashMap::new(), item_threads: HashMap::new(), rank_history: HashMap::new(), + rank_position_cache: None, }; let roots = external_root_host_items(&content); assert_eq!(roots, vec![gh]);