This is an archive of the discontinued Mercurial Phabricator instance.

Differential D8491

rust-filepatterns: match exact `rootglob`s with a `HashSet`, not in the regex
ClosedPublic

Authored by Alphare on May 6 2020, 9:11 AM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHGe0414fcd35e0: rust-filepatterns: match exact `rootglob`s with a `HashSet`, not in the regex
Summary

This optimization yields some very interesting results in rootglob-heavy
repositories.

I build a test repository of the following structure:

root
    /<uuid>/build/empty_file
    ... repeat for 4000 entries

and a .hgignore containing the corresponding 4000 rootglob entries pointing
to all build/ folders.

Rust+c hg status goes from 350ms down to 110ms.

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.

Event Timeline

Alphare created this revision.May 6 2020, 9:11 AM
Alphare added a commit: rHGe0414fcd35e0: rust-filepatterns: match exact `rootglob`s with a `HashSet`, not in the regex.May 7 2020, 2:20 PM
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHGe0414fcd35e0: rust-filepatterns: match exact `rootglob`s with a `HashSet`, not in the regex (authored by Alphare). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 21309

rust/hg-core/src/filepatterns.rs

new_bytes new_bytes
} }
} }
/// Wrapper function to `_build_single_regex` that short-circuits 'exact' globs /// Wrapper function to `_build_single_regex` that short-circuits 'exact' globs
/// that don't need to be transformed into a regex. /// that don't need to be transformed into a regex.
pub fn build_single_regex( pub fn build_single_regex(
entry: &IgnorePattern, entry: &IgnorePattern,
) -> Result<Vec<u8>, PatternError> { ) -> Result<Option<Vec<u8>>, PatternError> {
let IgnorePattern { let IgnorePattern {
pattern, syntax, .. pattern, syntax, ..
} = entry; } = entry;
let pattern = match syntax { let pattern = match syntax {
PatternSyntax::RootGlob PatternSyntax::RootGlob
| PatternSyntax::Path | PatternSyntax::Path
| PatternSyntax::RelGlob | PatternSyntax::RelGlob
| PatternSyntax::RootFiles => normalize_path_bytes(&pattern), | PatternSyntax::RootFiles => normalize_path_bytes(&pattern),
PatternSyntax::Include | PatternSyntax::SubInclude => { PatternSyntax::Include | PatternSyntax::SubInclude => {
return Err(PatternError::NonRegexPattern(entry.clone())) return Err(PatternError::NonRegexPattern(entry.clone()))
} }
_ => pattern.to_owned(), _ => pattern.to_owned(),
}; };
if *syntax == PatternSyntax::RootGlob if *syntax == PatternSyntax::RootGlob
&& !pattern.iter().any(|b| GLOB_SPECIAL_CHARACTERS.contains(b)) && !pattern.iter().any(|b| GLOB_SPECIAL_CHARACTERS.contains(b))
{ {
// The `regex` crate adds `.*` to the start and end of expressions Ok(None)
// if there are no anchors, so add the start anchor.
let mut escaped = vec![b'^'];
escaped.extend(escape_pattern(&pattern));
escaped.extend(GLOB_SUFFIX);
Ok(escaped)
} else { } else {
let mut entry = entry.clone(); let mut entry = entry.clone();
entry.pattern = pattern; entry.pattern = pattern;
Ok(_build_single_regex(&entry)) Ok(Some(_build_single_regex(&entry)))
} }
} }
lazy_static! { lazy_static! {
static ref SYNTAXES: FastHashMap<&'static [u8], &'static [u8]> = { static ref SYNTAXES: FastHashMap<&'static [u8], &'static [u8]> = {
let mut m = FastHashMap::default(); let mut m = FastHashMap::default();
m.insert(b"re".as_ref(), b"relre:".as_ref()); m.insert(b"re".as_ref(), b"relre:".as_ref());
fn test_build_single_regex() { fn test_build_single_regex() {
assert_eq!( assert_eq!(
build_single_regex(&IgnorePattern::new( build_single_regex(&IgnorePattern::new(
PatternSyntax::RelGlob, PatternSyntax::RelGlob,
b"rust/target/", b"rust/target/",
Path::new("") Path::new("")
)) ))
.unwrap(), .unwrap(),
br"(?:.*/)?rust/target(?:/|$)".to_vec(), Some(br"(?:.*/)?rust/target(?:/|$)".to_vec()),
); );
} }
#[test] #[test]
fn test_build_single_regex_shortcut() { fn test_build_single_regex_shortcut() {
assert_eq!( assert_eq!(
build_single_regex(&IgnorePattern::new( build_single_regex(&IgnorePattern::new(
PatternSyntax::RootGlob, PatternSyntax::RootGlob,
b"", b"",
Path::new("") Path::new("")
)) ))
.unwrap(), .unwrap(),
br"^\.(?:/|$)".to_vec(), None,
); );
assert_eq!( assert_eq!(
build_single_regex(&IgnorePattern::new( build_single_regex(&IgnorePattern::new(
PatternSyntax::RootGlob, PatternSyntax::RootGlob,
b"whatever", b"whatever",
Path::new("") Path::new("")
)) ))
.unwrap(), .unwrap(),
br"^whatever(?:/|$)".to_vec(), None,
); );
assert_eq!( assert_eq!(
build_single_regex(&IgnorePattern::new( build_single_regex(&IgnorePattern::new(
PatternSyntax::RootGlob, PatternSyntax::RootGlob,
b"*.o", b"*.o",
Path::new("") Path::new("")
)) ))
.unwrap(), .unwrap(),
br"^[^/]*\.o(?:/|$)".to_vec(), Some(br"^[^/]*\.o(?:/|$)".to_vec()),
); );
} }
} }

rust/hg-core/src/matchers.rs

files::find_dirs, files::find_dirs,
hg_path::{HgPath, HgPathBuf}, hg_path::{HgPath, HgPathBuf},
Escaped, Escaped,
}, },
DirsMultiset, DirstateMapError, FastHashMap, IgnorePattern, PatternError, DirsMultiset, DirstateMapError, FastHashMap, IgnorePattern, PatternError,
PatternSyntax, PatternSyntax,
}; };
use crate::filepatterns::normalize_path_bytes;
use std::borrow::ToOwned; use std::borrow::ToOwned;
use std::collections::HashSet; use std::collections::HashSet;
use std::fmt::{Display, Error, Formatter}; use std::fmt::{Display, Error, Formatter};
use std::iter::FromIterator; use std::iter::FromIterator;
use std::ops::Deref; use std::ops::Deref;
use std::path::{Path, PathBuf}; use std::path::{Path, PathBuf};
use micro_timer::timed; use micro_timer::timed;
Ok(move |path: &HgPath| re.is_match(path.as_bytes())) Ok(move |path: &HgPath| re.is_match(path.as_bytes()))
} }
/// Returns the regex pattern and a function that matches an `HgPath` against /// Returns the regex pattern and a function that matches an `HgPath` against
/// said regex formed by the given ignore patterns. /// said regex formed by the given ignore patterns.
fn build_regex_match<'a>( fn build_regex_match<'a>(
ignore_patterns: &'a [&'a IgnorePattern], ignore_patterns: &'a [&'a IgnorePattern],
) -> PatternResult<(Vec<u8>, Box<dyn Fn(&HgPath) -> bool + Sync>)> { ) -> PatternResult<(Vec<u8>, Box<dyn Fn(&HgPath) -> bool + Sync>)> {
let regexps: Result<Vec<_>, PatternError> = ignore_patterns let mut regexps = vec![];
.into_iter() let mut exact_set = HashSet::new();
.map(|k| build_single_regex(*k))
.collect(); for pattern in ignore_patterns {
let regexps = regexps?; if let Some(re) = build_single_regex(pattern)? {
regexps.push(re);
} else {
let exact = normalize_path_bytes(&pattern.pattern);
exact_set.insert(HgPathBuf::from_bytes(&exact));
}
}
let full_regex = regexps.join(&b'|'); let full_regex = regexps.join(&b'|');
// An empty pattern would cause the regex engine to incorrectly match the
// (empty) root directory
let func = if !(regexps.is_empty()) {
let matcher = re_matcher(&full_regex)?; let matcher = re_matcher(&full_regex)?;
let func = Box::new(move |filename: &HgPath| matcher(filename)); let func = move |filename: &HgPath| {
exact_set.contains(filename) || matcher(filename)
};
Box::new(func) as Box<dyn Fn(&HgPath) -> bool + Sync>
} else {
let func = move |filename: &HgPath| exact_set.contains(filename);
Box::new(func) as Box<dyn Fn(&HgPath) -> bool + Sync>
};
Ok((full_regex, func)) Ok((full_regex, func))
} }
/// Returns roots and directories corresponding to each pattern. /// Returns roots and directories corresponding to each pattern.
/// ///
/// This calculates the roots and directories exactly matching the patterns and /// This calculates the roots and directories exactly matching the patterns and
/// returns a tuple of (roots, dirs). It does not return other directories /// returns a tuple of (roots, dirs). It does not return other directories