( )⚙ D10559 dirstate-tree: Borrow copy source paths from the "on disk" bytes

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D10559

dirstate-tree: Borrow copy source paths from the "on disk" bytes
ClosedPublic

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

Details

Reviewers
Alphare
Group Reviewers
hg-reviewers
Commits
rHG9be618452c3b: dirstate-tree: Borrow copy source paths from the "on disk" bytes
rHG1c5e6f1099eb: dirstate-tree: Borrow copy source paths from the "on disk" bytes
Summary

Use std::borrow::Cow to avoid some memory allocations and copying.

These particular allocations are not visible when profiling (as many files
in a typical repo don’t have a copy source). This change is "warm up"
for doing the same with paths of files themselves, which is more involved
since those paths are used as HashMap keys. This gets of the way the
addition of a lifetime parameter to several types.

Diff Detail

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

Revision Contents
Changeset List

Diff 27635

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::borrow::Cow;
use std::convert::TryInto; use std::convert::TryInto;
use std::path::PathBuf; use std::path::PathBuf;
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::StateMapIter; use crate::StateMapIter;
use crate::StatusError; use crate::StatusError;
use crate::StatusOptions; use crate::StatusOptions;
pub struct DirstateMap<'on_disk> { pub struct DirstateMap<'on_disk> {
/// Contents of the `.hg/dirstate` file /// Contents of the `.hg/dirstate` file
on_disk: &'on_disk [u8], on_disk: &'on_disk [u8],
pub(super) root: ChildNodes, pub(super) root: ChildNodes<'on_disk>,
/// 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 = FastHashMap<WithBasename<HgPathBuf>, Node>; pub(super) type ChildNodes<'on_disk> =
FastHashMap<WithBasename<HgPathBuf>, Node<'on_disk>>;
/// Represents a file or a directory /// Represents a file or a directory
#[derive(Default)] #[derive(Default)]
pub(super) struct Node { pub(super) struct Node<'on_disk> {
/// `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<Cow<'on_disk, HgPath>>,
pub(super) children: ChildNodes, pub(super) children: ChildNodes<'on_disk>,
/// How many (non-inclusive) descendants of this node are tracked files /// How many (non-inclusive) descendants of this node are tracked files
tracked_descendants_count: usize, tracked_descendants_count: usize,
} }
impl Node { impl Node<'_> {
pub(super) fn state(&self) -> Option<EntryState> { pub(super) fn state(&self) -> Option<EntryState> {
self.entry.as_ref().map(|entry| entry.state) self.entry.as_ref().map(|entry| entry.state)
} }
} }
/// `(full_path, entry, copy_source)` /// `(full_path, entry, copy_source)`
type NodeDataMut<'a> = ( type NodeDataMut<'tree, 'on_disk> = (
&'a HgPath, &'tree HgPath,
&'a mut Option<DirstateEntry>, &'tree mut Option<DirstateEntry>,
&'a mut Option<HgPathBuf>, &'tree mut Option<Cow<'on_disk, HgPath>>,
); );
impl<'on_disk> DirstateMap<'on_disk> { impl<'on_disk> DirstateMap<'on_disk> {
pub fn new( pub fn new(
on_disk: &'on_disk [u8], on_disk: &'on_disk [u8],
) -> Result<(Self, Option<DirstateParents>), DirstateError> { ) -> Result<(Self, Option<DirstateParents>), DirstateError> {
let mut map = Self { let mut map = Self {
on_disk, on_disk,
node.entry.is_none(), node.entry.is_none(),
"duplicate dirstate entry in read" "duplicate dirstate entry in read"
); );
assert!( assert!(
node.copy_source.is_none(), node.copy_source.is_none(),
"duplicate dirstate entry in read" "duplicate dirstate entry in read"
); );
node.entry = Some(*entry); node.entry = Some(*entry);
node.copy_source = copy_source.map(HgPath::to_owned); node.copy_source = copy_source.map(Cow::Borrowed);
self.nodes_with_entry_count += 1; self.nodes_with_entry_count += 1;
if copy_source.is_some() { if copy_source.is_some() {
self.nodes_with_copy_source_count += 1 self.nodes_with_copy_source_count += 1
} }
}, },
)?; )?;
Ok(Some(parents.clone())) Ok(Some(parents.clone()))
} }
} }
/// Returns a mutable reference to the node at `path` if it exists /// Returns a mutable reference to the node at `path` if it exists
/// ///
/// This takes `root` instead of `&mut self` so that callers can mutate /// This takes `root` instead of `&mut self` so that callers can mutate
/// other fields while the returned borrow is still valid /// other fields while the returned borrow is still valid
fn get_node_mut<'tree>( fn get_node_mut<'tree>(
root: &'tree mut ChildNodes, root: &'tree mut ChildNodes<'on_disk>,
path: &HgPath, path: &HgPath,
) -> Option<&'tree mut Node> { ) -> Option<&'tree mut Node<'on_disk>> {
Self::get_node_mut_tracing_ancestors(root, path, |_| {}) Self::get_node_mut_tracing_ancestors(root, path, |_| {})
} }
/// Same as `get_node_mut`, and calls `each_ancestor` for each ancestor of /// Same as `get_node_mut`, and calls `each_ancestor` for each ancestor of
/// the node. /// the node.
/// ///
/// Note that `each_ancestor` may be called (with what would be ancestors) /// Note that `each_ancestor` may be called (with what would be ancestors)
/// even if it turns out there is no node at `path`. /// even if it turns out there is no node at `path`.
fn get_node_mut_tracing_ancestors<'tree>( fn get_node_mut_tracing_ancestors<'tree>(
root: &'tree mut ChildNodes, root: &'tree mut ChildNodes<'on_disk>,
path: &HgPath, path: &HgPath,
mut each_ancestor: impl FnMut(&mut Node), mut each_ancestor: impl FnMut(&mut Node),
) -> Option<&'tree mut Node> { ) -> Option<&'tree mut Node<'on_disk>> {
let mut children = root; let mut children = root;
let mut components = path.components(); let mut components = path.components();
let mut component = let mut component =
components.next().expect("expected at least one components"); components.next().expect("expected at least one components");
loop { loop {
let child = children.get_mut(component)?; let child = children.get_mut(component)?;
if let Some(next_component) = components.next() { if let Some(next_component) = components.next() {
each_ancestor(child); each_ancestor(child);
component = next_component; component = next_component;
children = &mut child.children; children = &mut child.children;
} else { } else {
return Some(child); return Some(child);
} }
} }
} }
fn get_or_insert_node<'tree>( fn get_or_insert_node<'tree>(
root: &'tree mut ChildNodes, root: &'tree mut ChildNodes<'on_disk>,
path: &HgPath, path: &HgPath,
) -> &'tree mut Node { ) -> &'tree mut Node<'on_disk> {
Self::get_or_insert_node_tracing_ancestors(root, path, |_| {}) Self::get_or_insert_node_tracing_ancestors(root, path, |_| {})
} }
fn get_or_insert_node_tracing_ancestors<'tree>( fn get_or_insert_node_tracing_ancestors<'tree>(
root: &'tree mut ChildNodes, root: &'tree mut ChildNodes<'on_disk>,
path: &HgPath, path: &HgPath,
mut each_ancestor: impl FnMut(&mut Node), mut each_ancestor: impl FnMut(&mut Node),
) -> &'tree mut Node { ) -> &'tree mut Node<'on_disk> {
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 // TODO: can we avoid allocating an owned key in cases where the
} }
/// Mutable iterator for the `(entry, copy source)` of each node. /// Mutable iterator for the `(entry, copy source)` of each node.
/// ///
/// It would not be safe to yield mutable references to nodes themeselves /// It would not be safe to yield mutable references to nodes themeselves
/// with `-> impl Iterator<Item = &mut Node>` since child nodes are /// with `-> impl Iterator<Item = &mut Node>` since child nodes are
/// reachable from their ancestor nodes, potentially creating multiple /// reachable from their ancestor nodes, potentially creating multiple
/// `&mut` references to a given node. /// `&mut` references to a given node.
fn iter_node_data_mut<'a>( fn iter_node_data_mut<'tree>(
&'a mut self, &'tree mut self,
) -> impl Iterator<Item = NodeDataMut<'a>> + 'a { ) -> impl Iterator<Item = NodeDataMut<'tree, 'on_disk>> + 'tree {
// Explict stack for pseudo-recursion, see `iter_nodes` above. // Explict stack for pseudo-recursion, see `iter_nodes` above.
let mut stack = Vec::new(); let mut stack = Vec::new();
let mut iter = self.root.iter_mut(); let mut iter = self.root.iter_mut();
std::iter::from_fn(move || { std::iter::from_fn(move || {
while let Some((key, child_node)) = iter.next() { while let Some((key, child_node)) = iter.next() {
// Pseudo-recursion // Pseudo-recursion
let data = ( let data = (
&**key.full_path(), &**key.full_path(),
} }
fn copy_map_remove(&mut self, key: &HgPath) -> Option<HgPathBuf> { fn copy_map_remove(&mut self, key: &HgPath) -> Option<HgPathBuf> {
let count = &mut self.nodes_with_copy_source_count; let count = &mut self.nodes_with_copy_source_count;
Self::get_node_mut(&mut self.root, key).and_then(|node| { Self::get_node_mut(&mut self.root, key).and_then(|node| {
if node.copy_source.is_some() { if node.copy_source.is_some() {
*count -= 1 *count -= 1
} }
node.copy_source.take() node.copy_source.take().map(Cow::into_owned)
}) })
} }
fn copy_map_insert( fn copy_map_insert(
&mut self, &mut self,
key: HgPathBuf, key: HgPathBuf,
value: HgPathBuf, value: HgPathBuf,
) -> Option<HgPathBuf> { ) -> Option<HgPathBuf> {
let node = Self::get_or_insert_node(&mut self.root, &key); let node = Self::get_or_insert_node(&mut self.root, &key);
if node.copy_source.is_none() { if node.copy_source.is_none() {
self.nodes_with_copy_source_count += 1 self.nodes_with_copy_source_count += 1
} }
node.copy_source.replace(value) node.copy_source.replace(value.into()).map(Cow::into_owned)
} }
fn len(&self) -> usize { fn len(&self) -> usize {
self.nodes_with_entry_count self.nodes_with_entry_count
} }
fn contains_key(&self, key: &HgPath) -> bool { fn contains_key(&self, key: &HgPath) -> bool {
self.get(key).is_some() self.get(key).is_some()