This is an archive of the discontinued Mercurial Phabricator instance.

Differential D9488

match: skip walking up the directory hierarchy if the number of pats are small
ClosedPublic

Authored by spectral on Dec 1 2020, 6:06 PM.

Details

Reviewers
pulkit
Group Reviewers
hg-reviewers
Commits
rHGc4c7a6b61146: match: skip walking up the directory hierarchy if the number of pats are small
Summary

Previously, we would receive a path like abc/def/ghi and "walk up" the directory
hierarchy, checking abc/def, abc, and b'' to see if they were in the set of
prefixes that this matcher covered. We did this indiscriminately - we generated
all of these paths even if the set of prefixes the matcher covered was
completely empty, which is the case for a lot of repos at my company (the narrow
matcher we use is usually non-recursive).

This brings the time for a rebase in one of my repos from 12.20s to 10.87s. In
this particular repo, this is entirely due to the len(prefix_set) == 0 check,
as I do not have any recursive patterns in the narrowspec.

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

spectral created this revision.Dec 1 2020, 6:06 PM
pulkit accepted this revision.Dec 2 2020, 2:09 AM
This revision is now accepted and ready to land.Dec 2 2020, 2:09 AM

Revision Contents
Changeset List

PathPackages
Mmercurial/match.py (50 lines)

Diff 23933

mercurial/match.py

@encoding.strmethod @encoding.strmethod
def __repr__(self): def __repr__(self):
s = stringutil.buildrepr(self._predrepr) or pycompat.byterepr( s = stringutil.buildrepr(self._predrepr) or pycompat.byterepr(
self.matchfn self.matchfn
) )
return b'<predicatenmatcher pred=%s>' % s return b'<predicatenmatcher pred=%s>' % s
def path_or_parents_in_set(path, prefix_set):
"""Returns True if `path` (or any parent of `path`) is in `prefix_set`."""
l = len(prefix_set)
if l == 0:
return False
if path in prefix_set:
return True
# If there's more than 5 paths in prefix_set, it's *probably* quicker to
# "walk up" the directory hierarchy instead, with the assumption that most
# directory hierarchies are relatively shallow and hash lookup is cheap.
if l > 5:
return any(
parentdir in prefix_set for parentdir in pathutil.finddirs(path)
)
# FIXME: Ideally we'd never get to this point if this is the case - we'd
# recognize ourselves as an 'always' matcher and skip this.
if b'' in prefix_set:
return True
if pycompat.ispy3:
sl = ord(b'/')
else:
sl = '/'
# We already checked that path isn't in prefix_set exactly, so
# `path[len(pf)] should never raise IndexError.
return any(path.startswith(pf) and path[len(pf)] == sl for pf in prefix_set)
class patternmatcher(basematcher): class patternmatcher(basematcher):
r"""Matches a set of (kind, pat, source) against a 'root' directory. r"""Matches a set of (kind, pat, source) against a 'root' directory.
>>> kindpats = [ >>> kindpats = [
... (b're', br'.*\.c$', b''), ... (b're', br'.*\.c$', b''),
... (b'path', b'foo/a', b''), ... (b'path', b'foo/a', b''),
... (b'relpath', b'b', b''), ... (b'relpath', b'b', b''),
... (b'glob', b'*.h', b''), ... (b'glob', b'*.h', b''),
@propertycache @propertycache
def _dirs(self): def _dirs(self):
return set(pathutil.dirs(self._fileset)) return set(pathutil.dirs(self._fileset))
def visitdir(self, dir): def visitdir(self, dir):
if self._prefix and dir in self._fileset: if self._prefix and dir in self._fileset:
return b'all' return b'all'
return ( return (
dir in self._fileset dir in self._dirs
or dir in self._dirs or path_or_parents_in_set(dir, self._fileset)
or any(
parentdir in self._fileset
for parentdir in pathutil.finddirs(dir)
)
) )
def visitchildrenset(self, dir): def visitchildrenset(self, dir):
ret = self.visitdir(dir) ret = self.visitdir(dir)
if ret is True: if ret is True:
return b'this' return b'this'
elif not ret: elif not ret:
return set() return set()
# parents are directories which are non-recursively included because # parents are directories which are non-recursively included because
# they are needed to get to items in _dirs or _roots. # they are needed to get to items in _dirs or _roots.
self._parents = parents self._parents = parents
def visitdir(self, dir): def visitdir(self, dir):
if self._prefix and dir in self._roots: if self._prefix and dir in self._roots:
return b'all' return b'all'
return ( return (
dir in self._roots dir in self._dirs
or dir in self._dirs
or dir in self._parents or dir in self._parents
or any( or path_or_parents_in_set(dir, self._roots)
parentdir in self._roots for parentdir in pathutil.finddirs(dir)
)
) )
@propertycache @propertycache
def _allparentschildren(self): def _allparentschildren(self):
# It may seem odd that we add dirs, roots, and parents, and then # It may seem odd that we add dirs, roots, and parents, and then
# restrict to only parents. This is to catch the case of: # restrict to only parents. This is to catch the case of:
# dirs = ['foo/bar'] # dirs = ['foo/bar']
# parents = ['foo'] # parents = ['foo']
# if we asked for the children of 'foo', but had only added # if we asked for the children of 'foo', but had only added
# self._parents, we wouldn't be able to respond ['bar']. # self._parents, we wouldn't be able to respond ['bar'].
return _dirchildren( return _dirchildren(
itertools.chain(self._dirs, self._roots, self._parents), itertools.chain(self._dirs, self._roots, self._parents),
onlyinclude=self._parents, onlyinclude=self._parents,
) )
def visitchildrenset(self, dir): def visitchildrenset(self, dir):
if self._prefix and dir in self._roots: if self._prefix and dir in self._roots:
return b'all' return b'all'
# Note: this does *not* include the 'dir in self._parents' case from # Note: this does *not* include the 'dir in self._parents' case from
# visitdir, that's handled below. # visitdir, that's handled below.
if ( if (
b'' in self._roots b'' in self._roots
or dir in self._roots
or dir in self._dirs or dir in self._dirs
or any( or path_or_parents_in_set(dir, self._roots)
parentdir in self._roots for parentdir in pathutil.finddirs(dir)
)
): ):
return b'this' return b'this'
if dir in self._parents: if dir in self._parents:
return self._allparentschildren.get(dir) or set() return self._allparentschildren.get(dir) or set()
return set() return set()
@encoding.strmethod @encoding.strmethod