This is an archive of the discontinued Mercurial Phabricator instance.

Differential D5058

match: optimize matcher when all patterns are of rootfilesin kind
ClosedPublic

Authored by martinvonz on Oct 13 2018, 5:20 AM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHG19ed212de2d1: match: optimize matcher when all patterns are of rootfilesin kind
Summary

Internally at Google, we use narrowspecs with only rootfilesin-kind
patterns. Sometimes there are thousands of such patterns
(i.e. thousands of tracked directories). In such cases, it can take
quite long to build and evaluate the resulting matcher.

This patch optimizes matchers that have only patterns of rootfilesin
so it instead of creating a regular expression, it matches the given
file's directory against the set of directories.

In a repo with ~3600 tracked directories, it takes about 1.35 s to
build the matcher and 2.7 s to walk the dirstate before this
patch. After, it takes 0.04 s to create the matcher and 0.87 s to walk
the dirstate.

It may be worthwhile to do similar optimizations for e.g. patterns of
type "kind:", but that's not a priority for us right now.

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

martinvonz created this revision.Oct 13 2018, 5:20 AM
Closed by commit rHG19ed212de2d1: match: optimize matcher when all patterns are of rootfilesin kind (authored by martinvonz). · Explain WhyOct 13 2018, 7:50 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mmercurial/match.py (16 lines)
Mtests/test-walk.t (32 lines)

Diff 12046

mercurial/match.py

if mf(f[len(prefix):]): if mf(f[len(prefix):]):
return True return True
return False return False
matchfuncs.append(matchsubinclude) matchfuncs.append(matchsubinclude)
regex = '' regex = ''
if kindpats: if kindpats:
if all(k == 'rootfilesin' for k, p, s in kindpats):
dirs = {p for k, p, s in kindpats}
def mf(f):
i = f.rfind('/')
if i >= 0:
dir = f[:i]
else:
dir = '.'
return dir in dirs
regex = b'rootfilesin: %s' % sorted(dirs)
matchfuncs.append(mf)
else:
regex, mf = _buildregexmatch(kindpats, globsuffix) regex, mf = _buildregexmatch(kindpats, globsuffix)
matchfuncs.append(mf) matchfuncs.append(mf)
if len(matchfuncs) == 1: if len(matchfuncs) == 1:
return regex, matchfuncs[0] return regex, matchfuncs[0]
else: else:
return regex, lambda f: any(mf(f) for mf in matchfuncs) return regex, lambda f: any(mf(f) for mf in matchfuncs)
def _buildregexmatch(kindpats, globsuffix): def _buildregexmatch(kindpats, globsuffix):
"""Build a match function from a list of kinds and kindpats, """Build a match function from a list of kinds and kindpats,

tests/test-walk.t

