revset: optimize missing ancestor expressions
A missing ancestor expression is any expression of the form (::x - ::y) or
equivalent. Such expressions are remarkably common, and so far have involved
multiple walks down the DAG, followed by a set difference operation.
With this patch, such expressions will be transformed into uses of the fast
algorithm at ancestor.missingancestor.
For a repository with over 600,000 revisions, perfrevset for '::tip - ::-10000'
returns:
Before: ! wall 3.999575 comb 4.000000 user 3.910000 sys 0.090000 (best of 3)
After: ! wall 0.132423 comb 0.130000 user 0.130000 sys 0.000000 (best of 75)
--- a/mercurial/revset.py Thu Feb 13 13:54:45 2014 -0800
+++ b/mercurial/revset.py Thu Feb 13 14:04:47 2014 -0800
@@ -1749,7 +1749,24 @@
elif op == 'and':
wa, ta = optimize(x[1], True)
wb, tb = optimize(x[2], True)
+
+ # (::x and not ::y)/(not ::y and ::x) have a fast path
+ def ismissingancestors(revs, bases):
+ return (
+ revs[0] == 'func'
+ and getstring(revs[1], _('not a symbol')) == 'ancestors'
+ and bases[0] == 'not'
+ and bases[1][0] == 'func'
+ and getstring(bases[1][1], _('not a symbol')) == 'ancestors')
+
w = min(wa, wb)
+ if ismissingancestors(ta, tb):
+ return w, ('func', ('symbol', '_missingancestors'),
+ ('list', ta[2], tb[1][2]))
+ if ismissingancestors(tb, ta):
+ return w, ('func', ('symbol', '_missingancestors'),
+ ('list', tb[2], ta[1][2]))
+
if wa > wb:
return w, (op, tb, ta)
return w, (op, ta, tb)
--- a/tests/test-revset.t Thu Feb 13 13:54:45 2014 -0800
+++ b/tests/test-revset.t Thu Feb 13 14:04:47 2014 -0800
@@ -444,6 +444,70 @@
$ log 'tag(tip)'
9
+check that conversion to _missingancestors works
+ $ try --optimize '::3 - ::1'
+ (minus
+ (dagrangepre
+ ('symbol', '3'))
+ (dagrangepre
+ ('symbol', '1')))
+ * optimized:
+ (func
+ ('symbol', '_missingancestors')
+ (list
+ ('symbol', '3')
+ ('symbol', '1')))
+ 3
+ $ try --optimize 'ancestors(1) - ancestors(3)'
+ (minus
+ (func
+ ('symbol', 'ancestors')
+ ('symbol', '1'))
+ (func
+ ('symbol', 'ancestors')
+ ('symbol', '3')))
+ * optimized:
+ (func
+ ('symbol', '_missingancestors')
+ (list
+ ('symbol', '1')
+ ('symbol', '3')))
+ $ try --optimize 'not ::2 and ::6'
+ (and
+ (not
+ (dagrangepre
+ ('symbol', '2')))
+ (dagrangepre
+ ('symbol', '6')))
+ * optimized:
+ (func
+ ('symbol', '_missingancestors')
+ (list
+ ('symbol', '6')
+ ('symbol', '2')))
+ 3
+ 4
+ 5
+ 6
+ $ try --optimize 'ancestors(6) and not ancestors(4)'
+ (and
+ (func
+ ('symbol', 'ancestors')
+ ('symbol', '6'))
+ (not
+ (func
+ ('symbol', 'ancestors')
+ ('symbol', '4'))))
+ * optimized:
+ (func
+ ('symbol', '_missingancestors')
+ (list
+ ('symbol', '6')
+ ('symbol', '4')))
+ 3
+ 5
+ 6
+
we can use patterns when searching for tags
$ log 'tag("1..*")'