( )⚙ D10553 dirstate-tree: Use HashMap instead of BTreeMap

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D10553

dirstate-tree: Use HashMap instead of BTreeMap
ClosedPublic

Authored by SimonSapin on May 3 2021, 6:25 AM.

Details

Reviewers
Alphare
Group Reviewers
hg-reviewers
Commits
rHG15395fd8ab28: dirstate-tree: Use HashMap instead of BTreeMap
rHG6e3246a3ba76: dirstate-tree: Use HashMap instead of BTreeMap
Summary

BTreeMap has the advantage of its "natural" iteration order being the one we need
in the status algorithm. With HashMap however, iteration order is undefined so
we need to allocate a Vec and sort it explicitly.

Unfortunately many BTreeMap operations are slower than in HashMap, and skipping
that extra allocation and sort is not enough to compensate.

Switching to HashMap + sort makes hg status 17% faster in one test case,
as measure with hyperfine:

Benchmark #1: ../hg2/hg status -R $REPO --config=experimental.dirstate-tree.in-memory=1
  Time (mean ± σ):     765.0 ms ±   8.8 ms    [User: 1.352 s, System: 0.747 s]
  Range (min … max):   751.8 ms … 778.7 ms    10 runs

Benchmark #2: ./hg status -R $REPO --config=experimental.dirstate-tree.in-memory=1
  Time (mean ± σ):     651.8 ms ±   9.9 ms    [User: 1.251 s, System: 0.799 s]
  Range (min … max):   642.2 ms … 671.8 ms    10 runs

Summary
  './hg status -R $REPO --config=experimental.dirstate-tree.in-memory=1' ran
    1.17 ± 0.02 times faster than '../hg2/hg status -R $REPO --config=experimental.dirstate-tree.in-memory=1'
  • ./hg is this revision
  • ../hg2/hg is its parent
  • $REPO is an old snapshot of mozilla-central

Diff Detail

Repository
rHG Mercurial
Branch
default
Lint
No Linters Available
Unit
No Unit Test Coverage

Event Timeline

SimonSapin created this revision.May 3 2021, 6:25 AM
Alphare accepted this revision.May 3 2021, 10:49 AM
This revision is now accepted and ready to land.May 3 2021, 10:49 AM
baymax updated this revision to Diff 27629.May 6 2021, 12:03 PM

✅ refresh by Heptapod after a successful CI run (🐙 💚)

SimonSapin added a commit: rHG6e3246a3ba76: dirstate-tree: Use HashMap instead of BTreeMap.May 6 2021, 12:56 PM
Closed by commit rHG6e3246a3ba76: dirstate-tree: Use HashMap instead of BTreeMap (authored by SimonSapin). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 27629

rust/hg-core/src/dirstate_tree/dirstate_map.rs

