This is an archive of the discontinued Mercurial Phabricator instance.

Differential D656

revset: remove "small" argument from "_optimize"
ClosedPublic

Authored by quark on Sep 7 2017, 12:16 PM.

Details

Reviewers
yuja
Group Reviewers
hg-reviewers
Commits
rHG53fb09c73ba8: revset: remove "small" argument from "_optimize"
Summary

_optimize calculates weights of subtrees. "small" affects some weight
calculation (either 1 or 0.5). The weights are now only useful in and
optimization where we might swap two arguments and use andsmally.

In the real world, it seems unlikely that revsets with weight of 0.5 or 1
matters the and order optimization. I think the important thing is to get
weights of expensive revsets right (ex. contains).

This patch removes the small argument to simplify the interface.

As for choosing between 0.5 vs 1, things returning a single revision
(ancestor, string) has a weight of 0.5. Things returning multiple
revisions returns 1. This could be sometimes useful in the andsmally
optimization, ex.

(((:)-2) & expensive()) & ((1-2) & expensive())
  ^^^                       ^
 ^^^^^^^                   ^^^^^
^^^^^^^^^^^^^^^^^^^^^^^   ^^^^^^^^^^^^^^^^^^^^^
  weight=1                 weight=0.5

would have an andsmally optimization so 1-2 gets executed first, which
seems to be desirable.

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.Sep 7 2017, 12:16 PM
quark added a child revision: D657: revset: move weight information to predicate.Sep 7 2017, 12:16 PM
quark edited the summary of this revision. (Show Details)
yuja added a subscriber: yuja.Sep 8 2017, 9:49 AM
yuja added inline comments.
mercurial/revsetlang.py
421

Any reason to choose 1 here and 0.5 for the others?

quark added inline comments.Sep 8 2017, 1:06 PM
mercurial/revsetlang.py
421

I think there are 2 factors deciding weight:

  1. Time complexity of the revset implementation
  2. The returned revset size (maybe more important for and optimization)

Here, : returns a larger revset so its weight is larger.

Maybe we can change all weight numbers to get rid of float numbers. ex. multiple by 10 for everything.

quark edited the summary of this revision. (Show Details)Sep 18 2017, 7:46 PM
quark updated this revision to Diff 1881.
yuja accepted this revision.Sep 19 2017, 10:51 AM

Queued, thanks.

(copied from the email thread)

On Fri, 8 Sep 2017 17:06:12 +0000, quark (Jun Wu) wrote:

yuja wrote in revsetlang.py:421
Any reason to choose 1 here and 0.5 for the others?

I think there are 2 factors deciding weight:

  1. Time complexity of the revset implementation
  2. The returned revset size (maybe more important for and optimization)

Here, : returns a larger revset so its weight is larger.

I don't think keeping (2) makes much sense because this patch effectively
removes the concept about the computed size. And it's far from being accurate
anyway. In theory, the computed size would be an input to the weight function
of the subsequent query, e.g.

W_contains(subset) = K_contains * estimated_size(subset)

That said, I don't have strong preference about this. So can you update the
commit message to include why 0.5 or 1.

This revision is now accepted and ready to land.Sep 19 2017, 10:51 AM
quark added a comment.EditedSep 19 2017, 1:35 PM
In D656#12304, @yuja wrote:

(copied from the email thread)

