Mercurial > public > mercurial-scm > hg
comparison 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 |
comparison
equal
deleted
inserted
replaced
| 20498:fb2df4506c87 | 20499:2efd608473fb |
|---|---|
| 1747 elif op in 'string symbol negate': | 1747 elif op in 'string symbol negate': |
| 1748 return smallbonus, x # single revisions are small | 1748 return smallbonus, x # single revisions are small |
| 1749 elif op == 'and': | 1749 elif op == 'and': |
| 1750 wa, ta = optimize(x[1], True) | 1750 wa, ta = optimize(x[1], True) |
| 1751 wb, tb = optimize(x[2], True) | 1751 wb, tb = optimize(x[2], True) |
| 1752 | |
| 1753 # (::x and not ::y)/(not ::y and ::x) have a fast path | |
| 1754 def ismissingancestors(revs, bases): | |
| 1755 return ( | |
| 1756 revs[0] == 'func' | |
| 1757 and getstring(revs[1], _('not a symbol')) == 'ancestors' | |
| 1758 and bases[0] == 'not' | |
| 1759 and bases[1][0] == 'func' | |
| 1760 and getstring(bases[1][1], _('not a symbol')) == 'ancestors') | |
| 1761 | |
| 1752 w = min(wa, wb) | 1762 w = min(wa, wb) |
| 1763 if ismissingancestors(ta, tb): | |
| 1764 return w, ('func', ('symbol', '_missingancestors'), | |
| 1765 ('list', ta[2], tb[1][2])) | |
| 1766 if ismissingancestors(tb, ta): | |
| 1767 return w, ('func', ('symbol', '_missingancestors'), | |
| 1768 ('list', tb[2], ta[1][2])) | |
| 1769 | |
| 1753 if wa > wb: | 1770 if wa > wb: |
| 1754 return w, (op, tb, ta) | 1771 return w, (op, tb, ta) |
| 1755 return w, (op, ta, tb) | 1772 return w, (op, ta, tb) |
| 1756 elif op == 'or': | 1773 elif op == 'or': |
| 1757 wa, ta = optimize(x[1], False) | 1774 wa, ta = optimize(x[1], False) |