( )⚙ D10554 dirstate-tree: Fold "tracked descendants" counter update in main walk

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D10554

dirstate-tree: Fold "tracked descendants" counter update in main walk
ClosedPublic

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

Details

Reviewers
Alphare
Group Reviewers
hg-reviewers
Commits
rHG7109a38830c9: dirstate-tree: Fold "tracked descendants" counter update in main walk
rHGb4142560de96: dirstate-tree: Fold "tracked descendants" counter update in main walk
Summary

For the purpose of implementing has_tracked_dir (which means "has tracked
descendants) without an expensive sub-tree traversal, we maintaing a counter
of tracked descendants on each "directory" node of the tree-shaped dirstate.

Before this changeset, mutating or inserting a node at a given path would
involve:

  • Walking the tree from root through ancestors to find the node or the spot where to insert it
  • Looking at the previous node if any to decide what counter update is needed
  • Performing any node mutation
  • Walking the tree *again* to update counters in ancestor nodes

When profiling hg status on a large repo, this second walk takes times
while loading a the dirstate from disk.

It turns out we have enough information to decide before he first tree walk
what counter update is needed. This changeset merges the two walks, gaining
~10% of the total time for hg update (in the same hyperfine benchmark as
the previous changeset).

Profiling was done by compiling with this .cargo/config:

[profile.release]
debug = true

then running with:

py-spy record -r 500 -n -o /tmp/hg.json --format speedscope -- \
./hg status -R $REPO --config experimental.dirstate-tree.in-memory=1

then visualizing the recorded JSON file in https://www.speedscope.app/

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.

Revision Contents
Changeset List

Diff 27664

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

