This is an archive of the discontinued Mercurial Phabricator instance.

Differential D4214

changegroup: refactor delta parent code
ClosedPublic

Authored by indygreg on Aug 9 2018, 4:52 PM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHGef3d3a2f9aa5: changegroup: refactor delta parent code
Summary

We had recently abstracted the delta parent functions to
facilitate extracting code from cgpacker. Now that we're in
a better place, it is time to revisit the design.

Changegroup version 1 requires that the previous node be used as the
delta parent. Later versions allow any available node to be used
as the base.

In the case where an arbitrary parent can be used, the choice of
a delta parent is best left in the hands of the storage backend.
So it makes sense for the delta parent selection to be hidden
away in the storage layer. This means deferring the choice of the
delta parent selection function to as close to delta generation
time as possible.

This commit moves the delta selection logic to essentially just
before delta generation. However, because changegroup version 1
limits what we can do, we have retained the ability to force a
delta against the previous revision.

As part of this, I realized that the ellipsis parent function was
unused! That's because ellipsis mode always sends full revisions
and not deltas.

Diff Detail

Repository
rHG Mercurial
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

indygreg created this revision.Aug 9 2018, 4:52 PM
durin42 added a subscriber: durin42.Aug 9 2018, 10:21 PM

Yeah, adgar and I spent a long time (and then martinvonz and I did too, I think) trying to figure out how to emit ellipsis deltas, and slowly we reached the conclusion that it wasn't easy, and given that we could assume a big pipe from server to client, we punted. It _might_ be a solvable problem, but it may cost a prohibitive amount of CPU time.

Closed by commit rHGef3d3a2f9aa5: changegroup: refactor delta parent code (authored by indygreg). · Explain WhyAug 9 2018, 10:24 PM
This revision was automatically updated to reflect the committed changes.
indygreg added a comment.Aug 9 2018, 10:34 PM

It is a hard problem because the server can't make any assumptions about what nodes the receiver has! So you either need the client to transmit the set of nodes it has. Without that, the best the server can do is encode a delta against a revision in the same delta group. And that would strictly be better than what's implemented (which is to always send a full revision!). It should be easy enough to change the logic though. Although we'd need to pass more information down to the code doing the delta generation.

Revision Contents
Changeset List

PathPackages
Mmercurial/changegroup.py (108 lines)

Diff 10208

mercurial/changegroup.py

