diff --git a/rust/hg-core/src/dirstate_tree/dirstate_map.rs b/rust/hg-core/src/dirstate_tree/dirstate_map.rs
--- a/rust/hg-core/src/dirstate_tree/dirstate_map.rs
+++ b/rust/hg-core/src/dirstate_tree/dirstate_map.rs
@@ -1,7 +1,7 @@
 use bytes_cast::BytesCast;
 use micro_timer::timed;
+use std::convert::TryInto;
 use std::path::PathBuf;
-use std::{collections::BTreeMap, convert::TryInto};
 
 use super::path_with_basename::WithBasename;
 use crate::dirstate::parsers::clear_ambiguous_mtime;
@@ -20,6 +20,7 @@
 use crate::DirstateParents;
 use crate::DirstateStatus;
 use crate::EntryState;
+use crate::FastHashMap;
 use crate::PatternFileWarning;
 use crate::StateMapIter;
 use crate::StatusError;
@@ -43,7 +44,7 @@
 /// path, so comparing full paths gives the same result as comparing base
 /// names. However `BTreeMap` would waste time always re-comparing the same
 /// string prefix.
-pub(super) type ChildNodes = BTreeMap<WithBasename<HgPathBuf>, Node>;
+pub(super) type ChildNodes = FastHashMap<WithBasename<HgPathBuf>, Node>;
 
 /// Represents a file or a directory
 #[derive(Default)]
@@ -86,7 +87,7 @@
         Self {
             parents: None,
             dirty_parents: false,
-            root: ChildNodes::new(),
+            root: ChildNodes::default(),
             nodes_with_entry_count: 0,
             nodes_with_copy_source_count: 0,
         }
diff --git a/rust/hg-core/src/dirstate_tree/path_with_basename.rs b/rust/hg-core/src/dirstate_tree/path_with_basename.rs
--- a/rust/hg-core/src/dirstate_tree/path_with_basename.rs
+++ b/rust/hg-core/src/dirstate_tree/path_with_basename.rs
@@ -55,6 +55,12 @@
     }
 }
 
+impl<T: AsRef<HgPath>> std::hash::Hash for WithBasename<T> {
+    fn hash<H: std::hash::Hasher>(&self, hasher: &mut H) {
+        self.base_name().hash(hasher)
+    }
+}
+
 impl<T: AsRef<HgPath> + PartialEq> PartialEq for WithBasename<T> {
     fn eq(&self, other: &Self) -> bool {
         self.base_name() == other.base_name()
diff --git a/rust/hg-core/src/dirstate_tree/status.rs b/rust/hg-core/src/dirstate_tree/status.rs
--- a/rust/hg-core/src/dirstate_tree/status.rs
+++ b/rust/hg-core/src/dirstate_tree/status.rs
@@ -110,11 +110,11 @@
 
         // `merge_join_by` requires both its input iterators to be sorted:
 
-        //
-        // * `BTreeMap` iterates according to keys’ ordering by definition
-
+        let mut dirstate_nodes: Vec<_> = dirstate_nodes.iter_mut().collect();
         // `sort_unstable_by_key` doesn’t allow keys borrowing from the value:
         // https://github.com/rust-lang/rust/issues/34162
+        dirstate_nodes
+            .sort_unstable_by(|(path1, _), (path2, _)| path1.cmp(path2));
         fs_entries.sort_unstable_by(|e1, e2| e1.base_name.cmp(&e2.base_name));
 
         itertools::merge_join_by(