pub(super) children: ChildNodes, pub(super) children: ChildNodes,
/// 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 {
/// Whether this node has a `DirstateEntry` with `.state.is_tracked()`
fn is_tracked_file(&self) -> bool {
if let Some(entry) = &self.entry {
entry.state.is_tracked()
} else {
false
}
}
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<'a> = (
&'a WithBasename<HgPathBuf>, &'a WithBasename<HgPathBuf>,
/// 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,
path: &HgPath, path: &HgPath,
) -> Option<&'tree mut Node> { ) -> Option<&'tree mut Node> {
Self::each_and_get(root, path, |_| {}) Self::get_node_mut_tracing_ancestors(root, path, |_| {})
} }
/// Call `each` for each ancestor node of the one at `path` (not including /// Same as `get_node_mut`, and calls `each_ancestor` for each ancestor of
/// that node itself), starting from nearest the root. /// the node.
/// ///
/// Panics (possibly after some calls to `each`) if there is no node at /// Note that `each_ancestor` may be called (with what would be ancestors)
/// `path`. /// even if it turns out there is no node at `path`.
fn for_each_ancestor_node<'tree>( fn get_node_mut_tracing_ancestors<'tree>(
&mut self,
path: &HgPath,
each: impl FnMut(&mut Node),
) {
let parent = path.parent();
if !parent.is_empty() {
Self::each_and_get(&mut self.root, parent, each)
.expect("missing dirstate node");
}
}
/// Common implementation detail of `get_node_mut` and
/// `for_each_ancestor_node`
fn each_and_get<'tree>(
root: &'tree mut ChildNodes, root: &'tree mut ChildNodes,
path: &HgPath, path: &HgPath,
mut each: impl FnMut(&mut Node), mut each_ancestor: impl FnMut(&mut Node),
) -> Option<&'tree mut Node> { ) -> Option<&'tree mut Node> {
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)?;
each(child);
if let Some(next_component) = components.next() { if let Some(next_component) = components.next() {
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,
path: &HgPath, path: &HgPath,
) -> &'tree mut Node { ) -> &'tree mut Node {
Self::get_or_insert_node_tracing_ancestors(root, path, |_| {})
}
fn get_or_insert_node_tracing_ancestors<'tree>(
root: &'tree mut ChildNodes,
path: &HgPath,
mut each_ancestor: impl FnMut(&mut Node),
) -> &'tree mut Node {
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
// map already contains that key, without introducing double // map already contains that key, without introducing double
// lookup? // lookup?
let child_node = let child_node =
child_nodes.entry(ancestor_path.to_owned()).or_default(); child_nodes.entry(ancestor_path.to_owned()).or_default();
if let Some(next) = inclusive_ancestor_paths.next() { if let Some(next) = inclusive_ancestor_paths.next() {
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 child_node; return child_node;
} }
} }
} }
/// The meaning of `new_copy_source` is: fn add_or_remove_file(
///
/// * `Some(Some(x))`: set `Node::copy_source` to `Some(x)`
/// * `Some(None)`: set `Node::copy_source` to `None`
/// * `None`: leave `Node::copy_source` unchanged
fn add_file_node(
&mut self, &mut self,
path: &HgPath, path: &HgPath,
old_state: EntryState,
new_entry: DirstateEntry, new_entry: DirstateEntry,
new_copy_source: Option<Option<HgPathBuf>>,
) { ) {
let node = Self::get_or_insert_node(&mut self.root, path);
if node.entry.is_none() {
self.nodes_with_entry_count += 1
}
if let Some(source) = &new_copy_source {
if node.copy_source.is_none() && source.is_some() {
self.nodes_with_copy_source_count += 1
}
if node.copy_source.is_some() && source.is_none() {
self.nodes_with_copy_source_count -= 1
}
}
let tracked_count_increment = let tracked_count_increment =
match (node.is_tracked_file(), new_entry.state.is_tracked()) { match (old_state.is_tracked(), new_entry.state.is_tracked()) {
(false, true) => 1, (false, true) => 1,
(true, false) => -1, (true, false) => -1,
_ => 0, _ => 0,
}; };
node.entry = Some(new_entry); let node = Self::get_or_insert_node_tracing_ancestors(
if let Some(source) = new_copy_source { &mut self.root,
node.copy_source = source path,
} |ancestor| {
// Borrow of `self.root` through `node` ends here // We can’t use `+= increment` because the counter is unsigned,
// and we want debug builds to detect accidental underflow
// through zero
match tracked_count_increment { match tracked_count_increment {
1 => self.for_each_ancestor_node(path, |node| { 1 => ancestor.tracked_descendants_count += 1,
node.tracked_descendants_count += 1 -1 => ancestor.tracked_descendants_count -= 1,
}),
// We can’t use `+= -1` because the counter is unsigned
-1 => self.for_each_ancestor_node(path, |node| {
node.tracked_descendants_count -= 1
}),
_ => {} _ => {}
} }
},
);
if node.entry.is_none() {
self.nodes_with_entry_count += 1
}
node.entry = Some(new_entry)
} }
fn iter_nodes<'a>( fn iter_nodes<'a>(
&'a self, &'a self,
) -> impl Iterator<Item = (&'a WithBasename<HgPathBuf>, &'a Node)> + 'a ) -> impl Iterator<Item = (&'a WithBasename<HgPathBuf>, &'a Node)> + 'a
{ {
// Depth first tree traversal. // Depth first tree traversal.
// //
self.root.clear(); self.root.clear();
self.nodes_with_entry_count = 0; self.nodes_with_entry_count = 0;
self.nodes_with_copy_source_count = 0; self.nodes_with_copy_source_count = 0;
} }
fn add_file( fn add_file(
&mut self, &mut self,
filename: &HgPath, filename: &HgPath,
_old_state: EntryState, old_state: EntryState,
entry: DirstateEntry, entry: DirstateEntry,
) -> Result<(), DirstateMapError> { ) -> Result<(), DirstateMapError> {
self.add_file_node(filename, entry, None); self.add_or_remove_file(filename, old_state, entry);
Ok(()) Ok(())
} }
fn remove_file( fn remove_file(
&mut self, &mut self,
filename: &HgPath, filename: &HgPath,
_old_state: EntryState, old_state: EntryState,
size: i32, size: i32,
) -> Result<(), DirstateMapError> { ) -> Result<(), DirstateMapError> {
let entry = DirstateEntry { let entry = DirstateEntry {
state: EntryState::Removed, state: EntryState::Removed,
mode: 0, mode: 0,
size, size,
mtime: 0, mtime: 0,
}; };
self.add_file_node(filename, entry, None); self.add_or_remove_file(filename, old_state, entry);
Ok(()) Ok(())
} }
fn drop_file( fn drop_file(
&mut self, &mut self,
filename: &HgPath, filename: &HgPath,
_old_state: EntryState, old_state: EntryState,
) -> Result<bool, DirstateMapError> { ) -> Result<bool, DirstateMapError> {
if let Some(node) = Self::get_node_mut(&mut self.root, filename) { let was_tracked = old_state.is_tracked();
let was_tracked = node.is_tracked_file(); if let Some(node) = Self::get_node_mut_tracing_ancestors(
&mut self.root,
filename,
|ancestor| {
if was_tracked {
ancestor.tracked_descendants_count -= 1
}
},
) {
let had_entry = node.entry.is_some(); let had_entry = node.entry.is_some();
let had_copy_source = node.copy_source.is_some(); let had_copy_source = node.copy_source.is_some();
// TODO: this leaves in the tree a "non-file" node. Should we // TODO: this leaves in the tree a "non-file" node. Should we
// remove the node instead, together with ancestor nodes for // remove the node instead, together with ancestor nodes for
// directories that become empty? // directories that become empty?
node.entry = None; node.entry = None;
node.copy_source = None; node.copy_source = None;
if had_entry { if had_entry {
self.nodes_with_entry_count -= 1 self.nodes_with_entry_count -= 1
} }
if had_copy_source { if had_copy_source {
self.nodes_with_copy_source_count -= 1 self.nodes_with_copy_source_count -= 1
} }
if was_tracked {
self.for_each_ancestor_node(filename, |node| {
node.tracked_descendants_count -= 1
})
}
Ok(had_entry) Ok(had_entry)
} else { } else {
assert!(!was_tracked);
Ok(false) Ok(false)
} }
} }
fn clear_ambiguous_times(&mut self, filenames: Vec<HgPathBuf>, now: i32) { fn clear_ambiguous_times(&mut self, filenames: Vec<HgPathBuf>, now: i32) {
for filename in filenames { for filename in filenames {
if let Some(node) = Self::get_node_mut(&mut self.root, &filename) { if let Some(node) = Self::get_node_mut(&mut self.root, &filename) {
if let Some(entry) = node.entry.as_mut() { if let Some(entry) = node.entry.as_mut() {
) -> Result<Option<&'a DirstateParents>, DirstateError> { ) -> Result<Option<&'a DirstateParents>, DirstateError> {
if file_contents.is_empty() { if file_contents.is_empty() {
return Ok(None); return Ok(None);
} }
let parents = parse_dirstate_entries( let parents = parse_dirstate_entries(
file_contents, file_contents,
|path, entry, copy_source| { |path, entry, copy_source| {
self.add_file_node( let tracked = entry.state.is_tracked();
let node = Self::get_or_insert_node_tracing_ancestors(
&mut self.root,
path, path,
*entry, |ancestor| {
Some(copy_source.map(HgPath::to_owned)), if tracked {
) ancestor.tracked_descendants_count += 1
}
},
);
assert!(
node.entry.is_none(),
"duplicate dirstate entry in read"
);
assert!(
node.copy_source.is_none(),
"duplicate dirstate entry in read"
);
node.entry = Some(*entry);
node.copy_source = copy_source.map(HgPath::to_owned);
self.nodes_with_entry_count += 1;
if copy_source.is_some() {
self.nodes_with_copy_source_count += 1
}
}, },
)?; )?;
if !self.dirty_parents { if !self.dirty_parents {
self.set_parents(parents); self.set_parents(parents);
} }
Ok(Some(parents)) Ok(Some(parents))