This is an archive of the discontinued Mercurial Phabricator instance.

Differential D4351

match: improve includematcher.visitchildrenset to be much faster and cached
ClosedPublic

Authored by spectral on Aug 21 2018, 6:18 PM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHG35ecaa999a12: match: improve includematcher.visitchildrenset to be much faster and cached
Summary

This improves the speed of visitchildrenset considerably, especially when there
are complicated matchers involved that may have many entries in _dirs or
_parents.

Unfortunately the benchmark isn't easily upstreamed due to its reliance on
https://github.com/vstinner/perf (primarily due to the conflict when importing
it if I were to contribute the benchmark as contrib/matcherbenchmarks.py)
instead of asv or some other perf measurement system.

To describe the benchmark briefly: I generated an includematcher of either 5 or
3500 "rootfilesin:prefix1/prefix2/prefix3/<randomsubdirs, 1-8 levels deep>"
items in the 'setup' function, and then called
im.visitchildrenset('prefix1/prefix2') in the 'stmt' function in perf.timeit.

For the set of 5:

  • before: 15.3 us +- 2.9 us
  • after: 1.59 us +- 0.02 us

For the set of 3500:

  • before: 3.90 ms +- 0.10 ms
  • after: 3.15 us +- 0.09 us (note the m->u change)

Diff Detail

Repository
rHG Mercurial
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

spectral created this revision.Aug 21 2018, 6:18 PM
durin42 added a subscriber: durin42.Aug 22 2018, 12:39 PM
durin42 added inline comments.
mercurial/match.py
560

could we extract this class to module-level and pass matcherself as a ctor parameter instead?

spectral updated this revision to Diff 10534.Aug 22 2018, 9:00 PM
spectral marked an inline comment as done.Aug 22 2018, 9:00 PM
yuja added a subscriber: yuja.Aug 29 2018, 6:55 PM

Can't apply. Can you rebase?

spectral updated this revision to Diff 10774.Sep 4 2018, 6:44 PM
spectral added a comment.Sep 4 2018, 6:44 PM
In D4351#67751, @yuja wrote:

Can't apply. Can you rebase?

Done, sorry for the delay.

yuja added a comment.Sep 6 2018, 8:08 AM

Queued, thanks.

Closed by commit rHG35ecaa999a12: match: improve includematcher.visitchildrenset to be much faster and cached (authored by spectral). · Explain WhySep 6 2018, 8:13 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mmercurial/match.py (83 lines)

Diff 10534

mercurial/match.py

def prefix(self): def prefix(self):
return self._prefix return self._prefix
@encoding.strmethod @encoding.strmethod
def __repr__(self): def __repr__(self):
return ('<patternmatcher patterns=%r>' % pycompat.bytestr(self._pats)) return ('<patternmatcher patterns=%r>' % pycompat.bytestr(self._pats))
# This is basically a reimplementation of util.dirs that stores the children
# instead of just a count of them, plus a small optional optimization to avoid
# some directories we don't need.
class _dirchildren(object):
def __init__(self, paths, onlyinclude=None):
self._dirs = {}
self._onlyinclude = onlyinclude or []
addpath = self.addpath
for f in paths:
addpath(f)
def addpath(self, path):
if path == '.':
return
dirs = self._dirs
findsplitdirs = _dirchildren._findsplitdirs
for d, b in findsplitdirs(path):
if d not in self._onlyinclude:
continue
dirs.setdefault(d, set()).add(b)
@staticmethod
def _findsplitdirs(path):
# yields (dirname, basename) tuples, walking back to the root. This is
# very similar to util.finddirs, except:
# - produces a (dirname, basename) tuple, not just 'dirname'
# - includes root dir
# Unlike manifest._splittopdir, this does not suffix `dirname` with a
# slash, and produces '.' for the root instead of ''.
oldpos = len(path)
pos = path.rfind('/')
while pos != -1:
yield path[:pos], path[pos + 1:oldpos]
oldpos = pos
pos = path.rfind('/', 0, pos)
yield '.', path[:oldpos]
def get(self, path):
return self._dirs.get(path, set())
class includematcher(basematcher): class includematcher(basematcher):
def __init__(self, root, cwd, kindpats, listsubrepos=False, badfn=None): def __init__(self, root, cwd, kindpats, listsubrepos=False, badfn=None):
super(includematcher, self).__init__(root, cwd, badfn) super(includematcher, self).__init__(root, cwd, badfn)
self._pats, self.matchfn = _buildmatch(kindpats, '(?:/|$)', self._pats, self.matchfn = _buildmatch(kindpats, '(?:/|$)',
listsubrepos, root) listsubrepos, root)
self._prefix = _prefix(kindpats) self._prefix = _prefix(kindpats)
return 'all' return 'all'
return ('.' in self._roots or return ('.' in self._roots or
dir in self._roots or dir in self._roots or
dir in self._dirs or dir in self._dirs or
dir in self._parents or dir in self._parents or
any(parentdir in self._roots any(parentdir in self._roots
for parentdir in util.finddirs(dir))) for parentdir in util.finddirs(dir)))
@propertycache
def _allparentschildren(self):
# It may seem odd that we add dirs, roots, and parents, and then
# restrict to only parents. This is to catch the case of:
# dirs = ['foo/bar']
# parents = ['foo']
durin42Unsubmitted
Done

