This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1351

changegroup: use any node, not min(), in treemanifest's generatemanifests
ClosedPublic

Authored by spectral on Nov 8 2017, 10:17 PM.

Download Raw Diff

Details

Reviewers

indygreg

Group Reviewers

hg-reviewers

Commits

rHGd80380ba8e7d: changegroup: use any node, not min(), in treemanifest's generatemanifests

Summary

This is fixing quadratic behavior, which is probably not noticeable in the
common case, but if a very large directory gets added here, it can get pretty
bad. This was noticed because we had some pushes that spent >25s in changegroup
generation calling min() here, according to profiling.

The original reasoning for min() being used in 829d369fc5a8 was that, at that
point in the series, we were adding almost everything to tmfnodes during the
first iteration through the loop , so we needed to avoid sending child
directories before parents. Later changes made it so that the child directories
were added only when we visited the parent directory (not all of them on the
first iteration), so this is no longer necessary - there won't be any child
directories in tmfnodes before the parents have been sent.

This does mean that the manifests are now exchanged unordered, whereas
previously we would essentially do [a, b, b/c, b/c/d, e], we now can send a, b,
and e in any order; b/c must still follow b, and b/c/d must still follow b/c.

Diff Detail

Repository

rHG Mercurial

Lint

Lint Skipped

Unit

Unit Tests Skipped

Event Timeline

spectral created this revision.Nov 8 2017, 10:17 PM

Herald added a reviewer: hg-reviewers. · View Herald TranscriptNov 8 2017, 10:17 PM

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

As the author of that line of code, this looks good to me. I'll let someone else queue it since I was involved in the internal discussion and I don't want to feel like I'm queuing my own code (even though I wasn't involved in the actual coding).

Should I be concerned about the lack of test fallout? This new behavior is non-deterministic. Do we not have testing for this code or is existing testing not low-level enough to uncover behavior changes resulting from this change?

mercurial/changegroup.py
737	Can we use `dict.popitem()` instead? That will pop a random key-value pair. I just don't know if the key needs to remain in the dict until later in the function...

In D1351#22473, @indygreg wrote:

Should I be concerned about the lack of test fallout? This new behavior is non-deterministic. Do we not have testing for this code or is existing testing not low-level enough to uncover behavior changes resulting from this change?

I'm not worried about it. It only makes a difference for treemanifests, and the change is just about the order in changegroup and (therefore) the order in which we write revlogs. We don't have much testing of treemanifests and we rarely check the exact format in a changegroup. We do print out a debug message on line 482 that could be used to see a difference before and after this patch, but I just checked that test-treemanifest.t doesn't pass --verbose. Still, I wouldn't mind if some Facebooker tried to run their treemanifest tests (in hgexperimental) against a version with this patch applied.

mercurial/changegroup.py
737	Good idea. I'm pretty sure that should be safe (but perhaps tests will prove me wrong).

spectral added inline comments.Nov 10 2017, 12:47 AM

mercurial/changegroup.py
737	I think that it needs to remain, makelookupmflinknode(dir) relies on it (L716). I haven't attempted to popitem and pass that to makelookupmflinknode instead, let me try that out now...

martinvonz added inline comments.Nov 10 2017, 12:51 AM

mercurial/changegroup.py
737	Oh, yuck. Can perhaps pass "nodes" into makelookupmflinknode() along with "dir"? It will still update it on line 721, but at least one of those unclear sideeffects go away.

spectral updated this revision to Diff 3388.Nov 10 2017, 1:32 AM

run-tests.py found no issues with this version, my manual testing (using PYTHONHASHSEED to adjust the ordering) also encountered no issues

mercurial/changegroup.py
737	profiling seems to indicate this is a little faster as well as being a bit cleaner, so thanks for making me check :)

indygreg accepted this revision.Nov 10 2017, 1:46 AM

This revision is now accepted and ready to land.Nov 10 2017, 1:46 AM

Closed by commit rHGd80380ba8e7d: changegroup: use any node, not min(), in treemanifest's generatemanifests (authored by spectral). · Explain WhyNov 10 2017, 1:49 AM

This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

			Path	Packages
M			mercurial/changegroup.py (10 lines)

Diff	ID	Description	Created	Lint	Unit
Base		Base
Diff 1	3358		Nov 8 2017, 10:17 PM	★	★
Diff 2	3388		Nov 10 2017, 1:32 AM	★	★
Diff 3	3389	rHGd80380ba8e7ddee0e49ad79a8c0a8a4c1c743afc	Nov 8 2017, 9:24 PM	★	★

Diff 3388

