{"thread":{"id":"4146","subject":"pack-object mystery explained","startedAt":"2006-05-15T15:29:37Z","lastAt":"2006-05-16T23:34:57Z","messageCount":6,"participants":["Nicolas Pitre","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"20000","messageId":"Pine.LNX.4.64.0605132305580.18071@localhost.localdomain","threadId":"4146","inReplyTo":null,"subject":"pack-object mystery explained","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-05-15T15:29:37Z","receivedAt":"2006-05-15T15:29:37Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"As Junio certainly knows since he added it himself, there is some code \ncurrently surrounded with #if 0 ... #endif in pack-objects.c that was \nmeant to improve delta window usage.\n\nThe idea was to _not_ keep any object in the object window which delta \ndepth reached the maximum depth since it obviously cannot be used as a \nbase for any further deltification anyway.  In doing so the object \nwindow would always be filled only with objects that are not too deep \nand therefore increase the possibility for better delta match.\n\nIn theory... only.\n\nBecause, in practice, doing so produces pack files that are between 20% \nto 60% *larger* than without this \"optimization\".\n\nThis is just so counter-intuitive that I wanted to find out why.  So I \nadded a few lines to output the target object sha1, and the sha1 of each \nobject in the object window as well as the return code from try_delta(), \nthe object depth and the size of the best delta, something like the \nattached patch.  Then diffing the output between a run with the code as \nis and another run with the \"optimization\" enabled produce a really \ninteresting result.\n\nLooking at the diff:\n\n--- /tmp/l1      2006-05-13 22:38:06.000000000 -0400\n+++ /tmp/l2     2006-05-13 23:04:53.000000000 -0400\n@@ -1255,7 +1255,6 @@\n  0 src 57cefdea530171c71c72229a85aa0212dedb2c5a depth 5 delta_sz 115\n nbdelta = 34 deltasz = 25794\n trg f24cfd2b46a65bde53610eecb6998fa615b62363\n- 0 src 0b90fb9ae3396d0f2b0a9ebf9acad8374f3db317 depth 10 delta_sz 0\n  1 src 8866189332568a317183f6f895014519515f67e7 depth 9 delta_sz 20146\n  1 src 4c1b0c3039a84c4c786a09ba70a84df46f995186 depth 8 delta_sz 3357\n  0 src 226d71966d4a0e8a8611ea09e35719688a987ceb depth 7 delta_sz 3357\n@@ -1265,10 +1264,10 @@\n  0 src e44310f5a8115011eafce41362d1752c4ee0f72f depth 3 delta_sz 1365\n  0 src b35d400ee1a2e8b5c97ca6ad82f6d91818519456 depth 2 delta_sz 1365\n  0 src b60fa8d2417c32cf72331e9869d4d3a3208e953f depth 2 delta_sz 1365\n+ 0 src 57cefdea530171c71c72229a85aa0212dedb2c5a depth 5 delta_sz 1365\n nbdelta = 35 deltasz = 27159\n trg 553e1e1749ab537a71c7a1cfb97f18f85dc9ef1f\n  1 src f24cfd2b46a65bde53610eecb6998fa615b62363 depth 6 delta_sz 990\n- 0 src 0b90fb9ae3396d0f2b0a9ebf9acad8374f3db317 depth 10 delta_sz 990\n  0 src 8866189332568a317183f6f895014519515f67e7 depth 9 delta_sz 990\n  0 src 4c1b0c3039a84c4c786a09ba70a84df46f995186 depth 8 delta_sz 990\n  0 src 226d71966d4a0e8a8611ea09e35719688a987ceb depth 7 delta_sz 990\n@@ -1277,11 +1276,11 @@\n  0 src 42b0d59e8c15dff0d72b0d3a486d0248bd767dfe depth 4 delta_sz 248\n  0 src e44310f5a8115011eafce41362d1752c4ee0f72f depth 3 delta_sz 248\n  0 src b35d400ee1a2e8b5c97ca6ad82f6d91818519456 depth 2 delta_sz 248\n+ 0 src b60fa8d2417c32cf72331e9869d4d3a3208e953f depth 2 delta_sz 248\n nbdelta = 36 deltasz = 27407\n[...]\n\nSo the object that reached a delta depth of 10 is clearly not added to \nthe window in the second log.\n\nBut here's the interesting part:\n\n trg f3c92c971e65e9df72fafdab52b4935866a0a794\n- 0 src e85f1c17089a1da95b264909cfc50235c74471da depth 10 delta_sz 0\n- 0 src 134d405ba2e6dd41c7501aa9e078a8879ba8025f depth 10 delta_sz 0\n- 0 src 6a241aab054a8d6b5c021aba77bba795d7684196 depth 10 delta_sz 0\n- 0 src 85cd595802ca565f380a9851efd5a3551c959db0 depth 10 delta_sz 0\n- 0 src 89fda42efb678d2f9f9e802454fe561b4452a167 depth 10 delta_sz 0\n- 0 src c10067c17ff9eef3ce0f01e5c14ba86bd2273d54 depth 10 delta_sz 0\n- 0 src 8e953a67596cf0f5c12f2d8c66055759a7d2201c depth 10 delta_sz 0\n  1 src 553e1e1749ab537a71c7a1cfb97f18f85dc9ef1f depth 6 delta_sz 6223\n  0 src f24cfd2b46a65bde53610eecb6998fa615b62363 depth 6 delta_sz 6223\n- 0 src 0b90fb9ae3396d0f2b0a9ebf9acad8374f3db317 depth 10 delta_sz 6223\n-nbdelta = 44 deltasz = 40076\n+ 1 src 8866189332568a317183f6f895014519515f67e7 depth 9 delta_sz 5135\n+ 0 src 4c1b0c3039a84c4c786a09ba70a84df46f995186 depth 8 delta_sz 5135\n+ 0 src 226d71966d4a0e8a8611ea09e35719688a987ceb depth 7 delta_sz 5135\n+ 0 src 78129ec0cd5fb9767caefee8a8dc1a17dc095bdb depth 6 delta_sz 5135\n+ 0 src 93a50b4444e3bba210f6879795979d0894ad5aaf depth 5 delta_sz 5135\n+ 0 src 42b0d59e8c15dff0d72b0d3a486d0248bd767dfe depth 4 delta_sz 5135\n+ 0 src e44310f5a8115011eafce41362d1752c4ee0f72f depth 3 delta_sz 5135\n+ 0 src b35d400ee1a2e8b5c97ca6ad82f6d91818519456 depth 2 delta_sz 5135\n+nbdelta = 44 deltasz = 38988\n trg fe925609b4024119c6171dd32350a6570bea8516\n- 1 src f3c92c971e65e9df72fafdab52b4935866a0a794 depth 7 delta_sz 99\n- 0 src e85f1c17089a1da95b264909cfc50235c74471da depth 10 delta_sz 99\n- 0 src 134d405ba2e6dd41c7501aa9e078a8879ba8025f depth 10 delta_sz 99\n- 0 src 6a241aab054a8d6b5c021aba77bba795d7684196 depth 10 delta_sz 99\n- 0 src 85cd595802ca565f380a9851efd5a3551c959db0 depth 10 delta_sz 99\n- 0 src 89fda42efb678d2f9f9e802454fe561b4452a167 depth 10 delta_sz 99\n- 0 src c10067c17ff9eef3ce0f01e5c14ba86bd2273d54 depth 10 delta_sz 99\n- 0 src 8e953a67596cf0f5c12f2d8c66055759a7d2201c depth 10 delta_sz 99\n- 0 src 553e1e1749ab537a71c7a1cfb97f18f85dc9ef1f depth 6 delta_sz 99\n- 0 src f24cfd2b46a65bde53610eecb6998fa615b62363 depth 6 delta_sz 99\n-nbdelta = 45 deltasz = 40175\n+ 1 src 553e1e1749ab537a71c7a1cfb97f18f85dc9ef1f depth 6 delta_sz 6006\n+ 0 src f24cfd2b46a65bde53610eecb6998fa615b62363 depth 6 delta_sz 6006\n+ 1 src 8866189332568a317183f6f895014519515f67e7 depth 9 delta_sz 5027\n+ 0 src 4c1b0c3039a84c4c786a09ba70a84df46f995186 depth 8 delta_sz 5027\n+ 0 src 226d71966d4a0e8a8611ea09e35719688a987ceb depth 7 delta_sz 5027\n+ 0 src 78129ec0cd5fb9767caefee8a8dc1a17dc095bdb depth 6 delta_sz 5027\n+ 0 src 93a50b4444e3bba210f6879795979d0894ad5aaf depth 5 delta_sz 5027\n+ 0 src 42b0d59e8c15dff0d72b0d3a486d0248bd767dfe depth 4 delta_sz 5027\n+ 0 src e44310f5a8115011eafce41362d1752c4ee0f72f depth 3 delta_sz 5027\n+ 0 src b35d400ee1a2e8b5c97ca6ad82f6d91818519456 depth 2 delta_sz 5027\n+nbdelta = 45 deltasz = 44015\n[...]\n\nHere we can see that f3c92c97 benefits from a window that has none of \nthose objects with a depth of 10 so it can find a better delta base.  \nBut in doing so it becomes itself depth 10 and is therefore discarded \nfrom the object window right away.  And the unfortunate fact is that \nf3c92c97 would have been the best base for the next object (fe925609) by \nfar with a delta size of 99 bytes instead of 5027 bytes.\n\nAnd then the story repeats itself for a while since fe925609 also \nbecomes depth 10 which means the object window doesn't get refreshed as \nlong as best match are based on 88661893 with a delta size around 5000 \nbytes instead of 100 bytes if f3c92c97 didn't reach depth 10 initially.\n\nSo it is like a priority inversion problem. Instead of evicting max \ndepth objects early to always have a full window of potential usable \nbase object to delta against andimprove the delta packing, this early \neviction of objects with max depth may enter a perverse state where the \nobject window is not recycled with new objects for a while, which is \nespecially bad if the window content is the source of suboptimal delta \nmatches.  And that perverse state will remain until the delta match \nbecomes bad enough to break the link with 88661893.\n\nI thought about recording the second best delta base for any object that \nreached maximum delta depth and reverting to that base whenever an \nobject of maximum depth would allow for a delta of greater saving if it \nwasn't of max depth already and could be used as a delta base again.  \nBut this quickly gets complicated if we want to retroactively consider \nprevious objects that didn't constitute a good enough saving to motivate \nthe switch of given object to its second best base but could benefit \nfrom such a switch if some other objects are making that switch anyway, \nand then it would be necessary to make sure not to exceed the depth of \nobjects already deltified from the object we're considering moving, \netc.  In short it gets really twisted for an incertain gain.\n\nBut... there is still a way to improve things with a really really \nsimple euristic...\n\n\nNicolas\n\n\ndiff --git a/pack-objects.c b/pack-objects.c\nindex 523a1c7..8ff7f30 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -1116,8 +1116,10 @@ static void find_deltas(struct object_en\n \t\tif (!n->index)\n \t\t\tdie(\"out of memory\");\n \n+fprintf(stderr, \"trg %s\\n\", sha1_to_hex(entry->sha1));\n \t\tj = window;\n \t\twhile (--j > 0) {\n+\t\t\tint rc;\n \t\t\tunsigned int other_idx = idx + j;\n \t\t\tstruct unpacked *m;\n \t\t\tif (other_idx >= window)\n@@ -1125,10 +1127,15 @@ static void find_deltas(struct object_en\n \t\t\tm = array + other_idx;\n \t\t\tif (!m->entry)\n \t\t\t\tbreak;\n-\t\t\tif (try_delta(n, m, m->index, depth) < 0)\n+\t\t\trc = try_delta(n, m, m->index, depth);\n+fprintf(stderr, \"% d src %s depth %d delta_sz %d\\n\", rc, sha1_to_hex(m->entry->sha1), m->entry->depth, n->entry->delta_size);\n+\t\t\tif (rc < 0)\n \t\t\t\tbreak;\n \t\t}\n+static int nbdelta=0, deltasz=0;\n+if (n->entry->delta) nbdelta++, deltasz += n->entry->delta_size;\n+fprintf(stderr, \"nbdelta = %d deltasz = %d\\n\", nbdelta, deltasz);\n #if 1\n \t\t/* if we made n a delta, and if n is already at max\n \t\t * depth, leaving it in the window is pointless.  we\n \t\t * should evict it first.\n"},{"id":"20002","messageId":"Pine.LNX.4.64.0605151129540.18071@localhost.localdomain","threadId":"4146","inReplyTo":"Pine.LNX.4.64.0605132305580.18071@localhost.localdomain","subject":"[PATCH] simple euristic for further free packing improvements","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-05-15T15:40:05Z","receivedAt":"2006-05-15T15:40:05Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Given that the early eviction of objects with maximum delta depth \nmay exhibit bad packing on its own, why not considering a bias against \ndeep base objects in try_delta() to mitigate that bad behavior.\n\nThis patch adjust the MAX_size allowed for a delta based on the depth of \nthe base object as well as enabling the early eviction of max depth \nobjects from the object window.  When used separately, those two things \nproduce slightly better and much worse results respectively.  But their \ncombined effect is a surprising significant packing improvement.\n\nWith this really simple patch the GIT repo gets nearly 15% smaller, and \nthe Linux kernel repo about 5% smaller, with no significantly measurable \nCPU usage difference.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n\n---\n\ndiff --git a/pack-objects.c b/pack-objects.c\nindex 523a1c7..b0388d7 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -1038,8 +1038,8 @@ static int try_delta(struct unpacked *tr\n \n \t/* Now some size filtering euristics. */\n \tsize = trg_entry->size;\n-\tmax_size = size / 2 - 20;\n-\tif (trg_entry->delta)\n+\tmax_size = (size/2 - 20) / (src_entry->depth + 1);\n+\tif (trg_entry->delta && trg_entry->delta_size <= max_size)\n \t\tmax_size = trg_entry->delta_size-1;\n \tsrc_size = src_entry->size;\n \tsizediff = src_size < size ? size - src_size : 0;\n@@ -1128,15 +1128,12 @@ static void find_deltas(struct object_en\n \t\t\tif (try_delta(n, m, m->index, depth) < 0)\n \t\t\t\tbreak;\n \t\t}\n-#if 0\n \t\t/* if we made n a delta, and if n is already at max\n \t\t * depth, leaving it in the window is pointless.  we\n \t\t * should evict it first.\n-\t\t * ... in theory only; somehow this makes things worse.\n \t\t */\n \t\tif (entry->delta && depth <= entry->depth)\n \t\t\tcontinue;\n-#endif\n \t\tidx++;\n \t\tif (idx >= window)\n \t\t\tidx = 0;\n"},{"id":"20036","messageId":"7v4pzqhh3t.fsf@assigned-by-dhcp.cox.net","threadId":"4146","inReplyTo":"Pine.LNX.4.64.0605151129540.18071@localhost.localdomain","subject":"Re: [PATCH] simple euristic for further free packing improvements","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-05-16T01:51:34Z","receivedAt":"2006-05-16T01:51:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre <nico@cam.org> writes:\n\n> Given that the early eviction of objects with maximum delta depth \n> may exhibit bad packing on its own, why not considering a bias against \n> deep base objects in try_delta() to mitigate that bad behavior.\n\nThis is really a good stuff.  Thanks.  Oh, and thanks for\nnoticing my puzzlement expressed with \"#if 0\" ;-).\n\n> @@ -1038,8 +1038,8 @@ static int try_delta(struct unpacked *tr\n>  \n>  \t/* Now some size filtering euristics. */\n>  \tsize = trg_entry->size;\n> -\tmax_size = size / 2 - 20;\n> -\tif (trg_entry->delta)\n> +\tmax_size = (size/2 - 20) / (src_entry->depth + 1);\n> +\tif (trg_entry->delta && trg_entry->delta_size <= max_size)\n>  \t\tmax_size = trg_entry->delta_size-1;\n>  \tsrc_size = src_entry->size;\n>  \tsizediff = src_size < size ? size - src_size : 0;\n\nAt the first glance, this seems rather too agressive.  It makes\nme wonder if it is a good balance to penalize the second\ngeneration base by requiring it to produce a small delta that is\nat most half as we normally would (and the third generation a\nthird), or maybe the penalty should kick in more gradually, like\ne.g. ((max_depth * 2 - src_entry->depth) / (max_depth * 2).\n\nHaving said that, judging from your past patches, I learned to\ntrust that you have tried tweaking this part and settled on this\nsimplicity and elegance, so I'll take the patch as is -- if\nsomebody wants to play with it that can always be done to\nfurther improve things.\n"},{"id":"20038","messageId":"Pine.LNX.4.64.0605152237240.18071@localhost.localdomain","threadId":"4146","inReplyTo":"7v4pzqhh3t.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] simple euristic for further free packing improvements","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-05-16T02:53:00Z","receivedAt":"2006-05-16T02:53:00Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 15 May 2006, Junio C Hamano wrote:\n\n> Nicolas Pitre <nico@cam.org> writes:\n> \n> > @@ -1038,8 +1038,8 @@ static int try_delta(struct unpacked *tr\n> >  \n> >  \t/* Now some size filtering euristics. */\n> >  \tsize = trg_entry->size;\n> > -\tmax_size = size / 2 - 20;\n> > -\tif (trg_entry->delta)\n> > +\tmax_size = (size/2 - 20) / (src_entry->depth + 1);\n> > +\tif (trg_entry->delta && trg_entry->delta_size <= max_size)\n> >  \t\tmax_size = trg_entry->delta_size-1;\n> >  \tsrc_size = src_entry->size;\n> >  \tsizediff = src_size < size ? size - src_size : 0;\n> \n> At the first glance, this seems rather too agressive.  It makes\n> me wonder if it is a good balance to penalize the second\n> generation base by requiring it to produce a small delta that is\n> at most half as we normally would (and the third generation a\n> third), or maybe the penalty should kick in more gradually, like\n> e.g. ((max_depth * 2 - src_entry->depth) / (max_depth * 2).\n> \n> Having said that, judging from your past patches, I learned to\n> trust that you have tried tweaking this part and settled on this\n> simplicity and elegance, so I'll take the patch as is -- if\n> somebody wants to play with it that can always be done to\n> further improve things.\n\nActually I didn't play with that part that much.  The only thing I tried \nbesides this version was (size - 20) / (src_entry->depth + 1) but it \nproduced larger packs than the current version.\n\nSo I thought it was better to provide a simple initial rule and leave \npossible improvements for later.\n\n\nNicolas\n"},{"id":"20077","messageId":"Pine.LNX.4.64.0605161510200.18071@localhost.localdomain","threadId":"4146","inReplyTo":"7v4pzqhh3t.fsf@assigned-by-dhcp.cox.net","subject":"[PATCH] improve depth heuristic for maximum delta size","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-05-16T20:29:14Z","receivedAt":"2006-05-16T20:29:14Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"This provides a linear decrement on the penalty related to delta depth\ninstead of being an 1/x function.  With this another 5% reduction is \nobserved on packs for both the GIT repo and the Linux kernel repo, as \nwell as fixing a pack size regression in another sample repo I have.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n\n---\n\nOn Mon, 15 May 2006, Junio C Hamano wrote:\n\n> Nicolas Pitre <nico@cam.org> writes:\n> \n> > @@ -1038,8 +1038,8 @@ static int try_delta(struct unpacked *tr\n> >  \n> >  \t/* Now some size filtering euristics. */\n> >  \tsize = trg_entry->size;\n> > -\tmax_size = size / 2 - 20;\n> > -\tif (trg_entry->delta)\n> > +\tmax_size = (size/2 - 20) / (src_entry->depth + 1);\n> > +\tif (trg_entry->delta && trg_entry->delta_size <= max_size)\n> >  \t\tmax_size = trg_entry->delta_size-1;\n> >  \tsrc_size = src_entry->size;\n> >  \tsizediff = src_size < size ? size - src_size : 0;\n> \n> At the first glance, this seems rather too agressive.  It makes\n> me wonder if it is a good balance to penalize the second\n> generation base by requiring it to produce a small delta that is\n> at most half as we normally would (and the third generation a\n> third), or maybe the penalty should kick in more gradually, like\n> e.g. ((max_depth * 2 - src_entry->depth) / (max_depth * 2).\n\nYou are right.  However your formula converge towards 0.5 which is not \nenough to be sure the bad effect with early eviction of max depth object \nfrom the object window won't come back.  I prefer this patch with a \nformula converging toward 0.\n\ndiff --git a/pack-objects.c b/pack-objects.c\nindex 566a2a2..3116020 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -1036,9 +1036,12 @@ static int try_delta(struct unpacked *tr\n \tif (src_entry->depth >= max_depth)\n \t\treturn 0;\n \n-\t/* Now some size filtering euristics. */\n+\t/* Now some size filtering heuristics. */\n \tsize = trg_entry->size;\n-\tmax_size = (size/2 - 20) / (src_entry->depth + 1);\n+\tmax_size = size/2 - 20;\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-1;\n \tsrc_size = src_entry->size;\n"},{"id":"20093","messageId":"7vmzdh35ni.fsf@assigned-by-dhcp.cox.net","threadId":"4146","inReplyTo":"Pine.LNX.4.64.0605161510200.18071@localhost.localdomain","subject":"Re: [PATCH] improve depth heuristic for maximum delta size","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-05-16T23:34:57Z","receivedAt":"2006-05-16T23:34:57Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre <nico@cam.org> writes:\n\n> This provides a linear decrement on the penalty related to delta depth\n> instead of being an 1/x function.  With this another 5% reduction is \n> observed on packs for both the GIT repo and the Linux kernel repo, as \n> well as fixing a pack size regression in another sample repo I have.\n\nGood job, and it does not seem to spend too many more cycles\neither (it does slow it down a bit because it needs to do more\ndeltas, but that is to be expected).\n\nHere is the average chain length and resulting pack size from\nfull repacking of git.git repository, with three versions.\n\n        Avg 6.20   6516kB (master)\n        Avg 5.97   5784kB (next, has 1/x version)\n        Avg 6.89   5536kB (this patch on top of next)\n\nWhat's interesting is that the 1/x version shortens the chain\n(i.e. decreased runtime cost) while producing smaller results,\ncompared to the master version.  The story is the same on the\nkernel archive.\n\n\tAvg 5.82 113808kB (master)\n\tAvg 4.76 108044kB (next, has 1/x version)\n\tAvg 5.81 105768kB (this patch on top of next)\n"}]}