{"thread":{"id":"43057","subject":"[PATCH] gc: default aggressive depth to 50","startedAt":"2016-08-11T16:13:35Z","lastAt":"2016-08-11T18:52:30Z","messageCount":3,"participants":["Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"293722","messageId":"20160811161309.ecmebaafcz6rkg6o@sigill.intra.peff.net","threadId":"43057","inReplyTo":null,"subject":"[PATCH] gc: default aggressive depth to 50","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-11T16:13:09Z","receivedAt":"2016-08-11T16:13:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This commit message is long and has lots of background and\nnumbers. The summary is: the current default of 250 doesn't\nsave much space, and costs CPU. It's not a good tradeoff.\nRead on for details.\n\nThe \"--aggressive\" flag to git-gc does three things:\n\n  1. use \"-f\" to throw out existing deltas and recompute from\n     scratch\n\n  2. use \"--window=250\" to look harder for deltas\n\n  3. use \"--depth=250\" to make longer delta chains\n\nItems (1) and (2) are good matches for an \"aggressive\"\nrepack. They ask the repack to do more computation work in\nthe hopes of getting a better pack. You pay the costs during\nthe repack, and other operations see only the benefit.\n\nItem (3) is not so clear. Allowing longer chains means fewer\nrestrictions on the deltas, which means potentially finding\nbetter ones and saving some space. But it also means that\noperations which access the deltas have to follow longer\nchains, which affects their performance. So it's a tradeoff,\nand it's not clear that the tradeoff is even a good one.\n\nThe existing \"250\" numbers for \"--aggressive\" come\noriginally from this thread:\n\n  http://public-inbox.org/git/alpine.LFD.0.9999.0712060803430.13796@woody.linux-foundation.org/\n\nwhere Linus says:\n\n  So when I said \"--depth=250 --window=250\", I chose those\n  numbers more as an example of extremely aggressive\n  packing, and I'm not at all sure that the end result is\n  necessarily wonderfully usable. It's going to save disk\n  space (and network bandwidth - the delta's will be re-used\n  for the network protocol too!), but there are definitely\n  downsides too, and using long delta chains may\n  simply not be worth it in practice.\n\nThere are some numbers in that thread, but they're mostly\nfocused on the improved window size, and measure the\nimprovement from --depth=250 and --window=250 together.\nE.g.:\n\n  http://public-inbox.org/git/9e4733910712062006l651571f3w7f76ce64c6650dff@mail.gmail.com/\n\ntalks about the improved run-time of \"git-blame\", which\ncomes from the reduced pack size. But most of that reduction\nis coming from --window=250, whereas most of the extra costs\ncome from --depth=250. There's a link in that thread showing\nthat increasing the depth beyond 50 doesn't seem to help\nmuch with the size:\n\n  https://vcscompare.blogspot.com/2008/06/git-repack-parameters.html\n\nbut again, no discussion of the timing impact.\n\nIn an earlier thread from Ted Ts'o which discussed setting\nthe non-aggressive default (from 10 to 50):\n\n  http://public-inbox.org/git/20070509134958.GA21489%40thunk.org/\n\nwe have more numbers, with the conclusion that going past 50\ndoes not help size much, and hurts the speed of normal\noperations.\n\nSo from that, we might guess that 50 is actually a sweet\nspot, even for aggressive, if we interpret aggressive to\n\"spend time now to make a better pack\". It is not clear that\n\"--depth=250\" is actually a better pack. It may be slightly\n_smaller_, but it carries a run-time penalty.\n\nHere are some more recent timings I did to verify that. They\nshow three things:\n\n  - the size of the resulting pack (so disk saved to store,\n    bandwidth saved on clones/fetches)\n\n  - the cost of \"rev-list --objects --all\", which shows the\n    effect of the delta chains on trees (commits typically\n    don't delta, and the command doesn't touch the blobs at\n    all)\n\n  - the cost of \"log -Sfoo\", which will additionally access\n    each blob\n\nAll cases were repacked with \"git repack -adf --depth=$d\n--window=250\" (so basically, what would happen if we tweaked\nthe \"gc --aggressive\" default depth).\n\nThe timings are all wall-clock best-of-3. The machine itself\nhas plenty of RAM compared to the repositories (which is\nprobably typical of most workstations these days), so we're\nreally measuring CPU usage, as the whole thing will be in\ndisk cache after the first run.\n\nThe core.deltaBaseCacheLimit is at its default of 96MiB.\nIt's possible that tweaking it would have some impact on the\ntests, as some of them (especially \"log -S\" on a large repo)\nare likely to overflow that. But bumping that carries a\nrun-time memory cost, so for these tests, I focused on what\nwe could do just with the on-disk pack tradeoffs.\n\nEach test is done for four depths: 250 (the current value),\n50 (the current default that tested well previously), 100\n(to show something on the larger side, which previous tests\nshowed was not a good tradeoff), and 10 (the very old\ndefault, which previous tests showed was worse than 50).\n\nHere are the numbers for linux.git:\n\n   depth |  size |  %    | rev-list |  %     | log -Sfoo |   %\n  -------+-------+-------+----------+--------+-----------+-------\n    250  | 967MB |  n/a  | 48.159s  |   n/a  | 378.088   |   n/a\n    100  | 971MB | +0.4% | 41.471s  | -13.9% | 342.060   |  -9.5%\n     50  | 979MB | +1.2% | 37.778s  | -21.6% | 311.040s  | -17.7%\n     10  | 1.1GB | +6.6% | 32.518s  | -32.5% | 279.890s  | -25.9%\n\nand for git.git:\n\n   depth |  size |  %    | rev-list |  %     | log -Sfoo |   %\n  -------+-------+-------+----------+--------+-----------+-------\n    250  |  48MB |  n/a  |  2.215s  |   n/a  |  20.922s  |   n/a\n    100  |  49MB | +0.5% |  2.140s  |  -3.4% |  17.736s  | -15.2%\n     50  |  49MB | +1.7% |  2.099s  |  -5.2% |  15.418s  | -26.3%\n     10  |  53MB | +9.3% |  2.001s  |  -9.7% |  12.677s  | -39.4%\n\nYou can see that that the CPU savings for regular operations improves as we\ndecrease the depth. The savings are less for \"rev-list\" on a smaller repository\nthan they are for blob-accessing operations, or even rev-list on a larger\nrepository. This may mean that a larger delta cache would help (though setting\ncore.deltaBaseCacheLimit by itself doesn't).\n\nBut we can also see that the space savings are not that great as the depth goes\nhigher. Saving 5-10% between 10 and 50 is probably worth the CPU tradeoff.\nSaving 1% to go from 50 to 100, or another 0.5% to go from 100 to 250 is\nprobably not.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n Documentation/config.txt | 2 +-\n builtin/gc.c             | 2 +-\n 2 files changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex 0bcb679..8eb403d 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -1366,7 +1366,7 @@ fsck.skipList::\n gc.aggressiveDepth::\n \tThe depth parameter used in the delta compression\n \talgorithm used by 'git gc --aggressive'.  This defaults\n-\tto 250.\n+\tto 50.\n \n gc.aggressiveWindow::\n \tThe window size parameter used in the delta compression\ndiff --git a/builtin/gc.c b/builtin/gc.c\nindex 332bcf7..069950d 100644\n--- a/builtin/gc.c\n+++ b/builtin/gc.c\n@@ -28,7 +28,7 @@ static const char * const builtin_gc_usage[] = {\n \n static int pack_refs = 1;\n static int prune_reflogs = 1;\n-static int aggressive_depth = 250;\n+static int aggressive_depth = 50;\n static int aggressive_window = 250;\n static int gc_auto_threshold = 6700;\n static int gc_auto_pack_limit = 50;\n-- \n2.9.2.790.gaa5bc72\n"},{"id":"293724","messageId":"20160811172050.44abuvwcn6gmcgk7@sigill.intra.peff.net","threadId":"43057","inReplyTo":"20160811161309.ecmebaafcz6rkg6o@sigill.intra.peff.net","subject":"Re: [PATCH] gc: default aggressive depth to 50","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-11T17:20:50Z","receivedAt":"2016-08-11T17:20:57Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 11, 2016 at 12:13:09PM -0400, Jeff King wrote:\n\n> Here are the numbers for linux.git:\n> \n>    depth |  size |  %    | rev-list |  %     | log -Sfoo |   %\n>   -------+-------+-------+----------+--------+-----------+-------\n>     250  | 967MB |  n/a  | 48.159s  |   n/a  | 378.088   |   n/a\n>     100  | 971MB | +0.4% | 41.471s  | -13.9% | 342.060   |  -9.5%\n>      50  | 979MB | +1.2% | 37.778s  | -21.6% | 311.040s  | -17.7%\n>      10  | 1.1GB | +6.6% | 32.518s  | -32.5% | 279.890s  | -25.9%\n> [...]\n> \n> You can see that that the CPU savings for regular operations improves as we\n> decrease the depth. The savings are less for \"rev-list\" on a smaller repository\n> than they are for blob-accessing operations, or even rev-list on a larger\n> repository. This may mean that a larger delta cache would help (though setting\n> core.deltaBaseCacheLimit by itself doesn't).\n\nThe problem with deltaBaseCacheLimit is that it only changes the memory\nparameter, but there are a fixed number of slots in the data structure.\nBumping it like this:\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 02940f1..ca79703 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -2073,7 +2073,7 @@ static void *unpack_compressed_entry(struct packed_git *p,\n \treturn buffer;\n }\n \n-#define MAX_DELTA_CACHE (256)\n+#define MAX_DELTA_CACHE (1024)\n \n static size_t delta_base_cached;\n \n\nalong with the cache size does help (this was discussed a year or two\nago, but nobody ever followed up with numbers or patches).\n\nHere are best-of-3 numbers for rev-list on linux.git at each depth with\nthat patch and \"-c core.deltabasecachelimit=256m\":\n\n  depth |   time\n  ----------------\n   250  | 36.524s\n   100  | 33.200s\n    50  | 31.065s\n    10  | 28.266s\n\nSo there's clearly a lot of room for improvement on the reading side in\ngeneral. And doing so clearly lessens the impact of the delta chains.\nBut you still get a 15% improvement moving to depth=50, versus only a\n1.2% storage increase. So I don't think it fundamentally changes the\nconclusion of the \"depth=50\" patch I'm responding to.\n\nI don't think bumping MAX_DELTA_CACHE naively is a good idea, though. I\nseem to recall that it has scaling problems as it grows, so we may want\na better data structure (but I haven't looked at it recently enough to\nsay anything intelligent). I might work on it in the near future, but if\nanybody is interested, please be my guest.\n\n-Peff\n"},{"id":"293790","messageId":"xmqqmvkj16lc.fsf@gitster.mtv.corp.google.com","threadId":"43057","inReplyTo":"20160811172050.44abuvwcn6gmcgk7@sigill.intra.peff.net","subject":"Re: [PATCH] gc: default aggressive depth to 50","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-08-11T18:52:15Z","receivedAt":"2016-08-11T18:52:30Z","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 Thu, Aug 11, 2016 at 12:13:09PM -0400, Jeff King wrote:\n>\n>> Here are the numbers for linux.git:\n>> \n>>    depth |  size |  %    | rev-list |  %     | log -Sfoo |   %\n>>   -------+-------+-------+----------+--------+-----------+-------\n>>     250  | 967MB |  n/a  | 48.159s  |   n/a  | 378.088   |   n/a\n>>     100  | 971MB | +0.4% | 41.471s  | -13.9% | 342.060   |  -9.5%\n>>      50  | 979MB | +1.2% | 37.778s  | -21.6% | 311.040s  | -17.7%\n>>      10  | 1.1GB | +6.6% | 32.518s  | -32.5% | 279.890s  | -25.9%\n>> [...]\n>> \n>> You can see that that the CPU savings for regular operations improves as we\n>> decrease the depth. The savings are less for \"rev-list\" on a smaller repository\n>> than they are for blob-accessing operations, or even rev-list on a larger\n>> repository. This may mean that a larger delta cache would help (though setting\n>> core.deltaBaseCacheLimit by itself doesn't).\n>\n> The problem with deltaBaseCacheLimit is that it only changes the memory\n> parameter, but there are a fixed number of slots in the data structure.\n> Bumping it like this:\n>\n> diff --git a/sha1_file.c b/sha1_file.c\n> index 02940f1..ca79703 100644\n> --- a/sha1_file.c\n> +++ b/sha1_file.c\n> @@ -2073,7 +2073,7 @@ static void *unpack_compressed_entry(struct packed_git *p,\n>  \treturn buffer;\n>  }\n>  \n> -#define MAX_DELTA_CACHE (256)\n> +#define MAX_DELTA_CACHE (1024)\n>  \n>  static size_t delta_base_cached;\n>\n> along with the cache size does help (this was discussed a year or two\n> ago, but nobody ever followed up with numbers or patches).\n\nYeah, and I also think Linus's \"--depth=250 is just a sample; it\nwill not perform well\" already cited the number of delta-cache\nentries being the limiting factor.\n\n> I don't think bumping MAX_DELTA_CACHE naively is a good idea, though. I\n> seem to recall that it has scaling problems as it grows, so we may want\n> a better data structure (but I haven't looked at it recently enough to\n> say anything intelligent).\n\nMe neither.  In any case, I do think reducing the aggressive depth\ndown to 50 is a very sensible move.  I also suspect that window size\nmay want to be a bit increased (or even made dynamic; the first time\nwe need the window size determined is after to_pack.objects[] array\nis fully populated, so we could use the number of commits as one of\nthe hint, for example), but that can be treated as a separate topic.\n\n\n"}]}