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.

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
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

spectral created this revision.Nov 8 2017, 10:17 PM
martinvonz added a subscriber: martinvonz.Nov 9 2017, 12:18 AM

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

indygreg added a subscriber: indygreg.Nov 10 2017, 12:30 AM

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

martinvonz added a comment.Nov 10 2017, 12:41 AM
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
spectral marked 4 inline comments as done.Nov 10 2017, 1:41 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

PathPackages
Mmercurial/changegroup.py (10 lines)

Diff 3389

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')