{"thread":{"id":"49155","subject":"[PATCH 0/6] reuse on-disk deltas for fetches with bitmaps","startedAt":"2018-08-17T20:54:31Z","lastAt":"2018-08-21T19:51:07Z","messageCount":17,"participants":["Jeff King","Stefan Beller","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":6},"messages":[{"id":"355942","messageId":"20180817205427.GA19580@sigill.intra.peff.net","threadId":"49155","inReplyTo":null,"subject":"[PATCH 0/6] reuse on-disk deltas for fetches with bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-17T20:54:27Z","receivedAt":"2018-08-17T20:54:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This series more aggressively reuses on-disk deltas to serve fetches\nwhen reachability bitmaps tell us a more complete picture of what the\nclient has. That saves server CPU and results in smaller packs. See the\nfinal patch for numbers and more discussion.\n\nIt's a resurrection of this very old series:\n\n  https://public-inbox.org/git/20140326072215.GA31739@sigill.intra.peff.net/\n\nThe core idea is good, but it got left as \"I should dig into this more\nto see if we can do even better\". In fact, I _did_ do some of that\ndigging, as you can see in the thread, so I'm mildly embarrassed not to\nhave reposted it before now.\n\nWe've been using that original at GitHub since 2014, which I think helps\ndemonstrate the correctness of the approach (and the numbers here and in\nthat thread show that performance is generally a net win over the status\nquo).\n\nI's rebased on top of the current master, since the original made some\nassumptions about struct object_entry that are no longer true post-v2.18\n(due to the struct-shrinking exercise). So I fixed that and a few other\nrough edges. But that also means you're not getting code with 4-years of\nproduction testing behind it. :)\n\nThe other really ugly thing in the original was the way it leaked\nobject_entry structs (though in practice that didn't really matter since\nwe needed them until the end of the program anyway). This version fixes\nthat.\n\n  [1/6]: t/perf: factor boilerplate out of test_perf\n  [2/6]: t/perf: factor out percent calculations\n  [3/6]: t/perf: add infrastructure for measuring sizes\n  [4/6]: t/perf: add perf tests for fetches from a bitmapped server\n  [5/6]: pack-bitmap: save \"have\" bitmap from walk\n  [6/6]: pack-objects: reuse on-disk deltas for thin \"have\" objects\n\n builtin/pack-objects.c             | 28 +++++++----\n pack-bitmap.c                      | 23 +++++++++-\n pack-bitmap.h                      |  7 +++\n pack-objects.c                     | 19 ++++++++\n pack-objects.h                     | 20 +++++++-\n t/perf/README                      | 25 ++++++++++\n t/perf/aggregate.perl              | 69 ++++++++++++++++++++++------\n t/perf/p5311-pack-bitmaps-fetch.sh | 45 ++++++++++++++++++\n t/perf/perf-lib.sh                 | 74 +++++++++++++++++++-----------\n 9 files changed, 258 insertions(+), 52 deletions(-)\n create mode 100755 t/perf/p5311-pack-bitmaps-fetch.sh\n\n-Peff\n"},{"id":"355943","messageId":"20180817205506.GA20088@sigill.intra.peff.net","threadId":"49155","inReplyTo":"20180817205427.GA19580@sigill.intra.peff.net","subject":"[PATCH 1/6] t/perf: factor boilerplate out of test_perf","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-17T20:55:06Z","receivedAt":"2018-08-17T20:55:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"About half of test_perf() is boilerplate preparing to run\n_any_ test, and the other half is specifically running a\ntiming test. Let's split it into two functions, so that we\ncan reuse the boilerplate in future commits.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nBest viewed with \"-w\".\n\n t/perf/perf-lib.sh | 61 ++++++++++++++++++++++++++--------------------\n 1 file changed, 35 insertions(+), 26 deletions(-)\n\ndiff --git a/t/perf/perf-lib.sh b/t/perf/perf-lib.sh\nindex e4c343a6b7..a54be09516 100644\n--- a/t/perf/perf-lib.sh\n+++ b/t/perf/perf-lib.sh\n@@ -179,8 +179,8 @@ exit $ret' >&3 2>&4\n \treturn \"$eval_ret\"\n }\n \n-\n-test_perf () {\n+test_wrapper_ () {\n+\ttest_wrapper_func_=$1; shift\n \ttest_start_\n \ttest \"$#\" = 3 && { test_prereq=$1; shift; } || test_prereq=\n \ttest \"$#\" = 2 ||\n@@ -191,35 +191,44 @@ test_perf () {\n \t\tbase=$(basename \"$0\" .sh)\n \t\techo \"$test_count\" >>\"$perf_results_dir\"/$base.subtests\n \t\techo \"$1\" >\"$perf_results_dir\"/$base.$test_count.descr\n-\t\tif test -z \"$verbose\"; then\n-\t\t\tprintf \"%s\" \"perf $test_count - $1:\"\n-\t\telse\n-\t\t\techo \"perf $test_count - $1:\"\n-\t\tfi\n-\t\tfor i in $(test_seq 1 $GIT_PERF_REPEAT_COUNT); do\n-\t\t\tsay >&3 \"running: $2\"\n-\t\t\tif test_run_perf_ \"$2\"\n-\t\t\tthen\n-\t\t\t\tif test -z \"$verbose\"; then\n-\t\t\t\t\tprintf \" %s\" \"$i\"\n-\t\t\t\telse\n-\t\t\t\t\techo \"* timing run $i/$GIT_PERF_REPEAT_COUNT:\"\n-\t\t\t\tfi\n+\t\tbase=\"$perf_results_dir\"/\"$perf_results_prefix$(basename \"$0\" .sh)\".\"$test_count\"\n+\t\t\"$test_wrapper_func_\" \"$@\"\n+\tfi\n+\n+\ttest_finish_\n+}\n+\n+test_perf_ () {\n+\tif test -z \"$verbose\"; then\n+\t\tprintf \"%s\" \"perf $test_count - $1:\"\n+\telse\n+\t\techo \"perf $test_count - $1:\"\n+\tfi\n+\tfor i in $(test_seq 1 $GIT_PERF_REPEAT_COUNT); do\n+\t\tsay >&3 \"running: $2\"\n+\t\tif test_run_perf_ \"$2\"\n+\t\tthen\n+\t\t\tif test -z \"$verbose\"; then\n+\t\t\t\tprintf \" %s\" \"$i\"\n \t\t\telse\n-\t\t\t\ttest -z \"$verbose\" && echo\n-\t\t\t\ttest_failure_ \"$@\"\n-\t\t\t\tbreak\n+\t\t\t\techo \"* timing run $i/$GIT_PERF_REPEAT_COUNT:\"\n \t\t\tfi\n-\t\tdone\n-\t\tif test -z \"$verbose\"; then\n-\t\t\techo \" ok\"\n \t\telse\n-\t\t\ttest_ok_ \"$1\"\n+\t\t\ttest -z \"$verbose\" && echo\n+\t\t\ttest_failure_ \"$@\"\n+\t\t\tbreak\n \t\tfi\n-\t\tbase=\"$perf_results_dir\"/\"$perf_results_prefix$(basename \"$0\" .sh)\".\"$test_count\"\n-\t\t\"$TEST_DIRECTORY\"/perf/min_time.perl test_time.* >\"$base\".times\n+\tdone\n+\tif test -z \"$verbose\"; then\n+\t\techo \" ok\"\n+\telse\n+\t\ttest_ok_ \"$1\"\n \tfi\n-\ttest_finish_\n+\t\"$TEST_DIRECTORY\"/perf/min_time.perl test_time.* >\"$base\".times\n+}\n+\n+test_perf () {\n+\ttest_wrapper_ test_perf_ \"$@\"\n }\n \n # We extend test_done to print timings at the end (./run disables this\n-- \n2.18.0.1205.g3878b1e64a\n\n"},{"id":"355944","messageId":"20180817205523.GB20088@sigill.intra.peff.net","threadId":"49155","inReplyTo":"20180817205427.GA19580@sigill.intra.peff.net","subject":"[PATCH 2/6] t/perf: factor out percent calculations","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-17T20:55:24Z","receivedAt":"2018-08-17T20:55:27Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This will let us reuse the code when we add new values to\naggregate besides times.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n t/perf/aggregate.perl | 21 ++++++++++++---------\n 1 file changed, 12 insertions(+), 9 deletions(-)\n\ndiff --git a/t/perf/aggregate.perl b/t/perf/aggregate.perl\nindex bc865160e7..3181b087ab 100755\n--- a/t/perf/aggregate.perl\n+++ b/t/perf/aggregate.perl\n@@ -19,21 +19,24 @@ sub get_times {\n \treturn ($rt, $4, $5);\n }\n \n+sub relative_change {\n+\tmy ($r, $firstr) = @_;\n+\tif ($firstr > 0) {\n+\t\treturn sprintf \"%+.1f%%\", 100.0*($r-$firstr)/$firstr;\n+\t} elsif ($r == 0) {\n+\t\treturn \"=\";\n+\t} else {\n+\t\treturn \"+inf\";\n+\t}\n+}\n+\n sub format_times {\n \tmy ($r, $u, $s, $firstr) = @_;\n \tif (!defined $r) {\n \t\treturn \"<missing>\";\n \t}\n \tmy $out = sprintf \"%.2f(%.2f+%.2f)\", $r, $u, $s;\n-\tif (defined $firstr) {\n-\t\tif ($firstr > 0) {\n-\t\t\t$out .= sprintf \" %+.1f%%\", 100.0*($r-$firstr)/$firstr;\n-\t\t} elsif ($r == 0) {\n-\t\t\t$out .= \" =\";\n-\t\t} else {\n-\t\t\t$out .= \" +inf\";\n-\t\t}\n-\t}\n+\t$out .= ' ' . relative_change($r, $firstr) if defined $firstr;\n \treturn $out;\n }\n \n-- \n2.18.0.1205.g3878b1e64a\n\n"},{"id":"355945","messageId":"20180817205637.GC20088@sigill.intra.peff.net","threadId":"49155","inReplyTo":"20180817205427.GA19580@sigill.intra.peff.net","subject":"[PATCH 3/6] t/perf: add infrastructure for measuring sizes","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-17T20:56:37Z","receivedAt":"2018-08-17T20:56:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The main objective of scripts in the perf framework is to\nrun \"test_perf\", which measures the time it takes to run\nsome operation. However, it can also be interesting to see\nthe change in the output size of certain operations.\n\nThis patch introduces test_size, which records a single\nnumeric output from the test and shows it in the aggregated\noutput (with pretty printing and relative size comparison).\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n t/perf/README         | 25 ++++++++++++++++++++++\n t/perf/aggregate.perl | 48 ++++++++++++++++++++++++++++++++++++++-----\n t/perf/perf-lib.sh    | 13 ++++++++++++\n 3 files changed, 81 insertions(+), 5 deletions(-)\n\ndiff --git a/t/perf/README b/t/perf/README\nindex 21321a0f36..be12090c38 100644\n--- a/t/perf/README\n+++ b/t/perf/README\n@@ -168,3 +168,28 @@ that\n   While we have tried to make sure that it can cope with embedded\n   whitespace and other special characters, it will not work with\n   multi-line data.\n+\n+Rather than tracking the performance by run-time as `test_perf` does, you\n+may also track output size by using `test_size`. The stdout of the\n+function should be a single numeric value, which will be captured and\n+shown in the aggregated output. For example:\n+\n+\ttest_perf 'time foo' '\n+\t\t./foo >foo.out\n+\t'\n+\n+\ttest_size 'output size'\n+\t\twc -c <foo.out\n+\t'\n+\n+might produce output like:\n+\n+\tTest                origin           HEAD\n+\t-------------------------------------------------------------\n+\t1234.1 time foo     0.37(0.79+0.02)  0.26(0.51+0.02) -29.7%\n+\t1234.2 output size             4.3M             3.6M -14.7%\n+\n+The item being measured (and its units) is up to the test; the context\n+and the test title should make it clear to the user whether bigger or\n+smaller numbers are better. Unlike test_perf, the test code will only be\n+run once, since output sizes tend to be more deterministic than timings.\ndiff --git a/t/perf/aggregate.perl b/t/perf/aggregate.perl\nindex 3181b087ab..494907a892 100755\n--- a/t/perf/aggregate.perl\n+++ b/t/perf/aggregate.perl\n@@ -13,10 +13,16 @@ sub get_times {\n \tmy $line = <$fh>;\n \treturn undef if not defined $line;\n \tclose $fh or die \"cannot close $name: $!\";\n-\t$line =~ /^(?:(\\d+):)?(\\d+):(\\d+(?:\\.\\d+)?) (\\d+(?:\\.\\d+)?) (\\d+(?:\\.\\d+)?)$/\n-\t\tor die \"bad input line: $line\";\n-\tmy $rt = ((defined $1 ? $1 : 0.0)*60+$2)*60+$3;\n-\treturn ($rt, $4, $5);\n+\t# times\n+\tif ($line =~ /^(?:(\\d+):)?(\\d+):(\\d+(?:\\.\\d+)?) (\\d+(?:\\.\\d+)?) (\\d+(?:\\.\\d+)?)$/) {\n+\t\tmy $rt = ((defined $1 ? $1 : 0.0)*60+$2)*60+$3;\n+\t\treturn ($rt, $4, $5);\n+\t# size\n+\t} elsif ($line =~ /^\\d+$/) {\n+\t\treturn $&;\n+\t} else {\n+\t\tdie \"bad input line: $line\";\n+\t}\n }\n \n sub relative_change {\n@@ -32,9 +38,15 @@ sub relative_change {\n \n sub format_times {\n \tmy ($r, $u, $s, $firstr) = @_;\n+\t# no value means we did not finish the test\n \tif (!defined $r) {\n \t\treturn \"<missing>\";\n \t}\n+\t# a single value means we have a size, not times\n+\tif (!defined $u) {\n+\t\treturn format_size($r, $firstr);\n+\t}\n+\t# otherwise, we have real/user/system times\n \tmy $out = sprintf \"%.2f(%.2f+%.2f)\", $r, $u, $s;\n \t$out .= ' ' . relative_change($r, $firstr) if defined $firstr;\n \treturn $out;\n@@ -54,6 +66,25 @@ sub usage {\n \texit(1);\n }\n \n+sub human_size {\n+\tmy $n = shift;\n+\tmy @units = ('', qw(K M G));\n+\twhile ($n > 900 && @units > 1) {\n+\t\t$n /= 1000;\n+\t\tshift @units;\n+\t}\n+\treturn $n unless length $units[0];\n+\treturn sprintf '%.1f%s', $n, $units[0];\n+}\n+\n+sub format_size {\n+\tmy ($size, $first) = @_;\n+\t# match the width of a time: 0.00(0.00+0.00)\n+\tmy $out = sprintf '%15s', human_size($size);\n+\t$out .= ' ' . relative_change($size, $first) if defined $first;\n+\treturn $out;\n+}\n+\n my (@dirs, %dirnames, %dirabbrevs, %prefixes, @tests,\n     $codespeed, $sortby, $subsection, $reponame);\n \n@@ -184,7 +215,14 @@ sub print_default_results {\n \t\tmy $firstr;\n \t\tfor my $i (0..$#dirs) {\n \t\t\tmy $d = $dirs[$i];\n-\t\t\t$times{$prefixes{$d}.$t} = [get_times(\"$resultsdir/$prefixes{$d}$t.times\")];\n+\t\t\tmy $base = \"$resultsdir/$prefixes{$d}$t\";\n+\t\t\t$times{$prefixes{$d}.$t} = [];\n+\t\t\tforeach my $type (qw(times size)) {\n+\t\t\t\tif (-e \"$base.$type\") {\n+\t\t\t\t\t$times{$prefixes{$d}.$t} = [get_times(\"$base.$type\")];\n+\t\t\t\t\tlast;\n+\t\t\t\t}\n+\t\t\t}\n \t\t\tmy ($r,$u,$s) = @{$times{$prefixes{$d}.$t}};\n \t\t\tmy $w = length format_times($r,$u,$s,$firstr);\n \t\t\t$colwidth[$i] = $w if $w > $colwidth[$i];\ndiff --git a/t/perf/perf-lib.sh b/t/perf/perf-lib.sh\nindex a54be09516..11d1922cf5 100644\n--- a/t/perf/perf-lib.sh\n+++ b/t/perf/perf-lib.sh\n@@ -231,6 +231,19 @@ test_perf () {\n \ttest_wrapper_ test_perf_ \"$@\"\n }\n \n+test_size_ () {\n+\tsay >&3 \"running: $2\"\n+\tif test_eval_ \"$2\" 3>\"$base\".size; then\n+\t\ttest_ok_ \"$1\"\n+\telse\n+\t\ttest_failure_ \"$@\"\n+\tfi\n+}\n+\n+test_size () {\n+\ttest_wrapper_ test_size_ \"$@\"\n+}\n+\n # We extend test_done to print timings at the end (./run disables this\n # and does it after running everything)\n test_at_end_hook_ () {\n-- \n2.18.0.1205.g3878b1e64a\n\n"},{"id":"355946","messageId":"20180817205741.GD20088@sigill.intra.peff.net","threadId":"49155","inReplyTo":"20180817205427.GA19580@sigill.intra.peff.net","subject":"[PATCH 4/6] t/perf: add perf tests for fetches from a bitmapped server","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-17T20:57:41Z","receivedAt":"2018-08-17T20:57:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"A server with bitmapped packs can serve a clone very\nquickly. However, fetches are not necessarily made any\nfaster, because we spend a lot less time in object traversal\n(which is what bitmaps help with) and more time finding\ndeltas (because we may have to throw out on-disk deltas if\nthe client does not have the base).\n\nAs a first step to making this faster, this patch introduces\na new perf script to measure fetches into a repo of various\nages from a fully-bitmapped server.\n\nWe separately measure the work done by the server (in\npack-objects) and that done by the client (in index-pack).\nFurthermore, we measure the size of the resulting pack.\n\nBreaking it down like this (instead of just doing a regular\n\"git fetch\") lets us see how much each side benefits from\nany changes. And since we know the pack size, if we estimate\nthe network speed, then one could calculate a complete\nwall-clock time for the operation (though the script does\nnot do this automatically).\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n t/perf/p5311-pack-bitmaps-fetch.sh | 45 ++++++++++++++++++++++++++++++\n 1 file changed, 45 insertions(+)\n create mode 100755 t/perf/p5311-pack-bitmaps-fetch.sh\n\ndiff --git a/t/perf/p5311-pack-bitmaps-fetch.sh b/t/perf/p5311-pack-bitmaps-fetch.sh\nnew file mode 100755\nindex 0000000000..b04575951f\n--- /dev/null\n+++ b/t/perf/p5311-pack-bitmaps-fetch.sh\n@@ -0,0 +1,45 @@\n+#!/bin/sh\n+\n+test_description='performance of fetches from bitmapped packs'\n+. ./perf-lib.sh\n+\n+test_perf_default_repo\n+\n+test_expect_success 'create bitmapped server repo' '\n+\tgit config pack.writebitmaps true &&\n+\tgit config pack.writebitmaphashcache true &&\n+\tgit repack -ad\n+'\n+\n+# simulate a fetch from a repository that last fetched N days ago, for\n+# various values of N. We do so by following the first-parent chain,\n+# and assume the first entry in the chain that is N days older than the current\n+# HEAD is where the HEAD would have been then.\n+for days in 1 2 4 8 16 32 64 128; do\n+\ttitle=$(printf '%10s' \"($days days)\")\n+\ttest_expect_success \"setup revs from $days days ago\" '\n+\t\tnow=$(git log -1 --format=%ct HEAD) &&\n+\t\tthen=$(($now - ($days * 86400))) &&\n+\t\ttip=$(git rev-list -1 --first-parent --until=$then HEAD) &&\n+\t\t{\n+\t\t\techo HEAD &&\n+\t\t\techo ^$tip\n+\t\t} >revs\n+\t'\n+\n+\ttest_perf \"server $title\" '\n+\t\tgit pack-objects --stdout --revs \\\n+\t\t\t\t --thin --delta-base-offset \\\n+\t\t\t\t <revs >tmp.pack\n+\t'\n+\n+\ttest_size \"size   $title\" '\n+\t\twc -c <tmp.pack\n+\t'\n+\n+\ttest_perf \"client $title\" '\n+\t\tgit index-pack --stdin --fix-thin <tmp.pack\n+\t'\n+done\n+\n+test_done\n-- \n2.18.0.1205.g3878b1e64a\n\n"},{"id":"355947","messageId":"20180817205920.GE20088@sigill.intra.peff.net","threadId":"49155","inReplyTo":"20180817205427.GA19580@sigill.intra.peff.net","subject":"[PATCH 5/6] pack-bitmap: save \"have\" bitmap from walk","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-17T20:59:21Z","receivedAt":"2018-08-17T20:59:24Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When we do a bitmap walk, we save the result, which\nrepresents (WANTs & ~HAVEs); i.e., every object we care\nabout visiting in our walk. However, we throw away the\nhaves bitmap, which can sometimes be useful, too. Save it\nand provide an access function so code which has performed a\nwalk can query it.\n\nA few notes on the accessor interface:\n\n - the bitmap code calls these \"haves\" because it grew out\n   of the want/have negotiation for fetches. But really,\n   these are simply the objects that would be flagged\n   UNINTERESTING in a regular traversal. Let's use that\n   more universal nomenclature for the external module\n   interface. We may want to change the internal naming\n   inside the bitmap code, but that's outside the scope of\n   this patch.\n\n - it still uses a bare \"sha1\" rather than \"oid\". That's\n   true of all of the bitmap code. And in this particular\n   instance, our caller in pack-objects is dealing with the\n   bare sha1 that comes from a packed REF_DELTA (we're\n   pointing directly to the mmap'd pack on disk). That's\n   something we'll have to deal with as we transition to a\n   new hash, but we can wait and see how the caller ends up\n   being fixed and adjust this interface accordingly.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nFunny story: the earlier version of this series called it bitmap_have().\nThat caused a bug later when somebody tried to build on it, thinking it\nwas \"does the bitmap have this object in the result\". Oops. Hence the\nmore descriptive name.\n\n pack-bitmap.c | 23 ++++++++++++++++++++++-\n pack-bitmap.h |  7 +++++++\n 2 files changed, 29 insertions(+), 1 deletion(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex f0a1937a1c..76fd93a3de 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -86,6 +86,9 @@ struct bitmap_index {\n \t/* Bitmap result of the last performed walk */\n \tstruct bitmap *result;\n \n+\t/* \"have\" bitmap from the last performed walk */\n+\tstruct bitmap *haves;\n+\n \t/* Version of the bitmap index */\n \tunsigned int version;\n \n@@ -759,8 +762,8 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n \t\tbitmap_and_not(wants_bitmap, haves_bitmap);\n \n \tbitmap_git->result = wants_bitmap;\n+\tbitmap_git->haves = haves_bitmap;\n \n-\tbitmap_free(haves_bitmap);\n \treturn bitmap_git;\n \n cleanup:\n@@ -1114,5 +1117,23 @@ void free_bitmap_index(struct bitmap_index *b)\n \tfree(b->ext_index.objects);\n \tfree(b->ext_index.hashes);\n \tbitmap_free(b->result);\n+\tbitmap_free(b->haves);\n \tfree(b);\n }\n+\n+int bitmap_has_sha1_in_uninteresting(struct bitmap_index *bitmap_git,\n+\t\t\t\t     const unsigned char *sha1)\n+{\n+\tint pos;\n+\n+\tif (!bitmap_git)\n+\t\treturn 0; /* no bitmap loaded */\n+\tif (!bitmap_git->haves)\n+\t\treturn 0; /* walk had no \"haves\" */\n+\n+\tpos = bitmap_position_packfile(bitmap_git, sha1);\n+\tif (pos < 0)\n+\t\treturn 0;\n+\n+\treturn bitmap_get(bitmap_git->haves, pos);\n+}\ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex 4555907dee..02a60ce670 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -50,6 +50,13 @@ int rebuild_existing_bitmaps(struct bitmap_index *, struct packing_data *mapping\n \t\t\t     khash_sha1 *reused_bitmaps, int show_progress);\n void free_bitmap_index(struct bitmap_index *);\n \n+/*\n+ * After a traversal has been performed on the bitmap_index, this can be\n+ * queried to see if a particular object was reachable from any of the\n+ * objects flagged as UNINTERESTING.\n+ */\n+int bitmap_has_sha1_in_uninteresting(struct bitmap_index *, const unsigned char *sha1);\n+\n void bitmap_writer_show_progress(int show);\n void bitmap_writer_set_checksum(unsigned char *sha1);\n void bitmap_writer_build_type_index(struct packing_data *to_pack,\n-- \n2.18.0.1205.g3878b1e64a\n\n"},{"id":"355948","messageId":"20180817210604.GF20088@sigill.intra.peff.net","threadId":"49155","inReplyTo":"20180817205427.GA19580@sigill.intra.peff.net","subject":"[PATCH 6/6] pack-objects: reuse on-disk deltas for thin \"have\" objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-17T21:06:04Z","receivedAt":"2018-08-17T21:06:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When we serve a fetch, we pass the \"wants\" and \"haves\" from\nthe fetch negotiation to pack-objects. That tells us not\nonly which objects we need to send, but we also use the\nboundary commits as \"preferred bases\": their trees and blobs\nare candidates for delta bases, both for reusing on-disk\ndeltas and for finding new ones.\n\nHowever, this misses some opportunities. Modulo some special\ncases like shallow or partial clones, we know that every\nobject reachable from the \"haves\" could be a preferred base.\nWe don't use them all for two reasons:\n\n  1. It's expensive to traverse the whole history and\n     enumerate all of the objects the other side has.\n\n  2. The delta search is expensive, so we want to keep the\n     number of candidate bases sane. The boundary commits\n     are the most likely to work.\n\nWhen we have reachability bitmaps, though, reason 1 no\nlonger applies. We can efficiently compute the set of\nreachable objects on the other side (and in fact already did\nso as part of the bitmap set-difference to get the list of\ninteresting objects). And using this set conveniently\ncovers the shallow and partial cases, since we have to\ndisable the use of bitmaps for those anyway.\n\nThe second reason argues against using these bases in the\nsearch for new deltas. But there's one case where we can use\nthis information for free: when we have an existing on-disk\ndelta that we're considering reusing, we can do so if we\nknow the other side has the base object. This in fact saves\ntime during the delta search, because it's one less delta we\nhave to compute.\n\nAnd that's exactly what this patch does: when we're\nconsidering whether to reuse an on-disk delta, if bitmaps\ntell us the other side has the object (and we're making a\nthin-pack), then we reuse it.\n\nHere are the results on p5311 using linux.git, which\nsimulates a client fetching after `N` days since their last\nfetch:\n\nTest                         origin              HEAD\n--------------------------------------------------------------------------\n5311.3: server   (1 days)    0.27(0.27+0.04)     0.12(0.09+0.03) -55.6%\n5311.4: size     (1 days)               0.9M              237.0K -73.7%\n5311.5: client   (1 days)    0.04(0.05+0.00)     0.10(0.10+0.00) +150.0%\n5311.7: server   (2 days)    0.34(0.42+0.04)     0.13(0.10+0.03) -61.8%\n5311.8: size     (2 days)               1.5M              347.7K -76.5%\n5311.9: client   (2 days)    0.07(0.08+0.00)     0.16(0.15+0.01) +128.6%\n5311.11: server   (4 days)   0.56(0.77+0.08)     0.13(0.10+0.02) -76.8%\n5311.12: size     (4 days)              2.8M              566.6K -79.8%\n5311.13: client   (4 days)   0.13(0.15+0.00)     0.34(0.31+0.02) +161.5%\n5311.15: server   (8 days)   0.97(1.39+0.11)     0.30(0.25+0.05) -69.1%\n5311.16: size     (8 days)              4.3M                1.0M -76.0%\n5311.17: client   (8 days)   0.20(0.22+0.01)     0.53(0.52+0.01) +165.0%\n5311.19: server  (16 days)   1.52(2.51+0.12)     0.30(0.26+0.03) -80.3%\n5311.20: size    (16 days)              8.0M                2.0M -74.5%\n5311.21: client  (16 days)   0.40(0.47+0.03)     1.01(0.98+0.04) +152.5%\n5311.23: server  (32 days)   2.40(4.44+0.20)     0.31(0.26+0.04) -87.1%\n5311.24: size    (32 days)             14.1M                4.1M -70.9%\n5311.25: client  (32 days)   0.70(0.90+0.03)     1.81(1.75+0.06) +158.6%\n5311.27: server  (64 days)   11.76(26.57+0.29)   0.55(0.50+0.08) -95.3%\n5311.28: size    (64 days)             89.4M               47.4M -47.0%\n5311.29: client  (64 days)   5.71(9.31+0.27)     15.20(15.20+0.32) +166.2%\n5311.31: server (128 days)   16.15(36.87+0.40)   0.91(0.82+0.14) -94.4%\n5311.32: size   (128 days)            134.8M              100.4M -25.5%\n5311.33: client (128 days)   9.42(16.86+0.49)    25.34(25.80+0.46) +169.0%\n\nIn all cases we save CPU time on the server (sometimes\nsignificant) and the resulting pack is smaller. We do spend\nmore CPU time on the client side, because it has to\nreconstruct more deltas. But that's the right tradeoff to\nmake, since clients tend to outnumber servers. It just means\nthe thin pack mechanism is doing its job.\n\nFrom the user's perspective, the end-to-end time of the\noperation will generally be faster. E.g., in the 128-day\ncase, we saved 15s on the server at a cost of 16s on the\nclient. Since the resulting pack is 34MB smaller, this is a\nnet win if the network speed is less than 270Mbit/s. And\nthat's actually the worst case. The 64-day case saves just\nover 11s at a cost of just under 11s. So it's a slight win\nat any network speed, and the 40MB saved is pure bonus. That\ntrend continues for the smaller fetches.\n\nThe implementation itself is mostly straightforward, with\nthe new logic going into check_object(). But there are two\ntricky bits.\n\nThe first is that check_object() needs access to the\nrelevant information (the thin flag and bitmap result). We\ncan do this by pushing these into program-lifetime globals.\n\nThe second is that the rest of the code assumes that any\nreused delta will point to another \"struct object_entry\" as\nits base. But by definition, we don't have such an entry!\n\nI looked at a number of options that didn't quite work:\n\n - we could use a different flag for reused deltas. But it's\n   not a single bit for \"I'm being reused\". We have to\n   actually store the oid of the base, which is normally\n   done by pointing to the existing object_entry. And we'd\n   have to modify all the code which looks at deltas.\n\n - we could add the reused bases to the end of the existing\n   object_entry array. While this does create some extra\n   work as later stages consider the extra entries, it's\n   actually not too bad (we're not sending them, so they\n   don't cost much in the delta search, and at most we'd\n   have 2*N of them).\n\n   But there's a more subtle problem. Adding to the existing\n   array means we might need to grow it with realloc, which\n   could move the earlier entries around. While many of the\n   references to other entries are done by integer index,\n   some (including ones on the stack) use pointers, which\n   would become invalidated.\n\n   This isn't insurmountable, but it would require quite a\n   bit of refactoring (and it's hard to know that you've got\n   it all, since it may work _most_ of the time and then\n   fail subtly based on memory allocation patterns).\n\n - we could allocate a new one-off entry for the base. In\n   fact, this is what an earlier version of this patch did.\n   However, since the refactoring brought in by ad635e82d6\n   (Merge branch 'nd/pack-objects-pack-struct', 2018-05-23),\n   the delta_idx code requires that both entries be in the\n   main packing list.\n\nSo taking all of those options into account, what I ended up\nwith is a separate list of \"external bases\" that are not\npart of the main packing list. Each delta entry that points\nto an external base has a single-bit flag to do so; we have a\nlittle breathing room in the bitfield section of\nobject_entry.\n\nThis lets us limit the change primarily to the oe_delta()\nand oe_set_delta_ext() functions. And as a bonus, most of\nthe rest of the code does not consider these dummy entries\nat all, saving both runtime CPU and code complexity.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n builtin/pack-objects.c | 28 +++++++++++++++++++---------\n pack-objects.c         | 19 +++++++++++++++++++\n pack-objects.h         | 20 ++++++++++++++++++--\n 3 files changed, 56 insertions(+), 11 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 80c880e9ad..6340cad944 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -40,6 +40,7 @@\n #define DELTA_CHILD(obj) oe_delta_child(&to_pack, obj)\n #define DELTA_SIBLING(obj) oe_delta_sibling(&to_pack, obj)\n #define SET_DELTA(obj, val) oe_set_delta(&to_pack, obj, val)\n+#define SET_DELTA_EXT(obj, oid) oe_set_delta_ext(&to_pack, obj, oid)\n #define SET_DELTA_SIZE(obj, val) oe_set_delta_size(&to_pack, obj, val)\n #define SET_DELTA_CHILD(obj, val) oe_set_delta_child(&to_pack, obj, val)\n #define SET_DELTA_SIBLING(obj, val) oe_set_delta_sibling(&to_pack, obj, val)\n@@ -59,6 +60,7 @@ static struct packing_data to_pack;\n \n static struct pack_idx_entry **written_list;\n static uint32_t nr_result, nr_written, nr_seen;\n+static struct bitmap_index *bitmap_git;\n \n static int non_empty;\n static int reuse_delta = 1, reuse_object = 1;\n@@ -79,6 +81,7 @@ static unsigned long pack_size_limit;\n static int depth = 50;\n static int delta_search_threads;\n static int pack_to_stdout;\n+static int thin = 0;\n static int num_preferred_base;\n static struct progress *progress_state;\n \n@@ -1510,11 +1513,15 @@ static void check_object(struct object_entry *entry)\n \t\t\tbreak;\n \t\t}\n \n-\t\tif (base_ref && (base_entry = packlist_find(&to_pack, base_ref, NULL))) {\n+\t\tif (base_ref && (\n+\t\t    (base_entry = packlist_find(&to_pack, base_ref, NULL)) ||\n+\t\t    (thin &&\n+\t\t     bitmap_has_sha1_in_uninteresting(bitmap_git, base_ref)))) {\n \t\t\t/*\n \t\t\t * If base_ref was set above that means we wish to\n-\t\t\t * reuse delta data, and we even found that base\n-\t\t\t * in the list of objects we want to pack. Goodie!\n+\t\t\t * reuse delta data, and either we found that object in\n+\t\t\t * the list of objects we want to pack, or it's one we\n+\t\t\t * know the receiver has.\n \t\t\t *\n \t\t\t * Depth value does not matter - find_deltas() will\n \t\t\t * never consider reused delta as the base object to\n@@ -1523,10 +1530,16 @@ static void check_object(struct object_entry *entry)\n \t\t\t */\n \t\t\toe_set_type(entry, entry->in_pack_type);\n \t\t\tSET_SIZE(entry, in_pack_size); /* delta size */\n-\t\t\tSET_DELTA(entry, base_entry);\n \t\t\tSET_DELTA_SIZE(entry, in_pack_size);\n-\t\t\tentry->delta_sibling_idx = base_entry->delta_child_idx;\n-\t\t\tSET_DELTA_CHILD(base_entry, entry);\n+\n+\t\t\tif (base_entry) {\n+\t\t\t\tSET_DELTA(entry, base_entry);\n+\t\t\t\tentry->delta_sibling_idx = base_entry->delta_child_idx;\n+\t\t\t\tSET_DELTA_CHILD(base_entry, entry);\n+\t\t\t} else {\n+\t\t\t\tSET_DELTA_EXT(entry, base_ref);\n+\t\t\t}\n+\n \t\t\tunuse_pack(&w_curs);\n \t\t\treturn;\n \t\t}\n@@ -2954,7 +2967,6 @@ static int pack_options_allow_reuse(void)\n \n static int get_object_list_from_bitmap(struct rev_info *revs)\n {\n-\tstruct bitmap_index *bitmap_git;\n \tif (!(bitmap_git = prepare_bitmap_walk(revs)))\n \t\treturn -1;\n \n@@ -2970,7 +2982,6 @@ static int get_object_list_from_bitmap(struct rev_info *revs)\n \t}\n \n \ttraverse_bitmap_commit_list(bitmap_git, &add_object_entry_from_bitmap);\n-\tfree_bitmap_index(bitmap_git);\n \treturn 0;\n }\n \n@@ -3118,7 +3129,6 @@ static int option_parse_unpack_unreachable(const struct option *opt,\n int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n {\n \tint use_internal_rev_list = 0;\n-\tint thin = 0;\n \tint shallow = 0;\n \tint all_progress_implied = 0;\n \tstruct argv_array rp = ARGV_ARRAY_INIT;\ndiff --git a/pack-objects.c b/pack-objects.c\nindex 92708522e7..9ae0cecd81 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -177,3 +177,22 @@ struct object_entry *packlist_alloc(struct packing_data *pdata,\n \n \treturn new_entry;\n }\n+\n+void oe_set_delta_ext(struct packing_data *pdata,\n+\t\t      struct object_entry *delta,\n+\t\t      const unsigned char *sha1)\n+{\n+\tstruct object_entry *base;\n+\n+\tALLOC_GROW(pdata->ext_bases, pdata->nr_ext + 1, pdata->alloc_ext);\n+\tbase = &pdata->ext_bases[pdata->nr_ext++];\n+\tmemset(base, 0, sizeof(*base));\n+\thashcpy(base->idx.oid.hash, sha1);\n+\n+\t/* These flags mark that we are not part of the actual pack output. */\n+\tbase->preferred_base = 1;\n+\tbase->filled = 1;\n+\n+\tdelta->ext_base = 1;\n+\tdelta->delta_idx = base - pdata->ext_bases + 1;\n+}\ndiff --git a/pack-objects.h b/pack-objects.h\nindex edf74dabdd..a9c7f1d0ab 100644\n--- a/pack-objects.h\n+++ b/pack-objects.h\n@@ -110,6 +110,7 @@ struct object_entry {\n \tunsigned dfs_state:OE_DFS_STATE_BITS;\n \tunsigned char in_pack_header_size;\n \tunsigned depth:OE_DEPTH_BITS;\n+\tunsigned ext_base:1; /* delta_idx points outside packlist */\n \n \t/*\n \t * pahole results on 64-bit linux (gcc and clang)\n@@ -140,6 +141,14 @@ struct packing_data {\n \tstruct packed_git **in_pack_by_idx;\n \tstruct packed_git **in_pack;\n \n+\t/*\n+\t * This list contains entries for bases which we know the other side\n+\t * has (e.g., via reachability bitmaps), but which aren't in our\n+\t * \"objects\" list.\n+\t */\n+\tstruct object_entry *ext_bases;\n+\tuint32_t nr_ext, alloc_ext;\n+\n \tuintmax_t oe_size_limit;\n };\n \n@@ -227,9 +236,12 @@ static inline struct object_entry *oe_delta(\n \t\tconst struct packing_data *pack,\n \t\tconst struct object_entry *e)\n {\n-\tif (e->delta_idx)\n+\tif (!e->delta_idx)\n+\t\treturn NULL;\n+\tif (e->ext_base)\n+\t\treturn &pack->ext_bases[e->delta_idx - 1];\n+\telse\n \t\treturn &pack->objects[e->delta_idx - 1];\n-\treturn NULL;\n }\n \n static inline void oe_set_delta(struct packing_data *pack,\n@@ -242,6 +254,10 @@ static inline void oe_set_delta(struct packing_data *pack,\n \t\te->delta_idx = 0;\n }\n \n+void oe_set_delta_ext(struct packing_data *pack,\n+\t\t      struct object_entry *e,\n+\t\t      const unsigned char *sha1);\n+\n static inline struct object_entry *oe_delta_child(\n \t\tconst struct packing_data *pack,\n \t\tconst struct object_entry *e)\n-- \n2.18.0.1205.g3878b1e64a\n"},{"id":"355955","messageId":"CAGZ79kaP3GPZi_5vSCspgbim5VwsTMRa-fLYbjgECqsx9BTaeg@mail.gmail.com","threadId":"49155","inReplyTo":"20180817205920.GE20088@sigill.intra.peff.net","subject":"Re: [PATCH 5/6] pack-bitmap: save \"have\" bitmap from walk","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-08-17T22:39:29Z","receivedAt":"2018-08-17T22:39:43Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"> diff --git a/pack-bitmap.h b/pack-bitmap.h\n> index 4555907dee..02a60ce670 100644\n> --- a/pack-bitmap.h\n> +++ b/pack-bitmap.h\n> @@ -50,6 +50,13 @@ int rebuild_existing_bitmaps(struct bitmap_index *, struct packing_data *mapping\n>                              khash_sha1 *reused_bitmaps, int show_progress);\n>  void free_bitmap_index(struct bitmap_index *);\n>\n> +/*\n> + * After a traversal has been performed on the bitmap_index, this can be\n> + * queried to see if a particular object was reachable from any of the\n> + * objects flagged as UNINTERESTING.\n\nIf the traversal has not been performed, we pretend the\nobject was not reachable?\n\nIs this a good API design, as it can be used when you do not\nhave done all preparations? similarly to prepare_bitmap_walk\nwe could have\n\n    if (!bitmap_git->result)\n        BUG(\"failed to perform bitmap walk before querying\");\n\n> +int bitmap_has_sha1_in_uninteresting(struct bitmap_index *, const unsigned char *sha1);\n\nYou seem to have rebased it to master resolving conflicts only. ;-)\nDo we want to talk about object ids here instead?\n\n(This is what I get to think about when reviewing this series\n\"bottom up\". I use \"git log -w -p master..HEAD\" after applying\nthe patches, probably I should also use --reverse, such that I\nget to see the commit message before the code for each commit\nand yet only need to scroll in one direction.)\n"},{"id":"355957","messageId":"20180817224539.GA4158@sigill.intra.peff.net","threadId":"49155","inReplyTo":"CAGZ79kaP3GPZi_5vSCspgbim5VwsTMRa-fLYbjgECqsx9BTaeg@mail.gmail.com","subject":"Re: [PATCH 5/6] pack-bitmap: save \"have\" bitmap from walk","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-17T22:45:39Z","receivedAt":"2018-08-17T22:45:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 17, 2018 at 03:39:29PM -0700, Stefan Beller wrote:\n\n> > diff --git a/pack-bitmap.h b/pack-bitmap.h\n> > index 4555907dee..02a60ce670 100644\n> > --- a/pack-bitmap.h\n> > +++ b/pack-bitmap.h\n> > @@ -50,6 +50,13 @@ int rebuild_existing_bitmaps(struct bitmap_index *, struct packing_data *mapping\n> >                              khash_sha1 *reused_bitmaps, int show_progress);\n> >  void free_bitmap_index(struct bitmap_index *);\n> >\n> > +/*\n> > + * After a traversal has been performed on the bitmap_index, this can be\n> > + * queried to see if a particular object was reachable from any of the\n> > + * objects flagged as UNINTERESTING.\n> \n> If the traversal has not been performed, we pretend the\n> object was not reachable?\n\nIf the traversal hasn't been performed, the results are not defined\n(though I suspect yeah, it happens to say \"no\").\n\n> Is this a good API design, as it can be used when you do not\n> have done all preparations? similarly to prepare_bitmap_walk\n> we could have\n> \n>     if (!bitmap_git->result)\n>         BUG(\"failed to perform bitmap walk before querying\");\n\nThat seems like a reasonable precaution.\n\n> > +int bitmap_has_sha1_in_uninteresting(struct bitmap_index *, const unsigned char *sha1);\n> \n> You seem to have rebased it to master resolving conflicts only. ;-)\n> Do we want to talk about object ids here instead?\n\nSee the discussion in the commit message.\n\n-Peff\n"},{"id":"355958","messageId":"CAGZ79kY9o_38WRX2TXC1JMA+9Y_ihf_jK8-f2pcYA+cYPF6B4A@mail.gmail.com","threadId":"49155","inReplyTo":"20180817210604.GF20088@sigill.intra.peff.net","subject":"Re: [PATCH 6/6] pack-objects: reuse on-disk deltas for thin \"have\" objects","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-08-17T22:57:18Z","receivedAt":"2018-08-17T22:59:54Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Fri, Aug 17, 2018 at 2:06 PM Jeff King <peff@peff.net> wrote:\n>\n> When we serve a fetch, we pass the \"wants\" and \"haves\" from\n> the fetch negotiation to pack-objects. That tells us not\n> only which objects we need to send, but we also use the\n> boundary commits as \"preferred bases\": their trees and blobs\n> are candidates for delta bases, both for reusing on-disk\n> deltas and for finding new ones.\n>\n> However, this misses some opportunities. Modulo some special\n> cases like shallow or partial clones, we know that every\n> object reachable from the \"haves\" could be a preferred base.\n> We don't use them all for two reasons:\n\ns/all/at all/ ?\n\n> The first is that check_object() needs access to the\n> relevant information (the thin flag and bitmap result). We\n> can do this by pushing these into program-lifetime globals.\n\nI discussed internally if extending the fetch protocol to include\nsubmodule packs would be a good idea, as then you can get all\nthe superproject+submodule updates via one connection. This\ngives some benefits, such as a more consistent view from the\nsuperproject as well as already knowing the have/wants for\nthe submodule.\n\nWith this background story, moving things into globals\nmakes me sad, but I guess we can flip this decision once\nwe actually move towards \"submodule packs in the\nmain connection\".\n\n>\n> The second is that the rest of the code assumes that any\n> reused delta will point to another \"struct object_entry\" as\n> its base. But by definition, we don't have such an entry!\n\nI got lost here by the definition (which def?).\n\n  The delta that we look up from the bitmap, doesn't may\n  not be in the pack, but it could be based off of an object\n  the client already has in its object store and for that\n  there is no struct object_entry in memory.\n\nIs that correct?\n\n> So taking all of those options into account, what I ended up\n> with is a separate list of \"external bases\" that are not\n> part of the main packing list. Each delta entry that points\n> to an external base has a single-bit flag to do so; we have a\n> little breathing room in the bitfield section of\n> object_entry.\n>\n> This lets us limit the change primarily to the oe_delta()\n> and oe_set_delta_ext() functions. And as a bonus, most of\n> the rest of the code does not consider these dummy entries\n> at all, saving both runtime CPU and code complexity.\n\nThanks,\nStefan\n"},{"id":"355960","messageId":"20180817233234.GA4472@sigill.intra.peff.net","threadId":"49155","inReplyTo":"CAGZ79kY9o_38WRX2TXC1JMA+9Y_ihf_jK8-f2pcYA+cYPF6B4A@mail.gmail.com","subject":"Re: [PATCH 6/6] pack-objects: reuse on-disk deltas for thin \"have\" objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-17T23:32:34Z","receivedAt":"2018-08-17T23:32:37Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 17, 2018 at 03:57:18PM -0700, Stefan Beller wrote:\n\n> On Fri, Aug 17, 2018 at 2:06 PM Jeff King <peff@peff.net> wrote:\n> >\n> > When we serve a fetch, we pass the \"wants\" and \"haves\" from\n> > the fetch negotiation to pack-objects. That tells us not\n> > only which objects we need to send, but we also use the\n> > boundary commits as \"preferred bases\": their trees and blobs\n> > are candidates for delta bases, both for reusing on-disk\n> > deltas and for finding new ones.\n> >\n> > However, this misses some opportunities. Modulo some special\n> > cases like shallow or partial clones, we know that every\n> > object reachable from the \"haves\" could be a preferred base.\n> > We don't use them all for two reasons:\n> \n> s/all/at all/ ?\n\nNo, I meant \"we don't use all of them\". As in the Pokemon \"gotta catch\n'em all\" slogan. ;)\n\nProbably writing out \"all of them\" is better.\n\n> > The first is that check_object() needs access to the\n> > relevant information (the thin flag and bitmap result). We\n> > can do this by pushing these into program-lifetime globals.\n> \n> I discussed internally if extending the fetch protocol to include\n> submodule packs would be a good idea, as then you can get all\n> the superproject+submodule updates via one connection. This\n> gives some benefits, such as a more consistent view from the\n> superproject as well as already knowing the have/wants for\n> the submodule.\n> \n> With this background story, moving things into globals\n> makes me sad, but I guess we can flip this decision once\n> we actually move towards \"submodule packs in the\n> main connection\".\n\nI don't think it significantly changes the existing code, which is\nalready relying on a ton of globals (most notably to_pack). The first\nstep in doing multiple packs in the same process is going to be to shove\nall of that into a \"struct pack_objects_context\" or similar, and these\ncan just follow the rest.\n\n> >\n> > The second is that the rest of the code assumes that any\n> > reused delta will point to another \"struct object_entry\" as\n> > its base. But by definition, we don't have such an entry!\n> \n> I got lost here by the definition (which def?).\n> \n>   The delta that we look up from the bitmap, doesn't may\n>   not be in the pack, but it could be based off of an object\n>   the client already has in its object store and for that\n>   there is no struct object_entry in memory.\n> \n> Is that correct?\n\nRight, we are interested in objects that we _couldn't_ find a struct\nfor.  I agree this could be more clear.\n\n-Peff\n"},{"id":"356136","messageId":"xmqqa7pgbvie.fsf@gitster-ct.c.googlers.com","threadId":"49155","inReplyTo":"20180817210604.GF20088@sigill.intra.peff.net","subject":"Re: [PATCH 6/6] pack-objects: reuse on-disk deltas for thin \"have\" objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-08-20T21:03:53Z","receivedAt":"2018-08-20T21:04:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> And that's exactly what this patch does: when we're\n> considering whether to reuse an on-disk delta, if bitmaps\n> tell us the other side has the object (and we're making a\n> thin-pack), then we reuse it.\n\nThat's really the natural extension and logical consequence of the\n\"reuse existing deltas\" mechanism from Feb 2006 ;-)\n\n> So taking all of those options into account, what I ended up\n> with is a separate list of \"external bases\" that are not\n> part of the main packing list. Each delta entry that points\n> to an external base has a single-bit flag to do so; we have a\n> little breathing room in the bitfield section of\n> object_entry.\n>\n> This lets us limit the change primarily to the oe_delta()\n> and oe_set_delta_ext() functions. And as a bonus, most of\n> the rest of the code does not consider these dummy entries\n> at all, saving both runtime CPU and code complexity.\n\nTricky ;-)\n\nI wonder if we can move the preferred base objects that we are not\ngoing to send also off of the \"main packing list\" to this new\nmechanism?\n\n> +static struct bitmap_index *bitmap_git;\n> ...\n> +static int thin = 0;\n\nPlease trust what BSS will do to your static vars.\n"},{"id":"356141","messageId":"20180820214223.GB14995@sigill.intra.peff.net","threadId":"49155","inReplyTo":"xmqqa7pgbvie.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH 6/6] pack-objects: reuse on-disk deltas for thin \"have\" objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-20T21:42:23Z","receivedAt":"2018-08-20T21:42:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 20, 2018 at 02:03:53PM -0700, Junio C Hamano wrote:\n\n> > So taking all of those options into account, what I ended up\n> > with is a separate list of \"external bases\" that are not\n> > part of the main packing list. Each delta entry that points\n> > to an external base has a single-bit flag to do so; we have a\n> > little breathing room in the bitfield section of\n> > object_entry.\n> >\n> > This lets us limit the change primarily to the oe_delta()\n> > and oe_set_delta_ext() functions. And as a bonus, most of\n> > the rest of the code does not consider these dummy entries\n> > at all, saving both runtime CPU and code complexity.\n> \n> Tricky ;-)\n> \n> I wonder if we can move the preferred base objects that we are not\n> going to send also off of the \"main packing list\" to this new\n> mechanism?\n\nThat gets trickier. Obviously we don't need to actually send them, so\nthey're ignored during the write phase. But we do put them into the\ndelta-search window along with the other objects, and we care about\nthings like their size and type (which our dummy objects do not even\nhave; they really are just placeholders for the oids).\n\nSo I'd guess that we'd end up with three arrays of entries:\n\n - objects we want to send, with full details including delta bases\n\n - preferred base objects with _some_ details\n\n - dummy thin objects for reused deltas\n\nThe trick is that I don't know which details fall under the \"some\" in\nthe second class. That could be extracted from a careful reading of the\ncode, but it seems like it has a high chance of regression (and I'm not\nsure there's a huge upside, given that the code is already written\nas-is).\n\nI also worried about the same thing with these new reused dummy objects.\nbut I think by now I'd have shaken out any problems in production use.\n\n> > +static struct bitmap_index *bitmap_git;\n> > ...\n> > +static int thin = 0;\n> \n> Please trust what BSS will do to your static vars.\n\nHeh. I copied the non-static declaration, but didn't think about\nshortening it. Looks like there were one or two minor comments, so I'll\ndo a re-roll that addresses them.\n\n-Peff\n"},{"id":"356185","messageId":"20180821190622.GA30301@sigill.intra.peff.net","threadId":"49155","inReplyTo":"20180817205427.GA19580@sigill.intra.peff.net","subject":"[PATCH v2 0/6] reuse on-disk deltas for fetches with bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-21T19:06:22Z","receivedAt":"2018-08-21T19:06:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 17, 2018 at 04:54:27PM -0400, Jeff King wrote:\n\n> This series more aggressively reuses on-disk deltas to serve fetches\n> when reachability bitmaps tell us a more complete picture of what the\n> client has. That saves server CPU and results in smaller packs. See the\n> final patch for numbers and more discussion.\n\nHere's a v2, with just a few cosmetic fixes to address the comments on\nv1 (range-diff below).\n\n  [1/6]: t/perf: factor boilerplate out of test_perf\n  [2/6]: t/perf: factor out percent calculations\n  [3/6]: t/perf: add infrastructure for measuring sizes\n  [4/6]: t/perf: add perf tests for fetches from a bitmapped server\n  [5/6]: pack-bitmap: save \"have\" bitmap from walk\n  [6/6]: pack-objects: reuse on-disk deltas for thin \"have\" objects\n\n builtin/pack-objects.c             | 28 +++++++----\n pack-bitmap.c                      | 25 +++++++++-\n pack-bitmap.h                      |  7 +++\n pack-objects.c                     | 19 ++++++++\n pack-objects.h                     | 20 +++++++-\n t/perf/README                      | 25 ++++++++++\n t/perf/aggregate.perl              | 69 ++++++++++++++++++++++------\n t/perf/p5311-pack-bitmaps-fetch.sh | 45 ++++++++++++++++++\n t/perf/perf-lib.sh                 | 74 +++++++++++++++++++-----------\n 9 files changed, 260 insertions(+), 52 deletions(-)\n create mode 100755 t/perf/p5311-pack-bitmaps-fetch.sh\n\n1:  89fa0ec8d8 ! 1:  3e1b94d7d6 pack-bitmap: save \"have\" bitmap from walk\n    @@ -69,6 +69,8 @@\n     +\n     +\tif (!bitmap_git)\n     +\t\treturn 0; /* no bitmap loaded */\n    ++\tif (!bitmap_git->result)\n    ++\t\tBUG(\"failed to perform bitmap walk before querying\");\n     +\tif (!bitmap_git->haves)\n     +\t\treturn 0; /* walk had no \"haves\" */\n     +\n2:  f7ca0d59e3 ! 2:  b8b2416aac pack-objects: reuse on-disk deltas for thin \"have\" objects\n    @@ -12,7 +12,7 @@\n         However, this misses some opportunities. Modulo some special\n         cases like shallow or partial clones, we know that every\n         object reachable from the \"haves\" could be a preferred base.\n    -    We don't use them all for two reasons:\n    +    We don't use all of them for two reasons:\n     \n           1. It's expensive to traverse the whole history and\n              enumerate all of the objects the other side has.\n    @@ -100,15 +100,16 @@\n     \n         The second is that the rest of the code assumes that any\n         reused delta will point to another \"struct object_entry\" as\n    -    its base. But by definition, we don't have such an entry!\n    +    its base. But of course the case we are interested in here\n    +    is the one where don't have such an entry!\n     \n         I looked at a number of options that didn't quite work:\n     \n    -     - we could use a different flag for reused deltas. But it's\n    -       not a single bit for \"I'm being reused\". We have to\n    -       actually store the oid of the base, which is normally\n    -       done by pointing to the existing object_entry. And we'd\n    -       have to modify all the code which looks at deltas.\n    +     - we could use a flag to signal a reused delta, but it's\n    +       not a single bit. We have to actually store the oid of\n    +       the base, which is normally done by pointing to the\n    +       existing object_entry. And we'd have to modify all the\n    +       code which looks at deltas.\n     \n          - we could add the reused bases to the end of the existing\n            object_entry array. While this does create some extra\n    @@ -173,7 +174,7 @@\n      static int depth = 50;\n      static int delta_search_threads;\n      static int pack_to_stdout;\n    -+static int thin = 0;\n    ++static int thin;\n      static int num_preferred_base;\n      static struct progress *progress_state;\n      \n"},{"id":"356192","messageId":"20180821190832.GA30888@sigill.intra.peff.net","threadId":"49155","inReplyTo":"20180821190622.GA30301@sigill.intra.peff.net","subject":"Re: [PATCH v2 0/6] reuse on-disk deltas for fetches with bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-21T19:08:32Z","receivedAt":"2018-08-21T19:08:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Aug 21, 2018 at 03:06:22PM -0400, Jeff King wrote:\n\n> On Fri, Aug 17, 2018 at 04:54:27PM -0400, Jeff King wrote:\n> \n> > This series more aggressively reuses on-disk deltas to serve fetches\n> > when reachability bitmaps tell us a more complete picture of what the\n> > client has. That saves server CPU and results in smaller packs. See the\n> > final patch for numbers and more discussion.\n> \n> Here's a v2, with just a few cosmetic fixes to address the comments on\n> v1 (range-diff below).\n\nWhoops. I accidentally just sent these as replies to the wrong thread:\n\n  https://public-inbox.org/git/20180821184140.GA24165@sigill.intra.peff.net/\n\nI'll avoid spamming the list by re-sending, but let me know if it's\neasier to simply repost.\n\n-Peff\n"},{"id":"356199","messageId":"xmqqo9dv8qf9.fsf@gitster-ct.c.googlers.com","threadId":"49155","inReplyTo":"20180821190622.GA30301@sigill.intra.peff.net","subject":"Re: [PATCH v2 0/6] reuse on-disk deltas for fetches with bitmaps","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-08-21T19:34:18Z","receivedAt":"2018-08-21T19:34:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Fri, Aug 17, 2018 at 04:54:27PM -0400, Jeff King wrote:\n>\n>> This series more aggressively reuses on-disk deltas to serve fetches\n>> when reachability bitmaps tell us a more complete picture of what the\n>> client has. That saves server CPU and results in smaller packs. See the\n>> final patch for numbers and more discussion.\n>\n> Here's a v2, with just a few cosmetic fixes to address the comments on\n> v1 (range-diff below).\n>\n>   [1/6]: t/perf: factor boilerplate out of test_perf\n>   [2/6]: t/perf: factor out percent calculations\n>   [3/6]: t/perf: add infrastructure for measuring sizes\n>   [4/6]: t/perf: add perf tests for fetches from a bitmapped server\n>   [5/6]: pack-bitmap: save \"have\" bitmap from walk\n>   [6/6]: pack-objects: reuse on-disk deltas for thin \"have\" objects\n\nThanks.\n\n> 1:  89fa0ec8d8 ! 1:  3e1b94d7d6 pack-bitmap: save \"have\" bitmap from walk\n>     @@ -69,6 +69,8 @@\n>      +\n>      +\tif (!bitmap_git)\n>      +\t\treturn 0; /* no bitmap loaded */\n>     ++\tif (!bitmap_git->result)\n>     ++\t\tBUG(\"failed to perform bitmap walk before querying\");\n>      +\tif (!bitmap_git->haves)\n>      +\t\treturn 0; /* walk had no \"haves\" */\n>      +\n\nThe first four are unchanged, so this actually compares 5/6 of the\nprevious and the current one.  Omitting the four identical ones\nmakes sense, but I wonder if it makes it easier to see if we keep\nthe number-label of the surviving patches.\n\n> 2:  f7ca0d59e3 ! 2:  b8b2416aac pack-objects: reuse on-disk deltas for thin \"have\" objects\n\n"},{"id":"356205","messageId":"20180821195102.GB859@sigill.intra.peff.net","threadId":"49155","inReplyTo":"xmqqo9dv8qf9.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH v2 0/6] reuse on-disk deltas for fetches with bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-21T19:51:02Z","receivedAt":"2018-08-21T19:51:07Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Aug 21, 2018 at 12:34:18PM -0700, Junio C Hamano wrote:\n\n> > 1:  89fa0ec8d8 ! 1:  3e1b94d7d6 pack-bitmap: save \"have\" bitmap from walk\n> >     @@ -69,6 +69,8 @@\n> >      +\n> >      +\tif (!bitmap_git)\n> >      +\t\treturn 0; /* no bitmap loaded */\n> >     ++\tif (!bitmap_git->result)\n> >     ++\t\tBUG(\"failed to perform bitmap walk before querying\");\n> >      +\tif (!bitmap_git->haves)\n> >      +\t\treturn 0; /* walk had no \"haves\" */\n> >      +\n> \n> The first four are unchanged, so this actually compares 5/6 of the\n> previous and the current one.  Omitting the four identical ones\n> makes sense, but I wonder if it makes it easier to see if we keep\n> the number-label of the surviving patches.\n\nAgreed, but I think this is user error, and not the tool.\n\nI ran:\n\n  git range-diff @{push}...HEAD\n\nsince I knew that I had not pushed since beginning my revisions today.\nBut of course \"rebase -i\" is clever enough not to change the commit id\non the earlier commits I did not touch, and thus the merge base is\nactually patch 4.\n\nI should instead be more explicit about the base, like:\n\n  git range-diff origin @{push} HEAD\n\nThat shows much more sensible output (see below).\n\nFor my triangular setup, I could even do:\n\n  git range-diff @{upstream} @{push} HEAD\n\nbut I'm not sure if that is generally applicable advice (I'm not sure\nhow many people have really bought into @{push} and using triangular\nconfig -- traditionally I think many people treat @{upstream} as the\nplace they push to). It also needs adjusting if your revisions might\nspan several sessions; you'd really need @{push}@{yesterday} or similar.\nThe best thing to compare against is probably what got queued, so\nsomething like:\n\n  git range-diff origin..origin/jk/$branch_name origin..HEAD\n\nthough that also introduces sign-off noise.\n\n-Peff\n\n-- >8 --\n1:  9665189d70 = 1:  9665189d70 t/perf: factor boilerplate out of test_perf\n2:  fa1ad80e4e = 2:  fa1ad80e4e t/perf: factor out percent calculations\n3:  abf0ddbb9f = 3:  abf0ddbb9f t/perf: add infrastructure for measuring sizes\n4:  49981526ad = 4:  49981526ad t/perf: add perf tests for fetches from a bitmapped server\n5:  89fa0ec8d8 ! 5:  3e1b94d7d6 pack-bitmap: save \"have\" bitmap from walk\n    @@ -69,6 +69,8 @@\n     +\n     +\tif (!bitmap_git)\n     +\t\treturn 0; /* no bitmap loaded */\n    ++\tif (!bitmap_git->result)\n    ++\t\tBUG(\"failed to perform bitmap walk before querying\");\n     +\tif (!bitmap_git->haves)\n     +\t\treturn 0; /* walk had no \"haves\" */\n     +\n6:  f7ca0d59e3 ! 6:  b8b2416aac pack-objects: reuse on-disk deltas for thin \"have\" objects\n    @@ -12,7 +12,7 @@\n         However, this misses some opportunities. Modulo some special\n         cases like shallow or partial clones, we know that every\n         object reachable from the \"haves\" could be a preferred base.\n    -    We don't use them all for two reasons:\n    +    We don't use all of them for two reasons:\n     \n           1. It's expensive to traverse the whole history and\n              enumerate all of the objects the other side has.\n    @@ -100,15 +100,16 @@\n     \n         The second is that the rest of the code assumes that any\n         reused delta will point to another \"struct object_entry\" as\n    -    its base. But by definition, we don't have such an entry!\n    +    its base. But of course the case we are interested in here\n    +    is the one where don't have such an entry!\n     \n         I looked at a number of options that didn't quite work:\n     \n    -     - we could use a different flag for reused deltas. But it's\n    -       not a single bit for \"I'm being reused\". We have to\n    -       actually store the oid of the base, which is normally\n    -       done by pointing to the existing object_entry. And we'd\n    -       have to modify all the code which looks at deltas.\n    +     - we could use a flag to signal a reused delta, but it's\n    +       not a single bit. We have to actually store the oid of\n    +       the base, which is normally done by pointing to the\n    +       existing object_entry. And we'd have to modify all the\n    +       code which looks at deltas.\n     \n          - we could add the reused bases to the end of the existing\n            object_entry array. While this does create some extra\n    @@ -173,7 +174,7 @@\n      static int depth = 50;\n      static int delta_search_threads;\n      static int pack_to_stdout;\n    -+static int thin = 0;\n    ++static int thin;\n      static int num_preferred_base;\n      static struct progress *progress_state;\n      \n\n\n"}]}