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.

Download Raw Diff

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

Herald added a reviewer: hg-reviewers. · View Herald TranscriptSep 7 2017, 12:16 PM

Herald added a subscriber: mercurial-devel. · View Herald Transcript

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: Time complexity of the revset implementation 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.

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:

Time complexity of the revset implementation

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

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/).

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

			Path	Packages
M			mercurial/revsetlang.py (42 lines)

Diff	ID	Description	Created	Lint	Unit
Base		Base
Diff 1	1665		Sep 7 2017, 12:16 PM	★	★
Diff 2	1881		Sep 18 2017, 7:46 PM	★	★
Diff 3	1918	rHG53fb09c73ba84966931240152ede7743c4d0271e	Sep 1 2017, 10:30 PM	★	★

	Status	Author	Revision
	Closed	quark	D657 revset: move weight information to predicate
	Closed	quark	D656 revset: remove "small" argument from "_optimize"

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: Time complexity of the revset implementation 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