tree latency measured

1 files changed, 131 insertions, 0 deletions

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 {