tree latency measured

3 files changed, 178 insertions, 3 deletions

diff --git a/src/simtest/bench.rs b/src/simtest/bench.rs
index 19603d2..40b413d 100644
--- a/src/simtest/bench.rs
+++ b/src/simtest/bench.rs
@@ -550,14 +550,16 @@ async fn run(seed: u64, scenario: &'static Scenario) -> String {
             (start, Totals::of(&nodes).await),
             converged,
         );
-        trees(&mut out, &nodes).await;
+        trees(&mut out, &nodes, &sim.net).await;
     }
     out
 }
 
 /// Every node's own writer's tree (`swarm::tree::own_shape`, `/admin/stats`), as it
-/// computes it at the end: the hops its writes take, and the members it leaves out.
-async fn trees(out: &mut String, nodes: &[AppState]) {
+/// computes it at the end: the hops its writes take, and the members it leaves out;
+/// and how long they take by the links' latencies alone, against parents chosen by
+/// latency and the fastest paths (`swarm::tree::own_latencies`).
+async fn trees(out: &mut String, nodes: &[AppState], net: &crate::transport::sim::SimNet) {
     let mut shapes = Vec::new();
     for node in nodes {
         shapes.extend(crate::swarm::tree::own_shape(node).await);
@@ -586,6 +588,38 @@ async fn trees(out: &mut String, nodes: &[AppState]) {
         },
         off as f64 / count,
     );
+
+    // Node IDs to the net's names (each node's alias).
+    let names: std::collections::HashMap<String, String> = nodes
+        .iter()
+        .filter_map(|node| Some((node.local_id().to_owned(), node.alias.clone()?)))
+        .collect();
+    let latency = |from: &str, to: &str| match (names.get(from), names.get(to)) {
+        (Some(from), Some(to)) => net.mean_delay(from, to).as_secs_f64() * 1000.0,
+        _ => f64::NAN,
+    };
+    let mut latencies = Vec::new();
+    for node in nodes {
+        latencies.extend(crate::swarm::tree::own_latencies(node, &latency).await);
+    }
+    let members: usize = latencies.iter().map(|l| l.members).sum();
+    if members == 0 {
+        return;
+    }
+    let mean = |of: fn(&crate::swarm::tree::Latencies) -> f64| {
+        latencies
+            .iter()
+            .map(|l| of(l) * l.members as f64)
+            .sum::<f64>()
+            / members as f64
+    };
+    let _ = writeln!(
+        out,
+        "    by link latency, to a member: {:.0} ms along own trees; {:.0} ms with parents chosen by latency; {:.0} ms by the fastest paths",
+        mean(|l| l.tree),
+        mean(|l| l.by_latency),
+        mean(|l| l.fastest),
+    );
 }
 
 /// The workload's counts (`during`), and the quiet phase's for as long.
diff --git a/src/swarm/tree.rs b/src/swarm/tree.rs
index d6d4a35..c84056c 100644
--- a/src/swarm/tree.rs
+++ b/src/swarm/tree.rs
@@ -273,6 +273,137 @@ fn shape(
     shape
 }
 
+/// How long our writes take to reach the members along our own tree, by link latency
+/// alone (the bench's, which knows each link's): the mean over the members it reaches
+/// (and the others do), against two other trees of ours. In one, each member's parent is chosen as now, but
+/// among those as close to us and as well placed (`rank`) by latency before pair
+/// score; in the other, every member takes the fastest path over the links members
+/// reach (no tree computed alike everywhere gets below it). In milliseconds, one way.
+#[cfg(test)]
+#[derive(Debug, Clone, Copy)]
+pub(crate) struct Latencies {
+    pub(crate) members: usize,
+    pub(crate) tree: f64,
+    pub(crate) by_latency: f64,
+    pub(crate) fastest: f64,
+}
+
+/// `Latencies` of our own tree, by `latency(from, to)` in milliseconds; None while the
+/// member list isn't known, or we aren't in it, or the tree reaches nobody.
+#[cfg(test)]
+pub(crate) async fn own_latencies(
+    state: &AppState,
+    latency: &(dyn Fn(&str, &str) -> f64 + Sync),
+) -> Option<Latencies> {
+    let me = state.local_id();
+    let (graph, distance) = distances(state, topology::pair_key(me))?;
+    let reaches = known_reaches(state, &graph).await;
+    let reached = |by: &str, member: &str| {
+        reaches
+            .get(by)
+            .is_none_or(|keys| keys.contains(&topology::pair_key(member)))
+    };
+    let members: Vec<&str> = graph
+        .keys()
+        .map(String::as_str)
+        .filter(|member| distance.get(*member).is_some_and(|d| *d > 0))
+        .collect();
+    let now: HashMap<&str, Option<&str>> = members
+        .iter()
+        .map(|member| (*member, parent(&graph, &distance, &reached, member)))
+        .collect();
+    let faster: HashMap<&str, Option<&str>> = members
+        .iter()
+        .map(|member| {
+            let its_rank = rank(&graph, &distance, &reached, member);
+            let candidate = graph
+                .get(*member)
+                .into_iter()
+                .flatten()
+                .map(String::as_str)
+                .filter(|candidate| {
+                    its_rank.is_some_and(|its| {
+                        rank(&graph, &distance, &reached, candidate).is_some_and(|r| r < its)
+                    }) && reached(member, candidate)
+                })
+                .min_by(|a, b| {
+                    let (da, fa, _) = rank(&graph, &distance, &reached, a).expect("ranked");
+                    let (db, fb, _) = rank(&graph, &distance, &reached, b).expect("ranked");
+                    (da, fa)
+                        .cmp(&(db, fb))
+                        .then(latency(a, member).total_cmp(&latency(b, member)))
+                        .then(topology::pair_score(a, member).cmp(&topology::pair_score(b, member)))
+                });
+            (*member, candidate)
+        })
+        .collect();
+    // Arrival along parents; None where the chain ends without us. Parents come
+    // before their children, so chains end.
+    fn arrival<'g>(
+        member: &'g str,
+        parents: &HashMap<&'g str, Option<&'g str>>,
+        latency: &dyn Fn(&str, &str) -> f64,
+        known: &mut HashMap<&'g str, Option<f64>>,
+    ) -> Option<f64> {
+        if let Some(at) = known.get(member) {
+            return *at;
+        }
+        let at = parents.get(member).copied().flatten().and_then(|parent| {
+            arrival(parent, parents, latency, known).map(|at| at + latency(parent, member))
+        });
+        known.insert(member, at);
+        at
+    }
+    let arrivals = |parents: &HashMap<&str, Option<&str>>| -> HashMap<&str, f64> {
+        let mut known = HashMap::from([(me, Some(0.0))]);
+        members
+            .iter()
+            .filter_map(|member| {
+                arrival(member, parents, latency, &mut known).map(|at| (*member, at))
+            })
+            .collect()
+    };
+    let (now, faster) = (arrivals(&now), arrivals(&faster));
+    // The fastest paths: Dijkstra over the links members reach (a parent `p` of
+    // `c` where `c` reaches `p`), from us.
+    let mut fastest: HashMap<&str, f64> = HashMap::from([(me, 0.0)]);
+    let mut done = std::collections::HashSet::new();
+    while let Some((&next, &at)) = fastest
+        .iter()
+        .filter(|(member, _)| !done.contains(*member))
+        .min_by(|a, b| a.1.total_cmp(b.1))
+    {
+        done.insert(next);
+        for other in graph.get(next).into_iter().flatten().map(String::as_str) {
+            if !reached(other, next) {
+                continue;
+            }
+            let through = at + latency(next, other);
+            if fastest.get(other).is_none_or(|known| through < *known) {
+                fastest.insert(other, through);
+            }
+        }
+    }
+    // Over the members all three reach (the other tree may leave out others than ours).
+    let common: Vec<&str> = now
+        .keys()
+        .copied()
+        .filter(|member| faster.contains_key(member) && fastest.contains_key(member))
+        .collect();
+    if common.is_empty() {
+        return None;
+    }
+    let mean = |times: &HashMap<&str, f64>| {
+        common.iter().map(|member| times[member]).sum::<f64>() / common.len() as f64
+    };
+    Some(Latencies {
+        members: common.len(),
+        tree: mean(&now),
+        by_latency: mean(&faster),
+        fastest: mean(&fastest),
+    })
+}
+
 /// What `writer`'s tree means for us: our children in it, and our neighbours it leaves
 /// out (`uncovered`).
 pub(crate) struct Plan {
diff --git a/src/transport/sim.rs b/src/transport/sim.rs
index d218d5c..12f3885 100644
--- a/src/transport/sim.rs
+++ b/src/transport/sim.rs
@@ -170,6 +170,16 @@ impl SimNet {
             .insert((from.to_owned(), to.to_owned()), params);
     }
 
+    /// The mean delay from `from` to `to` (one way): its link's, or the default's.
+    pub(crate) fn mean_delay(&self, from: &str, to: &str) -> Duration {
+        let inner = self.lock();
+        let link = inner
+            .links
+            .get(&(from.to_owned(), to.to_owned()))
+            .unwrap_or(&inner.default_link);
+        (link.delay.0 + link.delay.1) / 2
+    }
+
     /// Everything to and from `id` is lost until [`bring_up`](Self::bring_up), including
     /// messages already on their way. The node itself keeps running.
     pub(crate) fn take_down(&self, id: &str) {