add writer tree benchmark

2 files changed, 152 insertions, 1 deletions

diff --git a/docs/development.md b/docs/development.md
index cb42492..f56562e 100644
--- a/docs/development.md
+++ b/docs/development.md
@@ -21,7 +21,10 @@ The benchmarks are ignored tests named `bench_*`: the document's (writes and syn
 messages, `document/bench.rs`), the remakes' replay (`remake/bench.rs`), and what
 passing changes on costs over the simulated network (`simtest/bench.rs`: messages and
 bytes per write by kind, propagation delays, for a full mesh, a writer behind NAT, two
-transports and partial meshes of 50 and 100 nodes; about a quarter of an hour). One of
+transports and partial meshes of 50 and 100 nodes; about a quarter of an hour), and
+the same estimated on the member list's graph alone for up to 2000 members, with some
+links down, as now and along the writer's tree (`swarm/topology/tests.rs`,
+`bench_writer_trees`). One of
 them alone: `cargo test --release --features mycelium,libp2p,tor,dashboard
 bench_propagation -- --ignored --nocapture`.
 
diff --git a/src/swarm/topology/tests.rs b/src/swarm/topology/tests.rs
index d3a3e38..807ea63 100644
--- a/src/swarm/topology/tests.rs
+++ b/src/swarm/topology/tests.rs
@@ -311,3 +311,151 @@ fn hub_degree_is_bounded_in_large_swarms() {
         hub_degree_is_bounded(n, stable_count);
     }
 }
