• Jeff King's avatar
    pack-objects: reuse on-disk deltas for thin "have" objects · 6a1e32d5
    Jeff King authored
    When we serve a fetch, we pass the "wants" and "haves" from
    the fetch negotiation to pack-objects. That tells us not
    only which objects we need to send, but we also use the
    boundary commits as "preferred bases": their trees and blobs
    are candidates for delta bases, both for reusing on-disk
    deltas and for finding new ones.
    
    However, this misses some opportunities. Modulo some special
    cases like shallow or partial clones, we know that every
    object reachable from the "haves" could be a preferred base.
    We don't use all of them for two reasons:
    
      1. It's expensive to traverse the whole history and
         enumerate all of the objects the other side has.
    
      2. The delta search is expensive, so we want to keep the
         number of candidate bases sane. The boundary commits
         are the most likely to work.
    
    When we have reachability bitmaps, though, reason 1 no
    longer applies. We can efficiently compute the set of
    reachable objects on the other side (and in fact already did
    so as part of the bitmap set-difference to get the list of
    interesting objects). And using this set conveniently
    covers the shallow and partial cases, since we have to
    disable the use of bitmaps for those anyway.
    
    The second reason argues against using these bases in the
    search for new deltas. But there's one case where we can use
    this information for free: when we have an existing on-disk
    delta that we're considering reusing, we can do so if we
    know the other side has the base object. This in fact saves
    time during the delta search, because it's one less delta we
    have to compute.
    
    And that's exactly what this patch does: when we're
    considering whether to reuse an on-disk delta, if bitmaps
    tell us the other side has the object (and we're making a
    thin-pack), then we reuse it.
    
    Here are the results on p5311 using linux.git, which
    simulates a client fetching after `N` days since their last
    fetch:
    
     Test                         origin              HEAD
     --------------------------------------------------------------------------
     5311.3: server   (1 days)    0.27(0.27+0.04)     0.12(0.09+0.03) -55.6%
     5311.4: size     (1 days)               0.9M              237.0K -73.7%
     5311.5: client   (1 days)    0.04(0.05+0.00)     0.10(0.10+0.00) +150.0%
     5311.7: server   (2 days)    0.34(0.42+0.04)     0.13(0.10+0.03) -61.8%
     5311.8: size     (2 days)               1.5M              347.7K -76.5%
     5311.9: client   (2 days)    0.07(0.08+0.00)     0.16(0.15+0.01) +128.6%
     5311.11: server   (4 days)   0.56(0.77+0.08)     0.13(0.10+0.02) -76.8%
     5311.12: size     (4 days)              2.8M              566.6K -79.8%
     5311.13: client   (4 days)   0.13(0.15+0.00)     0.34(0.31+0.02) +161.5%
     5311.15: server   (8 days)   0.97(1.39+0.11)     0.30(0.25+0.05) -69.1%
     5311.16: size     (8 days)              4.3M                1.0M -76.0%
     5311.17: client   (8 days)   0.20(0.22+0.01)     0.53(0.52+0.01) +165.0%
     5311.19: server  (16 days)   1.52(2.51+0.12)     0.30(0.26+0.03) -80.3%
     5311.20: size    (16 days)              8.0M                2.0M -74.5%
     5311.21: client  (16 days)   0.40(0.47+0.03)     1.01(0.98+0.04) +152.5%
     5311.23: server  (32 days)   2.40(4.44+0.20)     0.31(0.26+0.04) -87.1%
     5311.24: size    (32 days)             14.1M                4.1M -70.9%
     5311.25: client  (32 days)   0.70(0.90+0.03)     1.81(1.75+0.06) +158.6%
     5311.27: server  (64 days)   11.76(26.57+0.29)   0.55(0.50+0.08) -95.3%
     5311.28: size    (64 days)             89.4M               47.4M -47.0%
     5311.29: client  (64 days)   5.71(9.31+0.27)     15.20(15.20+0.32) +166.2%
     5311.31: server (128 days)   16.15(36.87+0.40)   0.91(0.82+0.14) -94.4%
     5311.32: size   (128 days)            134.8M              100.4M -25.5%
     5311.33: client (128 days)   9.42(16.86+0.49)    25.34(25.80+0.46) +169.0%
    
    In all cases we save CPU time on the server (sometimes
    significant) and the resulting pack is smaller. We do spend
    more CPU time on the client side, because it has to
    reconstruct more deltas. But that's the right tradeoff to
    make, since clients tend to outnumber servers. It just means
    the thin pack mechanism is doing its job.
    
    From the user's perspective, the end-to-end time of the
    operation will generally be faster. E.g., in the 128-day
    case, we saved 15s on the server at a cost of 16s on the
    client. Since the resulting pack is 34MB smaller, this is a
    net win if the network speed is less than 270Mbit/s. And
    that's actually the worst case. The 64-day case saves just
    over 11s at a cost of just under 11s. So it's a slight win
    at any network speed, and the 40MB saved is pure bonus. That
    trend continues for the smaller fetches.
    
    The implementation itself is mostly straightforward, with
    the new logic going into check_object(). But there are two
    tricky bits.
    
    The first is that check_object() needs access to the
    relevant information (the thin flag and bitmap result). We
    can do this by pushing these into program-lifetime globals.
    
    The second is that the rest of the code assumes that any
    reused delta will point to another "struct object_entry" as
    its base. But of course the case we are interested in here
    is the one where don't have such an entry!
    
    I looked at a number of options that didn't quite work:
    
     - we could use a flag to signal a reused delta, but it's
       not a single bit. We have to actually store the oid of
       the base, which is normally done by pointing to the
       existing object_entry. And we'd have to modify all the
       code which looks at deltas.
    
     - we could add the reused bases to the end of the existing
       object_entry array. While this does create some extra
       work as later stages consider the extra entries, it's
       actually not too bad (we're not sending them, so they
       don't cost much in the delta search, and at most we'd
       have 2*N of them).
    
       But there's a more subtle problem. Adding to the existing
       array means we might need to grow it with realloc, which
       could move the earlier entries around. While many of the
       references to other entries are done by integer index,
       some (including ones on the stack) use pointers, which
       would become invalidated.
    
       This isn't insurmountable, but it would require quite a
       bit of refactoring (and it's hard to know that you've got
       it all, since it may work _most_ of the time and then
       fail subtly based on memory allocation patterns).
    
     - we could allocate a new one-off entry for the base. In
       fact, this is what an earlier version of this patch did.
       However, since the refactoring brought in by ad635e82
       (Merge branch 'nd/pack-objects-pack-struct', 2018-05-23),
       the delta_idx code requires that both entries be in the
       main packing list.
    
    So taking all of those options into account, what I ended up
    with is a separate list of "external bases" that are not
    part of the main packing list. Each delta entry that points
    to an external base has a single-bit flag to do so; we have a
    little breathing room in the bitfield section of
    object_entry.
    
    This lets us limit the change primarily to the oe_delta()
    and oe_set_delta_ext() functions. And as a bonus, most of
    the rest of the code does not consider these dummy entries
    at all, saving both runtime CPU and code complexity.
    Signed-off-by: default avatarJeff King <peff@peff.net>
    Signed-off-by: default avatarJunio C Hamano <gitster@pobox.com>
    6a1e32d5
