This is an archive of the discontinued Mercurial Phabricator instance.

Differential D10366

rust: Refactor parse_dirstate() to take a callback
AbandonedPublic

Authored by SimonSapin on Apr 12 2021, 8:23 AM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Summary

The callback is called each entry, with optional copy source,
instead of having parse_dirstate() return separate Vecs for copy mappings
and the rest of the data.

This avoids an intermediate heap allocation, but more importantly will allow
the dirstate tree experiment to store copy data next to the rest of data
instead of a separate mapping.

Diff Detail

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

Event Timeline

SimonSapin created this revision.Apr 12 2021, 8:23 AM
SimonSapin abandoned this revision.Apr 19 2021, 10:54 AM

In https://phab.mercurial-scm.org/D10362#159004 I was worried about potential perf impact, measured, and found none.

However when measuring the entire stack instead of just the first patch I found some regressions (7~12% more wall clock time for hg status or hg status -mard) and bisected them to this patch. This patch changes parse_dirstate from returning a pair of Vec that are then turned into HashMaps with Iterator::collect, to taking a callback that is called for each entry to directly insert into HashMaps. I expected that skipping the intermediate Vecs would be a slight improvement (or negligible), but this turns out slower because this starts with small maps and reallocate several times as they grow. Reallocating a HashMap is more expensive than reallocating a Vec because it involves re-hashing. Profiling one case shows ~10% time spend in RawTable::reserve_rehash in the hashbrown crate. Iterator::collect however can rely on Iterator::size_hint (which is accurate when starting from a Vec) and make a correctly-sized HashMap from the start, without re-hashing.

Therefore I’m rescinding most of this patch, in order to keep the intermediate Vec for the current DirstateMap and avoid the perf regression. The experimental tree-based DirstateMap still uses a callback, but that is small patch so I’ve folded it into D10367.

It might be possible to skip the intermediate Vec without adding re-hashing if we can pre-allocate a correctly-sized HashMap. Finding the accurate size would require parsing, but maybe an estimate would be good enough. The equivalent Python code does this: https://www.mercurial-scm.org/repo/hg-committed/file/5.7.1/mercurial/dirstate.py#l1660. However this unrelated to the initial goal of this patch and can be pursued separately.

Revision Contents
Changeset List

Diff 26819

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