# The one invariant we *know* holds is that the new (potentially # The one invariant we *know* holds is that the new (potentially
# bogus) DAG shape will be valid if we order the nodes in the # bogus) DAG shape will be valid if we order the nodes in the
# order that they're introduced in dramatis personae by the # order that they're introduced in dramatis personae by the
# changelog, so what we do is we sort the non-changelog histories # changelog, so what we do is we sort the non-changelog histories
# by the order in which they are used by the changelog. # by the order in which they are used by the changelog.
key = lambda n: cl.rev(lookup(n)) key = lambda n: cl.rev(lookup(n))
return [store.rev(n) for n in sorted(nodes, key=key)] return [store.rev(n) for n in sorted(nodes, key=key)]
def _revisiondeltanormal(store, rev, prev, linknode, deltaparentfn): def _revisiondeltanormal(store, rev, prev, linknode, forcedeltaparentprev):
"""Construct a revision delta for non-ellipses changegroup generation.""" """Construct a revision delta for non-ellipses changegroup generation."""
node = store.node(rev) node = store.node(rev)
p1, p2 = store.parentrevs(rev) p1, p2 = store.parentrevs(rev)
base = deltaparentfn(store, rev, p1, p2, prev)
if forcedeltaparentprev:
base = prev
else:
dp = store.deltaparent(rev)
if dp == nullrev and store.storedeltachains:
# Avoid sending full revisions when delta parent is null. Pick prev
# in that case. It's tempting to pick p1 in this case, as p1 will
# be smaller in the common case. However, computing a delta against
# p1 may require resolving the raw text of p1, which could be
# expensive. The revlog caches should have prev cached, meaning
# less CPU for changegroup generation. There is likely room to add
# a flag and/or config option to control this behavior.
base = prev
elif dp == nullrev:
# revlog is configured to use full snapshot for a reason,
# stick to full snapshot.
base = nullrev
elif dp not in (p1, p2, prev):
# Pick prev when we can't be sure remote has the base revision.
base = prev
else:
base = dp
if base != nullrev and not store.candelta(base, rev):
base = nullrev
revision = None revision = None
delta = None delta = None
baserevisionsize = None baserevisionsize = None
if store.iscensored(base) or store.iscensored(rev): if store.iscensored(base) or store.iscensored(rev):
try: try:
revision = store.revision(node, raw=True) revision = store.revision(node, raw=True)
basenode=nullid, basenode=nullid,
linknode=linknode, linknode=linknode,
flags=flags, flags=flags,
baserevisionsize=None, baserevisionsize=None,
revision=store.revision(n), revision=store.revision(n),
delta=None, delta=None,
) )
def deltagroup(repo, revs, store, ischangelog, lookup, deltaparentfn, def deltagroup(repo, revs, store, ischangelog, lookup, forcedeltaparentprev,
units=None, units=None,
ellipses=False, clrevtolocalrev=None, fullclnodes=None, ellipses=False, clrevtolocalrev=None, fullclnodes=None,
precomputedellipsis=None): precomputedellipsis=None):
"""Calculate deltas for a set of revisions. """Calculate deltas for a set of revisions.
Is a generator of ``revisiondelta`` instances. Is a generator of ``revisiondelta`` instances.
If units is not None, progress detail will be generated, units specifies If units is not None, progress detail will be generated, units specifies
if ellipses: if ellipses:
linkrev = cl.rev(linknode) linkrev = cl.rev(linknode)
clrevtolocalrev[linkrev] = curr clrevtolocalrev[linkrev] = curr
# This is a node to send in full, because the changeset it # This is a node to send in full, because the changeset it
# corresponds to was a full changeset. # corresponds to was a full changeset.
if linknode in fullclnodes: if linknode in fullclnodes:
delta = _revisiondeltanormal(store, curr, prev, linknode, delta = _revisiondeltanormal(store, curr, prev, linknode,
deltaparentfn) forcedeltaparentprev)
elif linkrev not in precomputedellipsis: elif linkrev not in precomputedellipsis:
delta = None delta = None
else: else:
delta = _revisiondeltanarrow( delta = _revisiondeltanarrow(
cl, store, ischangelog, curr, linkrev, linknode, cl, store, ischangelog, curr, linkrev, linknode,
clrevtolocalrev, fullclnodes, clrevtolocalrev, fullclnodes,
precomputedellipsis) precomputedellipsis)
else: else:
delta = _revisiondeltanormal(store, curr, prev, linknode, delta = _revisiondeltanormal(store, curr, prev, linknode,
deltaparentfn) forcedeltaparentprev)
if delta: if delta:
yield delta yield delta
if progress: if progress:
progress.complete() progress.complete()
class cgpacker(object): class cgpacker(object):
def __init__(self, repo, filematcher, version, allowreorder, def __init__(self, repo, filematcher, version, allowreorder,
deltaparentfn, builddeltaheader, manifestsend, builddeltaheader, manifestsend,
forcedeltaparentprev=False,
bundlecaps=None, ellipses=False, bundlecaps=None, ellipses=False,
shallow=False, ellipsisroots=None, fullnodes=None): shallow=False, ellipsisroots=None, fullnodes=None):
"""Given a source repo, construct a bundler. """Given a source repo, construct a bundler.
filematcher is a matcher that matches on files to include in the filematcher is a matcher that matches on files to include in the
changegroup. Used to facilitate sparse changegroups. changegroup. Used to facilitate sparse changegroups.
allowreorder controls whether reordering of revisions is allowed. allowreorder controls whether reordering of revisions is allowed.
This value is used when ``bundle.reorder`` is ``auto`` or isn't This value is used when ``bundle.reorder`` is ``auto`` or isn't
set. set.
deltaparentfn is a callable that resolves the delta parent for forcedeltaparentprev indicates whether delta parents must be against
a specific revision. the previous revision in a delta group. This should only be used for
compatibility with changegroup version 1.
builddeltaheader is a callable that constructs the header for a group builddeltaheader is a callable that constructs the header for a group
delta. delta.
manifestsend is a chunk to send after manifests have been fully emitted. manifestsend is a chunk to send after manifests have been fully emitted.
ellipses indicates whether ellipsis serving mode is enabled. ellipses indicates whether ellipsis serving mode is enabled.
nodes. We store this rather than the set of nodes that should be nodes. We store this rather than the set of nodes that should be
ellipsis because for very large histories we expect this to be ellipsis because for very large histories we expect this to be
significantly smaller. significantly smaller.
""" """
assert filematcher assert filematcher
self._filematcher = filematcher self._filematcher = filematcher
self.version = version self.version = version
self._deltaparentfn = deltaparentfn self._forcedeltaparentprev = forcedeltaparentprev
self._builddeltaheader = builddeltaheader self._builddeltaheader = builddeltaheader
self._manifestsend = manifestsend self._manifestsend = manifestsend
self._ellipses = ellipses self._ellipses = ellipses
# Set of capabilities we can use to build the bundle. # Set of capabilities we can use to build the bundle.
if bundlecaps is None: if bundlecaps is None:
bundlecaps = set() bundlecaps = set()
self._bundlecaps = bundlecaps self._bundlecaps = bundlecaps
'clrevorder': clrevorder, 'clrevorder': clrevorder,
'mfs': mfs, 'mfs': mfs,
'changedfiles': changedfiles, 'changedfiles': changedfiles,
'clrevtomanifestrev': clrevtomanifestrev, 'clrevtomanifestrev': clrevtomanifestrev,
} }
gen = deltagroup( gen = deltagroup(
self._repo, revs, cl, True, lookupcl, self._repo, revs, cl, True, lookupcl,
self._deltaparentfn, self._forcedeltaparentprev,
ellipses=self._ellipses, ellipses=self._ellipses,
units=_('changesets'), units=_('changesets'),
clrevtolocalrev={}, clrevtolocalrev={},
fullclnodes=self._fullclnodes, fullclnodes=self._fullclnodes,
precomputedellipsis=self._precomputedellipsis) precomputedellipsis=self._precomputedellipsis)
return state, gen return state, gen
revs = _sortnodesellipsis(store, prunednodes, cl, revs = _sortnodesellipsis(store, prunednodes, cl,
lookupfn) lookupfn)
else: else:
revs = _sortnodesnormal(store, prunednodes, revs = _sortnodesnormal(store, prunednodes,
self._reorder) self._reorder)
deltas = deltagroup( deltas = deltagroup(
self._repo, revs, store, False, lookupfn, self._repo, revs, store, False, lookupfn,
self._deltaparentfn, self._forcedeltaparentprev,
ellipses=self._ellipses, ellipses=self._ellipses,
units=_('manifests'), units=_('manifests'),
clrevtolocalrev=clrevtolocalrev, clrevtolocalrev=clrevtolocalrev,
fullclnodes=self._fullclnodes, fullclnodes=self._fullclnodes,
precomputedellipsis=self._precomputedellipsis) precomputedellipsis=self._precomputedellipsis)
yield dir, deltas yield dir, deltas
else: else:
revs = _sortnodesnormal(filerevlog, filenodes, revs = _sortnodesnormal(filerevlog, filenodes,
self._reorder) self._reorder)
progress.update(i + 1, item=fname) progress.update(i + 1, item=fname)
deltas = deltagroup( deltas = deltagroup(
self._repo, revs, filerevlog, False, lookupfilelog, self._repo, revs, filerevlog, False, lookupfilelog,
self._deltaparentfn, self._forcedeltaparentprev,
ellipses=self._ellipses, ellipses=self._ellipses,
clrevtolocalrev=clrevtolocalrev, clrevtolocalrev=clrevtolocalrev,
fullclnodes=self._fullclnodes, fullclnodes=self._fullclnodes,
precomputedellipsis=self._precomputedellipsis) precomputedellipsis=self._precomputedellipsis)
yield fname, deltas yield fname, deltas
progress.complete() progress.complete()
def _deltaparentprev(store, rev, p1, p2, prev):
"""Resolve a delta parent to the previous revision.
Used for version 1 changegroups, which don't support generaldelta.
"""
return prev
def _deltaparentgeneraldelta(store, rev, p1, p2, prev):
"""Resolve a delta parent when general deltas are supported."""
dp = store.deltaparent(rev)
if dp == nullrev and store.storedeltachains:
# Avoid sending full revisions when delta parent is null. Pick prev
# in that case. It's tempting to pick p1 in this case, as p1 will
# be smaller in the common case. However, computing a delta against
# p1 may require resolving the raw text of p1, which could be
# expensive. The revlog caches should have prev cached, meaning
# less CPU for changegroup generation. There is likely room to add
# a flag and/or config option to control this behavior.
base = prev
elif dp == nullrev:
# revlog is configured to use full snapshot for a reason,
# stick to full snapshot.
base = nullrev
elif dp not in (p1, p2, prev):
# Pick prev when we can't be sure remote has the base revision.
return prev
else:
base = dp
if base != nullrev and not store.candelta(base, rev):
base = nullrev
return base
def _deltaparentellipses(store, rev, p1, p2, prev):
"""Resolve a delta parent when in ellipses mode."""
# TODO: send better deltas when in narrow mode.
#
# changegroup.group() loops over revisions to send,
# including revisions we'll skip. What this means is that
# `prev` will be a potentially useless delta base for all
# ellipsis nodes, as the client likely won't have it. In
# the future we should do bookkeeping about which nodes
# have been sent to the client, and try to be
# significantly smarter about delta bases. This is
# slightly tricky because this same code has to work for
# all revlogs, and we don't have the linkrev/linknode here.
return p1
def _makecg1packer(repo, filematcher, bundlecaps, ellipses=False, def _makecg1packer(repo, filematcher, bundlecaps, ellipses=False,
shallow=False, ellipsisroots=None, fullnodes=None): shallow=False, ellipsisroots=None, fullnodes=None):
builddeltaheader = lambda d: _CHANGEGROUPV1_DELTA_HEADER.pack( builddeltaheader = lambda d: _CHANGEGROUPV1_DELTA_HEADER.pack(
d.node, d.p1node, d.p2node, d.linknode) d.node, d.p1node, d.p2node, d.linknode)
return cgpacker(repo, filematcher, b'01', return cgpacker(repo, filematcher, b'01',
deltaparentfn=_deltaparentprev,
allowreorder=None, allowreorder=None,
builddeltaheader=builddeltaheader, builddeltaheader=builddeltaheader,
manifestsend=b'', manifestsend=b'',
forcedeltaparentprev=True,
bundlecaps=bundlecaps, bundlecaps=bundlecaps,
ellipses=ellipses, ellipses=ellipses,
shallow=shallow, shallow=shallow,
ellipsisroots=ellipsisroots, ellipsisroots=ellipsisroots,
fullnodes=fullnodes) fullnodes=fullnodes)
def _makecg2packer(repo, filematcher, bundlecaps, ellipses=False, def _makecg2packer(repo, filematcher, bundlecaps, ellipses=False,
shallow=False, ellipsisroots=None, fullnodes=None): shallow=False, ellipsisroots=None, fullnodes=None):
builddeltaheader = lambda d: _CHANGEGROUPV2_DELTA_HEADER.pack( builddeltaheader = lambda d: _CHANGEGROUPV2_DELTA_HEADER.pack(
d.node, d.p1node, d.p2node, d.basenode, d.linknode) d.node, d.p1node, d.p2node, d.basenode, d.linknode)
# Since generaldelta is directly supported by cg2, reordering # Since generaldelta is directly supported by cg2, reordering
# generally doesn't help, so we disable it by default (treating # generally doesn't help, so we disable it by default (treating
# bundle.reorder=auto just like bundle.reorder=False). # bundle.reorder=auto just like bundle.reorder=False).
return cgpacker(repo, filematcher, b'02', return cgpacker(repo, filematcher, b'02',
deltaparentfn=_deltaparentgeneraldelta,
allowreorder=False, allowreorder=False,
builddeltaheader=builddeltaheader, builddeltaheader=builddeltaheader,
manifestsend=b'', manifestsend=b'',
bundlecaps=bundlecaps, bundlecaps=bundlecaps,
ellipses=ellipses, ellipses=ellipses,
shallow=shallow, shallow=shallow,
ellipsisroots=ellipsisroots, ellipsisroots=ellipsisroots,
fullnodes=fullnodes) fullnodes=fullnodes)
def _makecg3packer(repo, filematcher, bundlecaps, ellipses=False, def _makecg3packer(repo, filematcher, bundlecaps, ellipses=False,
shallow=False, ellipsisroots=None, fullnodes=None): shallow=False, ellipsisroots=None, fullnodes=None):
builddeltaheader = lambda d: _CHANGEGROUPV3_DELTA_HEADER.pack( builddeltaheader = lambda d: _CHANGEGROUPV3_DELTA_HEADER.pack(
d.node, d.p1node, d.p2node, d.basenode, d.linknode, d.flags) d.node, d.p1node, d.p2node, d.basenode, d.linknode, d.flags)
deltaparentfn = (_deltaparentellipses if ellipses
else _deltaparentgeneraldelta)
return cgpacker(repo, filematcher, b'03', return cgpacker(repo, filematcher, b'03',
deltaparentfn=deltaparentfn,
allowreorder=False, allowreorder=False,
builddeltaheader=builddeltaheader, builddeltaheader=builddeltaheader,
manifestsend=closechunk(), manifestsend=closechunk(),
bundlecaps=bundlecaps, bundlecaps=bundlecaps,
ellipses=ellipses, ellipses=ellipses,
shallow=shallow, shallow=shallow,
ellipsisroots=ellipsisroots, ellipsisroots=ellipsisroots,
fullnodes=fullnodes) fullnodes=fullnodes)