Name
Last commit
Last update
.github Loading commit data...
Documentation Loading commit data...
block-sha1 Loading commit data...
builtin Loading commit data...
ci Loading commit data...
compat Loading commit data...
contrib Loading commit data...
ewah Loading commit data...
git-gui Loading commit data...
gitk-git Loading commit data...
gitweb Loading commit data...
mergetools Loading commit data...
negotiator Loading commit data...
perl Loading commit data...
po Loading commit data...
ppc Loading commit data...
refs Loading commit data...
sha1collisiondetection @ 232357eb Loading commit data...
sha1dc Loading commit data...
t Loading commit data...
templates Loading commit data...
vcs-svn Loading commit data...
xdiff Loading commit data...
.clang-format Loading commit data...
.gitattributes Loading commit data...
.gitignore Loading commit data...
.gitmodules Loading commit data...
.mailmap Loading commit data...
.travis.yml Loading commit data...
.tsan-suppressions Loading commit data...
COPYING Loading commit data...
GIT-VERSION-GEN Loading commit data...
INSTALL Loading commit data...
LGPL-2.1 Loading commit data...
Makefile Loading commit data...
README.md Loading commit data...
RelNotes Loading commit data...
abspath.c Loading commit data...
aclocal.m4 Loading commit data...
advice.c Loading commit data...
advice.h Loading commit data...
alias.c Loading commit data...
alias.h Loading commit data...
alloc.c Loading commit data...
alloc.h Loading commit data...
apply.c Loading commit data...
apply.h Loading commit data...
archive-tar.c Loading commit data...
archive-zip.c Loading commit data...
archive.c Loading commit data...
archive.h Loading commit data...
argv-array.c Loading commit data...
argv-array.h Loading commit data...
attr.c Loading commit data...
attr.h Loading commit data...
banned.h Loading commit data...
base85.c Loading commit data...
bisect.c Loading commit data...
bisect.h Loading commit data...
blame.c Loading commit data...
blame.h Loading commit data...
blob.c Loading commit data...
blob.h Loading commit data...
branch.c Loading commit data...
branch.h Loading commit data...
builtin.h Loading commit data...
bulk-checkin.c Loading commit data...
bulk-checkin.h Loading commit data...
bundle.c Loading commit data...
bundle.h Loading commit data...
cache-tree.c Loading commit data...
cache-tree.h Loading commit data...
cache.h Loading commit data...
chdir-notify.c Loading commit data...
chdir-notify.h Loading commit data...
check-builtins.sh Loading commit data...
check-racy.c Loading commit data...
check_bindir Loading commit data...
checkout.c Loading commit data...
checkout.h Loading commit data...
color.c Loading commit data...
color.h Loading commit data...
column.c Loading commit data...
column.h Loading commit data...
combine-diff.c Loading commit data...
command-list.txt Loading commit data...
commit-graph.c Loading commit data...
commit-graph.h Loading commit data...
commit-slab-decl.h Loading commit data...
commit-slab-impl.h Loading commit data...
commit-slab.h Loading commit data...
commit.c Loading commit data...
commit.h Loading commit data...
common-main.c Loading commit data...
config.c Loading commit data...
config.h Loading commit data...
config.mak.dev Loading commit data...
config.mak.in Loading commit data...
config.mak.uname Loading commit data...
configure.ac Loading commit data...
connect.c Loading commit data...
connect.h Loading commit data...
connected.c Loading commit data...
connected.h Loading commit data...
convert.c Loading commit data...
convert.h Loading commit data...
copy.c Loading commit data...
credential-cache--daemon.c Loading commit data...
credential-cache.c Loading commit data...
credential-store.c Loading commit data...
credential.c Loading commit data...
credential.h Loading commit data...
csum-file.c Loading commit data...
csum-file.h Loading commit data...
ctype.c Loading commit data...
daemon.c Loading commit data...
date.c Loading commit data...
decorate.c Loading commit data...
decorate.h Loading commit data...
delta.h Loading commit data...
detect-compiler Loading commit data...
diff-delta.c Loading commit data...
diff-lib.c Loading commit data...
diff-no-index.c Loading commit data...
diff.c Loading commit data...
diff.h Loading commit data...
diffcore-break.c Loading commit data...
diffcore-delta.c Loading commit data...
diffcore-order.c Loading commit data...
diffcore-pickaxe.c Loading commit data...
diffcore-rename.c Loading commit data...
diffcore.h Loading commit data...
dir-iterator.c Loading commit data...
dir-iterator.h Loading commit data...
dir.c Loading commit data...
dir.h Loading commit data...
editor.c Loading commit data...
entry.c Loading commit data...
environment.c Loading commit data...
exec-cmd.c Loading commit data...
exec-cmd.h Loading commit data...
fast-import.c Loading commit data...
fetch-negotiator.c Loading commit data...
fetch-negotiator.h Loading commit data...
fetch-object.c Loading commit data...
fetch-object.h Loading commit data...
fetch-pack.c Loading commit data...
fetch-pack.h Loading commit data...
fmt-merge-msg.h Loading commit data...
fsck.c Loading commit data...
fsck.h Loading commit data...
fsmonitor.c Loading commit data...
fsmonitor.h Loading commit data...
generate-cmdlist.sh Loading commit data...
gettext.c Loading commit data...
gettext.h Loading commit data...
git-add--interactive.perl Loading commit data...
git-archimport.perl Loading commit data...
git-bisect.sh Loading commit data...
git-compat-util.h Loading commit data...
git-cvsexportcommit.perl Loading commit data...
git-cvsimport.perl Loading commit data...
git-cvsserver.perl Loading commit data...
git-difftool--helper.sh Loading commit data...
git-filter-branch.sh Loading commit data...
git-instaweb.sh Loading commit data...
git-merge-octopus.sh Loading commit data...
git-merge-one-file.sh Loading commit data...
git-merge-resolve.sh Loading commit data...
git-mergetool--lib.sh Loading commit data...
git-mergetool.sh Loading commit data...
git-p4.py Loading commit data...
git-parse-remote.sh Loading commit data...
git-quiltimport.sh Loading commit data...
git-rebase--am.sh Loading commit data...
git-rebase--interactive.sh Loading commit data...
git-rebase--merge.sh Loading commit data...
git-rebase--preserve-merges.sh Loading commit data...
git-rebase.sh Loading commit data...
git-remote-testgit.sh Loading commit data...
git-request-pull.sh Loading commit data...
git-send-email.perl Loading commit data...
git-sh-i18n.sh Loading commit data...
git-sh-setup.sh Loading commit data...
git-stash.sh Loading commit data...
git-submodule.sh Loading commit data...
git-svn.perl Loading commit data...
git-web--browse.sh Loading commit data...
git.c Loading commit data...
git.rc Loading commit data...
gpg-interface.c Loading commit data...
gpg-interface.h Loading commit data...
graph.c Loading commit data...
graph.h Loading commit data...
grep.c Loading commit data...
grep.h Loading commit data...
hash.h Loading commit data...
hashmap.c Loading commit data...
hashmap.h Loading commit data...
help.c Loading commit data...
help.h Loading commit data...
hex.c Loading commit data...
http-backend.c Loading commit data...
http-fetch.c Loading commit data...
http-push.c Loading commit data...
http-walker.c Loading commit data...
http.c Loading commit data...
http.h Loading commit data...
ident.c Loading commit data...
imap-send.c Loading commit data...
iterator.h Loading commit data...
json-writer.c Loading commit data...
json-writer.h Loading commit data...
khash.h Loading commit data...
kwset.c Loading commit data...
kwset.h Loading commit data...
levenshtein.c Loading commit data...
levenshtein.h Loading commit data...
line-log.c Loading commit data...
line-log.h Loading commit data...
line-range.c Loading commit data...
line-range.h Loading commit data...
linear-assignment.c Loading commit data...
linear-assignment.h Loading commit data...
list-objects-filter-options.c Loading commit data...
list-objects-filter-options.h Loading commit data...
list-objects-filter.c Loading commit data...
list-objects-filter.h Loading commit data...
list-objects.c Loading commit data...
list-objects.h Loading commit data...
list.h Loading commit data...
ll-merge.c Loading commit data...
ll-merge.h Loading commit data...
lockfile.c Loading commit data...
lockfile.h Loading commit data...
log-tree.c Loading commit data...
log-tree.h Loading commit data...
ls-refs.c Loading commit data...
ls-refs.h Loading commit data...
mailinfo.c Loading commit data...
mailinfo.h Loading commit data...
mailmap.c Loading commit data...
mailmap.h Loading commit data...
match-trees.c Loading commit data...
mem-pool.c Loading commit data...
mem-pool.h Loading commit data...
merge-blobs.c Loading commit data...
merge-blobs.h Loading commit data...
merge-recursive.c Loading commit data...
merge-recursive.h Loading commit data...
merge.c Loading commit data...
mergesort.c Loading commit data...
mergesort.h Loading commit data...
name-hash.c Loading commit data...
notes-cache.c Loading commit data...
notes-cache.h Loading commit data...
notes-merge.c Loading commit data...
notes-merge.h Loading commit data...
notes-utils.c Loading commit data...
notes-utils.h Loading commit data...
notes.c Loading commit data...
notes.h Loading commit data...
object-store.h Loading commit data...
object.c Loading commit data...
object.h Loading commit data...
oidmap.c Loading commit data...
oidmap.h Loading commit data...
oidset.c Loading commit data...
oidset.h Loading commit data...
pack-bitmap-write.c Loading commit data...
pack-bitmap.c Loading commit data...
pack-bitmap.h Loading commit data...
pack-check.c Loading commit data...
pack-objects.c Loading commit data...
pack-objects.h Loading commit data...
pack-revindex.c Loading commit data...
pack-revindex.h Loading commit data...
pack-write.c Loading commit data...
pack.h Loading commit data...
packfile.c Loading commit data...
packfile.h Loading commit data...
pager.c Loading commit data...
parse-options-cb.c Loading commit data...
parse-options.c Loading commit data...
parse-options.h Loading commit data...
patch-delta.c Loading commit data...
patch-ids.c Loading commit data...
patch-ids.h Loading commit data...
path.c Loading commit data...
path.h Loading commit data...
pathspec.c Loading commit data...
pathspec.h Loading commit data...
pkt-line.c Loading commit data...
pkt-line.h Loading commit data...
preload-index.c Loading commit data...
pretty.c Loading commit data...
pretty.h Loading commit data...
prio-queue.c Loading commit data...
prio-queue.h Loading commit data...
progress.c Loading commit data...
progress.h Loading commit data...
prompt.c Loading commit data...
prompt.h Loading commit data...
protocol.c Loading commit data...
protocol.h Loading commit data...
quote.c Loading commit data...
quote.h Loading commit data...
range-diff.c Loading commit data...
range-diff.h Loading commit data...
reachable.c Loading commit data...
reachable.h Loading commit data...
read-cache.c Loading commit data...
ref-filter.c Loading commit data...
ref-filter.h Loading commit data...
reflog-walk.c Loading commit data...
reflog-walk.h Loading commit data...
refs.c Loading commit data...
refs.h Loading commit data...
refspec.c Loading commit data...
refspec.h Loading commit data...
remote-curl.c Loading commit data...
remote-testsvn.c Loading commit data...
remote.c Loading commit data...
remote.h Loading commit data...
replace-object.c Loading commit data...
replace-object.h Loading commit data...
repository.c Loading commit data...
repository.h Loading commit data...
rerere.c Loading commit data...
rerere.h Loading commit data...
resolve-undo.c Loading commit data...
resolve-undo.h Loading commit data...
revision.c Loading commit data...
revision.h Loading commit data...
run-command.c Loading commit data...
run-command.h Loading commit data...
send-pack.c Loading commit data...
send-pack.h Loading commit data...
sequencer.c Loading commit data...
sequencer.h Loading commit data...
serve.c Loading commit data...
serve.h Loading commit data...
server-info.c Loading commit data...
setup.c Loading commit data...
sh-i18n--envsubst.c Loading commit data...
sha1-array.c Loading commit data...
sha1-array.h Loading commit data...
sha1-file.c Loading commit data...
sha1-lookup.c Loading commit data...
sha1-lookup.h Loading commit data...
sha1-name.c Loading commit data...
sha1dc_git.c Loading commit data...
sha1dc_git.h Loading commit data...
shallow.c Loading commit data...
shell.c Loading commit data...
shortlog.h Loading commit data...
sideband.c Loading commit data...
sideband.h Loading commit data...
sigchain.c Loading commit data...
sigchain.h Loading commit data...
split-index.c Loading commit data...
split-index.h Loading commit data...
strbuf.c Loading commit data...
strbuf.h Loading commit data...
streaming.c Loading commit data...
streaming.h Loading commit data...
string-list.c Loading commit data...
string-list.h Loading commit data...
sub-process.c Loading commit data...
sub-process.h Loading commit data...
submodule-config.c Loading commit data...
submodule-config.h Loading commit data...
submodule.c Loading commit data...
submodule.h Loading commit data...
symlinks.c Loading commit data...
tag.c Loading commit data...
tag.h Loading commit data...
tar.h Loading commit data...
tempfile.c Loading commit data...
tempfile.h Loading commit data...
thread-utils.c Loading commit data...
thread-utils.h Loading commit data...
tmp-objdir.c Loading commit data...
tmp-objdir.h Loading commit data...
trace.c Loading commit data...
trace.h Loading commit data...
trailer.c Loading commit data...
trailer.h Loading commit data...
transport-helper.c Loading commit data...
transport-internal.h Loading commit data...
transport.c Loading commit data...
transport.h Loading commit data...
tree-diff.c Loading commit data...
tree-walk.c Loading commit data...
tree-walk.h Loading commit data...
tree.c Loading commit data...
tree.h Loading commit data...
unicode-width.h Loading commit data...
unimplemented.sh Loading commit data...
unix-socket.c Loading commit data...
unix-socket.h Loading commit data...
unpack-trees.c Loading commit data...
unpack-trees.h Loading commit data...
upload-pack.c Loading commit data...
upload-pack.h Loading commit data...
url.c Loading commit data...
url.h Loading commit data...
urlmatch.c Loading commit data...
urlmatch.h Loading commit data...
usage.c Loading commit data...
userdiff.c Loading commit data...
userdiff.h Loading commit data...
utf8.c Loading commit data...
utf8.h Loading commit data...
varint.c Loading commit data...
varint.h Loading commit data...
version.c Loading commit data...
version.h Loading commit data...
versioncmp.c Loading commit data...
walker.c Loading commit data...
walker.h Loading commit data...
wildmatch.c Loading commit data...
wildmatch.h Loading commit data...
worktree.c Loading commit data...
worktree.h Loading commit data...
wrap-for-bin.sh Loading commit data...
wrapper.c Loading commit data...
write-or-die.c Loading commit data...
ws.c Loading commit data...
wt-status.c Loading commit data...
wt-status.h Loading commit data...
xdiff-interface.c Loading commit data...
xdiff-interface.h Loading commit data...
zlib.c Loading commit data...