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 {