changeset 51425:7c6d0b9dde37

rust-index: improve phase computation speed

While less memory efficient, using an array is *much* faster than using a
HashMap, especially with the default hasher. It even makes the code simpler,
so I'm not really sure what I was thinking in the first place, maybe it's more
obvious now.

This fix a significant performance regression when using the rust version of the
code. (however, the C code still outperform rust on this operation)

hg perf::phases on mozilla-try-2023-03-22
- 6.6.3:  0.451239 seconds
- before: 0.982495 seconds
- after:  0.265347 seconds
- C code: 0.183241 second

--- a/rust/hg-core/src/revlog/index.rs	Fri Feb 23 06:37:25 2024 +0100
+++ b/rust/hg-core/src/revlog/index.rs	Thu Feb 22 15:06:16 2024 +0100
@@ -1026,7 +1026,7 @@
         &self,
         roots: HashMap<Phase, Vec<Revision>>,
     ) -> Result<(usize, RootsPerPhase), GraphError> {
-        let mut phases = HashMap::new();
+        let mut phases = vec![Phase::Public; self.len()];
         let mut min_phase_rev = NULL_REVISION;
 
         for phase in Phase::non_public_phases() {
@@ -1053,24 +1053,17 @@
             let rev = Revision(rev);
             let [p1, p2] = self.parents(rev)?;
 
-            const DEFAULT_PHASE: &Phase = &Phase::Public;
-            if p1.0 >= 0
-                && phases.get(&p1).unwrap_or(DEFAULT_PHASE)
-                    > phases.get(&rev).unwrap_or(DEFAULT_PHASE)
-            {
-                phases.insert(rev, phases[&p1]);
+            if p1.0 >= 0 && phases[p1.0 as usize] > phases[rev.0 as usize] {
+                phases[rev.0 as usize] = phases[p1.0 as usize];
+            }
+            if p2.0 >= 0 && phases[p2.0 as usize] > phases[rev.0 as usize] {
+                phases[rev.0 as usize] = phases[p2.0 as usize];
             }
-            if p2.0 >= 0
-                && phases.get(&p2).unwrap_or(DEFAULT_PHASE)
-                    > phases.get(&rev).unwrap_or(DEFAULT_PHASE)
-            {
-                phases.insert(rev, phases[&p2]);
-            }
-            let set = match phases.get(&rev).unwrap_or(DEFAULT_PHASE) {
+            let set = match phases[rev.0 as usize] {
                 Phase::Public => continue,
-                phase => &mut phase_sets[*phase as usize - 1],
+                phase => &mut phase_sets[phase as usize - 1],
             };
-            set.insert(rev);
+            set.push(rev);
         }
 
         Ok((self.len(), phase_sets))
@@ -1079,13 +1072,13 @@
     fn add_roots_get_min(
         &self,
         phase_roots: &[Revision],
-        phases: &mut HashMap<Revision, Phase>,
+        phases: &mut [Phase],
         phase: Phase,
     ) -> Revision {
         let mut min_rev = NULL_REVISION;
 
         for root in phase_roots {
-            phases.insert(*root, phase);
+            phases[root.0 as usize] = phase;
             if min_rev == NULL_REVISION || min_rev > *root {
                 min_rev = *root;
             }
@@ -1606,7 +1599,7 @@
 }
 
 /// Set of roots of all non-public phases
-pub type RootsPerPhase = [HashSet<Revision>; Phase::non_public_phases().len()];
+pub type RootsPerPhase = [Vec<Revision>; Phase::non_public_phases().len()];
 
 #[derive(Debug, Copy, Clone, PartialEq, Eq, Ord, PartialOrd, Hash)]
 pub enum Phase {