{"thread":{"id":"8998","subject":"[PATCH] apply delta depth bias to already deltified objects","startedAt":"2007-07-12T06:38:30Z","lastAt":"2007-07-12T18:33:21Z","messageCount":6,"participants":["Nicolas Pitre","Brian Downing"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"47121","messageId":"alpine.LFD.0.999.0707120049120.32552@xanadu.home","threadId":"8998","inReplyTo":null,"subject":"[PATCH] apply delta depth bias to already deltified objects","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-07-12T06:38:30Z","receivedAt":"2007-07-12T06:38:30Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"\nWe already apply a bias on the initial delta attempt with max_size being \na function of the base object depth.  This already has the effect of \nfavoring shallower deltas even if deeper deltas could be smaller, and \ntherefore creating a wider delta tree (see commits 4e8da195 and \nc3b06a69).\n\nThis principle should also be applied to all delta attempts for the same \nobject and not only the first attempt.  With this the criteria for the \nbest delta is not only its size but also its depth, so that a shallower \ndelta might be selected even if it is larger than a deeper one.  Even if \nsome deltas get larger, they allow for wider delta trees making the \ndepth limit less quickly reached and therefore better deltas can be \nsubsequently found, keeping the resulting pack size equal or even \nsmaller.  Runtime access to the pack should also benefit from shallower \ndeltas.\n\nTesting on the GIT repo before this patch provided those numbers:\n\n$ git repack -a -f --depth=10\nTotal 56534 (delta 39441), reused 0 (delta 0)\n29.38user 0.33system 0:29.73elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+20996minor)pagefaults 0swaps\n\n$ git verify-pack -v\nchain length = 1: 3150 objects\nchain length = 2: 2713 objects\nchain length = 3: 2441 objects\nchain length = 4: 2205 objects\nchain length = 5: 2014 objects\nchain length = 6: 1895 objects\nchain length = 7: 1802 objects\nchain length = 8: 1997 objects\nchain length = 9: 2710 objects\nchain length = 10: 18514 objects\n\nPack size is 18273039 bytes.\n\nWith this patch:\n\n$ git repack -a -f --depth=10\nTotal 56534 (delta 39370), reused 0 (delta 0)\n24.32user 0.35system 0:24.78elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+19142minor)pagefaults 0swaps\n\n$ git verify-pack -v\nchain length = 1: 4059 objects\nchain length = 2: 4048 objects\nchain length = 3: 3775 objects\nchain length = 4: 3428 objects\nchain length = 5: 3007 objects\nchain length = 6: 2793 objects\nchain length = 7: 2701 objects\nchain length = 8: 2988 objects\nchain length = 9: 3935 objects\nchain length = 10: 8636 objects\n\nPack size is 16311008 bytes.\n\nSummary: this patch makes for slightly faster repacks, a smaller pack, \nand a much lower count of object hanging on the max delta depth.\n\nSame repo again with the default depth of 50:\n\nBefore:\nTotal 56534 (delta 39545), reused 0 (delta 0)\n23.01user 0.36system 0:23.40elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+21017minor)pagefaults 0swaps\nchain length = 1: 2882 objects\nchain length = 2: 2443 objects\nchain length = 3: 2157 objects\n[...]\nchain length = 48: 505 objects\nchain length = 49: 782 objects\nchain length = 50: 1802 objects\nPack size: 14651260 bytes.\n\nAfter:\n\nTotal 56534 (delta 39596), reused 0 (delta 0)\n22.98user 0.20system 0:23.20elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+20560minor)pagefaults 0swaps\nchain length = 1: 2985 objects\nchain length = 2: 2625 objects\nchain length = 3: 2282 objects\n[...]\nchain length = 48: 477 objects\nchain length = 49: 564 objects\nchain length = 50: 392 objects\nPack size: 14383165 bytes.\n\nWith the Linux kernel repo:\n\nBefore:\n\nTotal 531582 (delta 431824), reused 0 (delta 0)\n276.66user 3.64system 4:45.35elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+149606minor)pagefaults 0swaps\nchain length = 1: 40779 objects\nchain length = 2: 35650 objects\nchain length = 3: 30226 objects\nchain length = 4: 25619 objects\nchain length = 5: 21709 objects\n[...]\nchain length = 46: 2223 objects\nchain length = 47: 3263 objects\nchain length = 48: 3175 objects\nchain length = 49: 2128 objects\nchain length = 50: 6413 objects\nPack size: 155680720 bytes.\n\nAfter:\n\nTotal 531582 (delta 432537), reused 0 (delta 0)\n270.31user 3.15system 4:35.07elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+140517minor)pagefaults 0swaps\nchain length = 1: 41555 objects\nchain length = 2: 36919 objects\nchain length = 3: 31217 objects\nchain length = 4: 26762 objects\nchain length = 5: 22348 objects\n[...]\nchain length = 46: 1842 objects\nchain length = 47: 1800 objects\nchain length = 48: 1483 objects\nchain length = 49: 1216 objects\nchain length = 50: 1310 objects\nPack size: 154421656 bytes.\n\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n\nThis apparently makes BRian's patological case worse (although better \nthan before his same-size-shallower patch), but I think that the \nimprovement in the general case is worth it.  Even Brian's pack gets \nsmaller so...\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 54b9d26..1eb86ed 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -1332,12 +1332,14 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \n \t/* Now some size filtering heuristics. */\n \ttrg_size = trg_entry->size;\n-\tmax_size = trg_size/2 - 20;\n+\tif (!trg_entry->delta)\n+\t\tmax_size = trg_size/2 - 20;\n+\telse\n+\t\tmax_size = trg_entry->delta_size * max_depth /\n+\t\t\t\t(max_depth - trg_entry->depth + 1);\n \tmax_size = max_size * (max_depth - src_entry->depth) / max_depth;\n \tif (max_size == 0)\n \t\treturn 0;\n-\tif (trg_entry->delta && trg_entry->delta_size <= max_size)\n-\t\tmax_size = trg_entry->delta_size;\n \tsrc_size = src_entry->size;\n \tsizediff = src_size < trg_size ? trg_size - src_size : 0;\n \tif (sizediff >= max_size)\n"},{"id":"47170","messageId":"20070712152016.GB19073@lavos.net","threadId":"8998","inReplyTo":"alpine.LFD.0.999.0707120049120.32552@xanadu.home","subject":"Re: [PATCH] apply delta depth bias to already deltified objects","fromName":"Brian Downing","fromEmail":"bdowning@lavos.net","sentAt":"2007-07-12T15:20:16Z","receivedAt":"2007-07-12T15:20:16Z","isPatch":true,"sender":{"key":"bdowning@lavos.net","avatar":"https://avatars.githubusercontent.com/u/366426?v=4"},"body":"On Thu, Jul 12, 2007 at 02:38:30AM -0400, Nicolas Pitre wrote:\n> This apparently makes BRian's patological case worse (although better \n> than before his same-size-shallower patch), but I think that the \n> improvement in the general case is worth it.  Even Brian's pack gets \n> smaller so...\n\nI've found why this makes my case worse, and I think it's correctable\nand will benefit everything when fixed:\n\nLet's say we've currently got a delta match of 11 bytes at depth 5.\nSo trg_entry->delta_size = 11 and trg_entry->depth = 5.  max_depth is\n100.\n\nNow let's say the next object we're comparing against is at depth 2\n(src_entry->depth = 2).  Even if we can find a delta of the same size\nwe should take it.\n\nNow, with Nico's new patch:\n\n\t\tmax_size = trg_entry->delta_size * max_depth /\n\t\t\t\t(max_depth - trg_entry->depth + 1);\n\nmax_size is now 11.  So far so good.\n\nNow, however, the other bias happens:\n\n\tmax_size = max_size * (max_depth - src_entry->depth) / max_depth;\n\n    max_size = 11 * (100 - 2) / 100;\n    max_size = 1078 / 100;\n    max_size = 10;\n\nThis was okay when max_size was always (trg_size/2 - 20) here, but now\nit's cutting it off too much.  max_size is now 10, and we can't make\na better depth match of the same size anymore.\n\nI think the second bias equation should be scaled so as not to take\neffect unless (src_entry->depth [+ 1?] > trg_entry->depth).\n\nOther than this flaw I think this patch looks great.\n\n-bcd\n"},{"id":"47174","messageId":"alpine.LFD.0.999.0707121146550.32552@xanadu.home","threadId":"8998","inReplyTo":"20070712152016.GB19073@lavos.net","subject":"Re: [PATCH] apply delta depth bias to already deltified objects","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-07-12T16:27:02Z","receivedAt":"2007-07-12T16:27:02Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 12 Jul 2007, Brian Downing wrote:\n\n> On Thu, Jul 12, 2007 at 02:38:30AM -0400, Nicolas Pitre wrote:\n> > This apparently makes BRian's patological case worse (although better \n> > than before his same-size-shallower patch), but I think that the \n> > improvement in the general case is worth it.  Even Brian's pack gets \n> > smaller so...\n> \n> I've found why this makes my case worse, and I think it's correctable\n> and will benefit everything when fixed:\n> \n> Let's say we've currently got a delta match of 11 bytes at depth 5.\n> So trg_entry->delta_size = 11 and trg_entry->depth = 5.  max_depth is\n> 100.\n> \n> Now let's say the next object we're comparing against is at depth 2\n> (src_entry->depth = 2).  Even if we can find a delta of the same size\n> we should take it.\n> \n> Now, with Nico's new patch:\n> \n> \t\tmax_size = trg_entry->delta_size * max_depth /\n> \t\t\t\t(max_depth - trg_entry->depth + 1);\n> \n> max_size is now 11.  So far so good.\n> \n> Now, however, the other bias happens:\n> \n> \tmax_size = max_size * (max_depth - src_entry->depth) / max_depth;\n> \n>     max_size = 11 * (100 - 2) / 100;\n>     max_size = 1078 / 100;\n>     max_size = 10;\n\nHmmm... Integer truncation errors.\n\nIn theory, the allowed max_size should be slightly higher than what we \ngot in the depth 5 case because this case is less deep.  So...\n\n    max_size = trg_entry->delta_size * max_depth /\n                    (max_depth - trg_entry->depth + 1);\n    max_size = 11 * 100 / (100 - 5 + 1) = 11.4583\n\n    max_size = max_size * (max_depth - src_entry->depth) / max_depth;\n    max_size = 11.4583 * (100 - 2) / 100 = 11.2292\n\nSo the max_size, because the depth is less, is slightly higher.\n\n> This was okay when max_size was always (trg_size/2 - 20) here, but now\n> it's cutting it off too much.  max_size is now 10, and we can't make\n> a better depth match of the same size anymore.\n> \n> I think the second bias equation should be scaled so as not to take\n> effect unless (src_entry->depth [+ 1?] > trg_entry->depth).\n\nBetter yet, the integer truncation error should be compensated for, with \nthis:\n\n    max_size =\n        (trg_entry->delta_size * max_depth + max_depth - trg_entry->depth) /\n                    (max_depth - trg_entry->depth + 1);\n\n\nNicolas\n"},{"id":"47176","messageId":"20070712164458.GC19073@lavos.net","threadId":"8998","inReplyTo":"alpine.LFD.0.999.0707121146550.32552@xanadu.home","subject":"Re: [PATCH] apply delta depth bias to already deltified objects","fromName":"Brian Downing","fromEmail":"bdowning@lavos.net","sentAt":"2007-07-12T16:44:58Z","receivedAt":"2007-07-12T16:44:58Z","isPatch":true,"sender":{"key":"bdowning@lavos.net","avatar":"https://avatars.githubusercontent.com/u/366426?v=4"},"body":"On Thu, Jul 12, 2007 at 12:27:02PM -0400, Nicolas Pitre wrote:\n> Better yet, the integer truncation error should be compensated for, with \n> this:\n> \n>     max_size =\n>         (trg_entry->delta_size * max_depth + max_depth - trg_entry->depth) /\n>                     (max_depth - trg_entry->depth + 1);\n\nYep, with this, my degenerate case seems to find the optimum solution\n(depth ~ 65) even at crazy maximum depths like 1000.\n\nLooks good to me.\n\n-bcd\n"},{"id":"47182","messageId":"alpine.LFD.0.999.0707121404090.32552@xanadu.home","threadId":"8998","inReplyTo":"20070712164458.GC19073@lavos.net","subject":"Re: [PATCH] apply delta depth bias to already deltified objects","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-07-12T18:07:27Z","receivedAt":"2007-07-12T18:07:27Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 12 Jul 2007, Brian Downing wrote:\n\n> On Thu, Jul 12, 2007 at 12:27:02PM -0400, Nicolas Pitre wrote:\n> > Better yet, the integer truncation error should be compensated for, with \n> > this:\n> > \n> >     max_size =\n> >         (trg_entry->delta_size * max_depth + max_depth - trg_entry->depth) /\n> >                     (max_depth - trg_entry->depth + 1);\n> \n> Yep, with this, my degenerate case seems to find the optimum solution\n> (depth ~ 65) even at crazy maximum depths like 1000.\n> \n> Looks good to me.\n\nGreat.\n\nNow to conclude this, I have a patch with much simpler math which I'll \npost rsn.\n\n\nNicolas\n"},{"id":"47185","messageId":"alpine.LFD.0.999.0707121415450.32552@xanadu.home","threadId":"8998","inReplyTo":"alpine.LFD.0.999.0707120049120.32552@xanadu.home","subject":"[PATCH] apply delta depth bias to already deltified objects","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-07-12T18:33:21Z","receivedAt":"2007-07-12T18:33:21Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"We already apply a bias on the initial delta attempt with max_size being \na function of the base object depth.  This has the effect of favoring \nshallower deltas even if deeper deltas could be smaller, and therefore \ncreating a wider delta tree (see commits 4e8da195 and c3b06a69).\n\nThis principle should also be applied to all delta attempts for the same \nobject and not only the first attempt.  With this the criteria for the \nbest delta is not only its size but also its depth, so that a shallower \ndelta might be selected even if it is larger than a deeper one.  Even if \nsome deltas get larger, they allow for wider delta trees making the \ndepth limit less quickly reached and therefore better deltas can be \nsubsequently found, keeping the resulting pack size even smaller.  \nRuntime access to the pack should also benefit from shallower deltas.\n\nTesting on different repositories showed slighter faster repacks, \nsmaller resulting packs, and a much nicer curve for delta depth \ndistribution with no more peak at the maximum depth level.  \nImprovements are even more significant with smaller depth limits.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n\nNo, I wonn't provide the full test results again.  Yes, they're \ndifferent and even slightly better with this version, but I can't be \nbothered to run them all and wait for the results again.  You'll have to \ntake my word or do your own.\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 54b9d26..b4f3e7c 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -1303,6 +1303,7 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \tstruct object_entry *trg_entry = trg->entry;\n \tstruct object_entry *src_entry = src->entry;\n \tunsigned long trg_size, src_size, delta_size, sizediff, max_size, sz;\n+\tunsigned ref_depth;\n \tenum object_type type;\n \tvoid *delta_buf;\n \n@@ -1332,12 +1333,17 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \n \t/* Now some size filtering heuristics. */\n \ttrg_size = trg_entry->size;\n-\tmax_size = trg_size/2 - 20;\n-\tmax_size = max_size * (max_depth - src_entry->depth) / max_depth;\n+\tif (!trg_entry->delta) {\n+\t\tmax_size = trg_size/2 - 20;\n+\t\tref_depth = 1;\n+\t} else {\n+\t\tmax_size = trg_entry->delta_size;\n+\t\tref_depth = trg_entry->depth;\n+\t}\n+\tmax_size = max_size * (max_depth - src_entry->depth) /\n+\t\t\t\t\t\t(max_depth - ref_depth + 1);\n \tif (max_size == 0)\n \t\treturn 0;\n-\tif (trg_entry->delta && trg_entry->delta_size <= max_size)\n-\t\tmax_size = trg_entry->delta_size;\n \tsrc_size = src_entry->size;\n \tsizediff = src_size < trg_size ? trg_size - src_size : 0;\n \tif (sizediff >= max_size)\n"}]}