bench eager tree depth

1 files changed, 52 insertions, 3 deletions

diff --git a/src/simtest/bench.rs b/src/simtest/bench.rs
index affdf69..dd0d4eb 100644
--- a/src/simtest/bench.rs
+++ b/src/simtest/bench.rs
@@ -615,7 +615,7 @@ async fn run(seed: u64, scenario: &'static Scenario) -> String {
         );
         trees(&mut out, &nodes, &sim.net).await;
         sent_kept(&mut out, &nodes).await;
-        eager_links(&mut out, &nodes);
+        eager_links(&mut out, &nodes, &sim.net);
         if let Some(writer) = writer {
             slowest(&mut out, &nodes, &nodes[writer], &sim.net).await;
         }
@@ -749,8 +749,11 @@ fn mean(values: &[u64]) -> u64 {
 /// node pushes to at once (eager), how many push to it, the nodes none pushes to (they
 /// get every change by announcement and pull), the links eager at one end only (a
 /// PRUNE or GRAFT lost, or crossing), and the round trips of eager links against lazy
-/// ones (does the tree take slow links?). Nothing for a way that keeps no such links.
-fn eager_links(out: &mut String, nodes: &[AppState]) {
+/// ones (does the tree take slow links?). And how far each member is from every other
+/// along eager links alone, by the links' latencies (the fastest such path, as the
+/// first copy of a push takes it), against writers' trees' (`trees`): how deep the
+/// tree is. Nothing for a way that keeps no such links.
+fn eager_links(out: &mut String, nodes: &[AppState], net: &crate::transport::sim::SimNet) {
     let mut pushes: HashMap<String, Vec<String>> = HashMap::new();
     // The round trips of eager and of lazy links, as each node measured them.
     let (mut eager_rtts, mut lazy_rtts) = (Vec::new(), Vec::new());
@@ -823,6 +826,52 @@ fn eager_links(out: &mut String, nodes: &[AppState]) {
         eager_rtts.iter().filter(|rtt| **rtt > SLOW_LINK_MS).count(),
         mean(&lazy_rtts),
     );
+    // From each member, the fastest path to every other along eager links (Dijkstra,
+    // by the net's mean one-way delays), and its hops.
+    let ids: Vec<&String> = pushes.keys().collect();
+    let delay =
+        |from: &str, to: &str| net.mean_delay(&name(from), &name(to)).as_secs_f64() * 1000.0;
+    let (mut latency_sum, mut hops_sum, mut hops_most, mut reached, mut unreached) =
+        (0.0, 0usize, 0usize, 0usize, 0usize);
+    for root in &ids {
+        let mut best: HashMap<&str, (f64, usize)> = HashMap::new();
+        best.insert(root.as_str(), (0.0, 0));
+        let mut done: std::collections::HashSet<&str> = std::collections::HashSet::new();
+        loop {
+            let next = best
+                .iter()
+                .filter(|(id, _)| !done.contains(*id))
+                .min_by(|(_, a), (_, b)| a.0.total_cmp(&b.0))
+                .map(|(id, at)| (*id, *at));
+            let Some((id, (at, hops))) = next else {
+                break;
+            };
+            done.insert(id);
+            for peer in pushes.get(id).into_iter().flatten() {
+                let via = at + delay(id, peer);
+                let known = best.get(peer.as_str());
+                if known.is_none_or(|(known, _)| via < *known) {
+                    best.insert(peer.as_str(), (via, hops + 1));
+                }
+            }
+        }
+        for (id, (at, hops)) in &best {
+            if *id != root.as_str() {
+                latency_sum += at;
+                hops_sum += hops;
+                hops_most = hops_most.max(*hops);
+                reached += 1;
+            }
+        }
+        unreached += ids.len() - best.len();
+    }
+    let reached_f = reached.max(1) as f64;
+    let _ = writeln!(
+        out,
+        "    along PlumTree's eager links, to a member: {:.0} ms by link latency; {:.2} hops on average, {hops_most} at most; {unreached} not reached",
+        latency_sum / reached_f,
+        hops_sum as f64 / reached_f,
+    );
 }
 
 /// Whether the nodes' views of the writers' trees agree: each member's parent as the