( )⚙ D6506 revlog: speed up isancestor

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D6506

revlog: speed up isancestor
ClosedPublic

Authored by valentin.gatienbaron on Jun 10 2019, 2:32 PM.

Details

Reviewers
indygreg
Group Reviewers
hg-reviewers
Commits
rHG055c3e2c44f0: revlog: speed up isancestor
Summary

Currently, it is implemented on top of commonancestorsheads.
Implement it on top of reachableroots instead, as reachableroots could
stop walking the graph much sooner than commonancestorsheads.

Measuring repo.changelog.isancestorrev on two revisions in a private repository:
before: ! wall 0.005175 comb 0.010000 user 0.010000 sys 0.000000 (best of 550)
after : ! wall 0.000072 comb 0.000000 user 0.000000 sys 0.000000 (best of 36199)

When hg does this kind of operations 1500 times in pull ->
bookmarks.comparebookmarks -> bookmarks.validdest, that's 11s that
drop from the --profile output.

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

durin42 added a subscriber: durin42.Jun 12 2019, 11:57 AM

Impressive work. Thanks!

valentin.gatienbaron added a commit: rHG055c3e2c44f0: revlog: speed up isancestor.Jun 12 2019, 12:44 PM
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHG055c3e2c44f0: revlog: speed up isancestor (authored by valentin.gatienbaron). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mmercurial/changelog.py (3 lines)
Mmercurial/dagop.py (16 lines)
Mmercurial/revlog.py (15 lines)

Diff 15456

mercurial/changelog.py

return filterediter() return filterediter()
def revs(self, start=0, stop=None): def revs(self, start=0, stop=None):
"""filtered version of revlog.revs""" """filtered version of revlog.revs"""
for i in super(changelog, self).revs(start, stop): for i in super(changelog, self).revs(start, stop):
if i not in self.filteredrevs: if i not in self.filteredrevs:
yield i yield i
def reachableroots(self, minroot, heads, roots, includepath=False):
return self.index.reachableroots2(minroot, heads, roots, includepath)
def _checknofilteredinrevs(self, revs): def _checknofilteredinrevs(self, revs):
"""raise the appropriate error if 'revs' contains a filtered revision """raise the appropriate error if 'revs' contains a filtered revision
This returns a version of 'revs' to be used thereafter by the caller. This returns a version of 'revs' to be used thereafter by the caller.
In particular, if revs is an iterator, it is converted into a set. In particular, if revs is an iterator, it is converted into a set.
""" """
safehasattr = util.safehasattr safehasattr = util.safehasattr
if safehasattr(revs, '__next__'): if safehasattr(revs, '__next__'):

mercurial/dagop.py

seen = set(revs) seen = set(revs)
for rev in revsfn(start=first + 1): for rev in revsfn(start=first + 1):
for prev in parentrevsfn(rev): for prev in parentrevsfn(rev):
if prev != nullrev and prev in seen: if prev != nullrev and prev in seen:
seen.add(rev) seen.add(rev)
yield rev yield rev
break break
def _reachablerootspure(repo, minroot, roots, heads, includepath): def _reachablerootspure(pfunc, minroot, roots, heads, includepath):
"""See reachableroots""" """See revlog.reachableroots"""
if not roots: if not roots:
return [] return []
parentrevs = repo.changelog.parentrevs
roots = set(roots) roots = set(roots)
visit = list(heads) visit = list(heads)
reachable = set() reachable = set()
seen = {} seen = {}
# prefetch all the things! (because python is slow) # prefetch all the things! (because python is slow)
reached = reachable.add reached = reachable.add
dovisit = visit.append dovisit = visit.append
nextvisit = visit.pop nextvisit = visit.pop
# open-code the post-order traversal due to the tiny size of # open-code the post-order traversal due to the tiny size of
# sys.getrecursionlimit() # sys.getrecursionlimit()
while visit: while visit:
rev = nextvisit() rev = nextvisit()
if rev in roots: if rev in roots:
reached(rev) reached(rev)
if not includepath: if not includepath:
continue continue
parents = parentrevs(rev) parents = pfunc(rev)
seen[rev] = parents seen[rev] = parents
for parent in parents: for parent in parents:
if parent >= minroot and parent not in seen: if parent >= minroot and parent not in seen:
dovisit(parent) dovisit(parent)
if not reachable: if not reachable:
return baseset() return baseset()
if not includepath: if not includepath:
return reachable return reachable
for rev in sorted(seen): for rev in sorted(seen):
for parent in seen[rev]: for parent in seen[rev]:
if parent in reachable: if parent in reachable:
reached(rev) reached(rev)
return reachable return reachable
def reachableroots(repo, roots, heads, includepath=False): def reachableroots(repo, roots, heads, includepath=False):
"""return (heads(::<roots> and <roots>::<heads>)) """See revlog.reachableroots"""
If includepath is True, return (<roots>::<heads>)."""
if not roots: if not roots:
return baseset() return baseset()
minroot = roots.min() minroot = roots.min()
roots = list(roots) roots = list(roots)
heads = list(heads) heads = list(heads)
try:
revs = repo.changelog.reachableroots(minroot, heads, roots, includepath) revs = repo.changelog.reachableroots(minroot, heads, roots, includepath)
except AttributeError:
revs = _reachablerootspure(repo, minroot, roots, heads, includepath)
revs = baseset(revs) revs = baseset(revs)
revs.sort() revs.sort()
return revs return revs
def _changesrange(fctx1, fctx2, linerange2, diffopts): def _changesrange(fctx1, fctx2, linerange2, diffopts):
"""Return `(diffinrange, linerange1)` where `diffinrange` is True """Return `(diffinrange, linerange1)` where `diffinrange` is True
if diff from fctx2 to fctx1 has changes in linerange2 and if diff from fctx2 to fctx1 has changes in linerange2 and
`linerange1` is the new line range for fctx1. `linerange1` is the new line range for fctx1.

mercurial/revlog.py

return self.isancestorrev(a, b) return self.isancestorrev(a, b)
def isancestorrev(self, a, b): def isancestorrev(self, a, b):
"""return True if revision a is an ancestor of revision b """return True if revision a is an ancestor of revision b
A revision is considered an ancestor of itself. A revision is considered an ancestor of itself.
The implementation of this is trivial but the use of The implementation of this is trivial but the use of
commonancestorsheads is not.""" reachableroots is not."""
if a == nullrev: if a == nullrev:
return True return True
elif a == b: elif a == b:
return True return True
elif a > b: elif a > b:
return False return False
return a in self._commonancestorsheads(a, b) return bool(self.reachableroots(a, [b], [a], includepath=False))
def reachableroots(self, minroot, heads, roots, includepath=False):
"""return (heads(::<roots> and <roots>::<heads>))
If includepath is True, return (<roots>::<heads>)."""
try:
return self.index.reachableroots2(minroot, heads, roots,
includepath)
except AttributeError:
return dagop._reachablerootspure(self.parentrevs,
minroot, roots, heads, includepath)
def ancestor(self, a, b): def ancestor(self, a, b):
"""calculate the "best" common ancestor of nodes a and b""" """calculate the "best" common ancestor of nodes a and b"""
a, b = self.rev(a), self.rev(b) a, b = self.rev(a), self.rev(b)
try: try:
ancs = self.index.ancestors(a, b) ancs = self.index.ancestors(a, b)
except (AttributeError, OverflowError): except (AttributeError, OverflowError):