This is an archive of the discontinued Mercurial Phabricator instance.

revset: optimize "draft() & ::x" pattern
ClosedPublic

Authored by quark on Aug 18 2017, 12:50 AM.

Details

Summary

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)

Diff Detail

Repository
rHG Mercurial
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

quark created this revision.Aug 18 2017, 12:50 AM
quark edited the summary of this revision. (Show Details)Aug 18 2017, 12:51 AM
quark updated this revision to Diff 1057.Aug 18 2017, 12:56 AM
quark edited the summary of this revision. (Show Details)Aug 18 2017, 1:14 AM
quark updated this revision to Diff 1058.Aug 18 2017, 1:25 AM

I'll review in more detail later, but just a quick comment for now

mercurial/revset.py
1554

Isn't "getphase(repo,rev) >= keepphase" more natural? You'd then replace phasenamemap by something like

minphase = {
    '_notpublic': draft,
    'draft': draft,
    'secret': secret,
}
quark updated this revision to Diff 1059.Aug 18 2017, 1:44 AM
quark updated this revision to Diff 1071.Aug 18 2017, 10:50 AM
quark marked an inline comment as done.Aug 18 2017, 10:51 AM
quark added inline comments.
mercurial/revset.py
1554

Good point. Thanks!

quark marked an inline comment as done.Aug 18 2017, 11:04 AM

By the way, take your time. This is not an urgent change.

tests/test-revset.t
4534

Need to change to just P5.

quark added inline comments.Aug 18 2017, 11:07 AM
mercurial/dagop.py
93

Could use revs.filter instead.

quark updated this revision to Diff 1074.Aug 18 2017, 1:18 PM
quark marked 2 inline comments as done.Aug 18 2017, 1:19 PM
quark updated this revision to Diff 1075.Aug 18 2017, 1:27 PM
yuja added a subscriber: yuja.Aug 19 2017, 12:30 AM
yuja added inline comments.
mercurial/revsetlang.py
492

FWIW, I wrote placeholder matcher once, which could be used as follows.

m = _matchtree('_() & ::_', ('and', ta, tb))
if m and getsymbol(m[1]) in _fastphases:
    ...

https://bitbucket.org/yuja/hg-work/commits/6c0ae642d86a188af8e940e430522e915f478b25

This is outdated and needs modification, but do you like it?

quark added inline comments.Aug 19 2017, 1:33 AM
mercurial/revsetlang.py
492

Yes! That's much shorter (I had to copy the trees from debugshell) and more robust (no fragile len(x) >= 3 handling).

For performance concerns, I think it's fine. Practically, revset parsing is hardly a bottleneck. With chg, _treecache could be pre-populated.

yuja added inline comments.Aug 19 2017, 3:14 AM
mercurial/revsetlang.py
492

I'll rebase my patches then. I'm sure that isn't trivial because I introduced the order flag.

quark added inline comments.Aug 19 2017, 1:44 PM
mercurial/revsetlang.py
492

Maybe order could be removed from AST since they can be inferred during tree traversal? I have a draft D451 that verifies the idea.

quark planned changes to this revision.Aug 24 2017, 12:06 AM

Let's wait for my revset order and Yuya's matchtree patches first.

quark updated this revision to Diff 1570.Sep 1 2017, 9:24 PM
quark updated this revision to Diff 1571.Sep 1 2017, 9:28 PM
yuja accepted this revision.Sep 3 2017, 10:08 AM

Queued, thanks. I've removed _() because _phaseandancestors() is an internal function.

mercurial/revset.py
1558

revs & phasecache.getrevset(repo, [phasename]) might be
slightly faster, but I don't think it would make any noticeable difference.

mercurial/revsetlang.py
475

Perhaps ::x & phasename() can be optimized, too.

This revision is now accepted and ready to land.Sep 3 2017, 10:08 AM
This revision was automatically updated to reflect the committed changes.