From 31d25938a299fe16d9b1019998b5e5a68b9b7d78 Mon Sep 17 00:00:00 2001
From: tv <tv@krebsco.de>
Date: Sun, 8 Nov 2026 20:29:04 +0000
Subject: screen: order changes by their places, each hash looked up once

in_order is about a seventh of screening in the profile, most of it
hashing change hashes: each change went into and out of three maps,
and each dependency into two. Look each hash up once, in a map from
hash to place, and keep the rest by place in vectors.
---
 src/access/screen.rs | 72 ++++++++++++++++++++++++++--------------------------
 1 file changed, 36 insertions(+), 36 deletions(-)

(limited to 'src/access')

diff --git a/src/access/screen.rs b/src/access/screen.rs
index 3fbc7ab..0ff7ff2 100644
--- a/src/access/screen.rs
+++ b/src/access/screen.rs
@@ -780,56 +780,56 @@ fn reaches_signed(
     })
 }
 
-/// `candidates` in an order where every change comes after its dependencies among them
-/// (ready), and those with a dependency neither in `doc` nor among them, nor ready
-/// (unready).
+/// `candidates` (each once) in an order where every change comes after its
+/// dependencies among them (ready), and those with a dependency neither in `doc` nor
+/// among them, nor ready (unready). By their places in `candidates`, each hash looked
+/// up once: hashing them costs more than the rest of ordering them.
 fn in_order(doc: &Document, candidates: Vec<Change>) -> (Vec<Change>, Vec<Change>) {
-    let mut by_hash: HashMap<ChangeHash, Change> = candidates
-        .into_iter()
-        .map(|change| (change.hash(), change))
+    let place: HashMap<ChangeHash, usize> = candidates
+        .iter()
+        .enumerate()
+        .map(|(at, change)| (change.hash(), at))
         .collect();
     // Each one's dependencies among these not placed yet, and those building on each;
     // one with a dependency neither in the document nor among these is never placed,
     // nor anything building on it.
-    let mut unplaced: HashMap<ChangeHash, usize> = HashMap::new();
-    let mut building: HashMap<ChangeHash, Vec<ChangeHash>> = HashMap::new();
-    let mut next: std::collections::BTreeSet<ChangeHash> = std::collections::BTreeSet::new();
-    for (hash, change) in &by_hash {
-        let mut among = 0;
-        let mut missing = false;
+    let mut unplaced = vec![0usize; candidates.len()];
+    let mut building: Vec<Vec<usize>> = vec![Vec::new(); candidates.len()];
+    let mut missing = vec![false; candidates.len()];
+    for (at, change) in candidates.iter().enumerate() {
         for dep in change.deps() {
-            if by_hash.contains_key(dep) {
-                among += 1;
-                building.entry(*dep).or_default().push(*hash);
-            } else if !crate::document::changes::holds(doc, dep) {
-                missing = true;
+            match place.get(dep) {
+                Some(&of) => {
+                    unplaced[at] += 1;
+                    building[of].push(at);
+                }
+                None if !crate::document::changes::holds(doc, dep) => missing[at] = true,
+                None => {}
             }
         }
-        if missing {
-            continue;
-        }
-        if among == 0 {
-            next.insert(*hash);
-        } else {
-            unplaced.insert(*hash, among);
-        }
     }
     // The smallest hash of those ready first: the same order on every node, whatever
     // order they came in.
-    let mut ready = Vec::new();
-    while let Some(hash) = next.pop_first() {
-        ready.push(by_hash.remove(&hash).expect("there"));
-        for child in building.remove(&hash).unwrap_or_default() {
-            if let Some(left) = unplaced.get_mut(&child) {
-                *left -= 1;
-                if *left == 0 {
-                    unplaced.remove(&child);
-                    next.insert(child);
-                }
+    let mut next: BTreeSet<(ChangeHash, usize)> = (0..candidates.len())
+        .filter(|&at| unplaced[at] == 0 && !missing[at])
+        .map(|at| (candidates[at].hash(), at))
+        .collect();
+    let mut order = Vec::new();
+    while let Some((_, at)) = next.pop_first() {
+        order.push(at);
+        for &child in &building[at] {
+            unplaced[child] -= 1;
+            if unplaced[child] == 0 && !missing[child] {
+                next.insert((candidates[child].hash(), child));
             }
         }
     }
-    (ready, by_hash.into_values().collect())
+    let mut slots: Vec<Option<Change>> = candidates.into_iter().map(Some).collect();
+    let ready = order
+        .into_iter()
+        .filter_map(|at| slots[at].take())
+        .collect();
+    (ready, slots.into_iter().flatten().collect())
 }
 
 #[cfg(test)]
-- 
cgit v1.3.1