Mercurial > public > mercurial-scm > hg
diff mercurial/dagop.py @ 34065:c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
The `draft() & ::x` type query could be common for selecting one or more
draft feature branches being worked on.
Before this patch, `::x` may travel through the changelog DAG for a long
distance until it gets a smaller revision number than `min(draft())`. It
could be very slow on long changelog with distant (in terms of revision
numbers) drafts.
This patch adds a fast path for this situation, and will stop traveling the
changelog DAG once `::x` hits a non-draft revision.
The fast path also works for `secret()` and `not public()`.
To measure the performance difference, I used drawdag to create a repo that
emulates distant drafts:
DRAFT4
|
DRAFT3 # draft
/
PUBLIC9999 # public
|
PUBLIC9998
|
. DRAFT2
. |
. DRAFT1 # draft
| /
PUBLIC0001 # public
And measured the performance using the repo:
(BEFORE)
$ hg perfrevset 'draft() & ::(DRAFT2+DRAFT4)'
! wall 0.017132 comb 0.010000 user 0.010000 sys 0.000000 (best of 156)
$ hg perfrevset 'draft() & ::(all())'
! wall 0.024221 comb 0.030000 user 0.030000 sys 0.000000 (best of 113)
(AFTER)
$ hg perfrevset 'draft() & ::(DRAFT2+DRAFT4)'
! wall 0.000243 comb 0.000000 user 0.000000 sys 0.000000 (best of 9303)
$ hg perfrevset 'draft() & ::(all())'
! wall 0.004319 comb 0.000000 user 0.000000 sys 0.000000 (best of 655)
Differential Revision: https://phab.mercurial-scm.org/D441
| author | Jun Wu <quark@fb.com> |
|---|---|
| date | Mon, 28 Aug 2017 14:49:00 -0700 |
| parents | b2670290eab4 |
| children | 0d27685b4a2f |
line wrap: on
line diff
--- a/mercurial/dagop.py Fri Sep 01 12:13:17 2017 -0700 +++ b/mercurial/dagop.py Mon Aug 28 14:49:00 2017 -0700 @@ -75,27 +75,49 @@ if prev != node.nullrev: heapq.heappush(pendingheap, (heapsign * prev, pdepth)) -def _genrevancestors(repo, revs, followfirst, startdepth, stopdepth): +def _genrevancestors(repo, revs, followfirst, startdepth, stopdepth, cutfunc): if followfirst: cut = 1 else: cut = None cl = repo.changelog - def pfunc(rev): + def plainpfunc(rev): try: return cl.parentrevs(rev)[:cut] except error.WdirUnsupported: return (pctx.rev() for pctx in repo[rev].parents()[:cut]) + if cutfunc is None: + pfunc = plainpfunc + else: + pfunc = lambda rev: [r for r in plainpfunc(rev) if not cutfunc(r)] + revs = revs.filter(lambda rev: not cutfunc(rev)) return _walkrevtree(pfunc, revs, startdepth, stopdepth, reverse=True) -def revancestors(repo, revs, followfirst, startdepth=None, stopdepth=None): +def revancestors(repo, revs, followfirst=False, startdepth=None, + stopdepth=None, cutfunc=None): """Like revlog.ancestors(), but supports additional options, includes the given revs themselves, and returns a smartset Scan ends at the stopdepth (exlusive) if specified. Revisions found earlier than the startdepth are omitted. + + If cutfunc is provided, it will be used to cut the traversal of the DAG. + When cutfunc(X) returns True, the DAG traversal stops - revision X and + X's ancestors in the traversal path will be skipped. This could be an + optimization sometimes. + + Note: if Y is an ancestor of X, cutfunc(X) returning True does not + necessarily mean Y will also be cut. Usually cutfunc(Y) also wants to + return True in this case. For example, + + D # revancestors(repo, D, cutfunc=lambda rev: rev == B) + |\ # will include "A", because the path D -> C -> A was not cut. + B C # If "B" gets cut, "A" might want to be cut too. + |/ + A """ - gen = _genrevancestors(repo, revs, followfirst, startdepth, stopdepth) + gen = _genrevancestors(repo, revs, followfirst, startdepth, stopdepth, + cutfunc) return generatorset(gen, iterasc=False) def _genrevdescendants(repo, revs, followfirst):