diff options
| -rw-r--r-- | src/simtest/bench.rs | 90 | ||||
| -rw-r--r-- | src/swarm/tree.rs | 35 |
2 files changed, 125 insertions, 0 deletions
diff --git a/src/simtest/bench.rs b/src/simtest/bench.rs index 8368f7d..30a43c7 100644 --- a/src/simtest/bench.rs +++ b/src/simtest/bench.rs @@ -567,6 +567,9 @@ async fn run(seed: u64, scenario: &'static Scenario) -> String { converged, ); trees(&mut out, &nodes, &sim.net).await; + if let Some(writer) = writer { + slowest(&mut out, &nodes, &nodes[writer], &sim.net).await; + } } out } @@ -646,6 +649,93 @@ async fn trees(out: &mut String, nodes: &[AppState], net: &crate::transport::sim ); } +/// The members `writer`'s changes take longest to reach along its tree, by the links' +/// latencies alone (the parents as each member chose them, `swarm::tree::own_place`), +/// those later than `LATE_MS`: how far each is from the writer, its parent and the +/// latency to it, and the members it could take instead (they come before it) and the +/// fastest link to one. One way, in milliseconds. +async fn slowest( + out: &mut String, + nodes: &[AppState], + writer: &AppState, + net: &crate::transport::sim::SimNet, +) { + let names: HashMap<String, String> = nodes + .iter() + .filter_map(|node| Some((node.local_id().to_owned(), node.alias.clone()?))) + .collect(); + let name = |id: &str| names.get(id).cloned().unwrap_or_else(|| id.to_owned()); + let latency = + |from: &str, to: &str| net.mean_delay(&name(from), &name(to)).as_secs_f64() * 1000.0; + let mut places = HashMap::new(); + for node in nodes { + if node.local_id() != writer.local_id() + && let Some(place) = crate::swarm::tree::own_place(node, writer.local_id()).await + { + places.insert(node.local_id().to_owned(), place); + } + } + // Arrival along parents; None where the chain ends without the writer. + fn arrival( + member: &str, + writer: &str, + places: &HashMap<String, crate::swarm::tree::Place>, + latency: &dyn Fn(&str, &str) -> f64, + depth: usize, + ) -> Option<f64> { + if member == writer { + return Some(0.0); + } + let parent = places.get(member)?.parent.as_deref()?; + if depth > places.len() { + return None; + } + Some(arrival(parent, writer, places, latency, depth + 1)? + latency(parent, member)) + } + let mut late: Vec<(f64, &String)> = places + .keys() + .filter_map(|member| { + arrival(member, writer.local_id(), &places, &latency, 0).map(|at| (at, member)) + }) + .filter(|(at, _)| *at > LATE_MS as f64) + .collect(); + if late.is_empty() { + return; + } + late.sort_by(|a, b| b.0.total_cmp(&a.0)); + let listed: Vec<String> = late + .iter() + .take(5) + .map(|(at, member)| { + let place = &places[member.as_str()]; + let parent = place.parent.as_deref().unwrap_or_default(); + let fastest = place + .before + .iter() + .map(|other| (latency(other, member), other)) + .min_by(|a, b| a.0.total_cmp(&b.0)); + format!( + "{} {at:.0} ms ({} hops; from {} over {:.0} ms; of {} it could take, {})", + name(member), + place.distance, + name(parent), + latency(parent, member), + place.before.len(), + fastest.map_or_else(String::new, |(ms, other)| format!( + "{} over {ms:.0} ms", + name(other) + )), + ) + }) + .collect(); + let _ = writeln!( + out, + " later than {LATE_MS} ms by the links along the writer's tree: {}{}", + listed.join("; "), + if late.len() > 5 { "; …" } else { "" } + ); +} + /// The workload's counts (`during`), and the quiet phase's for as long. fn report( out: &mut String, diff --git a/src/swarm/tree.rs b/src/swarm/tree.rs index 0aef94c..81004e8 100644 --- a/src/swarm/tree.rs +++ b/src/swarm/tree.rs @@ -370,6 +370,41 @@ pub(crate) async fn own_parent(state: &AppState, writer: &str) -> Option<String> parent(&graph, &distance, &reached, &round_trip, state.local_id()).map(str::to_owned) } +/// Where we are in `writer`'s tree, as we see it: our distance from the writer, our +/// parent (`parent`), and the neighbours we reach that come before us (whom we could +/// take). None while the member list isn't known, or the writer or we aren't in it. +#[cfg(test)] +pub(crate) struct Place { + pub(crate) distance: u32, + pub(crate) parent: Option<String>, + pub(crate) before: Vec<String>, +} + +#[cfg(test)] +pub(crate) async fn own_place(state: &AppState, writer: &str) -> Option<Place> { + let (graph, distance) = distances(state, topology::pair_key(writer))?; + let known = known_reaches(state, &graph).await; + let reached = |by: &str, member: &str| known.reached(by, member); + let round_trip = |by: &str, member: &str| known.round_trip(by, member); + let me = state.local_id(); + let its_rank = rank(&graph, &distance, &reached, me)?; + let before = graph + .get(me) + .into_iter() + .flatten() + .filter(|candidate| { + rank(&graph, &distance, &reached, candidate).is_some_and(|r| r < its_rank) + && reached(me, candidate) + }) + .cloned() + .collect(); + Some(Place { + distance: distance[me], + parent: parent(&graph, &distance, &reached, &round_trip, me).map(str::to_owned), + before, + }) +} + /// `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)] |