This is an archive of the discontinued Mercurial Phabricator instance.

Differential D8215

rust-status: move to recursive traversal to prepare for parallel traversal
ClosedPublic

Authored by Alphare on Mar 4 2020, 10:29 AM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHGf8a9922a02cb: rust-status: move to recursive traversal to prepare for parallel traversal
Summary

I have looked into traversing the working directory in parallel either
by a recursive or an iterative algorithm. The recursive approach won quite
decisively both in terms of performance and code readability.

You can look at my experiment here:
https://heptapod.octobus.net/Alphare/rayon-recursive-traversal

The chance of a stack overflow happening because the directories get too nested
seems slim.

This change does not yet do anything in parallel.

Diff Detail

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

Event Timeline

Alphare created this revision.Mar 4 2020, 10:29 AM
durin42 added a subscriber: durin42.Mar 4 2020, 4:29 PM

I'm broadly happy with this series, but:

  1. I get test-check-rust-format.t errors
  2. I don't seem to be having any luck running the tests. It looks like the rust module policy doesn't cause the right things to get installed? In particular, HGWITHRUSTEXT=cpython HGMODULEPOLICY=rust+c make clean tests flunks test-remotefilelog-datapack.py because it can't import parsers.so? And it looks like test-dirstate-race.t is just broken by this series?
  3. The re2-missing fallback message breaks tests for users that want rust things, but lack re2. This isn't going to work, I'm afraid.

The series is so big it's not practical for me to figure out which revision(s) I should be commenting on, so hopefully that's actionable feedback...

Alphare updated this revision to Diff 20500.Mar 5 2020, 3:34 AM
Alphare added a subscriber: marmoute.Mar 5 2020, 3:42 AM
In D8215#122325, @durin42 wrote:
  1. I get test-check-rust-format.t errors

Indeed. It appears that none of the machines I use to run the entire test suite (so... not my laptop) have rustfmt installed, which skips this test. I have updated the series to fix this issue, and will install rustfmt where needed.

  1. I don't seem to be having any luck running the tests. It looks like the rust module policy doesn't cause the right things to get installed? In particular, HGWITHRUSTEXT=cpython HGMODULEPOLICY=rust+c make clean tests flunks test-remotefilelog-datapack.py because it can't import parsers.so? And it looks like test-dirstate-race.t is just broken by this series?

I will look into this, this is bad.

  1. The re2-missing fallback message breaks tests for users that want rust things, but lack re2. This isn't going to work, I'm afraid.

@marmoute suggested I do something in debuginstall to check for re2 on the Rust side instead, I think it's a good idea.

The series is so big it's not practical for me to figure out which revision(s) I should be commenting on, so hopefully that's actionable feedback...

It is, thanks!

Alphare added a comment.Mar 6 2020, 3:48 AM
In D8215#122325, @durin42 wrote:

And it looks like test-dirstate-race.t is just broken by this series?

I can't reproduce that however. Do you have a particular way of doing so? Because it's a race test... it might be flaky.

I still don't have a clear solution for the modulepolicy thing, because everything is broken if we use strict policies.

Alphare added a comment.Mar 6 2020, 4:26 AM
In D8215#122642, @Alphare wrote:

I still don't have a clear solution for the modulepolicy thing, because everything is broken if we use strict policies.

It appears that I got confused by an unrelated issue. @marmoute pushed a fix for this as D8245.

Alphare updated this revision to Diff 20561.Mar 6 2020, 11:31 AM
Alphare added a commit: rHGf8a9922a02cb: rust-status: move to recursive traversal to prepare for parallel traversal.Mar 11 2020, 12:25 PM
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHGf8a9922a02cb: rust-status: move to recursive traversal to prepare for parallel traversal (authored by Alphare). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mrust/hg-core/src/dirstate/status.rs (203 lines)

