( )⚙ D12317 dirstate-tree: optimize HashMap lookups with raw_entry_mut

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D12317

dirstate-tree: optimize HashMap lookups with raw_entry_mut
ClosedPublic

Authored by SimonSapin on Mar 3 2022, 2:59 PM.

Details

Reviewers
Alphare
Group Reviewers
hg-reviewers
Commits
rHG11c0411bf4e2: dirstate-tree: optimize HashMap lookups with raw_entry_mut
Summary

This switches to using HashMap from the hashbrown crate,
in order to use its raw_entry_mut method.
The standard library’s HashMap is also based on this same crate,
but raw_entry_mut is not yet stable there:
https://github.com/rust-lang/rust/issues/56167

Using version 0.9 because 0.10 is yanked and 0.11 requires Rust 1.49

This replaces in DirstateMap::get_or_insert_node a call to
HashMap<K, V>::entry with K = WithBasename<Cow<'on_disk, HgPath>>.

entry takes and consumes an "owned" key: K parameter, in case a new entry
ends up inserted. This key is converted by to_cow from a value that borrows
the 'path lifetime.

When this function is called by Dirstate::new_v1, 'path is in fact
the same as 'on_disk so to_cow can return an owned key that contains
Cow::Borrowed.

For other callers, to_cow needs to create a Cow::Owned and thus make
a costly heap memory allocation. This is wasteful if this key was already
present in the map. Even when inserting a new node this is typically the case
for its ancestor nodes (assuming most directories have numerous descendants).

Diff Detail

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

Event Timeline

SimonSapin created this revision.Mar 3 2022, 2:59 PM
Alphare accepted this revision.Mar 9 2022, 4:39 AM
Alphare added a subscriber: Alphare.
Alphare added inline comments.
rust/hg-core/src/lib.rs
60

Looks like AHash has a good chance of being faster than XxHash, but we will have to benchmark it later.

This revision is now accepted and ready to land.Mar 9 2022, 4:39 AM

Revision Contents
Changeset List

Diff 32528

rust/Cargo.lock

# This file is automatically @generated by Cargo. # This file is automatically @generated by Cargo.
# It is not intended for manual editing. # It is not intended for manual editing.
version = 3 version = 3
[[package]] [[package]]
name = "adler" name = "adler"
version = "0.2.3" version = "0.2.3"
source = "registry+https://github.com/rust-lang/crates.io-index" source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "ee2a4ec343196209d6594e19543ae87a39f96d5534d7174822a3ad825dd6ed7e" checksum = "ee2a4ec343196209d6594e19543ae87a39f96d5534d7174822a3ad825dd6ed7e"
[[package]] [[package]]
name = "ahash"
version = "0.4.7"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "739f4a8db6605981345c5654f3a85b056ce52f37a39d34da03f25bf2151ea16e"
[[package]]
name = "aho-corasick" name = "aho-corasick"
version = "0.7.15" version = "0.7.15"
source = "registry+https://github.com/rust-lang/crates.io-index" source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "7404febffaa47dac81aa44dba71523c9d069b1bdc50a77db41195149e17f68e5" checksum = "7404febffaa47dac81aa44dba71523c9d069b1bdc50a77db41195149e17f68e5"
dependencies = [ dependencies = [
"memchr", "memchr",
] ]
[[package]] [[package]]
name = "glob" name = "glob"
version = "0.3.0" version = "0.3.0"
source = "registry+https://github.com/rust-lang/crates.io-index" source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "9b919933a397b79c37e33b77bb2aa3dc8eb6e165ad809e58ff75bc7db2e34574" checksum = "9b919933a397b79c37e33b77bb2aa3dc8eb6e165ad809e58ff75bc7db2e34574"
[[package]] [[package]]
name = "hashbrown"
version = "0.9.1"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "d7afe4a420e3fe79967a00898cc1f4db7c8a49a9333a29f8a4bd76a253d5cd04"
dependencies = [
"ahash",
"rayon",
]
[[package]]
name = "hermit-abi" name = "hermit-abi"
version = "0.1.17" version = "0.1.17"
source = "registry+https://github.com/rust-lang/crates.io-index" source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "5aca5565f760fb5b220e499d72710ed156fdb74e631659e99377d9ebfbd13ae8" checksum = "5aca5565f760fb5b220e499d72710ed156fdb74e631659e99377d9ebfbd13ae8"
dependencies = [ dependencies = [
"libc", "libc",
] ]
"bitflags", "bitflags",
"byteorder", "byteorder",
"bytes-cast", "bytes-cast",
"clap", "clap",
"crossbeam-channel 0.4.4", "crossbeam-channel 0.4.4",
"derive_more", "derive_more",
"flate2", "flate2",
"format-bytes", "format-bytes",
"hashbrown",
"home", "home",
"im-rc", "im-rc",
"itertools", "itertools",
"lazy_static", "lazy_static",
"libc", "libc",
"log", "log",
"memmap2", "memmap2",
"micro-timer", "micro-timer",

rust/hg-core/Cargo.toml