use bytes_cast::BytesCast; use bytes_cast::BytesCast;
use micro_timer::timed; use micro_timer::timed;
use std::convert::TryInto;
use std::path::PathBuf; use std::path::PathBuf;
use std::{collections::BTreeMap, convert::TryInto};
use super::path_with_basename::WithBasename; use super::path_with_basename::WithBasename;
use crate::dirstate::parsers::clear_ambiguous_mtime; use crate::dirstate::parsers::clear_ambiguous_mtime;
use crate::dirstate::parsers::pack_entry; use crate::dirstate::parsers::pack_entry;
use crate::dirstate::parsers::packed_entry_size; use crate::dirstate::parsers::packed_entry_size;
use crate::dirstate::parsers::parse_dirstate_entries; use crate::dirstate::parsers::parse_dirstate_entries;
use crate::dirstate::parsers::parse_dirstate_parents; use crate::dirstate::parsers::parse_dirstate_parents;
use crate::dirstate::parsers::Timestamp; use crate::dirstate::parsers::Timestamp;
use crate::matchers::Matcher; use crate::matchers::Matcher;
use crate::revlog::node::NULL_NODE; use crate::revlog::node::NULL_NODE;
use crate::utils::hg_path::{HgPath, HgPathBuf}; use crate::utils::hg_path::{HgPath, HgPathBuf};
use crate::CopyMapIter; use crate::CopyMapIter;
use crate::DirstateEntry; use crate::DirstateEntry;
use crate::DirstateError; use crate::DirstateError;
use crate::DirstateMapError; use crate::DirstateMapError;
use crate::DirstateParents; use crate::DirstateParents;
use crate::DirstateStatus; use crate::DirstateStatus;
use crate::EntryState; use crate::EntryState;
use crate::FastHashMap;
use crate::PatternFileWarning; use crate::PatternFileWarning;
use crate::StateMapIter; use crate::StateMapIter;
use crate::StatusError; use crate::StatusError;
use crate::StatusOptions; use crate::StatusOptions;
pub struct DirstateMap { pub struct DirstateMap {
parents: Option<DirstateParents>, parents: Option<DirstateParents>,
dirty_parents: bool, dirty_parents: bool,
pub(super) root: ChildNodes, pub(super) root: ChildNodes,
/// Number of nodes anywhere in the tree that have `.entry.is_some()`. /// Number of nodes anywhere in the tree that have `.entry.is_some()`.
nodes_with_entry_count: usize, nodes_with_entry_count: usize,
/// Number of nodes anywhere in the tree that have /// Number of nodes anywhere in the tree that have
/// `.copy_source.is_some()`. /// `.copy_source.is_some()`.
nodes_with_copy_source_count: usize, nodes_with_copy_source_count: usize,
} }
/// Using a plain `HgPathBuf` of the full path from the repository root as a /// Using a plain `HgPathBuf` of the full path from the repository root as a
/// map key would also work: all paths in a given map have the same parent /// map key would also work: all paths in a given map have the same parent
/// path, so comparing full paths gives the same result as comparing base /// path, so comparing full paths gives the same result as comparing base
/// names. However `BTreeMap` would waste time always re-comparing the same /// names. However `BTreeMap` would waste time always re-comparing the same
/// string prefix. /// string prefix.
pub(super) type ChildNodes = BTreeMap<WithBasename<HgPathBuf>, Node>; pub(super) type ChildNodes = FastHashMap<WithBasename<HgPathBuf>, Node>;
/// Represents a file or a directory /// Represents a file or a directory
#[derive(Default)] #[derive(Default)]
pub(super) struct Node { pub(super) struct Node {
/// `None` for directories /// `None` for directories
pub(super) entry: Option<DirstateEntry>, pub(super) entry: Option<DirstateEntry>,
pub(super) copy_source: Option<HgPathBuf>, pub(super) copy_source: Option<HgPathBuf>,
&'a mut Option<HgPathBuf>, &'a mut Option<HgPathBuf>,
); );
impl DirstateMap { impl DirstateMap {
pub fn new() -> Self { pub fn new() -> Self {
Self { Self {
parents: None, parents: None,
dirty_parents: false, dirty_parents: false,
root: ChildNodes::new(), root: ChildNodes::default(),
nodes_with_entry_count: 0, nodes_with_entry_count: 0,
nodes_with_copy_source_count: 0, nodes_with_copy_source_count: 0,
} }
} }
fn get_node(&self, path: &HgPath) -> Option<&Node> { fn get_node(&self, path: &HgPath) -> Option<&Node> {
let mut children = &self.root; let mut children = &self.root;
let mut components = path.components(); let mut components = path.components();

rust/hg-core/src/dirstate_tree/path_with_basename.rs

} }
impl<T: AsRef<HgPath>> Borrow<HgPath> for WithBasename<T> { impl<T: AsRef<HgPath>> Borrow<HgPath> for WithBasename<T> {
fn borrow(&self) -> &HgPath { fn borrow(&self) -> &HgPath {
self.base_name() self.base_name()
} }
} }
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> { impl<T: AsRef<HgPath> + PartialEq> PartialEq for WithBasename<T> {
fn eq(&self, other: &Self) -> bool { fn eq(&self, other: &Self) -> bool {
self.base_name() == other.base_name() self.base_name() == other.base_name()
} }
} }
impl<T: AsRef<HgPath> + Eq> Eq for WithBasename<T> {} impl<T: AsRef<HgPath> + Eq> Eq for WithBasename<T> {}

rust/hg-core/src/dirstate_tree/status.rs

) { ) {
entries entries
} else { } else {
return; return;
}; };
// `merge_join_by` requires both its input iterators to be sorted: // `merge_join_by` requires both its input iterators to be sorted:
// let mut dirstate_nodes: Vec<_> = dirstate_nodes.iter_mut().collect();
// * `BTreeMap` iterates according to keys’ ordering by definition
// `sort_unstable_by_key` doesn’t allow keys borrowing from the value: // `sort_unstable_by_key` doesn’t allow keys borrowing from the value:
// https://github.com/rust-lang/rust/issues/34162 // 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)); fs_entries.sort_unstable_by(|e1, e2| e1.base_name.cmp(&e2.base_name));
itertools::merge_join_by( itertools::merge_join_by(
dirstate_nodes, dirstate_nodes,
&fs_entries, &fs_entries,
|(full_path, _node), fs_entry| { |(full_path, _node), fs_entry| {
full_path.base_name().cmp(&fs_entry.base_name) full_path.base_name().cmp(&fs_entry.base_name)
}, },