Mercurial > hg
comparison rust/hg-core/src/dirstate_tree/dirstate_map.rs @ 48950:11c0411bf4e2
dirstate-tree: optimize HashMap lookups with raw_entry_mut
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).
Differential Revision: https://phab.mercurial-scm.org/D12317
author | Simon Sapin <simon.sapin@octobus.net> |
---|---|
date | Tue, 08 Feb 2022 15:51:52 +0100 |
parents | 473af5cbc209 |
children | 12adf8c695ed |
comparison
equal
deleted
inserted
replaced
48949:469b9ee336a6 | 48950:11c0411bf4e2 |
---|---|
20 use crate::DirstateEntry; | 20 use crate::DirstateEntry; |
21 use crate::DirstateError; | 21 use crate::DirstateError; |
22 use crate::DirstateParents; | 22 use crate::DirstateParents; |
23 use crate::DirstateStatus; | 23 use crate::DirstateStatus; |
24 use crate::EntryState; | 24 use crate::EntryState; |
25 use crate::FastHashMap; | 25 use crate::FastHashbrownMap as FastHashMap; |
26 use crate::PatternFileWarning; | 26 use crate::PatternFileWarning; |
27 use crate::StatusError; | 27 use crate::StatusError; |
28 use crate::StatusOptions; | 28 use crate::StatusOptions; |
29 | 29 |
30 /// Append to an existing data file if the amount of unreachable data (not used | 30 /// Append to an existing data file if the amount of unreachable data (not used |
583 WithBasename::inclusive_ancestors_of(path); | 583 WithBasename::inclusive_ancestors_of(path); |
584 let mut ancestor_path = inclusive_ancestor_paths | 584 let mut ancestor_path = inclusive_ancestor_paths |
585 .next() | 585 .next() |
586 .expect("expected at least one inclusive ancestor"); | 586 .expect("expected at least one inclusive ancestor"); |
587 loop { | 587 loop { |
588 // TODO: can we avoid allocating an owned key in cases where the | 588 let (_, child_node) = child_nodes |
589 // map already contains that key, without introducing double | |
590 // lookup? | |
591 let child_node = child_nodes | |
592 .make_mut(on_disk, unreachable_bytes)? | 589 .make_mut(on_disk, unreachable_bytes)? |
593 .entry(to_cow(ancestor_path)) | 590 .raw_entry_mut() |
594 .or_default(); | 591 .from_key(ancestor_path.base_name()) |
592 .or_insert_with(|| (to_cow(ancestor_path), Node::default())); | |
595 if let Some(next) = inclusive_ancestor_paths.next() { | 593 if let Some(next) = inclusive_ancestor_paths.next() { |
596 each_ancestor(child_node); | 594 each_ancestor(child_node); |
597 ancestor_path = next; | 595 ancestor_path = next; |
598 child_nodes = &mut child_node.children; | 596 child_nodes = &mut child_node.children; |
599 } else { | 597 } else { |