@@ -115,7 +115,7 @@ impl FileAnalyzer for NpmPackageAnalyzer {
                 EXPORTS_GUARD,
                 "exports_guard_pop",
             );
-            replace_edge(graph, pkg_name_pop, exports_guard_pop, 1);
+            set_edge_precedence(graph, pkg_name_pop, exports_guard_pop, 1);
             let main = Some(npm_pkg.main)
                 .filter(|main| !main.is_empty())
                 .and_then(|main| NormalizedRelativePath::from_str(&main))
 
@@ -61,12 +61,16 @@ pub fn add_edge(graph: &mut StackGraph, from: Handle<Node>, to: Handle<Node>, pr
     graph.add_edge(from, to, precedence);
 }
 
-pub fn replace_edge(graph: &mut StackGraph, from: Handle<Node>, to: Handle<Node>, precedence: i32) {
+pub fn set_edge_precedence(
+    graph: &mut StackGraph,
+    from: Handle<Node>,
+    to: Handle<Node>,
+    precedence: i32,
+) {
     if from == to {
         return;
     }
-    graph.remove_edge(from, to);
-    graph.add_edge(from, to, precedence);
+    graph.set_edge_precedence(from, to, precedence);
 }
 
 pub fn add_module_pops(
 
@@ -49,7 +49,7 @@ use crate::stitching::ToAppendable;
 
 /// Helps detect similar paths in the path-finding algorithm.
 pub struct SimilarPathDetector<P> {
-    paths: HashMap<PathKey, SmallVec<[P; 8]>>,
+    paths: HashMap<PathKey, SmallVec<[P; 4]>>,
 }
 
 #[doc(hidden)]
@@ -110,11 +110,26 @@ where
     {
         let key = path.key();
 
+        // Iterate through the bucket to determine if this paths is better than any already known
+        // path. Note that the bucket might be modified during the loop if a path is removed which
+        // is shadowed by the new path!
         let possibly_similar_paths = self.paths.entry(key).or_default();
-        for other_path in possibly_similar_paths.iter() {
-            match cmp(arena, path, other_path) {
-                Some(ord) if ord != Ordering::Less => return true,
-                _ => continue,
+        let mut idx = 0;
+        while idx < possibly_similar_paths.len() {
+            match cmp(arena, path, &possibly_similar_paths[idx]) {
+                Some(Ordering::Less) => {
+                    // the new path is better, remove the old one
+                    possibly_similar_paths.remove(idx);
+                    // keep `idx` which now points to the next element
+                    continue;
+                }
+                Some(_) => {
+                    // the new path is equal or worse, and ignored
+                    return true;
+                }
+                None => {
+                    idx += 1;
+                }
             }
         }
 
 
@@ -1303,14 +1303,20 @@ impl StackGraph {
         let edges = &mut self.outgoing_edges[source];
         if let Err(index) = edges.binary_search_by_key(&sink, |o| o.sink) {
             edges.insert(index, OutgoingEdge { sink, precedence });
+            self.incoming_edges[sink] += Degree::One;
         }
     }
 
     /// Removes an edge from the stack graph.
-    pub fn remove_edge(&mut self, source: Handle<Node>, sink: Handle<Node>) {
+    pub fn set_edge_precedence(
+        &mut self,
+        source: Handle<Node>,
+        sink: Handle<Node>,
+        precedence: i32,
+    ) {
         let edges = &mut self.outgoing_edges[source];
         if let Ok(index) = edges.binary_search_by_key(&sink, |o| o.sink) {
-            edges.remove(index);
+            edges[index].precedence = precedence;
         }
     }
 
@@ -1325,6 +1331,11 @@ impl StackGraph {
             None => Either::Left(std::iter::empty()),
         }
     }
+
+    /// Returns the number of edges that end at a particular sink node.
+    pub fn incoming_edge_degree(&self, sink: Handle<Node>) -> Degree {
+        self.incoming_edges[sink]
+    }
 }
 
 //-------------------------------------------------------------------------------------------------
@@ -1430,6 +1441,36 @@ impl StackGraph {
 //-------------------------------------------------------------------------------------------------
 // Stack graphs
 
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+#[repr(u8)]
+pub enum Degree {
+    Zero,
+    One,
+    Multiple,
+}
+
+impl Default for Degree {
+    fn default() -> Self {
+        Self::Zero
+    }
+}
+
+impl std::ops::Add for Degree {
+    type Output = Self;
+    fn add(self, rhs: Self) -> Self::Output {
+        match (self, rhs) {
+            (Self::Zero, result) | (result, Self::Zero) => result,
+            _ => Self::Multiple,
+        }
+    }
+}
+
+impl std::ops::AddAssign for Degree {
+    fn add_assign(&mut self, rhs: Self) {
+        *self = *self + rhs;
+    }
+}
+
 /// Contains all of the nodes and edges that make up a stack graph.
 pub struct StackGraph {
     interned_strings: InternedStringArena,
@@ -1442,9 +1483,10 @@ pub struct StackGraph {
     pub(crate) nodes: Arena<Node>,
     pub(crate) source_info: SupplementalArena<Node, SourceInfo>,
     node_id_handles: NodeIDHandles,
-    outgoing_edges: SupplementalArena<Node, SmallVec<[OutgoingEdge; 8]>>,
+    outgoing_edges: SupplementalArena<Node, SmallVec<[OutgoingEdge; 4]>>,
+    incoming_edges: SupplementalArena<Node, Degree>,
     pub(crate) node_debug_info: SupplementalArena<Node, DebugInfo>,
-    pub(crate) edge_debug_info: SupplementalArena<Node, SmallVec<[(Handle<Node>, DebugInfo); 8]>>,
+    pub(crate) edge_debug_info: SupplementalArena<Node, SmallVec<[(Handle<Node>, DebugInfo); 4]>>,
 }
 
 impl StackGraph {
@@ -1625,6 +1667,7 @@ impl Default for StackGraph {
             source_info: SupplementalArena::new(),
             node_id_handles: NodeIDHandles::new(),
             outgoing_edges: SupplementalArena::new(),
+            incoming_edges: SupplementalArena::new(),
             node_debug_info: SupplementalArena::new(),
             edge_debug_info: SupplementalArena::new(),
         }
Original file line number	Diff line number	Diff line change
`@@ -61,12 +61,16 @@ pub fn add_edge(graph: &mut StackGraph, from: Handle<Node>, to: Handle<Node>, pr`
`61`	`61`	`graph.add_edge(from, to, precedence);`
`62`	`62`	`}`
`63`	`63`
`64`		`-pub fn replace_edge(graph: &mut StackGraph, from: Handle<Node>, to: Handle<Node>, precedence: i32) {`
	`64`	`+pub fn set_edge_precedence(`
	`65`	`+ graph: &mut StackGraph,`
	`66`	`+ from: Handle<Node>,`
	`67`	`+ to: Handle<Node>,`
	`68`	`+ precedence: i32,`
	`69`	`+) {`
`65`	`70`	`if from == to {`
`66`	`71`	`return;`
`67`	`72`	`}`
`68`		`- graph.remove_edge(from, to);`
`69`		`- graph.add_edge(from, to, precedence);`
	`73`	`+ graph.set_edge_precedence(from, to, precedence);`
`70`	`74`	`}`
`71`	`75`
`72`	`76`	`pub fn add_module_pops(`