could we extract this class to module-level and pass matcherself as a ctor parameter instead?

durin42: could we extract this class to module-level and pass matcherself as a ctor parameter instead?
# if we asked for the children of 'foo', but had only added
# self._parents, we wouldn't be able to respond ['bar'].
return _dirchildren(
itertools.chain(self._dirs, self._roots, 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 'all' return '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 ('.' in self._roots or if ('.' in self._roots or
dir in self._roots or dir in self._roots or
dir in self._dirs or dir in self._dirs or
any(parentdir in self._roots any(parentdir in self._roots
for parentdir in util.finddirs(dir))): for parentdir in util.finddirs(dir))):
return 'this' return 'this'
ret = set()
if dir in self._parents: if dir in self._parents:
# We add a '/' on to `dir` so that we don't return items that are return self._allparentschildren.get(dir) or set()
# prefixed by `dir` but are actually siblings of `dir`. return set()
suffixeddir = dir + '/' if dir != '.' else ''
# Look in all _roots, _dirs, and _parents for things that start with
# 'suffixeddir'.
for d in [q for q in
itertools.chain(self._roots, self._dirs, self._parents) if
q.startswith(suffixeddir)]:
# Don't emit '.' in the response for the root directory
if not suffixeddir and d == '.':
continue
# We return the item name without the `suffixeddir` prefix or a
# slash suffix
d = d[len(suffixeddir):]
if '/' in d:
# This is a subdirectory-of-a-subdirectory, i.e.
# suffixeddir='foo/', d was 'foo/bar/baz' before removing
# 'foo/'.
d = d[:d.index('/')]
ret.add(d)
return ret
@encoding.strmethod @encoding.strmethod
def __repr__(self): def __repr__(self):
return ('<includematcher includes=%r>' % pycompat.bytestr(self._pats)) return ('<includematcher includes=%r>' % pycompat.bytestr(self._pats))
class exactmatcher(basematcher): class exactmatcher(basematcher):
'''Matches the input files exactly. They are interpreted as paths, not '''Matches the input files exactly. They are interpreted as paths, not
patterns (so no kind-prefixes). patterns (so no kind-prefixes).
@propertycache @propertycache
def _dirs(self): def _dirs(self):
return set(util.dirs(self._fileset)) | {'.'} return set(util.dirs(self._fileset)) | {'.'}
def visitdir(self, dir): def visitdir(self, dir):
return dir in self._dirs return dir in self._dirs
def visitchildrenset(self, dir): def visitchildrenset(self, dir):
if dir in self._dirs: if self._fileset and dir in self._dirs:
candidates = self._dirs - {'.'} candidates = self._dirs - {'.'}
if dir != '.': if dir != '.':
d = dir + '/' d = dir + '/'
candidates = set(c[len(d):] for c in candidates if candidates = set(c[len(d):] for c in candidates if
c.startswith(d)) c.startswith(d))
# self._dirs includes all of the directories, recursively, so if # self._dirs includes all of the directories, recursively, so if
# we're attempting to match foo/bar/baz.txt, it'll have '.', 'foo', # we're attempting to match foo/bar/baz.txt, it'll have '.', 'foo',
# 'foo/bar' in it. Thus we can safely ignore a candidate that has a # 'foo/bar' in it. Thus we can safely ignore a candidate that has a
p = [] p = []
# Append the parents as non-recursive/exact directories, since they must be # Append the parents as non-recursive/exact directories, since they must be
# scanned to get to either the roots or the other exact directories. # scanned to get to either the roots or the other exact directories.
p.extend(util.dirs(d)) p.extend(util.dirs(d))
p.extend(util.dirs(r)) p.extend(util.dirs(r))
# util.dirs() does not include the root directory, so add it manually # util.dirs() does not include the root directory, so add it manually
p.append('.') p.append('.')
# FIXME: all uses of this function convert these to sets, do so before
# returning.
# FIXME: all uses of this function do not need anything in 'roots' and
# 'dirs' to also be in 'parents', consider removing them before returning.
return r, d, p return r, d, p
def _explicitfiles(kindpats): def _explicitfiles(kindpats):
'''Returns the potential explicit filenames from the patterns. '''Returns the potential explicit filenames from the patterns.
>>> _explicitfiles([(b'path', b'foo/bar', b'')]) >>> _explicitfiles([(b'path', b'foo/bar', b'')])
['foo/bar'] ['foo/bar']
>>> _explicitfiles([(b'rootfilesin', b'foo/bar', b'')]) >>> _explicitfiles([(b'rootfilesin', b'foo/bar', b'')])