{"thread":{"id":"36296","subject":"[PATCH/RFC 0/6] reuse deltas found by bitmaps","startedAt":"2014-03-26T07:22:16Z","lastAt":"2014-03-28T04:23:29Z","messageCount":17,"participants":["Jeff King","Junio C Hamano","Siddharth Agarwal","Eric Sunshine"],"isPatch":true,"patchVersion":1,"patchTotal":6},"messages":[{"id":"237782","messageId":"20140326072215.GA31739@sigill.intra.peff.net","threadId":"36296","inReplyTo":null,"subject":"[PATCH/RFC 0/6] reuse deltas found by bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-03-26T07:22:16Z","receivedAt":"2014-03-26T07:22:16Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"[tl;dr the patch is the same as before, but there is a script to measure\n       its effects; please try it out on your repos]\n\nThis is a continuation of the discussion here:\n\n  http://thread.gmane.org/gmane.comp.version-control.git/239647\n\nI'll summarize the story so far.\n\nBasically, the problem is that while pack bitmaps make the \"Counting\nobjects\" phase of a fetch fast (which in turn makes clones very fast),\nthey do not help as much for an incremental fetch. One, because we have\na lot fewer objects to count, so there is less for us to speed up there.\nAnd two, we spend a lot more effort on delta compression for a fetch,\nbecause we are often throwing out on-disk deltas that we are not sure\nthat the other side has.\n\nOne common case is that the server side is mostly packed and has\nbitmaps, and the fetching client has some subset of its objects, but\nwants to bring itself up to the tip. Any delta that the server has on\ndisk is generally eligible for reuse, because the base is either:\n\n  1. An object that the client already has.\n\n  2. An object that we are going to send as part of the new pack.\n\nHowever, we quite often do not notice case (1), because we only consider\na subset of the client's objects as \"preferred bases\" for thin-packing.\nThe reason for this is that traditionally it was expensive to enumerate\nall of the objects we know the client has. But with bitmaps, this is\nvery cheap. So the basic idea is to better notice which objects the\nclient has and change our delta reuse and preferred-base rules.\n\nThere are three basic strategies I can think of for doing this:\n\n  1. Add every object the client has to the packing list as a preferred\n     base.\n\n  2. When considering whether a delta can be reused, check the bitmaps\n     to see if the client has the base. If so, allow reuse.\n\n  3. Do (2), but also add the object as a preferred base.\n\nI think that option (1) is probably a bad idea; we'll spend a lot of\ntime generating a large packing list, and the huge number of objects\nwill probably clog the delta window.\n\nOption (3) might or might not be a good idea. It would hopefully give us\nsome relevant subset of the objects to use as preferred bases, in case\nother objects also need deltas.\n\nThe implementation I'm including here is the one I've shown before,\nwhich does (2). Part of the reason that I'm reposting it before looking\nfurther into these options is that I've written a t/perf script that can\nhelp with the analysis.\n\nI've run it against git.git and linux.git. I'd be curious to see the\nresults on other repositories that might have different delta patterns.\n\nThe script simulates a fetch from a fully-packed server by a client who\nhas not fetched in N days, for several values of N. It measures the time\ntaken on the server (to run pack-objects), the time taken on the client\n(to run index-pack), and the size of the resulting pack. Here are the\nresults for running it on linux.git (note that the script output has the\ntests interleaved, but I've rearranged it here for clarity):\n\n    Test                         origin             HEAD                   \n    -----------------------------------------------------------------------\n    5311.4: size     (1 days)               1.0M              59.5K -94.1% \n    5311.8: size     (2 days)               1.0M              59.5K -94.1% \n    5311.12: size     (4 days)              1.1M              67.9K -93.5% \n    5311.16: size     (8 days)              1.5M             130.1K -91.4% \n    5311.20: size    (16 days)              3.7M             359.8K -90.3% \n    5311.24: size    (32 days)              8.6M               1.4M -84.3% \n    5311.28: size    (64 days)             68.3M              23.0M -66.3% \n    5311.32: size   (128 days)             83.1M              35.1M -57.7% \n\nYou can see that it produces much smaller packs, because we're getting\nbetter delta reuse (and bitmaps don't generally produce preferred bases\nat all, so we were probably failing to make thin packs at all). The\npercentage benefit lessens as we go further back, of course, because the\nthin objects will be at the \"edge\" of the pack (and the bigger the pack,\nthe less of it is edge).\n\nSo far so good...here are the server timings:\n\n    Test                         origin             HEAD                   \n    -----------------------------------------------------------------------\n    5311.3: server   (1 days)    0.29(0.33+0.03)    0.14(0.11+0.02) -51.7% \n    5311.7: server   (2 days)    0.29(0.33+0.04)    0.14(0.11+0.02) -51.7% \n    5311.11: server   (4 days)   0.29(0.32+0.04)    0.14(0.11+0.02) -51.7% \n    5311.15: server   (8 days)   0.36(0.45+0.04)    0.14(0.11+0.02) -61.1% \n    5311.19: server  (16 days)   0.74(1.17+0.05)    0.26(0.23+0.02) -64.9% \n    5311.23: server  (32 days)   1.38(2.53+0.06)    0.29(0.25+0.03) -79.0% \n    5311.27: server  (64 days)   7.12(15.70+0.18)   0.43(0.38+0.07) -94.0% \n    5311.31: server (128 days)   7.60(16.72+0.19)   0.52(0.48+0.07) -93.2% \n\nAgain, looking good. We're cutting out the whole delta-search phase on\nthe server, because we can reuse all of our deltas. Note that these\nmeasurements represent the optimal case: a fully packed repository with\na client that wants every object we have. So we should get full delta\nreuse. That also means that this test probably won't show any advantages\nfor option (3) above, where we would add more preferred bases. We don't\nhave any candidates for delta compression, so it doesn't matter how many\npreferred bases we have.\n\nAnd here's the bad(ish) news:\n\n    Test                         origin             HEAD                   \n    -----------------------------------------------------------------------\n    5311.5: client   (1 days)    0.03(0.04+0.00)    0.08(0.07+0.00) +166.7%\n    5311.9: client   (2 days)    0.03(0.04+0.00)    0.09(0.08+0.00) +200.0%\n    5311.13: client   (4 days)   0.04(0.03+0.01)    0.09(0.08+0.00) +125.0%\n    5311.17: client   (8 days)   0.05(0.06+0.00)    0.12(0.11+0.00) +140.0%\n    5311.21: client  (16 days)   0.13(0.14+0.00)    0.29(0.28+0.01) +123.1%\n    5311.25: client  (32 days)   0.32(0.37+0.01)    0.67(0.66+0.01) +109.4%\n    5311.29: client  (64 days)   3.14(4.52+0.19)    6.27(6.50+0.13) +99.7% \n    5311.33: client (128 days)   4.16(6.06+0.23)    7.17(7.86+0.16) +72.4% \n\nThe client has to spend more effort, because it now has to \"fix\" the\nthin pack it receives. But there's a silver lining. Even though the\npercent change looks bad, that's only because the client was already\nspending much less time than the server. In absolute numbers, we should\ncome out ahead.\n\nLet's look at the 128-day case as an example.  Before this series, we\nspent 7.6s on the server and 4.2s on the client. We sent an 83M pack. If\nwe assume a 25MBit connection, that's 26.5s of transfer. The total is\n38.3s for the whole fetch (this is slightly inaccurate, because\nindex-pack does some work while the pack is streaming in from the\nnetwork, but most of it does happen afterwards).\n\nAfter the series, we spend only 0.5s on the server, but 7.2s on the\nclient. Our pack shrinks to 35M, or 11.2s of transfer time. Our total is\nnow 18.9s (about half).\n\nThe other cases show a similar effect, though sometimes less pronounced\n(but the very small fetches are already so fast that they are not really\nthat interesting). Even without the net win in wall-clock time, I think\nthe reduced server and network load are worth it, but it's nice that it\nends up faster overall, too.\n\nThe other interesting thing is to compare CPU and wall-clock time. In\nthe 128-day case we only saved 7s of wall-clock time, but we saved\nalmost 17s of CPU time (this is on a HT quad-core machine). On the\nclient side, we added 3s of wall-clock time, but we spent only 1.8s of\nextra CPU time.\n\nThis is because most of index-pack is multi-threaded, but the\nthin-object resolution is not. So the more thin objects we send, the\nless effectively index-pack can use multiple cores. This might be worth\nlooking into as a next step.\n\nI'd be curious to see numbers for other repositories. I know that Ben\nmentioned in our initial discussion that while they saw a server CPU\ntime improvement on their repo at Facebook, they didn't see the same\npack-size savings.\n\nIf you want to run the test yourself, you can either apply these\npatches, or fetch from:\n\n  git://github.com/peff/git.git jk/bitmap-reuse-delta\n\nand then run:\n\n  cd t/perf\n  export GIT_PERF_REPO=/path/to/your/repo\n  ./run origin HEAD p5311-pack-bitmaps-fetch.sh\n\nIf you want to re-show the results without re-running the test, you can\ndo:\n\n  perl aggregate.perl origin HEAD p5311-pack-bitmaps-fetch.sh\n\n-Peff\n"},{"id":"237783","messageId":"20140326072232.GA32193@sigill.intra.peff.net","threadId":"36296","inReplyTo":"20140326072215.GA31739@sigill.intra.peff.net","subject":"[PATCH 1/6] t/perf-lib: factor boilerplate out of test_perf","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-03-26T07:22:33Z","receivedAt":"2014-03-26T07:22:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"About half of test_perf() is boilerplate, and half is\nactually related to running the perf test. Let's split it\ninto two functions, so that we can reuse the boilerplate in\nfuture commits.\n\nSigned-off-by: Jeff King <peff@peff.net>\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 a8c9574..20f306a 100644\n--- a/t/perf/perf-lib.sh\n+++ b/t/perf/perf-lib.sh\n@@ -150,8 +150,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@@ -162,35 +162,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-- \n1.9.1.601.g7ec968e\n"},{"id":"237784","messageId":"20140326072237.GB32193@sigill.intra.peff.net","threadId":"36296","inReplyTo":"20140326072215.GA31739@sigill.intra.peff.net","subject":"[PATCH 2/6] t/perf/aggregate: factor our percent calculations","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-03-26T07:22:37Z","receivedAt":"2014-03-26T07:22:37Z","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 15f7fc1..690cd8c 100755\n--- a/t/perf/aggregate.perl\n+++ b/t/perf/aggregate.perl\n@@ -16,21 +16,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-- \n1.9.1.601.g7ec968e\n"},{"id":"237785","messageId":"20140326072241.GC32193@sigill.intra.peff.net","threadId":"36296","inReplyTo":"20140326072215.GA31739@sigill.intra.peff.net","subject":"[PATCH 3/6] t/perf: add infrastructure for measuring sizes","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-03-26T07:22:41Z","receivedAt":"2014-03-26T07:22:41Z","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         | 20 ++++++++++++++++++++\n t/perf/aggregate.perl | 48 +++++++++++++++++++++++++++++++++++++++++++-----\n t/perf/perf-lib.sh    | 13 +++++++++++++\n 3 files changed, 76 insertions(+), 5 deletions(-)\n\ndiff --git a/t/perf/README b/t/perf/README\nindex 8848c14..09c400f 100644\n--- a/t/perf/README\n+++ b/t/perf/README\n@@ -144,3 +144,23 @@ 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%\ndiff --git a/t/perf/aggregate.perl b/t/perf/aggregate.perl\nindex 690cd8c..42739a5 100755\n--- a/t/perf/aggregate.perl\n+++ b/t/perf/aggregate.perl\n@@ -10,10 +10,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@@ -29,14 +35,39 @@ 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 }\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 while (scalar @ARGV) {\n \tmy $arg = $ARGV[0];\n@@ -139,7 +170,14 @@ sub have_slash {\n \tmy $firstr;\n \tfor my $i (0..$#dirs) {\n \t\tmy $d = $dirs[$i];\n-\t\t$times{$prefixes{$d}.$t} = [get_times(\"test-results/$prefixes{$d}$t.times\")];\n+\t\tmy $base = \"test-results/$prefixes{$d}$t\";\n+\t\t$times{$prefixes{$d}.$t} = [];\n+\t\tforeach my $type (qw(times size)) {\n+\t\t\tif (-e \"$base.$type\") {\n+\t\t\t\t$times{$prefixes{$d}.$t} = [get_times(\"$base.$type\")];\n+\t\t\t\tlast;\n+\t\t\t}\n+\t\t}\n \t\tmy ($r,$u,$s) = @{$times{$prefixes{$d}.$t}};\n \t\tmy $w = length format_times($r,$u,$s,$firstr);\n \t\t$colwidth[$i] = $w if $w > $colwidth[$i];\ndiff --git a/t/perf/perf-lib.sh b/t/perf/perf-lib.sh\nindex 20f306a..fb8e017 100644\n--- a/t/perf/perf-lib.sh\n+++ b/t/perf/perf-lib.sh\n@@ -202,6 +202,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-- \n1.9.1.601.g7ec968e\n"},{"id":"237786","messageId":"20140326072247.GD32193@sigill.intra.peff.net","threadId":"36296","inReplyTo":"20140326072215.GA31739@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":"2014-03-26T07:22:47Z","receivedAt":"2014-03-26T07:22:47Z","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 other side).\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 we can calculate a complete\nwall-clock time for the operation.\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 0000000..b045759\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-- \n1.9.1.601.g7ec968e\n"},{"id":"237787","messageId":"20140326072329.GE32193@sigill.intra.peff.net","threadId":"36296","inReplyTo":"20140326072215.GA31739@sigill.intra.peff.net","subject":"[PATCH 5/6] pack-bitmap: save \"have\" bitmap from walk","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-03-26T07:23:29Z","receivedAt":"2014-03-26T07:23:29Z","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\nSigned-off-by: Jeff King <peff@peff.net>\n---\n pack-bitmap.c | 21 ++++++++++++++++++++-\n pack-bitmap.h |  2 ++\n 2 files changed, 22 insertions(+), 1 deletion(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex a31e529..f7d417b 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -86,6 +86,9 @@ static 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@@ -769,8 +772,8 @@ int 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 0;\n }\n \n@@ -1097,3 +1100,19 @@ int rebuild_existing_bitmaps(struct packing_data *mapping,\n \tbitmap_free(rebuild);\n \treturn 0;\n }\n+\n+int bitmap_have(const unsigned char *sha1)\n+{\n+\tint pos;\n+\n+\tif (!bitmap_git.loaded)\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(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 8b7f4e9..a63ee6b 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -49,6 +49,8 @@ int prepare_bitmap_walk(struct rev_info *revs);\n int reuse_partial_packfile_from_bitmap(struct packed_git **packfile, uint32_t *entries, off_t *up_to);\n int rebuild_existing_bitmaps(struct packing_data *mapping, khash_sha1 *reused_bitmaps, int show_progress);\n \n+int bitmap_have(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 pack_idx_entry **index, uint32_t index_nr);\n-- \n1.9.1.601.g7ec968e\n"},{"id":"237788","messageId":"20140326072338.GF32193@sigill.intra.peff.net","threadId":"36296","inReplyTo":"20140326072215.GA31739@sigill.intra.peff.net","subject":"[PATCH 6/6] pack-objects: reuse deltas for thin \"have\" objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-03-26T07:23:38Z","receivedAt":"2014-03-26T07:23:38Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When we calculate the \"wants\" and \"haves\" for a pack, we\nonly add the objects in the boundary commits as preferred\nbases. However, we know that every object reachable from the\n\"haves\" could be a preferred base.\n\nWe probably don't want to add these to our preferred base\nlist, because they would clog the delta-search window.\nHowever, there is no reason we cannot reuse an on-disk delta\nagainst such a deep \"have\" base, avoiding the delta search\nfor that object altogether.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n builtin/pack-objects.c | 16 +++++++++++++++-\n 1 file changed, 15 insertions(+), 1 deletion(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 7950c43..92bd682 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -53,6 +53,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 static int pack_compression_level = Z_DEFAULT_COMPRESSION;\n@@ -1419,6 +1420,20 @@ static void check_object(struct object_entry *entry)\n \t\t\tbase_entry->delta_child = entry;\n \t\t\tunuse_pack(&w_curs);\n \t\t\treturn;\n+\t\t} else if(thin && base_ref && bitmap_have(base_ref)) {\n+\t\t\tentry->type = entry->in_pack_type;\n+\t\t\tentry->delta_size = entry->size;\n+\t\t\t/*\n+\t\t\t * XXX we'll leak this, but it's probably OK\n+\t\t\t * since we'll exit immediately after the packing\n+\t\t\t * is done\n+\t\t\t */\n+\t\t\tentry->delta = xcalloc(1, sizeof(*entry->delta));\n+\t\t\thashcpy(entry->delta->idx.sha1, base_ref);\n+\t\t\tentry->delta->preferred_base = 1;\n+\t\t\tentry->delta->filled = 1;\n+\t\t\tunuse_pack(&w_curs);\n+\t\t\treturn;\n \t\t}\n \n \t\tif (entry->type) {\n@@ -2559,7 +2574,6 @@ static int option_parse_ulong(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 all_progress_implied = 0;\n \tconst char *rp_av[6];\n \tint rp_ac = 0;\n-- \n1.9.1.601.g7ec968e\n"},{"id":"237820","messageId":"xmqq7g7gkgp6.fsf@gitster.dls.corp.google.com","threadId":"36296","inReplyTo":"20140326072215.GA31739@sigill.intra.peff.net","subject":"Re: [PATCH/RFC 0/6] reuse deltas found by bitmaps","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-03-26T17:33:41Z","receivedAt":"2014-03-26T17:33:41Z","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>   2. When considering whether a delta can be reused, check the bitmaps\n>      to see if the client has the base. If so, allow reuse.\n> ...\n> The implementation I'm including here is the one I've shown before,\n> which does (2). Part of the reason that I'm reposting it before looking\n> further into these options is that I've written a t/perf script that can\n> help with the analysis.\n\nConceptually, that feels like a natural extension for the \"thin\npack\" transfer.  I wouldn't foresee a correctness issue, as long as\nthe fetcher runs \"index-pack --fix-thin\" at their end.\n"},{"id":"237822","messageId":"20140326181300.GA7087@sigill.intra.peff.net","threadId":"36296","inReplyTo":"xmqq7g7gkgp6.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH/RFC 0/6] reuse deltas found by bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-03-26T18:13:00Z","receivedAt":"2014-03-26T18:13:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Mar 26, 2014 at 10:33:41AM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> >   2. When considering whether a delta can be reused, check the bitmaps\n> >      to see if the client has the base. If so, allow reuse.\n> > ...\n> > The implementation I'm including here is the one I've shown before,\n> > which does (2). Part of the reason that I'm reposting it before looking\n> > further into these options is that I've written a t/perf script that can\n> > help with the analysis.\n> \n> Conceptually, that feels like a natural extension for the \"thin\n> pack\" transfer.  I wouldn't foresee a correctness issue, as long as\n> the fetcher runs \"index-pack --fix-thin\" at their end.\n\nRight, this is only enabled when --thin is negotiated during the\nprotocol transfer. I don't think there's any correctness problem here.\nBut I want to make sure we are doing the fastest thing.\n\nHere's another set of results comparing three runs: v1.9.0 (with no\nbitmaps), origin/master (bitmaps), and this series. Apologies for the\nlong lines.\n\n  Test                         v1.9.0            origin                     HEAD                   \n  -------------------------------------------------------------------------------------------------\n  5311.3: server   (1 days)    0.20(0.17+0.02)   0.29(0.34+0.04) +45.0%     0.14(0.12+0.02) -30.0% \n  5311.4: size     (1 days)              56.2K              1.0M +1694.4%             59.5K +5.9%  \n  5311.5: client   (1 days)    0.08(0.07+0.00)   0.03(0.04+0.00) -62.5%     0.08(0.07+0.00) +0.0%  \n  5311.7: server   (2 days)    0.06(0.06+0.00)   0.28(0.33+0.04) +366.7%    0.14(0.11+0.02) +133.3%\n  5311.8: size     (2 days)              56.2K              1.0M +1694.4%             59.5K +5.9%  \n  5311.9: client   (2 days)    0.09(0.08+0.00)   0.03(0.04+0.00) -66.7%     0.09(0.08+0.00) +0.0%  \n  5311.11: server   (4 days)   0.21(0.18+0.02)   0.29(0.33+0.03) +38.1%     0.14(0.11+0.02) -33.3% \n  5311.12: size     (4 days)             64.2K              1.1M +1536.6%             67.9K +5.8%  \n  5311.13: client   (4 days)   0.08(0.08+0.00)   0.04(0.03+0.01) -50.0%     0.09(0.07+0.01) +12.5% \n  5311.15: server   (8 days)   0.22(0.21+0.02)   0.36(0.47+0.03) +63.6%     0.14(0.11+0.02) -36.4% \n  5311.16: size     (8 days)            125.7K              1.5M +1100.8%            130.1K +3.5%  \n  5311.17: client   (8 days)   0.11(0.10+0.00)   0.05(0.05+0.00) -54.5%     0.13(0.11+0.01) +18.2% \n  5311.19: server  (16 days)   0.26(0.26+0.03)   0.76(1.20+0.04) +192.3%    0.25(0.21+0.04) -3.8%  \n  5311.20: size    (16 days)            358.6K              3.7M +931.7%             359.8K +0.3%  \n  5311.21: client  (16 days)   0.28(0.27+0.01)   0.13(0.15+0.00) -53.6%     0.30(0.28+0.02) +7.1%  \n  5311.23: server  (32 days)   0.44(0.54+0.07)   1.39(2.54+0.04) +215.9%    0.28(0.23+0.04) -36.4% \n  5311.24: size    (32 days)              1.1M              8.6M +652.4%               2.1M +83.9% \n  5311.25: client  (32 days)   0.66(0.64+0.02)   0.32(0.38+0.01) -51.5%     0.69(0.67+0.04) +4.5%  \n  5311.27: server  (64 days)   2.78(4.02+0.17)   7.02(15.59+0.16) +152.5%   0.43(0.37+0.07) -84.5% \n  5311.28: size    (64 days)             18.7M             68.3M +265.5%              24.5M +31.3% \n  5311.29: client  (64 days)   6.25(6.29+0.16)   3.21(4.76+0.14) -48.6%     6.27(6.46+0.18) +0.3%  \n  5311.31: server (128 days)   4.48(7.32+0.21)   7.56(16.60+0.16) +68.8%    0.51(0.45+0.10) -88.6% \n  5311.32: size   (128 days)             25.8M             83.1M +222.3%              35.9M +39.2% \n  5311.33: client (128 days)   7.32(7.58+0.17)   3.94(5.87+0.18) -46.2%     7.15(7.80+0.20) -2.3%  \n\nMy previous results showed that this series was an improvement over\nstraight bitmaps. But what it didn't show is that bitmaps actually\nprovide a regression for some fetches (I think because we do not find\nthe boundary commits at all, and do not have any preferred bases).\n\nJust looking at the 128-day case again, using bitmaps increased our\nserver CPU time _and_ made a much bigger pack. This series not only\nfixes the CPU time regression, but it also drops the server CPU time to\nalmost nothing. That's a nice improvement, and it makes perfect sense:\nwe are reusing on-disk deltas instead of on-the-fly computing deltas\nagainst the preferred bases.\n\nAnd it does help with the size regression, though the end result is\nstill a bit worse than v1.9.0. I'm not exactly sure what's going on\nhere. My guess is that we have objects to send that are not deltas on\ndisk (probably because they are at the tip of history and other things\nare deltas against them). We would still want to do delta compression of\nthem against preferred bases, but we don't have any preferred bases in\nour list.\n\nSo I think we still want to add back in some list of preferred base\nobjects when bitmaps are in use. The question is, which objects?\nWith bitmaps, it's easy to add in all of the objects the client has, but\nthat is probably going to be counterproductive (I still need to measure\nit, though).\n\nI think we could still add the objects from the tip of the client's HAVE\nlist. This patch would still be a CPU win on top of that, because it\nwould reduce the number of objects which need a delta search in the\nfirst place.\n\nBut it also creates worse packs on the client side after --fix-thin is\nrun. Any preferred base we use it something the client may have to add\nback in. So once a thin base is used, we would want to use it again to\nreduce the work the client has to do to fix it. And in that sense, it\nwould be helpful to add in bases that we reuse via this patch as\npreferred bases for further delta searches.\n\nBut solely relying on that would give us a rather incomplete set of\nbases. If we are sending a blob for \"foo.c\" that has an on-disk delta\nagainst an older version that the client has, we'd reuse that delta. And\nthen further versions of foo.c might be able to use that same base,\nwhich is good. But if we are sending one version of \"bar.c\" that has no\non-disk delta, then it has no useful preferred bases.\n\nSo I think the next steps are probably:\n\n  1. Measure the \"all objects are preferred bases\" approach and confirm\n     that it is bad.\n\n  2. Measure the \"reused deltas become preferred bases\" approach. I\n     expect the resulting size to be slightly better than what I have\n     now, but not as good as v1.9.0's size (but taking less CPU time).\n\n  3. Measure the \"figure out boundaries and add them as preferred bases,\n     like we do without bitmaps\" approach. I expect this to behave\n     similarly to v1.9.0.\n\n  4. Combine (2) and (3) and measure them. I'm _hoping_ this will give\n     us the best of both worlds, but I still want to do the individual\n     measurements so we can see where any improvement is coming from.\n\n-Peff\n"},{"id":"237869","messageId":"xmqqvbv0h9rm.fsf@gitster.dls.corp.google.com","threadId":"36296","inReplyTo":"20140326181300.GA7087@sigill.intra.peff.net","subject":"Re: [PATCH/RFC 0/6] reuse deltas found by bitmaps","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-03-26T22:31:41Z","receivedAt":"2014-03-26T22:31:41Z","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> Just looking at the 128-day case again, using bitmaps increased our\n> server CPU time _and_ made a much bigger pack. This series not only\n> fixes the CPU time regression, but it also drops the server CPU time to\n> almost nothing. That's a nice improvement, and it makes perfect sense:\n> we are reusing on-disk deltas instead of on-the-fly computing deltas\n> against the preferred bases.\n\nTrue.\n\n> I think we could still add the objects from the tip of the client's HAVE\n> list.\n\nThat should make the result at least per to the non-bitmap case,\nright?\n\n> This patch would still be a CPU win on top of that, because it\n> would reduce the number of objects which need a delta search in the\n> first place.\n\nYes.\n\n> So I think the next steps are probably:\n>\n>   1. Measure the \"all objects are preferred bases\" approach and confirm\n>      that it is bad.\n\n;-)\n\n>   2. Measure the \"reused deltas become preferred bases\" approach. I\n>      expect the resulting size to be slightly better than what I have\n>      now, but not as good as v1.9.0's size (but taking less CPU time).\n\nDo you mean \"the bases for reused deltas become preferred bases, so\nthat we can deltify more objects off of them\"?\n\n>   3. Measure the \"figure out boundaries and add them as preferred bases,\n>      like we do without bitmaps\" approach. I expect this to behave\n>      similarly to v1.9.0.\n\nYes.\n\n>   4. Combine (2) and (3) and measure them. I'm _hoping_ this will give\n>      us the best of both worlds, but I still want to do the individual\n>      measurements so we can see where any improvement is coming from.\n\nSensible.  Thanks.\n"},{"id":"237870","messageId":"xmqqr45oh9n4.fsf@gitster.dls.corp.google.com","threadId":"36296","inReplyTo":"20140326072232.GA32193@sigill.intra.peff.net","subject":"Re: [PATCH 1/6] t/perf-lib: factor boilerplate out of test_perf","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-03-26T22:34:23Z","receivedAt":"2014-03-26T22:34:23Z","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> About half of test_perf() is boilerplate, and half is\n> actually related to running the perf test. Let's split it\n> into two functions, so that we can reuse the boilerplate in\n> future commits.\n>\n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n>  t/perf/perf-lib.sh | 61 +++++++++++++++++++++++++++++++-----------------------\n>  1 file changed, 35 insertions(+), 26 deletions(-)\n\nThese early steps somewhat conflict with another topic that is\nstalled (due to having no real users) on 'pu'.  I do not think we\nwould terribly mind dropping tg/perf-lib-test-perf-cleanup and have\nit rebased if the author or somebody else wants to have it in my\ntree later, but just FYI.\n\n>\n> diff --git a/t/perf/perf-lib.sh b/t/perf/perf-lib.sh\n> index a8c9574..20f306a 100644\n> --- a/t/perf/perf-lib.sh\n> +++ b/t/perf/perf-lib.sh\n> @@ -150,8 +150,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> @@ -162,35 +162,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"},{"id":"237871","messageId":"20140326223616.GA19811@sigill.intra.peff.net","threadId":"36296","inReplyTo":"xmqqvbv0h9rm.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH/RFC 0/6] reuse deltas found by bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-03-26T22:36:16Z","receivedAt":"2014-03-26T22:36:16Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Mar 26, 2014 at 03:31:41PM -0700, Junio C Hamano wrote:\n\n> > I think we could still add the objects from the tip of the client's HAVE\n> > list.\n> \n> That should make the result at least per to the non-bitmap case,\n> right?\n\nThat's my expectation.\n> \n> >   2. Measure the \"reused deltas become preferred bases\" approach. I\n> >      expect the resulting size to be slightly better than what I have\n> >      now, but not as good as v1.9.0's size (but taking less CPU time).\n> \n> Do you mean \"the bases for reused deltas become preferred bases, so\n> that we can deltify more objects off of them\"?\n\nExactly.\n\nI'll update more when I have results for some of these. :)\n\n-Peff\n"},{"id":"237872","messageId":"5333576F.1050603@fb.com","threadId":"36296","inReplyTo":"20140326072215.GA31739@sigill.intra.peff.net","subject":"Re: [PATCH/RFC 0/6] reuse deltas found by bitmaps","fromName":"Siddharth Agarwal","fromEmail":"sid0@fb.com","sentAt":"2014-03-26T22:40:47Z","receivedAt":"2014-03-26T22:40:47Z","isPatch":true,"sender":{"key":"sid0@fb.com","avatar":null},"body":"On 03/26/2014 12:22 AM, Jeff King wrote:\n> [tl;dr the patch is the same as before, but there is a script to measure\n>         its effects; please try it out on your repos]\n\nHere are results from one of our repos:\n\nTest                         origin HEAD\n-------------------------------------------------------------------------\n5311.3: server   (1 days)    1.77(2.49+0.15)     0.76(0.65+0.12) -57.1%\n5311.4: size     (1 days)               7.8M                3.1M -60.2%\n5311.5: client   (1 days)    0.56(0.48+0.03)     1.18(0.97+0.05) +110.7%\n5311.7: server   (2 days)    2.79(3.68+0.25)     0.77(0.65+0.14) -72.4%\n5311.8: size     (2 days)              24.2M                6.8M -71.8%\n5311.9: client   (2 days)    1.14(0.95+0.10)     2.72(2.33+0.13) +138.6%\n5311.11: server   (4 days)   3.70(4.76+0.28)     0.84(0.72+0.14) -77.3%\n5311.12: size     (4 days)             51.2M               18.9M -63.0%\n5311.13: client   (4 days)   2.29(2.02+0.29)     4.58(3.91+0.30) +100.0%\n5311.15: server   (8 days)   5.16(7.48+0.38)     1.20(1.18+0.21) -76.7%\n5311.16: size     (8 days)             78.3M               42.6M -45.5%\n5311.17: client   (8 days)   3.73(3.67+0.40)     6.59(5.95+0.51) +76.7%\n5311.19: server  (16 days)   6.48(10.27+0.52)    1.60(1.85+0.27) -75.3%\n5311.20: size    (16 days)             97.5M               64.0M -34.4%\n5311.21: client  (16 days)   5.31(5.76+0.57)     8.99(8.61+0.68) +69.3%\n5311.23: server  (32 days)   8.56(14.00+0.67)    2.31(2.91+0.37) -73.0%\n5311.24: size    (32 days)            124.7M               92.0M -26.2%\n5311.25: client  (32 days)   7.69(9.20+0.76)     12.80(13.07+0.91) +66.4%\n5311.27: server  (64 days)   37.47(45.48+1.55)   29.75(29.58+0.96) -20.6%\n5311.28: size    (64 days)            245.5M              207.1M -15.6%\n5311.29: client  (64 days)   15.11(18.26+1.58)   25.02(25.90+2.03) +65.6%\n5311.31: server (128 days)   43.85(57.02+2.57)   29.88(29.54+1.35) -31.9%\n5311.32: size   (128 days)            507.3M              461.6M -9.0%\n5311.33: client (128 days)   27.13(31.54+3.32)   37.76(39.49+3.16) +39.2%\n\nI'm currently running tests on a much larger repo than that. The full \nperf run will take several hours on that, so the soonest I can likely \npublish results for that is tomorrow.\n"},{"id":"237880","messageId":"20140327011323.GA9266@sigill.intra.peff.net","threadId":"36296","inReplyTo":"20140326181300.GA7087@sigill.intra.peff.net","subject":"Re: [PATCH/RFC 0/6] reuse deltas found by bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-03-27T01:13:23Z","receivedAt":"2014-03-27T01:13:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Mar 26, 2014 at 02:13:00PM -0400, Jeff King wrote:\n\n> So I think the next steps are probably:\n> \n>   1. Measure the \"all objects are preferred bases\" approach and confirm\n>      that it is bad.\n\nBelow is a very rough patch to accomplish this. It just traverses the\n\"have\" bitmap and adds every object with the \"exclude\" flag. The result\nis as comically bad as I expected.\n\nFor a big fetch, it seems like it's working (numbers against v1.9.0):\n\n  5311.31: server (128 days)   4.49(7.35+0.23)   4.98(6.82+3.31) +10.9%\n  5311.32: size   (128 days)             25.8M             32.0M +24.2%\n  5311.33: client (128 days)   7.17(7.38+0.20)   7.33(7.90+0.20) +2.2%\n\nA modest increase in CPU time, and we get back most of our size\n(remember that our \"bad\" case here is ~80M).\n\nBut for a small fetch...\n\n  5311.3: server   (1 days)    0.20(0.17+0.03)   4.39(4.03+6.59) +2095.0%\n  5311.4: size     (1 days)              57.2K             59.5K +4.1%\n  5311.5: client   (1 days)    0.08(0.08+0.00)   0.08(0.08+0.00) +0.0%\n\nYikes. Besides spending lots of CPU on handling the enlarged object\nlist, notice that we still only dropped the size in the 128-day case to\n32M. Which is almost exactly what the earlier \"reuse on-disk deltas\"\npatch achieved.\n\nWhat I think is happening is that we manage to reuse those on-disk\ndeltas (since they are now preferred bases, and we know we can). But we\nnever actually come up with any _new_ deltas, because the search window\nis overwhelmed with candidates. So not only do we waste a huge amount of\nCPU, but we just end up at the same not-quite-optimal result as before.\n\nSo this is a dead end, but I think it was good to double-check that.\n\nThe patch below is messy and would probably be better split into a few\npatches, but I don't expect anyone to apply it (or even read it,\nreally). It's just for reference.\n\n---\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 0ee5f1f..1a5d401 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1026,7 +1026,7 @@ static int add_object_entry_from_bitmap(const unsigned char *sha1,\n \tif (have_duplicate_entry(sha1, 0, &index_pos))\n \t\treturn 0;\n \n-\tcreate_object_entry(sha1, type, name_hash, 0, 0, index_pos, pack, offset);\n+\tcreate_object_entry(sha1, type, name_hash, flags, 0, index_pos, pack, offset);\n \n \tdisplay_progress(progress_state, to_pack.nr_objects);\n \treturn 1;\n@@ -2436,6 +2436,7 @@ static int get_object_list_from_bitmap(struct rev_info *revs)\n \t}\n \n \ttraverse_bitmap_commit_list(&add_object_entry_from_bitmap);\n+\tbitmap_have_foreach(&add_object_entry_from_bitmap);\n \treturn 0;\n }\n \ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 1bae7e8..f4e30f5 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -605,6 +605,7 @@ static void show_objects_for_type(\n \tstruct bitmap *objects,\n \tstruct ewah_bitmap *type_filter,\n \tenum object_type object_type,\n+\tint flags,\n \tshow_reachable_fn show_reach)\n {\n \tsize_t pos = 0, i = 0;\n@@ -613,9 +614,6 @@ static void show_objects_for_type(\n \tstruct ewah_iterator it;\n \teword_t filter;\n \n-\tif (bitmap_git.reuse_objects == bitmap_git.pack->num_objects)\n-\t\treturn;\n-\n \tewah_iterator_init(&it, type_filter);\n \n \twhile (i < objects->word_alloc && ewah_iterator_next(&filter, &it)) {\n@@ -640,7 +638,7 @@ static void show_objects_for_type(\n \t\t\tif (bitmap_git.hashes)\n \t\t\t\thash = ntohl(bitmap_git.hashes[entry->nr]);\n \n-\t\t\tshow_reach(sha1, object_type, 0, hash, bitmap_git.pack, entry->offset);\n+\t\t\tshow_reach(sha1, object_type, flags, hash, bitmap_git.pack, entry->offset);\n \t\t}\n \n \t\tpos += BITS_IN_WORD;\n@@ -816,14 +814,17 @@ void traverse_bitmap_commit_list(show_reachable_fn show_reachable)\n {\n \tassert(bitmap_git.result);\n \n+\tif (bitmap_git.reuse_objects == bitmap_git.pack->num_objects)\n+\t\treturn;\n+\n \tshow_objects_for_type(bitmap_git.result, bitmap_git.commits,\n-\t\tOBJ_COMMIT, show_reachable);\n+\t\tOBJ_COMMIT, 0, show_reachable);\n \tshow_objects_for_type(bitmap_git.result, bitmap_git.trees,\n-\t\tOBJ_TREE, show_reachable);\n+\t\tOBJ_TREE, 0, show_reachable);\n \tshow_objects_for_type(bitmap_git.result, bitmap_git.blobs,\n-\t\tOBJ_BLOB, show_reachable);\n+\t\tOBJ_BLOB, 0, show_reachable);\n \tshow_objects_for_type(bitmap_git.result, bitmap_git.tags,\n-\t\tOBJ_TAG, show_reachable);\n+\t\tOBJ_TAG, 0, show_reachable);\n \n \tshow_extended_objects(bitmap_git.result, show_reachable);\n \n@@ -1090,3 +1091,18 @@ int bitmap_have(const unsigned char *sha1)\n \n \treturn bitmap_get(bitmap_git.haves, pos);\n }\n+\n+void bitmap_have_foreach(show_reachable_fn show_reachable)\n+{\n+\tif (!bitmap_git.haves)\n+\t\treturn;\n+\n+\tshow_objects_for_type(bitmap_git.haves, bitmap_git.commits,\n+\t\tOBJ_COMMIT, 1, show_reachable);\n+\tshow_objects_for_type(bitmap_git.haves, bitmap_git.trees,\n+\t\tOBJ_TREE, 1, show_reachable);\n+\tshow_objects_for_type(bitmap_git.haves, bitmap_git.blobs,\n+\t\tOBJ_BLOB, 1, show_reachable);\n+\tshow_objects_for_type(bitmap_git.haves, bitmap_git.tags,\n+\t\tOBJ_TAG, 1, show_reachable);\n+}\ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex a63ee6b..02c08f8 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -50,6 +50,7 @@ int reuse_partial_packfile_from_bitmap(struct packed_git **packfile, uint32_t *e\n int rebuild_existing_bitmaps(struct packing_data *mapping, khash_sha1 *reused_bitmaps, int show_progress);\n \n int bitmap_have(const unsigned char *sha1);\n+void bitmap_have_foreach(show_reachable_fn);\n \n void bitmap_writer_show_progress(int show);\n void bitmap_writer_set_checksum(unsigned char *sha1);\n"},{"id":"237897","messageId":"53343106.4090303@fb.com","threadId":"36296","inReplyTo":"5333576F.1050603@fb.com","subject":"Re: [PATCH/RFC 0/6] reuse deltas found by bitmaps","fromName":"Siddharth Agarwal","fromEmail":"sid0@fb.com","sentAt":"2014-03-27T14:09:10Z","receivedAt":"2014-03-27T14:09:10Z","isPatch":true,"sender":{"key":"sid0@fb.com","avatar":null},"body":"On 03/26/2014 03:40 PM, Siddharth Agarwal wrote:\n> On 03/26/2014 12:22 AM, Jeff King wrote:\n>> [tl;dr the patch is the same as before, but there is a script to measure\n>>         its effects; please try it out on your repos]\n\nHere are the numbers from another, much larger repo:\n\nTest                         origin HEAD\n------------------------------------------------------------------------------------ \n\n5311.3: server   (1 days)    11.72(14.02+1.44) 6.33(5.87+0.75) -46.0%\n5311.4: size     (1 days) 19.4M                     15.3M -21.3%\n5311.5: client   (1 days)    6.99(8.06+1.50) 10.60(10.34+1.83) +51.6%\n5311.7: server   (2 days)    39.82(40.56+3.05) 33.94(31.21+3.10) -14.8%\n5311.8: size     (2 days) 26.5M                     22.8M -14.1%\n5311.9: client   (2 days)    15.81(16.48+4.29) 19.20(18.20+4.19) +21.4%\n5311.11: server   (4 days)   37.21(39.75+3.73) 28.01(26.97+1.75) -24.7%\n5311.12: size     (4 days) 37.5M                     34.1M -9.0%\n5311.13: client   (4 days)   24.24(26.43+6.76) 31.14(30.75+5.96) +28.5%\n5311.15: server   (8 days)   33.74(40.47+3.39) 22.42(22.25+1.51) -33.6%\n5311.16: size     (8 days) 81.9M                     78.4M -4.2%\n5311.17: client   (8 days)   81.96(91.07+22.35) 88.03(89.45+17.11) +7.4%\n5311.19: server  (16 days)   30.87(34.57+2.78) 27.03(25.93+2.73) -12.4%\n5311.20: size    (16 days) 153.2M                    150.9M -1.5%\n5311.21: client  (16 days)   169.99(183.57+46.96) 177.12(177.17+37.93) \n+4.2%\n5311.23: server  (32 days)   51.00(75.49+4.62) 19.52(19.28+1.93) -61.7%\n5311.24: size    (32 days) 279.4M                    283.0M +1.3%\n5311.25: client  (32 days)   272.43(296.17+76.48) 284.75(285.98+63.19) \n+4.5%\n5311.27: server  (64 days)   51.73(97.88+6.40) 37.32(32.63+5.05) -27.9%\n5311.28: size    (64 days) 1.7G                      1.8G +5.0%\n5311.29: client  (64 days)   2600.42(2751.56+718.10) \n2429.06(2501.29+651.56) -6.6%\n5311.31: server (128 days)   51.33(95.33+6.91) 37.73(32.98+5.09) -26.5%\n5311.32: size   (128 days) 1.7G                      1.8G +5.0%\n5311.33: client (128 days)   2595.68(2739.45+729.07) \n2386.99(2524.54+583.07) -8.0%\n"},{"id":"237911","messageId":"xmqq8urvfvjd.fsf@gitster.dls.corp.google.com","threadId":"36296","inReplyTo":"20140327011323.GA9266@sigill.intra.peff.net","subject":"Re: [PATCH/RFC 0/6] reuse deltas found by bitmaps","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-03-27T16:36:38Z","receivedAt":"2014-03-27T16:36:38Z","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> But for a small fetch...\n>\n>   5311.3: server   (1 days)    0.20(0.17+0.03)   4.39(4.03+6.59) +2095.0%\n>   5311.4: size     (1 days)              57.2K             59.5K +4.1%\n>   5311.5: client   (1 days)    0.08(0.08+0.00)   0.08(0.08+0.00) +0.0%\n\nNice ;-)\n\n> So this is a dead end, but I think it was good to double-check that.\n\nThanks.\n"},{"id":"237982","messageId":"CAPig+cSRVSBU-RsWTYgRqvRp76Ot9FjjXVyS476vA+CNOSozuA@mail.gmail.com","threadId":"36296","inReplyTo":"20140326072338.GF32193@sigill.intra.peff.net","subject":"Re: [PATCH 6/6] pack-objects: reuse deltas for thin \"have\" objects","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2014-03-28T04:23:29Z","receivedAt":"2014-03-28T04:23:29Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Wed, Mar 26, 2014 at 3:23 AM, Jeff King <peff@peff.net> wrote:\n> When we calculate the \"wants\" and \"haves\" for a pack, we\n> only add the objects in the boundary commits as preferred\n> bases. However, we know that every object reachable from the\n> \"haves\" could be a preferred base.\n>\n> We probably don't want to add these to our preferred base\n> list, because they would clog the delta-search window.\n> However, there is no reason we cannot reuse an on-disk delta\n> against such a deep \"have\" base, avoiding the delta search\n> for that object altogether.\n>\n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n>  builtin/pack-objects.c | 16 +++++++++++++++-\n>  1 file changed, 15 insertions(+), 1 deletion(-)\n>\n> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\n> index 7950c43..92bd682 100644\n> --- a/builtin/pack-objects.c\n> +++ b/builtin/pack-objects.c\n> @@ -53,6 +53,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>  static int pack_compression_level = Z_DEFAULT_COMPRESSION;\n> @@ -1419,6 +1420,20 @@ static void check_object(struct object_entry *entry)\n>                         base_entry->delta_child = entry;\n>                         unuse_pack(&w_curs);\n>                         return;\n> +               } else if(thin && base_ref && bitmap_have(base_ref)) {\n\nMissing space after 'if'.\n\n> +                       entry->type = entry->in_pack_type;\n> +                       entry->delta_size = entry->size;\n> +                       /*\n> +                        * XXX we'll leak this, but it's probably OK\n> +                        * since we'll exit immediately after the packing\n> +                        * is done\n> +                        */\n> +                       entry->delta = xcalloc(1, sizeof(*entry->delta));\n> +                       hashcpy(entry->delta->idx.sha1, base_ref);\n> +                       entry->delta->preferred_base = 1;\n> +                       entry->delta->filled = 1;\n> +                       unuse_pack(&w_curs);\n> +                       return;\n>                 }\n>\n>                 if (entry->type) {\n> @@ -2559,7 +2574,6 @@ static int option_parse_ulong(const struct option *opt,\n>  int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n>  {\n>         int use_internal_rev_list = 0;\n> -       int thin = 0;\n>         int all_progress_implied = 0;\n>         const char *rp_av[6];\n>         int rp_ac = 0;\n> --\n> 1.9.1.601.g7ec968e\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at  http://vger.kernel.org/majordomo-info.html\n"}]}