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
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

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 32607

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 {