This is an archive of the discontinued Mercurial Phabricator instance.

Differential D561

revset: drop optimization about reordering "or" set elements
ClosedPublic

Authored by quark on Aug 29 2017, 10:02 AM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHG72b5f4d53c58: revset: drop optimization about reordering "or" set elements
Summary

The reordering optimization is more important for "and" than "or", given the
implementation details about "addset" and "filteredset" - reordering "or"
may help "contains" test but not iteration, reordering "and" could help
both. We are going to simplify the tree to remove ordering information.
Removing "or" reordering optimization would make things simpler.

This effectively reverts c63cb2d10d6d. It tracks back to the "orset"
function added by the initial commit of revset (c9ce8ecd6).

In the future, we might consider optimization at runtime (ex. do reordering
and rewrites inside "orset").

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

quark created this revision.Aug 29 2017, 10:02 AM
quark edited the summary of this revision. (Show Details)Aug 29 2017, 10:13 AM
Closed by commit rHG72b5f4d53c58: revset: drop optimization about reordering "or" set elements (authored by quark). · Explain WhyAug 30 2017, 9:53 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mmercurial/revsetlang.py (3 lines)
Mtests/test-revset.t (71 lines)

Diff 1432

mercurial/revsetlang.py

ss.append((w, t)) ss.append((w, t))
continue continue
flushss() flushss()
ws.append(w) ws.append(w)
ts.append(t) ts.append(t)
flushss() flushss()
if len(ts) == 1: if len(ts) == 1:
return ws[0], ts[0] # 'or' operation is fully optimized out return ws[0], ts[0] # 'or' operation is fully optimized out
if order != defineorder:
# reorder by weight only when f(a + b) == f(b + a)
ts = [wt[1] for wt in sorted(zip(ws, ts), key=lambda wt: wt[0])]
return max(ws), (op, ('list',) + tuple(ts), order) return max(ws), (op, ('list',) + tuple(ts), order)
elif op == 'not': elif op == 'not':
# Optimize not public() to _notpublic() because we have a fast version # Optimize not public() to _notpublic() because we have a fast version
if x[1][:3] == ('func', ('symbol', 'public'), None): if x[1][:3] == ('func', ('symbol', 'public'), None):
order = x[1][3] order = x[1][3]
newsym = ('func', ('symbol', '_notpublic'), None, order) newsym = ('func', ('symbol', '_notpublic'), None, order)
o = _optimize(newsym, not small) o = _optimize(newsym, not small)
return o[0], o[1] return o[0], o[1]

tests/test-revset.t

* optimized: * optimized:
(and (and
(range (range
('symbol', '2') ('symbol', '2')
('symbol', '0') ('symbol', '0')
define) define)
(or (or
(list (list
('symbol', '2')
(range (range
('symbol', '0') ('symbol', '0')
('symbol', '1') ('symbol', '1')
follow)) follow)
('symbol', '2'))
follow) follow)
define) define)
* set: * set:
<filteredset <filteredset
<spanset- 0:3>, <spanset- 0:3>,
<addset <addset
<baseset [2]>, <spanset+ 0:2>,
<spanset+ 0:2>>> <baseset [2]>>>
2 2
1 1
0 0
'_intlist(a b)' should behave like 'a + b': '_intlist(a b)' should behave like 'a + b':
$ trylist --optimize '2:0 & %ld' 0 1 2 $ trylist --optimize '2:0 & %ld' 0 1 2
(and (and
* set: * set:
<filteredset <filteredset
<baseset- [0, 1, 2]>, <baseset- [0, 1, 2]>,
<contains 'glob:*'>> <contains 'glob:*'>>
2 2
1 1
0 0
'A + B' can be rewritten to 'B + A' by weight only when the order doesn't
matter (e.g. 'X & (A + B)' can be 'X & (B + A)', but '(A + B) & X' can't):
$ try -p optimized '0:2 & (reverse(contains("a")) + 2)'
* optimized:
(and
(range
('symbol', '0')
('symbol', '2')
define)
(or
(list
('symbol', '2')
(func
('symbol', 'reverse')
(func
('symbol', 'contains')
('string', 'a')
define)
follow))
follow)
define)
* set:
<filteredset
<spanset+ 0:3>,
<addset
<baseset [2]>,
<filteredset
<fullreposet+ 0:10>,
<contains 'a'>>>>
0
1
2
$ try -p optimized '(reverse(contains("a")) + 2) & 0:2'
* optimized:
(and
(range
('symbol', '0')
('symbol', '2')
follow)
(or
(list
(func
('symbol', 'reverse')
(func
('symbol', 'contains')
('string', 'a')
define)
define)
('symbol', '2'))
define)
define)
* set:
<addset
<filteredset
<spanset- 0:3>,
<contains 'a'>>,
<baseset [2]>>
1
0
2
test sort revset test sort revset
-------------------------------------------- --------------------------------------------
test when adding two unordered revsets test when adding two unordered revsets
$ log 'sort(keyword(issue) or modifies(b))' $ log 'sort(keyword(issue) or modifies(b))'
4 4
6 6