f beans/borlotti ../beans/borlotti f beans/borlotti ../beans/borlotti
f beans/kidney ../beans/kidney f beans/kidney ../beans/kidney
f beans/navy ../beans/navy f beans/navy ../beans/navy
f beans/pinto ../beans/pinto f beans/pinto ../beans/pinto
f beans/turtle ../beans/turtle f beans/turtle ../beans/turtle
$ hg debugwalk -v 'rootfilesin:' $ hg debugwalk -v 'rootfilesin:'
* matcher: * matcher:
<patternmatcher patterns='(?:[^/]+$)'> <patternmatcher patterns="rootfilesin: ['.']">
f fennel ../fennel f fennel ../fennel
f fenugreek ../fenugreek f fenugreek ../fenugreek
f fiddlehead ../fiddlehead f fiddlehead ../fiddlehead
$ hg debugwalk -v -I 'rootfilesin:' $ hg debugwalk -v -I 'rootfilesin:'
* matcher: * matcher:
<includematcher includes='(?:[^/]+$)'> <includematcher includes="rootfilesin: ['.']">
f fennel ../fennel f fennel ../fennel
f fenugreek ../fenugreek f fenugreek ../fenugreek
f fiddlehead ../fiddlehead f fiddlehead ../fiddlehead
$ hg debugwalk -v 'rootfilesin:.' $ hg debugwalk -v 'rootfilesin:.'
* matcher: * matcher:
<patternmatcher patterns='(?:[^/]+$)'> <patternmatcher patterns="rootfilesin: ['.']">
f fennel ../fennel f fennel ../fennel
f fenugreek ../fenugreek f fenugreek ../fenugreek
f fiddlehead ../fiddlehead f fiddlehead ../fiddlehead
$ hg debugwalk -v -I 'rootfilesin:.' $ hg debugwalk -v -I 'rootfilesin:.'
* matcher: * matcher:
<includematcher includes='(?:[^/]+$)'> <includematcher includes="rootfilesin: ['.']">
f fennel ../fennel f fennel ../fennel
f fenugreek ../fenugreek f fenugreek ../fenugreek
f fiddlehead ../fiddlehead f fiddlehead ../fiddlehead
$ hg debugwalk -v -X 'rootfilesin:' $ hg debugwalk -v -X 'rootfilesin:'
* matcher: * matcher:
<differencematcher <differencematcher
m1=<alwaysmatcher>, m1=<alwaysmatcher>,
m2=<includematcher includes='(?:[^/]+$)'>> m2=<includematcher includes="rootfilesin: ['.']">>
f beans/black ../beans/black f beans/black ../beans/black
f beans/borlotti ../beans/borlotti f beans/borlotti ../beans/borlotti
f beans/kidney ../beans/kidney f beans/kidney ../beans/kidney
f beans/navy ../beans/navy f beans/navy ../beans/navy
f beans/pinto ../beans/pinto f beans/pinto ../beans/pinto
f beans/turtle ../beans/turtle f beans/turtle ../beans/turtle
f mammals/Procyonidae/cacomistle Procyonidae/cacomistle f mammals/Procyonidae/cacomistle Procyonidae/cacomistle
f mammals/Procyonidae/coatimundi Procyonidae/coatimundi f mammals/Procyonidae/coatimundi Procyonidae/coatimundi
f mammals/Procyonidae/raccoon Procyonidae/raccoon f mammals/Procyonidae/raccoon Procyonidae/raccoon
f mammals/skunk skunk f mammals/skunk skunk
$ hg debugwalk -v 'rootfilesin:fennel' $ hg debugwalk -v 'rootfilesin:fennel'
* matcher: * matcher:
<patternmatcher patterns='(?:fennel/[^/]+$)'> <patternmatcher patterns="rootfilesin: ['fennel']">
$ hg debugwalk -v -I 'rootfilesin:fennel' $ hg debugwalk -v -I 'rootfilesin:fennel'
* matcher: * matcher:
<includematcher includes='(?:fennel/[^/]+$)'> <includematcher includes="rootfilesin: ['fennel']">
$ hg debugwalk -v 'rootfilesin:skunk' $ hg debugwalk -v 'rootfilesin:skunk'
* matcher: * matcher:
<patternmatcher patterns='(?:skunk/[^/]+$)'> <patternmatcher patterns="rootfilesin: ['skunk']">
$ hg debugwalk -v -I 'rootfilesin:skunk' $ hg debugwalk -v -I 'rootfilesin:skunk'
* matcher: * matcher:
<includematcher includes='(?:skunk/[^/]+$)'> <includematcher includes="rootfilesin: ['skunk']">
$ hg debugwalk -v 'rootfilesin:beans' $ hg debugwalk -v 'rootfilesin:beans'
* matcher: * matcher:
<patternmatcher patterns='(?:beans/[^/]+$)'> <patternmatcher patterns="rootfilesin: ['beans']">
f beans/black ../beans/black f beans/black ../beans/black
f beans/borlotti ../beans/borlotti f beans/borlotti ../beans/borlotti
f beans/kidney ../beans/kidney f beans/kidney ../beans/kidney
f beans/navy ../beans/navy f beans/navy ../beans/navy
f beans/pinto ../beans/pinto f beans/pinto ../beans/pinto
f beans/turtle ../beans/turtle f beans/turtle ../beans/turtle
$ hg debugwalk -v -I 'rootfilesin:beans' $ hg debugwalk -v -I 'rootfilesin:beans'
* matcher: * matcher:
<includematcher includes='(?:beans/[^/]+$)'> <includematcher includes="rootfilesin: ['beans']">
f beans/black ../beans/black f beans/black ../beans/black
f beans/borlotti ../beans/borlotti f beans/borlotti ../beans/borlotti
f beans/kidney ../beans/kidney f beans/kidney ../beans/kidney
f beans/navy ../beans/navy f beans/navy ../beans/navy
f beans/pinto ../beans/pinto f beans/pinto ../beans/pinto
f beans/turtle ../beans/turtle f beans/turtle ../beans/turtle
$ hg debugwalk -v 'rootfilesin:mammals' $ hg debugwalk -v 'rootfilesin:mammals'
* matcher: * matcher:
<patternmatcher patterns='(?:mammals/[^/]+$)'> <patternmatcher patterns="rootfilesin: ['mammals']">
f mammals/skunk skunk f mammals/skunk skunk
$ hg debugwalk -v -I 'rootfilesin:mammals' $ hg debugwalk -v -I 'rootfilesin:mammals'
* matcher: * matcher:
<includematcher includes='(?:mammals/[^/]+$)'> <includematcher includes="rootfilesin: ['mammals']">
f mammals/skunk skunk f mammals/skunk skunk
$ hg debugwalk -v 'rootfilesin:mammals/' $ hg debugwalk -v 'rootfilesin:mammals/'
* matcher: * matcher:
<patternmatcher patterns='(?:mammals/[^/]+$)'> <patternmatcher patterns="rootfilesin: ['mammals']">
f mammals/skunk skunk f mammals/skunk skunk
$ hg debugwalk -v -I 'rootfilesin:mammals/' $ hg debugwalk -v -I 'rootfilesin:mammals/'
* matcher: * matcher:
<includematcher includes='(?:mammals/[^/]+$)'> <includematcher includes="rootfilesin: ['mammals']">
f mammals/skunk skunk f mammals/skunk skunk
$ hg debugwalk -v -X 'rootfilesin:mammals' $ hg debugwalk -v -X 'rootfilesin:mammals'
* matcher: * matcher:
<differencematcher <differencematcher
m1=<alwaysmatcher>, m1=<alwaysmatcher>,
m2=<includematcher includes='(?:mammals/[^/]+$)'>> m2=<includematcher includes="rootfilesin: ['mammals']">>
f beans/black ../beans/black f beans/black ../beans/black
f beans/borlotti ../beans/borlotti f beans/borlotti ../beans/borlotti
f beans/kidney ../beans/kidney f beans/kidney ../beans/kidney
f beans/navy ../beans/navy f beans/navy ../beans/navy
f beans/pinto ../beans/pinto f beans/pinto ../beans/pinto
f beans/turtle ../beans/turtle f beans/turtle ../beans/turtle
f fennel ../fennel f fennel ../fennel
f fenugreek ../fenugreek f fenugreek ../fenugreek