mercurial/changegroup.py

	repo = self._repo			repo = self._repo
	mfl = repo.manifestlog			mfl = repo.manifestlog
	dirlog = mfl._revlog.dirlog			dirlog = mfl._revlog.dirlog
	tmfnodes = {'': mfs}			tmfnodes = {'': mfs}

	# Callback for the manifest, used to collect linkrevs for filelog			# Callback for the manifest, used to collect linkrevs for filelog
	# revisions.			# revisions.
	# Returns the linkrev node (collected in lookupcl).			# Returns the linkrev node (collected in lookupcl).
	def makelookupmflinknode(dir):			def makelookupmflinknode(dir, nodes):
	if fastpathlinkrev:			if fastpathlinkrev:
	assert not dir			assert not dir
	return mfs.__getitem__			return mfs.__getitem__

	def lookupmflinknode(x):			def lookupmflinknode(x):
	"""Callback for looking up the linknode for manifests.			"""Callback for looking up the linknode for manifests.

	Returns the linkrev node for the specified manifest.			Returns the linkrev node for the specified manifest.

	SIDE EFFECT:			SIDE EFFECT:

	1) fclnodes gets populated with the list of relevant			1) fclnodes gets populated with the list of relevant
	file nodes if we're not using fastpathlinkrev			file nodes if we're not using fastpathlinkrev
	2) When treemanifests are in use, collects treemanifest nodes			2) When treemanifests are in use, collects treemanifest nodes
	to send			to send

	Note that this means manifests must be completely sent to			Note that this means manifests must be completely sent to
	the client before you can trust the list of files and			the client before you can trust the list of files and
	treemanifests to send.			treemanifests to send.
	"""			"""
	clnode = tmfnodes[dir][x]			clnode = nodes[x]
	mdata = mfl.get(dir, x).readfast(shallow=True)			mdata = mfl.get(dir, x).readfast(shallow=True)
	for p, n, fl in mdata.iterentries():			for p, n, fl in mdata.iterentries():
	if fl == 't': # subdirectory manifest			if fl == 't': # subdirectory manifest
	subdir = dir + p + '/'			subdir = dir + p + '/'
	tmfclnodes = tmfnodes.setdefault(subdir, {})			tmfclnodes = tmfnodes.setdefault(subdir, {})
	tmfclnode = tmfclnodes.setdefault(n, clnode)			tmfclnode = tmfclnodes.setdefault(n, clnode)
	if clrevorder[clnode] < clrevorder[tmfclnode]:			if clrevorder[clnode] < clrevorder[tmfclnode]:
	tmfclnodes[n] = clnode			tmfclnodes[n] = clnode
	else:			else:
	f = dir + p			f = dir + p
	fclnodes = fnodes.setdefault(f, {})			fclnodes = fnodes.setdefault(f, {})
	fclnode = fclnodes.setdefault(n, clnode)			fclnode = fclnodes.setdefault(n, clnode)
	if clrevorder[clnode] < clrevorder[fclnode]:			if clrevorder[clnode] < clrevorder[fclnode]:
	fclnodes[n] = clnode			fclnodes[n] = clnode
	return clnode			return clnode
	return lookupmflinknode			return lookupmflinknode

	size = 0			size = 0
	while tmfnodes:			while tmfnodes:
	dir = min(tmfnodes)			dir, nodes = tmfnodes.popitem()
	nodes = tmfnodes[dir]
	prunednodes = self.prune(dirlog(dir), nodes, commonrevs)			prunednodes = self.prune(dirlog(dir), nodes, commonrevs)
				indygregUnsubmitted Done Can we use `dict.popitem()` instead? That will pop a random key-value pair. I just don't know if the key needs to remain in the dict until later in the function... indygreg: Can we use ``dict.popitem()`` instead? That will pop a random key-value pair. I just don't know…
				martinvonzUnsubmitted Done Good idea. I'm pretty sure that should be safe (but perhaps tests will prove me wrong). martinvonz: Good idea. I'm pretty sure that should be safe (but perhaps tests will prove me wrong).
				spectralAuthorUnsubmitted Done I think that it needs to remain, makelookupmflinknode(dir) relies on it (L716). I haven't attempted to popitem and pass that to makelookupmflinknode instead, let me try that out now... spectral: I think that it needs to remain, makelookupmflinknode(dir) relies on it (L716). I haven't…
				martinvonzUnsubmitted Done Oh, yuck. Can perhaps pass "nodes" into makelookupmflinknode() along with "dir"? It will still update it on line 721, but at least one of those unclear sideeffects go away. martinvonz: Oh, yuck. Can perhaps pass "nodes" into makelookupmflinknode() along with "dir"? It will still…
				spectralAuthorUnsubmitted Not Done profiling seems to indicate this is a little faster as well as being a bit cleaner, so thanks for making me check :) spectral: profiling seems to indicate this is a little faster as well as being a bit cleaner, so thanks…
	if not dir or prunednodes:			if not dir or prunednodes:
	for x in self._packmanifests(dir, prunednodes,			for x in self._packmanifests(dir, prunednodes,
	makelookupmflinknode(dir)):			makelookupmflinknode(dir, nodes)):
	size += len(x)			size += len(x)
	yield x			yield x
	del tmfnodes[dir]
	self._verbosenote(_('%8.i (manifests)\n') % size)			self._verbosenote(_('%8.i (manifests)\n') % size)
	yield self._manifestsdone()			yield self._manifestsdone()

	# The 'source' parameter is useful for extensions			# The 'source' parameter is useful for extensions
	def generatefiles(self, changedfiles, linknodes, commonrevs, source):			def generatefiles(self, changedfiles, linknodes, commonrevs, source):
	repo = self._repo			repo = self._repo
	progress = self._progress			progress = self._progress
	msgbundling = _('bundling')			msgbundling = _('bundling')