+
+/// What passing one change on costs over the graph the member list gives, by the
+/// number of messages, while some links don't work (`down`: a share of them, chosen by
+/// their members' keys): as now (every node that gets it tells all its neighbours but
+/// the one it came from, over the links that work), and along the writer's tree.
+///
+/// The tree: every member's distance from the writer over the member list's graph (as
+/// every node computes it alike), and each member's parent the neighbour it reaches
+/// (as it tells its neighbours, `swarm::reach`) that comes first by distance, then pair
+/// score, of those before it (by distance, then pair key: no cycles). Whoever has a
+/// change of the writer's passes it on to its children in the writer's tree, however
+/// it got it. A member with no parent it reaches waits for an announcement from a
+/// neighbour that has it (a pull), then passes it on to its own children.
+///
+/// Reported per change: messages along the tree, pulls, the share that got it along the
+/// tree alone, and how many announcement rounds the last one waited. Arrival in
+/// breadth-first order: no delays, no losses. A benchmark: `cargo benchmarks`.
+#[test]
+#[ignore = "a benchmark: cargo benchmarks"]
+fn bench_writer_trees() {
+    use std::collections::{HashMap, HashSet};
+    // Along the tree from `from`, to all below it: the messages counted in `total`.
+    fn along<'a>(
+        from: &'a str,
+        children: &HashMap<&'a str, Vec<&'a str>>,
+        has: &mut HashSet<&'a str>,
+        total: &mut usize,
+    ) {
+        let mut queue = VecDeque::from([from]);
+        has.insert(from);
+        while let Some(m) = queue.pop_front() {
+            for &child in children.get(m).map_or(&[][..], Vec::as_slice) {
+                *total += 1;
+                if has.insert(child) {
+                    queue.push_back(child);
+                }
+            }
+        }
+    }
+    println!();
+    let k = 12;
+    for n in [13, 50, 100, 250, 1000, 2000] {
+        let ms = members(n);
+        let g = graph(&ms, k);
+        let key: HashMap<&str, u64> = ms.iter().map(|m| (m.as_str(), pair_key(m))).collect();
+        let degree: f64 = g.values().map(BTreeSet::len).sum::<usize>() as f64 / n as f64;
+        let sources: Vec<&str> = ms
+            .iter()
+            .step_by((n / 10).max(1))
+            .map(String::as_str)
+            .collect();
+        for down_percent in [0, 5, 20] {
+            let works =
+                |a: &str, b: &str| g[a].contains(b) && mix(key[a] ^ key[b]) % 100 >= down_percent;
+            let (mut now_total, mut tree_total, mut pulls_total) = (0usize, 0usize, 0usize);
+            let (mut eager_total, mut reached_total) = (0usize, 0usize);
+            let (mut depth_max, mut children_max, mut rounds_max) = (0usize, 0usize, 0usize);
+            for &source in &sources {
+                // As now, over the links that work.
+                let mut seen: HashSet<&str> = HashSet::from([source]);
+                let mut queue: VecDeque<(&str, Option<&str>)> = VecDeque::from([(source, None)]);
+                while let Some((m, from)) = queue.pop_front() {
+                    for next in &g[m] {
+                        if Some(next.as_str()) == from || !works(m, next) {
+                            continue;
+                        }
+                        now_total += 1;
+                        if seen.insert(next.as_str()) {
+                            queue.push_back((next.as_str(), Some(m)));
+                        }
+                    }
+                }
+                // Distances over the member list's graph.
+                let mut depth: HashMap<&str, usize> = HashMap::from([(source, 0)]);
+                let mut order = vec![source];
+                let mut at = 0;
+                while at < order.len() {
+                    let m = order[at];
+                    at += 1;
+                    for next in &g[m] {
+                        if !depth.contains_key(next.as_str()) {
+                            depth.insert(next.as_str(), depth[m] + 1);
+                            order.push(next.as_str());
+                        }
+                    }
+                }
+                depth_max = depth_max.max(depth.values().copied().max().unwrap_or(0));
+                // Each member's parent: one it reaches, before it.
+                let rank = |m: &str| (depth[m], key[m]);
+                let mut children: HashMap<&str, Vec<&str>> = HashMap::new();
+                for &m in &order[1..] {
+                    let parent = g[m]
+                        .iter()
+                        .map(String::as_str)
+                        .filter(|p| rank(p) < rank(m) && works(m, p))
+                        .min_by_key(|p| (depth[p], pair_score(p, m)));
+                    if let Some(parent) = parent {
+                        children.entry(parent).or_default().push(m);
+                    }
+                }
+                children_max = children_max.max(children.values().map(Vec::len).max().unwrap_or(0));
+                // Along the tree from whoever has it; then pulls where announcements
+                // reach, round by round.
+                let mut has: HashSet<&str> = HashSet::new();
+                along(source, &children, &mut has, &mut tree_total);
+                eager_total += has.len();
+                let mut rounds = 0;
+                loop {
+                    let pulling: Vec<&str> = ms
+                        .iter()
+                        .map(String::as_str)
+                        .filter(|m| {
+                            !has.contains(m)
+                                && g[*m]
+                                    .iter()
+                                    .any(|x| has.contains(x.as_str()) && works(m, x))
+                        })
+                        .collect();
+                    if pulling.is_empty() {
+                        break;
+                    }
+                    rounds += 1;
+                    for m in pulling {
+                        if !has.contains(m) {
+                            pulls_total += 1;
+                            along(m, &children, &mut has, &mut tree_total);
+                        }
+                    }
+                }
+                rounds_max = rounds_max.max(rounds);
+                reached_total += has.len();
+            }
+            let changes = sources.len() as f64;
+            let share = |count: usize| 100.0 * count as f64 / changes / n as f64;
+            println!(
+                "{n:>5} members, {degree:.1} neighbours, {down_percent:>2}% of links down: per change \
+                 {:>6.0} messages now; along the writer's tree {:>5.0}, and {:>4.0} pulls \
+                 ({:.1}% along the tree alone, {:.1}% in all, the last after {rounds_max} \
+                 announcement rounds; {depth_max} hops, {children_max} children at most)",
+                now_total as f64 / changes,
+                tree_total as f64 / changes,
+                pulls_total as f64 / changes,
+                share(eager_total),
+                share(reached_total),
+            );
+        }
+    }
+}