I saw your email (and the next one). The commit message was updated accordingly. I think Phabricator in-bound email now works as long as the "From" address is known (i.e. listed at https://phab.mercurial-scm.org/settings/user/yuja/page/email/).

lothiraldan added a subscriber: lothiraldan.Sep 20 2017, 2:37 AM
In D656#12341, @quark wrote:
In D656#12304, @yuja wrote:

(copied from the email thread)

I saw your email (and the next one). The commit message was updated accordingly. I think Phabricator in-bound email now works as long as the "From" address is known (i.e. listed at https://phab.mercurial-scm.org/settings/user/yuja/page/email/).

If Phabricator in-bound email are working, could we update https://bz.mercurial-scm.org/show_bug.cgi?id=5666 accordingly?

Closed by commit rHG53fb09c73ba8: revset: remove "small" argument from "_optimize" (authored by quark). · Explain WhySep 20 2017, 9:02 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mmercurial/revsetlang.py (42 lines)

Diff 1918

mercurial/revsetlang.py

"""Transform raw parsed tree to evaluatable tree which can be fed to """Transform raw parsed tree to evaluatable tree which can be fed to
optimize() or getset() optimize() or getset()
All pseudo operations should be mapped to real operations or functions All pseudo operations should be mapped to real operations or functions
defined in methods or symbols table respectively. defined in methods or symbols table respectively.
""" """
return _analyze(x) return _analyze(x)
def _optimize(x, small): def _optimize(x):
if x is None: if x is None:
return 0, x return 0, x
smallbonus = 1
if small:
smallbonus = .5
op = x[0] op = x[0]
if op in ('string', 'symbol'): if op in ('string', 'symbol'):
return smallbonus, x # single revisions are small return 0.5, x # single revisions are small
elif op == 'and': elif op == 'and':
wa, ta = _optimize(x[1], True) wa, ta = _optimize(x[1])
wb, tb = _optimize(x[2], True) wb, tb = _optimize(x[2])
w = min(wa, wb) w = min(wa, wb)
# (draft/secret/_notpublic() & ::x) have a fast path # (draft/secret/_notpublic() & ::x) have a fast path
m = _match('_() & ancestors(_)', ('and', ta, tb)) m = _match('_() & ancestors(_)', ('and', ta, tb))
if m and getsymbol(m[1]) in {'draft', 'secret', '_notpublic'}: if m and getsymbol(m[1]) in {'draft', 'secret', '_notpublic'}:
return w, _build('_phaseandancestors(_, _)', m[1], m[2]) return w, _build('_phaseandancestors(_, _)', m[1], m[2])
# (::x and not ::y)/(not ::y and ::x) have a fast path # (::x and not ::y)/(not ::y and ::x) have a fast path
def flushss(): def flushss():
if not ss: if not ss:
return return
if len(ss) == 1: if len(ss) == 1:
w, t = ss[0] w, t = ss[0]
else: else:
s = '\0'.join(t[1] for w, t in ss) s = '\0'.join(t[1] for w, t in ss)
y = _build('_list(_)', ('string', s)) y = _build('_list(_)', ('string', s))
w, t = _optimize(y, False) w, t = _optimize(y)
ws.append(w) ws.append(w)
ts.append(t) ts.append(t)
del ss[:] del ss[:]
for y in getlist(x[1]): for y in getlist(x[1]):
w, t = _optimize(y, False) w, t = _optimize(y)
if t is not None and (t[0] == 'string' or t[0] == 'symbol'): if t is not None and (t[0] == 'string' or t[0] == 'symbol'):
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
return max(ws), (op, ('list',) + tuple(ts)) return max(ws), (op, ('list',) + tuple(ts))
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 _match('public()', x[1]): if _match('public()', x[1]):
o = _optimize(_build('_notpublic()'), not small) o = _optimize(_build('_notpublic()'))
return o[0], o[1] return o[0], o[1]
else: else:
o = _optimize(x[1], not small) o = _optimize(x[1])
return o[0], (op, o[1]) return o[0], (op, o[1])
elif op == 'rangeall': elif op == 'rangeall':
return smallbonus, x return 1, x
yujaUnsubmitted
Not Done

Any reason to choose 1 here and 0.5 for the others?

yuja: Any reason to choose 1 here and 0.5 for the others?
quarkAuthorUnsubmitted
Not Done

I think there are 2 factors deciding weight:

  1. Time complexity of the revset implementation
  2. The returned revset size (maybe more important for and optimization)

Here, : returns a larger revset so its weight is larger.

Maybe we can change all weight numbers to get rid of float numbers. ex. multiple by 10 for everything.

quark: I think there are 2 factors deciding weight: 1. Time complexity of the revset implementation 2.
elif op in ('rangepre', 'rangepost', 'parentpost'): elif op in ('rangepre', 'rangepost', 'parentpost'):
o = _optimize(x[1], small) o = _optimize(x[1])
return o[0], (op, o[1]) return o[0], (op, o[1])
elif op in ('dagrange', 'range'): elif op in ('dagrange', 'range'):
wa, ta = _optimize(x[1], small) wa, ta = _optimize(x[1])
wb, tb = _optimize(x[2], small) wb, tb = _optimize(x[2])
return wa + wb, (op, ta, tb) return wa + wb, (op, ta, tb)
elif op in ('parent', 'ancestor', 'relation', 'subscript'): elif op in ('parent', 'ancestor', 'relation', 'subscript'):
w, t = _optimize(x[1], small) w, t = _optimize(x[1])
return w, (op, t, x[2]) return w, (op, t, x[2])
elif op == 'relsubscript': elif op == 'relsubscript':
w, t = _optimize(x[1], small) w, t = _optimize(x[1])
return w, (op, t, x[2], x[3]) return w, (op, t, x[2], x[3])
elif op == 'list': elif op == 'list':
ws, ts = zip(*(_optimize(y, small) for y in x[1:])) ws, ts = zip(*(_optimize(y) for y in x[1:]))
return sum(ws), (op,) + ts return sum(ws), (op,) + ts
elif op == 'keyvalue': elif op == 'keyvalue':
w, t = _optimize(x[2], small) w, t = _optimize(x[2])
return w, (op, x[1], t) return w, (op, x[1], t)
elif op == 'func': elif op == 'func':
f = getsymbol(x[1]) f = getsymbol(x[1])
wa, ta = _optimize(x[2], small) wa, ta = _optimize(x[2])
if f in ('author', 'branch', 'closed', 'date', 'desc', 'file', 'grep', if f in ('author', 'branch', 'closed', 'date', 'desc', 'file', 'grep',
'keyword', 'outgoing', 'user', 'destination'): 'keyword', 'outgoing', 'user', 'destination'):
w = 10 # slow w = 10 # slow
elif f in ('modifies', 'adds', 'removes'): elif f in ('modifies', 'adds', 'removes'):
w = 30 # slower w = 30 # slower
elif f == "contains": elif f == "contains":
w = 100 # very slow w = 100 # very slow
elif f == "ancestor": elif f == "ancestor":
w = 1 * smallbonus w = 0.5
elif f in ('reverse', 'limit', 'first', 'wdir', '_intlist'): elif f in ('reverse', 'limit', 'first', 'wdir', '_intlist'):
w = 0 w = 0
elif f == "sort": elif f == "sort":
w = 10 # assume most sorts look at changelog w = 10 # assume most sorts look at changelog
else: else:
w = 1 w = 1
return w + wa, (op, x[1], ta) return w + wa, (op, x[1], ta)
raise ValueError('invalid operator %r' % op) raise ValueError('invalid operator %r' % op)
def optimize(tree): def optimize(tree):
"""Optimize evaluatable tree """Optimize evaluatable tree
All pseudo operations should be transformed beforehand. All pseudo operations should be transformed beforehand.
""" """
_weight, newtree = _optimize(tree, small=True) _weight, newtree = _optimize(tree)
return newtree return newtree
# the set of valid characters for the initial letter of symbols in # the set of valid characters for the initial letter of symbols in
# alias declarations and definitions # alias declarations and definitions
_aliassyminitletters = _syminitletters | {'$'} _aliassyminitletters = _syminitletters | {'$'}
def _parsewith(spec, lookup=None, syminitletters=None): def _parsewith(spec, lookup=None, syminitletters=None):
"""Generate a parse tree of given spec with given tokenizing options """Generate a parse tree of given spec with given tokenizing options