Diff 20458

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

}, },
path_auditor::PathAuditor, path_auditor::PathAuditor,
}, },
CopyMap, DirstateEntry, DirstateMap, EntryState, FastHashMap, CopyMap, DirstateEntry, DirstateMap, EntryState, FastHashMap,
PatternError, PatternError,
}; };
use lazy_static::lazy_static; use lazy_static::lazy_static;
use rayon::prelude::*; use rayon::prelude::*;
use std::collections::VecDeque;
use std::{ use std::{
borrow::Cow, borrow::Cow,
collections::HashSet, collections::HashSet,
fs::{read_dir, DirEntry}, fs::{read_dir, DirEntry},
io::ErrorKind, io::ErrorKind,
ops::Deref, ops::Deref,
path::Path, path::Path,
}; };
pub last_normal_time: i64, pub last_normal_time: i64,
/// Whether we are on a filesystem with UNIX-like exec flags /// Whether we are on a filesystem with UNIX-like exec flags
pub check_exec: bool, pub check_exec: bool,
pub list_clean: bool, pub list_clean: bool,
pub list_unknown: bool, pub list_unknown: bool,
pub list_ignored: bool, pub list_ignored: bool,
} }
/// Dispatch a single file found during `traverse`. /// Dispatch a single entry (file, folder, symlink...) found during `traverse`.
/// If `file` is a folder that needs to be traversed, it will be pushed into /// If the entry is a folder that needs to be traversed, it will be pushed into
/// `work`. /// `work`.
fn traverse_worker<'a>( fn handle_traversed_entry<'a>(
work: &mut VecDeque<HgPathBuf>, dir_entry: &DirEntry,
matcher: &impl Matcher, matcher: &(impl Matcher + Sync),
root_dir: impl AsRef<Path>,
dmap: &DirstateMap, dmap: &DirstateMap,
filename: impl AsRef<HgPath>, filename: impl AsRef<HgPath>,
dir_entry: &DirEntry, old_results: &FastHashMap<Cow<'a, HgPath>, Dispatch>,
ignore_fn: &impl for<'r> Fn(&'r HgPath) -> bool, ignore_fn: &(impl for<'r> Fn(&'r HgPath) -> bool + Sync),
options: StatusOptions, options: StatusOptions,
) -> Option<IoResult<(Cow<'a, HgPath>, Dispatch)>> { ) -> IoResult<Vec<(Cow<'a, HgPath>, Dispatch)>> {
let file_type = match dir_entry.file_type() { let file_type = dir_entry.file_type()?;
Ok(x) => x,
Err(e) => return Some(Err(e.into())),
};
let filename = filename.as_ref(); let filename = filename.as_ref();
let entry_option = dmap.get(filename); let entry_option = dmap.get(filename);
if file_type.is_dir() { if file_type.is_dir() {
// Do we need to traverse it? // Do we need to traverse it?
if !ignore_fn(&filename) || options.list_ignored { if !ignore_fn(&filename) || options.list_ignored {
work.push_front(filename.to_owned()); return traverse_dir(
matcher,
root_dir,
dmap,
filename.to_owned(),
&old_results,
ignore_fn,
options,
);
} }
// Nested `if` until `rust-lang/rust#53668` is stable // Nested `if` until `rust-lang/rust#53668` is stable
if let Some(entry) = entry_option { if let Some(entry) = entry_option {
// Used to be a file, is now a folder // Used to be a file, is now a folder
if matcher.matches_everything() || matcher.matches(&filename) { if matcher.matches_everything() || matcher.matches(&filename) {
return Some(Ok(( return Ok(vec![(
Cow::Owned(filename.to_owned()), Cow::Owned(filename.to_owned()),
dispatch_missing(entry.state), dispatch_missing(entry.state),
))); )]);
} }
} }
} else if file_type.is_file() || file_type.is_symlink() { } else if file_type.is_file() || file_type.is_symlink() {
if let Some(entry) = entry_option { if let Some(entry) = entry_option {
if matcher.matches_everything() || matcher.matches(&filename) { if matcher.matches_everything() || matcher.matches(&filename) {
let metadata = match dir_entry.metadata() { let metadata = dir_entry.metadata()?;
Ok(x) => x, return Ok(vec![(
Err(e) => return Some(Err(e.into())),
};
return Some(Ok((
Cow::Owned(filename.to_owned()), Cow::Owned(filename.to_owned()),
dispatch_found( dispatch_found(
&filename, &filename,
*entry, *entry,
HgMetadata::from_metadata(metadata), HgMetadata::from_metadata(metadata),
&dmap.copy_map, &dmap.copy_map,
options, options,
), ),
))); )]);
} }
} else if (matcher.matches_everything() || matcher.matches(&filename)) } else if (matcher.matches_everything() || matcher.matches(&filename))
&& !ignore_fn(&filename) && !ignore_fn(&filename)
{ {
return Some(Ok(( return Ok(vec![(
Cow::Owned(filename.to_owned()), Cow::Owned(filename.to_owned()),
Dispatch::Unknown, Dispatch::Unknown,
))); )]);
} else if ignore_fn(&filename) { } else if ignore_fn(&filename) {
return Some(Ok(( return Ok(vec![(
Cow::Owned(filename.to_owned()), Cow::Owned(filename.to_owned()),
Dispatch::Ignored, Dispatch::Ignored,
))); )]);
} }
} else if let Some(entry) = entry_option { } else if let Some(entry) = entry_option {
// Used to be a file or a folder, now something else. // Used to be a file or a folder, now something else.
if matcher.matches_everything() || matcher.matches(&filename) { if matcher.matches_everything() || matcher.matches(&filename) {
return Some(Ok(( return Ok(vec![(
Cow::Owned(filename.to_owned()), Cow::Owned(filename.to_owned()),
dispatch_missing(entry.state), dispatch_missing(entry.state),
))); )]);
} }
} }
None return Ok(vec![]);
} }
/// Walk the working directory recursively to look for changes compared to the /// Walk the working directory recursively to look for changes compared to the
/// current `DirstateMap`. /// current `DirstateMap`.
fn traverse<'a>( fn traverse<'a>(
matcher: &(impl Matcher + Sync), matcher: &(impl Matcher + Sync),
root_dir: impl AsRef<Path>, root_dir: impl AsRef<Path>,
dmap: &DirstateMap, dmap: &DirstateMap,
path: impl AsRef<HgPath>, path: impl AsRef<HgPath>,
old_results: FastHashMap<Cow<'a, HgPath>, Dispatch>, old_results: FastHashMap<Cow<'a, HgPath>, Dispatch>,
ignore_fn: &(impl for<'r> Fn(&'r HgPath) -> bool + Sync), ignore_fn: &(impl for<'r> Fn(&'r HgPath) -> bool + Sync),
options: StatusOptions, options: StatusOptions,
) -> IoResult<FastHashMap<Cow<'a, HgPath>, Dispatch>> { ) -> IoResult<FastHashMap<Cow<'a, HgPath>, Dispatch>> {
let root_dir = root_dir.as_ref(); let root_dir = root_dir.as_ref();
let mut new_results = FastHashMap::default();
let mut work = VecDeque::new(); let mut new_results: FastHashMap<Cow<'a, HgPath>, Dispatch> =
work.push_front(path.as_ref().to_owned()); traverse_dir(
matcher,
root_dir,
&dmap,
path,
&old_results,
&ignore_fn,
options,
)?
.into_par_iter()
.collect();
new_results.extend(old_results.into_iter());
while let Some(ref directory) = work.pop_front() { Ok(new_results)
}
/// Decides whether the directory needs to be listed, and if so dispatches its
/// entries
fn traverse_dir<'a>(
matcher: &(impl Matcher + Sync),
root_dir: impl AsRef<Path>,
dmap: &DirstateMap,
path: impl AsRef<HgPath>,
old_results: &FastHashMap<Cow<'a, HgPath>, Dispatch>,
ignore_fn: &(impl for<'r> Fn(&'r HgPath) -> bool + Sync),
options: StatusOptions,
) -> IoResult<Vec<(Cow<'a, HgPath>, Dispatch)>> {
let directory = path.as_ref();
if directory.as_bytes() == b".hg" { if directory.as_bytes() == b".hg" {
continue; return Ok(vec![]);
} }
let visit_entries = match matcher.visit_children_set(directory) { let visit_entries = match matcher.visit_children_set(directory) {
VisitChildrenSet::Empty => continue, VisitChildrenSet::Empty => return Ok(vec![]),
VisitChildrenSet::This | VisitChildrenSet::Recursive => None, VisitChildrenSet::This | VisitChildrenSet::Recursive => None,
VisitChildrenSet::Set(set) => Some(set), VisitChildrenSet::Set(set) => Some(set),
}; };
let buf = hg_path_to_path_buf(directory)?; let buf = hg_path_to_path_buf(directory)?;
let dir_path = root_dir.join(buf); let dir_path = root_dir.as_ref().join(buf);
let skip_dot_hg = !directory.as_bytes().is_empty(); let skip_dot_hg = !directory.as_bytes().is_empty();
let entries = match list_directory(dir_path, skip_dot_hg) { let entries = match list_directory(dir_path, skip_dot_hg) {
Err(e) => match e.kind() { Err(e) => match e.kind() {
ErrorKind::NotFound | ErrorKind::PermissionDenied => { ErrorKind::NotFound | ErrorKind::PermissionDenied => {
new_results.insert( return Ok(vec![(
Cow::Owned(directory.to_owned()), Cow::Owned(directory.to_owned()),
Dispatch::Bad(BadMatch::OsError( Dispatch::Bad(BadMatch::OsError(
// Unwrapping here is OK because the error always // Unwrapping here is OK because the error always
// is a real os error // is a real os error
e.raw_os_error().unwrap(), e.raw_os_error().unwrap(),
)), )),
); )]);
continue;
} }
_ => return Err(e), _ => return Err(e),
}, },
Ok(entries) => entries, Ok(entries) => entries,
}; };
let mut new_results = vec![];
for (filename, dir_entry) in entries { for (filename, dir_entry) in entries {
if let Some(ref set) = visit_entries { if let Some(ref set) = visit_entries {
if !set.contains(filename.deref()) { if !set.contains(filename.deref()) {
continue; continue;
} }
} }
// TODO normalize // TODO normalize
let filename = if directory.is_empty() { let filename = if directory.is_empty() {
filename.to_owned() filename.to_owned()
} else { } else {
directory.join(&filename) directory.join(&filename)
}; };
if !old_results.contains_key(filename.deref()) { if !old_results.contains_key(filename.deref()) {
if let Some((res, dispatch)) = traverse_worker( new_results.extend(handle_traversed_entry(
&mut work, matcher, &dmap, &filename, &dir_entry, &dir_entry,
&ignore_fn, options, matcher,
) root_dir.as_ref(),
.transpose()? &dmap,
{ &filename,
new_results.insert(res, dispatch); old_results,
} ignore_fn,
} options,
)?);
} }
} }
new_results.extend(old_results.into_iter());
Ok(new_results) Ok(new_results)
} }
/// Stat all entries in the `DirstateMap` and mark them for dispatch. /// Stat all entries in the `DirstateMap` and mark them for dispatch.
fn stat_dmap_entries( fn stat_dmap_entries(
dmap: &DirstateMap, dmap: &DirstateMap,
root_dir: impl AsRef<Path> + Sync + Send, root_dir: impl AsRef<Path> + Sync + Send,
options: StatusOptions, options: StatusOptions,