pub fn read<'a>( pub fn read<'a>(
&mut self, &mut self,
file_contents: &'a [u8], file_contents: &'a [u8],
) -> 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, entries, copies) = parse_dirstate(file_contents)?; let parents =
self.state_map.extend( parse_dirstate(file_contents, |path, entry, copy_source| {
entries self.state_map.insert(path.to_owned(), *entry);
.into_iter() if let Some(copy) = copy_source {
.map(|(path, entry)| (path.to_owned(), entry)), self.copy_map.insert(path.to_owned(), copy.to_owned());
); }
self.copy_map.extend( })?;
copies
.into_iter()
.map(|(path, copy)| (path.to_owned(), copy.to_owned())),
);
if !self.dirty_parents { if !self.dirty_parents {
self.set_parents(&parents); self.set_parents(parents);
} }
Ok(Some(parents)) Ok(Some(parents))
} }
pub fn pack( pub fn pack(
&mut self, &mut self,
parents: DirstateParents, parents: DirstateParents,

rust/hg-core/src/dirstate/parsers.rs

use std::convert::{TryFrom, TryInto}; use std::convert::{TryFrom, TryInto};
use std::time::Duration; use std::time::Duration;
/// Parents are stored in the dirstate as byte hashes. /// Parents are stored in the dirstate as byte hashes.
pub const PARENT_SIZE: usize = 20; pub const PARENT_SIZE: usize = 20;
/// Dirstate entries have a static part of 8 + 32 + 32 + 32 + 32 bits. /// Dirstate entries have a static part of 8 + 32 + 32 + 32 + 32 bits.
const MIN_ENTRY_SIZE: usize = 17; const MIN_ENTRY_SIZE: usize = 17;
type ParseResult<'a> = (
&'a DirstateParents,
Vec<(&'a HgPath, DirstateEntry)>,
Vec<(&'a HgPath, &'a HgPath)>,
);
pub fn parse_dirstate_parents( pub fn parse_dirstate_parents(
contents: &[u8], contents: &[u8],
) -> Result<&DirstateParents, HgError> { ) -> Result<&DirstateParents, HgError> {
let (parents, _rest) = DirstateParents::from_bytes(contents) let (parents, _rest) = DirstateParents::from_bytes(contents)
.map_err(|_| HgError::corrupted("Too little data for dirstate."))?; .map_err(|_| HgError::corrupted("Too little data for dirstate."))?;
Ok(parents) Ok(parents)
} }
/// `each_entry` is called for each entry with (path, metadata, optional copy
/// source)
#[timed] #[timed]
pub fn parse_dirstate(mut contents: &[u8]) -> Result<ParseResult, HgError> { pub fn parse_dirstate<'a>(
let mut copies = Vec::new(); mut contents: &'a [u8],
let mut entries = Vec::new(); mut each_entry: impl FnMut(&'a HgPath, &DirstateEntry, Option<&'a HgPath>),
) -> Result<&'a DirstateParents, HgError> {
let (parents, rest) = DirstateParents::from_bytes(contents) let (parents, rest) = DirstateParents::from_bytes(contents)
.map_err(|_| HgError::corrupted("Too little data for dirstate."))?; .map_err(|_| HgError::corrupted("Too little data for dirstate."))?;
contents = rest; contents = rest;
while !contents.is_empty() { while !contents.is_empty() {
let (raw_entry, rest) = RawEntry::from_bytes(contents) let (raw_entry, rest) = RawEntry::from_bytes(contents)
.map_err(|_| HgError::corrupted("Overflow in dirstate."))?; .map_err(|_| HgError::corrupted("Overflow in dirstate."))?;
let entry = DirstateEntry { let entry = DirstateEntry {
state: EntryState::try_from(raw_entry.state)?, state: EntryState::try_from(raw_entry.state)?,
mode: raw_entry.mode.get(), mode: raw_entry.mode.get(),
mtime: raw_entry.mtime.get(), mtime: raw_entry.mtime.get(),
size: raw_entry.size.get(), size: raw_entry.size.get(),
}; };
let (paths, rest) = let (paths, rest) =
u8::slice_from_bytes(rest, raw_entry.length.get() as usize) u8::slice_from_bytes(rest, raw_entry.length.get() as usize)
.map_err(|_| HgError::corrupted("Overflow in dirstate."))?; .map_err(|_| HgError::corrupted("Overflow in dirstate."))?;
// `paths` is either a single path, or two paths separated by a NULL // `paths` is either a single path, or two paths separated by a NULL
// byte // byte
let mut iter = paths.splitn(2, |&byte| byte == b'\0'); let mut iter = paths.splitn(2, |&byte| byte == b'\0');
let path = HgPath::new( let path = HgPath::new(
iter.next().expect("splitn always yields at least one item"), iter.next().expect("splitn always yields at least one item"),
); );
if let Some(copy_source) = iter.next() { let copy_source = iter.next().map(HgPath::new);
copies.push((path, HgPath::new(copy_source)));
} each_entry(path, &entry, copy_source);
entries.push((path, entry));
contents = rest; contents = rest;
} }
Ok((parents, entries, copies)) Ok(parents)
} }
/// `now` is the duration in seconds since the Unix epoch /// `now` is the duration in seconds since the Unix epoch
pub fn pack_dirstate( pub fn pack_dirstate(
state_map: &mut StateMap, state_map: &mut StateMap,
copy_map: &CopyMap, copy_map: &CopyMap,
parents: DirstateParents, parents: DirstateParents,
now: Duration, now: Duration,
p1: b"12345678910111213141".into(), p1: b"12345678910111213141".into(),
p2: b"00000000000000000000".into(), p2: b"00000000000000000000".into(),
}; };
let now = Duration::new(15000000, 0); let now = Duration::new(15000000, 0);
let result = let result =
pack_dirstate(&mut state_map, &copymap, parents.clone(), now) pack_dirstate(&mut state_map, &copymap, parents.clone(), now)
.unwrap(); .unwrap();
let (new_parents, entries, copies) = let mut new_state_map = StateMap::default();
parse_dirstate(result.as_slice()).unwrap(); let mut new_copy_map = CopyMap::default();
let new_state_map: StateMap = entries let new_parents =
.into_iter() parse_dirstate(&result, |path, entry, copy_source| {
.map(|(path, entry)| (path.to_owned(), entry)) new_state_map.insert(path.to_owned(), *entry);
.collect(); if let Some(copy) = copy_source {
let new_copy_map: CopyMap = copies new_copy_map.insert(path.to_owned(), copy.to_owned());
.into_iter() }
.map(|(path, copy)| (path.to_owned(), copy.to_owned())) })
.collect(); .unwrap();
assert_eq!( assert_eq!(
(&parents, state_map, copymap), (&parents, state_map, copymap),
(new_parents, new_state_map, new_copy_map) (new_parents, new_state_map, new_copy_map)
) )
} }
#[test] #[test]
p1: b"12345678910111213141".into(), p1: b"12345678910111213141".into(),
p2: b"00000000000000000000".into(), p2: b"00000000000000000000".into(),
}; };
let now = Duration::new(15000000, 0); let now = Duration::new(15000000, 0);
let result = let result =
pack_dirstate(&mut state_map, &copymap, parents.clone(), now) pack_dirstate(&mut state_map, &copymap, parents.clone(), now)
.unwrap(); .unwrap();
let (new_parents, entries, copies) = let mut new_state_map = StateMap::default();
parse_dirstate(result.as_slice()).unwrap(); let mut new_copy_map = CopyMap::default();
let new_state_map: StateMap = entries let new_parents =
.into_iter() parse_dirstate(&result, |path, entry, copy_source| {
.map(|(path, entry)| (path.to_owned(), entry)) new_state_map.insert(path.to_owned(), *entry);
.collect(); if let Some(copy) = copy_source {
let new_copy_map: CopyMap = copies new_copy_map.insert(path.to_owned(), copy.to_owned());
.into_iter() }
.map(|(path, copy)| (path.to_owned(), copy.to_owned())) })
.collect(); .unwrap();
assert_eq!( assert_eq!(
(&parents, state_map, copymap), (&parents, state_map, copymap),
(new_parents, new_state_map, new_copy_map) (new_parents, new_state_map, new_copy_map)
) )
} }
#[test] #[test]
p1: b"12345678910111213141".into(), p1: b"12345678910111213141".into(),
p2: b"00000000000000000000".into(), p2: b"00000000000000000000".into(),
}; };
let now = Duration::new(15000000, 0); let now = Duration::new(15000000, 0);
let result = let result =
pack_dirstate(&mut state_map, &copymap, parents.clone(), now) pack_dirstate(&mut state_map, &copymap, parents.clone(), now)
.unwrap(); .unwrap();
let (new_parents, entries, copies) = let mut new_state_map = StateMap::default();
parse_dirstate(result.as_slice()).unwrap(); let mut new_copy_map = CopyMap::default();
let new_state_map: StateMap = entries let new_parents =
.into_iter() parse_dirstate(&result, |path, entry, copy_source| {
.map(|(path, entry)| (path.to_owned(), entry)) new_state_map.insert(path.to_owned(), *entry);
.collect(); if let Some(copy) = copy_source {
let new_copy_map: CopyMap = copies new_copy_map.insert(path.to_owned(), copy.to_owned());
.into_iter() }
.map(|(path, copy)| (path.to_owned(), copy.to_owned())) })
.collect(); .unwrap();
assert_eq!( assert_eq!(
( (
&parents, &parents,
[( [(
HgPathBuf::from_bytes(b"f1"), HgPathBuf::from_bytes(b"f1"),
DirstateEntry { DirstateEntry {
state: EntryState::Normal, state: EntryState::Normal,

rust/hg-core/src/operations/list_tracked_files.rs

impl Dirstate { impl Dirstate {
pub fn new(repo: &Repo) -> Result<Self, HgError> { pub fn new(repo: &Repo) -> Result<Self, HgError> {
let content = repo.hg_vfs().read("dirstate")?; let content = repo.hg_vfs().read("dirstate")?;
Ok(Self { content }) Ok(Self { content })
} }
pub fn tracked_files(&self) -> Result<Vec<&HgPath>, HgError> { pub fn tracked_files(&self) -> Result<Vec<&HgPath>, HgError> {
let (_, entries, _) = parse_dirstate(&self.content)?; let mut files = Vec::new();
let mut files: Vec<&HgPath> = entries parse_dirstate(&self.content, |path, entry, _| match entry.state {
.into_iter() EntryState::Removed => {}
.filter_map(|(path, entry)| match entry.state { _ => files.push(path),
EntryState::Removed => None, })?;
_ => Some(path),
})
.collect();
files.par_sort_unstable(); files.par_sort_unstable();
Ok(files) Ok(files)
} }
} }
/// List files under Mercurial control at a given revision. /// List files under Mercurial control at a given revision.
pub fn list_rev_tracked_files( pub fn list_rev_tracked_files(
repo: &Repo, repo: &Repo,

rust/hg-cpython/src/parsers.rs

// parsers.rs // parsers.rs
// //
// Copyright 2019 Raphaël Gomès <rgomes@octobus.net> // Copyright 2019 Raphaël Gomès <rgomes@octobus.net>
// //
// This software may be used and distributed according to the terms of the // This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version. // GNU General Public License version 2 or any later version.
//! Bindings for the `hg::dirstate::parsers` module provided by the //! Bindings for the `hg::dirstate::parsers` module provided by the
//! `hg-core` package. //! `hg-core` package.
//! //!
//! From Python, this will be seen as `mercurial.rustext.parsers` //! From Python, this will be seen as `mercurial.rustext.parsers`
use cpython::{ use cpython::{
exc, PyBytes, PyDict, PyErr, PyInt, PyModule, PyResult, PyTuple, Python, exc, PyBytes, PyDict, PyErr, PyInt, PyModule, PyResult, PyTuple, Python,
PythonObject, ToPyObject, PythonObject, ToPyObject,
}; };
use hg::{ use hg::{
pack_dirstate, parse_dirstate, utils::hg_path::HgPathBuf, DirstateEntry, pack_dirstate, parse_dirstate, utils::hg_path::HgPathBuf, DirstateParents,
DirstateParents, FastHashMap, PARENT_SIZE, FastHashMap, PARENT_SIZE,
}; };
use std::convert::TryInto; use std::convert::TryInto;
use crate::dirstate::{extract_dirstate, make_dirstate_tuple}; use crate::dirstate::{extract_dirstate, make_dirstate_tuple};
use std::time::Duration; use std::time::Duration;
fn parse_dirstate_wrapper( fn parse_dirstate_wrapper(
py: Python, py: Python,
dmap: PyDict, dmap: PyDict,
copymap: PyDict, copymap: PyDict,
st: PyBytes, st: PyBytes,
) -> PyResult<PyTuple> { ) -> PyResult<PyTuple> {
match parse_dirstate(st.data(py)) { let mut py_result = Ok(());
Ok((parents, entries, copies)) => { let result = parse_dirstate(st.data(py), |path, entry, copy_source| {
let dirstate_map: FastHashMap<HgPathBuf, DirstateEntry> = entries if py_result.is_err() {
.into_iter() return;
.map(|(path, entry)| (path.to_owned(), entry)) }
.collect(); macro_rules! handle_py_result {
let copy_map: FastHashMap<HgPathBuf, HgPathBuf> = copies ($e: expr) => {
.into_iter() match $e {
.map(|(path, copy)| (path.to_owned(), copy.to_owned())) Ok(value) => value,
.collect(); Err(error) => {
py_result = Err(error);
for (filename, entry) in &dirstate_map { return;
dmap.set_item( }
py,
PyBytes::new(py, filename.as_bytes()),
make_dirstate_tuple(py, entry)?,
)?;
} }
for (path, copy_path) in copy_map { };
copymap.set_item( }
handle_py_result!(dmap.set_item(
py, py,
PyBytes::new(py, path.as_bytes()), PyBytes::new(py, path.as_bytes()),
PyBytes::new(py, copy_path.as_bytes()), handle_py_result!(make_dirstate_tuple(py, entry)),
)?; ));
}
Ok(dirstate_parents_to_pytuple(py, parents)) if let Some(copy) = copy_source {
handle_py_result!(copymap.set_item(
py,
PyBytes::new(py, path.as_bytes()),
PyBytes::new(py, copy.as_bytes()),
));
} }
});
py_result?;
match result {
Ok(parents) => Ok(dirstate_parents_to_pytuple(py, parents)),
Err(e) => Err(PyErr::new::<exc::ValueError, _>(py, e.to_string())), Err(e) => Err(PyErr::new::<exc::ValueError, _>(py, e.to_string())),
} }
} }
fn pack_dirstate_wrapper( fn pack_dirstate_wrapper(
py: Python, py: Python,
dmap: PyDict, dmap: PyDict,
copymap: PyDict, copymap: PyDict,