[package] [package]
name = "hg-core" name = "hg-core"
version = "0.1.0" version = "0.1.0"
authors = ["Georges Racinet <gracinet@anybox.fr>"] authors = ["Georges Racinet <gracinet@anybox.fr>"]
description = "Mercurial pure Rust core library, with no assumption on Python bindings (FFI)" description = "Mercurial pure Rust core library, with no assumption on Python bindings (FFI)"
edition = "2018" edition = "2018"
[lib] [lib]
name = "hg" name = "hg"
[dependencies] [dependencies]
bitflags = "1.2" bitflags = "1.2"
bytes-cast = "0.2" bytes-cast = "0.2"
byteorder = "1.3.4" byteorder = "1.3.4"
derive_more = "0.99" derive_more = "0.99"
hashbrown = {version = "0.9.1", features = ["rayon"]}
home = "0.5" home = "0.5"
im-rc = "15.0.*" im-rc = "15.0.*"
itertools = "0.9" itertools = "0.9"
lazy_static = "1.4.0" lazy_static = "1.4.0"
libc = "0.2" libc = "0.2"
rand = "0.8.4" rand = "0.8.4"
rand_pcg = "0.3.1" rand_pcg = "0.3.1"
rand_distr = "0.4.2" rand_distr = "0.4.2"

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

use crate::dirstate::SIZE_NON_NORMAL; use crate::dirstate::SIZE_NON_NORMAL;
use crate::matchers::Matcher; use crate::matchers::Matcher;
use crate::utils::hg_path::{HgPath, HgPathBuf}; use crate::utils::hg_path::{HgPath, HgPathBuf};
use crate::DirstateEntry; use crate::DirstateEntry;
use crate::DirstateError; use crate::DirstateError;
use crate::DirstateParents; use crate::DirstateParents;
use crate::DirstateStatus; use crate::DirstateStatus;
use crate::EntryState; use crate::EntryState;
use crate::FastHashMap; use crate::FastHashbrownMap as FastHashMap;
use crate::PatternFileWarning; use crate::PatternFileWarning;
use crate::StatusError; use crate::StatusError;
use crate::StatusOptions; use crate::StatusOptions;
/// Append to an existing data file if the amount of unreachable data (not used /// Append to an existing data file if the amount of unreachable data (not used
/// anymore) is less than this fraction of the total amount of existing data. /// anymore) is less than this fraction of the total amount of existing data.
const ACCEPTABLE_UNREACHABLE_BYTES_RATIO: f32 = 0.5; const ACCEPTABLE_UNREACHABLE_BYTES_RATIO: f32 = 0.5;
) -> Result<&'tree mut Node<'on_disk>, DirstateV2ParseError> { ) -> Result<&'tree mut Node<'on_disk>, DirstateV2ParseError> {
let mut child_nodes = root; let mut child_nodes = root;
let mut inclusive_ancestor_paths = let mut inclusive_ancestor_paths =
WithBasename::inclusive_ancestors_of(path); WithBasename::inclusive_ancestors_of(path);
let mut ancestor_path = inclusive_ancestor_paths let mut ancestor_path = inclusive_ancestor_paths
.next() .next()
.expect("expected at least one inclusive ancestor"); .expect("expected at least one inclusive ancestor");
loop { loop {
// TODO: can we avoid allocating an owned key in cases where the let (_, child_node) = child_nodes
// map already contains that key, without introducing double
// lookup?
let child_node = child_nodes
.make_mut(on_disk, unreachable_bytes)? .make_mut(on_disk, unreachable_bytes)?
.entry(to_cow(ancestor_path)) .raw_entry_mut()
.or_default(); .from_key(ancestor_path.base_name())
.or_insert_with(|| (to_cow(ancestor_path), Node::default()));
if let Some(next) = inclusive_ancestor_paths.next() { if let Some(next) = inclusive_ancestor_paths.next() {
each_ancestor(child_node); each_ancestor(child_node);
ancestor_path = next; ancestor_path = next;
child_nodes = &mut child_node.children; child_nodes = &mut child_node.children;
} else { } else {
return Ok(child_node); return Ok(child_node);
} }
} }

rust/hg-core/src/lib.rs

pub type LineNumber = usize; pub type LineNumber = usize;
/// Rust's default hasher is too slow because it tries to prevent collision /// Rust's default hasher is too slow because it tries to prevent collision
/// attacks. We are not concerned about those: if an ill-minded person has /// attacks. We are not concerned about those: if an ill-minded person has
/// write access to your repository, you have other issues. /// write access to your repository, you have other issues.
pub type FastHashMap<K, V> = HashMap<K, V, RandomXxHashBuilder64>; pub type FastHashMap<K, V> = HashMap<K, V, RandomXxHashBuilder64>;
// TODO: should this be the default `FastHashMap` for all of hg-core, not just
// dirstate_tree? How does XxHash compare with AHash, hashbrown’s default?
AlphareUnsubmitted
Not Done

Looks like AHash has a good chance of being faster than XxHash, but we will have to benchmark it later.

Alphare: Looks like `AHash` has a good chance of being faster than `XxHash`, but we will have to…
pub type FastHashbrownMap<K, V> =
hashbrown::HashMap<K, V, RandomXxHashBuilder64>;
#[derive(Debug, PartialEq)] #[derive(Debug, PartialEq)]
pub enum DirstateMapError { pub enum DirstateMapError {
PathNotFound(HgPathBuf), PathNotFound(HgPathBuf),
EmptyPath, EmptyPath,
InvalidPath(HgPathError), InvalidPath(HgPathError),
} }
impl fmt::Display for DirstateMapError { impl fmt::Display for DirstateMapError {