( )⚙ D10294 match: convert O(n) to O(log n) in exactmatcher.visitchildrenset

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D10294

match: convert O(n) to O(log n) in exactmatcher.visitchildrenset
ClosedPublic

Authored by spectral on Apr 1 2021, 3:21 PM.

Details

Reviewers
Alphare
pulkit
Group Reviewers
hg-reviewers
Commits
rHG8bca353b1ebc: match: convert O(n) to O(log n) in exactmatcher.visitchildrenset
rHG67414b0aadbb: match: convert O(n) to O(log n) in exactmatcher.visitchildrenset
Summary

When using narrow, during rebase this is called (at least) once per directory in
the set of files in the commit being rebased. Every time it's called, we did the
set arithmetic (now extracted and cached), which was probably pretty cheap but
not necessary to repeat each time, looped over every item in the matcher and
kept things that started with the directory we were querying.

With very large narrowspecs, and a commit that touched a file in a large number
of directories, this was slow. In a pathological repo, the rebase of a single
commit (that touched over 17k files, I believe in approximately as many
directories) with a narrowspec that had >32k entries took 8,246s of profiled
time, with 5,007s of that spent in visitchildrenset (transitively). With this
change, the time spent in visitchildrenset is less than 34s (which is where my
profile cut off). Most of the remaining time was network access due to our
custom remotefilelog-based setup not properly prefetching.

Diff Detail

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

Event Timeline

spectral created this revision.Apr 1 2021, 3:21 PM
Alphare accepted this revision.Apr 8 2021, 6:20 AM
Alphare added a subscriber: Alphare.

I'm hoping that (at least) some of that logic could become obsolete with the new dirstate rewrite since we'll have a tree structure. For now this looks reasonable thanks to your generous comments.

pulkit accepted this revision.Apr 8 2021, 12:50 PM
This revision is now accepted and ready to land.Apr 8 2021, 12:50 PM

Revision Contents
Changeset List

PathPackages
Mmercurial/match.py (31 lines)

Diff 26640

mercurial/match.py

# match.py - filename matching # match.py - filename matching
# #
# Copyright 2008, 2009 Matt Mackall <mpm@selenic.com> and others # Copyright 2008, 2009 Matt Mackall <mpm@selenic.com> and others
# #
# This software may be used and distributed according to the terms of the # This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version. # GNU General Public License version 2 or any later version.
from __future__ import absolute_import, print_function from __future__ import absolute_import, print_function
import bisect
import copy import copy
import itertools import itertools
import os import os
import re import re
from .i18n import _ from .i18n import _
from .pycompat import open from .pycompat import open
from . import ( from . import (
@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):
return dir in self._dirs return dir in self._dirs
@propertycache
def _visitchildrenset_candidates(self):
"""A memoized set of candidates for visitchildrenset."""
return self._fileset | self._dirs - {b''}
@propertycache
def _sorted_visitchildrenset_candidates(self):
"""A memoized sorted list of candidates for visitchildrenset."""
return sorted(self._visitchildrenset_candidates)
def visitchildrenset(self, dir): def visitchildrenset(self, dir):
if not self._fileset or dir not in self._dirs: if not self._fileset or dir not in self._dirs:
return set() return set()
candidates = self._fileset | self._dirs - {b''} if dir == b'':
if dir != b'': candidates = self._visitchildrenset_candidates
else:
candidates = self._sorted_visitchildrenset_candidates
d = dir + b'/' d = dir + b'/'
candidates = {c[len(d) :] for c in candidates if c.startswith(d)} # Use bisect to find the first element potentially starting with d
# (i.e. >= d). This should always find at least one element (we'll
# assert later if this is not the case).
first = bisect.bisect_left(candidates, d)
# We need a representation of the first element that is > d that
# does not start with d, so since we added a `/` on the end of dir,
# we'll add whatever comes after slash (we could probably assume
# that `0` is after `/`, but let's not) to the end of dir instead.
dnext = dir + encoding.strtolocal(chr(ord(b'/') + 1))
# Use bisect to find the first element >= d_next
last = bisect.bisect_left(candidates, dnext, lo=first)
dlen = len(d)
candidates = {c[dlen :] for c in candidates[first:last]}
# 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
# '/' in it, indicating a it's for a subdir-of-a-subdir; the # '/' in it, indicating a it's for a subdir-of-a-subdir; the
# immediate subdir will be in there without a slash. # immediate subdir will be in there without a slash.
ret = {c for c in candidates if b'/' not in c} ret = {c for c in candidates if b'/' not in c}
# We really do not expect ret to be empty, since that would imply that # We really do not expect ret to be empty, since that would imply that
# there's something in _dirs that didn't have a file in _fileset. # there's something in _dirs that didn't have a file in _fileset.