Mercurial > public > mercurial-scm > hg-stable
diff mercurial/revset.py @ 20499:2efd608473fb
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)
| author | Siddharth Agarwal <sid0@fb.com> |
|---|---|
| date | Thu, 13 Feb 2014 14:04:47 -0800 |
| parents | fb2df4506c87 |
| children | 659b8d8ddf19 |
line wrap: on
line diff
--- 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)