{"thread":{"id":"3967","subject":"[PATCH/RFC] reverse the pack-objects delta window logic","startedAt":"2006-04-26T03:37:21Z","lastAt":"2006-04-28T01:56:00Z","messageCount":9,"participants":["Nicolas Pitre","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"19131","messageId":"Pine.LNX.4.64.0604252330190.18520@localhost.localdomain","threadId":"3967","inReplyTo":null,"subject":"[PATCH/RFC] reverse the pack-objects delta window logic","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-26T03:37:21Z","receivedAt":"2006-04-26T03:37:21Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"This allows for keeping a single delta index constant while delta \ntargets are tested against the same base object.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n\n---\n\nNote, this is a RFC particularly to Junio since the resulting pack is \nlarger than without the patch with git-repack -a -f.  However using a \nsubsequent git-repack -a brings the pack size down to expected size.  So \nI'm not sure I've got everything right.\n\ndiff --git a/pack-objects.c b/pack-objects.c\nindex c0acc46..33027a8 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -19,19 +19,17 @@ struct object_entry {\n \tunsigned long offset;\t/* offset into the final pack file;\n \t\t\t\t * nonzero if already written.\n \t\t\t\t */\n-\tunsigned int depth;\t/* delta depth */\n-\tunsigned int delta_limit;\t/* base adjustment for in-pack delta */\n+\tunsigned int delta_limit;\t/* deepest delta from this object */\n \tunsigned int hash;\t/* name hint hash */\n \tenum object_type type;\n \tenum object_type in_pack_type;\t/* could be delta */\n \tunsigned long delta_size;\t/* delta data size (uncompressed) */\n \tstruct object_entry *delta;\t/* delta base object */\n-\tstruct packed_git *in_pack; \t/* already in pack */\n-\tunsigned int in_pack_offset;\n \tstruct object_entry *delta_child; /* delitified objects who bases me */\n \tstruct object_entry *delta_sibling; /* other deltified objects who\n-\t\t\t\t\t     * uses the same base as me\n-\t\t\t\t\t     */\n+\t\t\t\t\t       uses the same base as me */\n+\tstruct packed_git *in_pack; \t/* already in pack */\n+\tunsigned int in_pack_offset;\n \tint preferred_base;\t/* we do not pack this, but is encouraged to\n \t\t\t\t * be used as the base objectto delta huge\n \t\t\t\t * objects against.\n@@ -906,11 +904,11 @@ static void get_object_details(void)\n \tfor (i = 0, entry = objects; i < nr_objects; i++, entry++)\n \t\tcheck_object(entry);\n \n-\tif (nr_objects == nr_result) {\n+\tif (!no_reuse_delta && nr_objects == nr_result) {\n \t\t/*\n-\t\t * Depth of objects that depend on the entry -- this\n-\t\t * is subtracted from depth-max to break too deep\n-\t\t * delta chain because of delta data reusing.\n+\t\t * We must determine the maximum depth of reused deltas\n+\t\t * for those objects used as their base before find_deltas()\n+\t\t * starts considering them as potential delta targets.\n \t\t * However, we loosen this restriction when we know we\n \t\t * are creating a thin pack -- it will have to be\n \t\t * expanded on the other end anyway, so do not\n@@ -1004,64 +1002,78 @@ struct unpacked {\n  * more importantly, the bigger file is likely the more recent\n  * one.\n  */\n-static int try_delta(struct unpacked *cur, struct unpacked *old, unsigned max_depth)\n+static int try_delta(struct unpacked *trg, struct unpacked *src,\n+\t\t     struct delta_index *src_index, unsigned max_depth)\n {\n-\tstruct object_entry *cur_entry = cur->entry;\n-\tstruct object_entry *old_entry = old->entry;\n-\tunsigned long size, oldsize, delta_size, sizediff;\n-\tlong max_size;\n+\tstruct object_entry *trg_entry = trg->entry;\n+\tstruct object_entry *src_entry = src->entry;\n+\tunsigned long size, src_size, delta_size, sizediff, max_size;\n \tvoid *delta_buf;\n \n \t/* Don't bother doing diffs between different types */\n-\tif (cur_entry->type != old_entry->type)\n+\tif (trg_entry->type != src_entry->type)\n \t\treturn -1;\n \n \t/* We do not compute delta to *create* objects we are not\n \t * going to pack.\n \t */\n-\tif (cur_entry->preferred_base)\n-\t\treturn -1;\n+\tif (trg_entry->preferred_base)\n+\t\treturn 0;\n \n-\t/* If the current object is at pack edge, take the depth the\n-\t * objects that depend on the current object into account --\n-\t * otherwise they would become too deep.\n+\t/*\n+\t * Make sure deltifying this object won't make its deepest delta\n+\t * too deep, but only when not producing a thin pack.\n \t */\n-\tif (cur_entry->delta_child) {\n-\t\tif (max_depth <= cur_entry->delta_limit)\n-\t\t\treturn 0;\n-\t\tmax_depth -= cur_entry->delta_limit;\n-\t}\n-\n-\tsize = cur_entry->size;\n-\toldsize = old_entry->size;\n-\tsizediff = oldsize > size ? oldsize - size : size - oldsize;\n+\tif (nr_objects == nr_result && trg_entry->delta_limit >= max_depth)\n+\t\treturn 0;\n \n+\t/* Now some size filtering euristics. */\n+\tsize = trg_entry->size;\n \tif (size < 50)\n-\t\treturn -1;\n-\tif (old_entry->depth >= max_depth)\n \t\treturn 0;\n-\n-\t/*\n-\t * NOTE!\n-\t *\n-\t * We always delta from the bigger to the smaller, since that's\n-\t * more space-efficient (deletes don't have to say _what_ they\n-\t * delete).\n-\t */\n \tmax_size = size / 2 - 20;\n-\tif (cur_entry->delta)\n-\t\tmax_size = cur_entry->delta_size-1;\n+\tif (trg_entry->delta)\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 \tif (sizediff >= max_size)\n \t\treturn 0;\n-\tdelta_buf = diff_delta(old->data, oldsize,\n-\t\t\t       cur->data, size, &delta_size, max_size);\n+\n+\tdelta_buf = create_delta(src_index, trg->data, size, &delta_size, max_size);\n \tif (!delta_buf)\n \t\treturn 0;\n-\tcur_entry->delta = old_entry;\n-\tcur_entry->delta_size = delta_size;\n-\tcur_entry->depth = old_entry->depth + 1;\n+\n+\tif (trg_entry->delta) {\n+\t\t/*\n+\t\t * The target object already has a delta base but we just\n+\t\t * found a better one.  Remove it from its former base\n+\t\t * childhood and redetermine the base delta_limit (if used).\n+\t\t */\n+\t\tstruct object_entry *base = trg_entry->delta;\n+\t\tstruct object_entry **child_link = &base->delta_child;\n+\t\tbase->delta_limit = 0;\n+\t\twhile (*child_link) {\n+\t\t\tif (*child_link == trg_entry) {\n+\t\t\t\t*child_link = trg_entry->delta_sibling;\n+\t\t\t\tif (nr_objects != nr_result)\n+\t\t\t\t\tbreak;\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tif (base->delta_limit <= (*child_link)->delta_limit)\n+\t\t\t\tbase->delta_limit =\n+\t\t\t\t\t(*child_link)->delta_limit + 1;\n+\t\t\tchild_link = &(*child_link)->delta_sibling;\n+\t\t}\n+\t}\n+\n+\ttrg_entry->delta = src_entry;\n+\ttrg_entry->delta_size = delta_size;\n+\ttrg_entry->delta_sibling = src_entry->delta_child;\n+\tsrc_entry->delta_child = trg_entry;\n+\tif (src_entry->delta_limit <= trg_entry->delta_limit)\n+\t\tsrc_entry->delta_limit = trg_entry->delta_limit + 1;\n \tfree(delta_buf);\n-\treturn 0;\n+\treturn 1;\n }\n \n static void progress_interval(int signum)\n@@ -1078,14 +1090,15 @@ static void find_deltas(struct object_en\n \tunsigned last_percent = 999;\n \n \tmemset(array, 0, array_size);\n-\ti = nr_objects;\n+\ti = 0;\n \tidx = 0;\n \tif (progress)\n \t\tfprintf(stderr, \"Deltifying %d objects.\\n\", nr_result);\n \n-\twhile (--i >= 0) {\n-\t\tstruct object_entry *entry = list[i];\n+\twhile (i < nr_objects) {\n+\t\tstruct object_entry *entry = list[i++];\n \t\tstruct unpacked *n = array + idx;\n+\t\tstruct delta_index *delta_index;\n \t\tunsigned long size;\n \t\tchar type[10];\n \t\tint j;\n@@ -1113,7 +1126,13 @@ static void find_deltas(struct object_en\n \t\tn->entry = entry;\n \t\tn->data = read_sha1_file(entry->sha1, type, &size);\n \t\tif (size != entry->size)\n-\t\t\tdie(\"object %s inconsistent object length (%lu vs %lu)\", sha1_to_hex(entry->sha1), size, entry->size);\n+\t\t\tdie(\"object %s inconsistent object length (%lu vs %lu)\",\n+\t\t\t    sha1_to_hex(entry->sha1), size, entry->size);\n+\t\tif (!size)\n+\t\t\tcontinue;\n+\t\tdelta_index = create_delta_index(n->data, size);\n+\t\tif (!delta_index)\n+\t\t\tdie(\"out of memory\");\n \n \t\tj = window;\n \t\twhile (--j > 0) {\n@@ -1124,18 +1143,10 @@ 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, depth) < 0)\n+\t\t\tif (try_delta(m, n, delta_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\tfree_delta_index(delta_index);\n \t\tidx++;\n \t\tif (idx >= window)\n \t\t\tidx = 0;\n"},{"id":"19135","messageId":"7vpsj4sxer.fsf@assigned-by-dhcp.cox.net","threadId":"3967","inReplyTo":"Pine.LNX.4.64.0604252330190.18520@localhost.localdomain","subject":"Re: [PATCH/RFC] reverse the pack-objects delta window logic","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-26T05:45:00Z","receivedAt":"2006-04-26T05:45:00Z","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> Note, this is a RFC particularly to Junio since the resulting pack is \n> larger than without the patch with git-repack -a -f.  However using a \n> subsequent git-repack -a brings the pack size down to expected size.  So \n> I'm not sure I've got everything right.\n\nI haven't tested it seriously yet, but there is nothing that\nlooks obviously wrong that might cause the inflation problem,\nfrom the cursory look after applying the patch on top of your\nlast round.\n\n> +\tif (nr_objects == nr_result && trg_entry->delta_limit >= max_depth)\n> +\t\treturn 0;\n\nThe older code was loosening this check only for a delta chain\nthat is already in pack (which is limited to its previous\nmax_depth).  The end result is almost the same -- a thin pack\nrecipient would have deeper delta than it asked. The difference\nis that the earlier code had implicit 2*max_depth limit, but\nthis one makes the chain length unbounded, which I do not think\nit is necessarily a bad change.  In any case it does not explain\nwhy you are getting larger resulting pack, though.\n\n> +\t/* Now some size filtering euristics. */\n> +\tsize = trg_entry->size;\n>  \tif (size < 50)\n> -\t\treturn -1;\n> -\tif (old_entry->depth >= max_depth)\n>  \t\treturn 0;\n\nThis is necessary because you are scanning from smaller to\nlarger, and I think it is a good change.\n\n> -\t/*\n> -\t * NOTE!\n> -\t *\n> -\t * We always delta from the bigger to the smaller, since that's\n> -\t * more space-efficient (deletes don't have to say _what_ they\n> -\t * delete).\n> -\t */\n\nThis comment by Linus still applies, even though the scan order\nis now reversed; no need to remove it.\n\n> +\n> +\tif (trg_entry->delta) {\n> +\t\t/*\n> +\t\t * The target object already has a delta base but we just\n> +\t\t * found a better one.  Remove it from its former base\n> +\t\t * childhood and redetermine the base delta_limit (if used).\n> +\t\t */\n\nAnd you are making the delta chain unbound for thin case, you\ncan probably omit this with the same if() here; the\nrecomputation seems rather expensive.\n\n> +\t\t\tdie(\"object %s inconsistent object length (%lu vs %lu)\",\n> +\t\t\t    sha1_to_hex(entry->sha1), size, entry->size);\n> +\t\tif (!size)\n> +\t\t\tcontinue;\n> +\t\tdelta_index = create_delta_index(n->data, size);\n> +\t\tif (!delta_index)\n> +\t\t\tdie(\"out of memory\");\n\nIt might be worth saying \"if (size < 50)\" here as well; no point\nwasting the delta window for small sources.\n\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\nI was almost tempted to suggest that the degradation you are\nseeing might be related to this mystery I did not get around to\nsolve.  By allowing to give chance to try delta against less\noptimum candidates, it appeared that we ended up making the\nfinal pack size bigger than otherwise, which suggests that our\nchoice between plain undeltified and a delta half its size might\nbe favoring delta too much.  But it does not appear to be\nrelated to the inflation you are seeing.\n\nWith object list taken between v1.2.3..v1.3.0 in git.git\nrepository and without delta reuse, 3054 objects are packed\n(delta 1734) with this code.  The \"next\" makes 1818 delta (only\n5% more), which makes me suspect that it is making a bad choice\nof delta base, because the final pack size is 1.5M vs 1.9M.\n\nThe chain length distribution is a bit different (run\n\"git-verify-pack -v\" and look at the end of its output).\n\nThe \"next\" version:\n\nchain length = 1: 257 objects\nchain length = 2: 189 objects\nchain length = 3: 156 objects\nchain length = 4: 149 objects\nchain length = 5: 113 objects\nchain length = 6: 105 objects\nchain length = 7: 105 objects\nchain length = 8: 102 objects\nchain length = 9: 103 objects\nchain length = 10: 539 objects\n\nthis version:\n\nchain length = 1: 415 objects\nchain length = 2: 333 objects\nchain length = 3: 259 objects\nchain length = 4: 197 objects\nchain length = 5: 155 objects\nchain length = 6: 134 objects\nchain length = 7: 106 objects\nchain length = 8: 69 objects\nchain length = 9: 47 objects\nchain length = 10: 19 objects\n\nThe resulting pack would be faster to access (it has much\nshorter median chain length).\n\nBTW, have you tried it without --no-reuse-pack on an object list\nthat is not thin?  It appears you are busting the depth limit.\n\nUsing the same \"git rev-list --objects v1.2.3..v1.3.0\" as input,\ngit-pack-objects without --no-reuse-pack gives this\ndistribution:\n\nchain length = 1: 364 objects\nchain length = 2: 269 objects\nchain length = 3: 198 objects\nchain length = 4: 164 objects\nchain length = 5: 148 objects\nchain length = 6: 123 objects\nchain length = 7: 122 objects\nchain length = 8: 103 objects\nchain length = 9: 92 objects\nchain length = 10: 234 objects\nchain length = 11: 12 objects\nchain length = 12: 1 object\nchain length = 13: 2 objects\n\nSo it _might_ be that the depth limiting code is subtly broken\nwhich is causing you throw away a perfectly good delta base\nwhich in turn results in a bad pack.  The distribution from the\n\"next\" version looks like this:\n\nchain length = 1: 358 objects\nchain length = 2: 250 objects\nchain length = 3: 214 objects\nchain length = 4: 169 objects\nchain length = 5: 150 objects\nchain length = 6: 122 objects\nchain length = 7: 126 objects\nchain length = 8: 100 objects\nchain length = 9: 101 objects\nchain length = 10: 232 objects\n\n\n-- >8 --\n\nSummary of the experiment.\n\n# test dataset\ngit rev-list --objects v1.2.3..v1.3.0 >RL-1.2.3--1.3.0\n\n# baseline: \"next\" version is what is on my $PATH\ngit-pack-objects --no-reuse-delta test-next-pack-nr <RL-1.2.3--1.3.0\ngit-verify-pack -v test-next-pack-nr-*.pack | tail -n 20\ngit-pack-objects test-next-pack <RL-1.2.3--1.3.0\ngit-verify-pack -v test-next-pack-*.pack | tail -n 20\n\n# freshly compiled version with the patch in question\n./git-pack-objects --no-reuse-delta test-nico-pack-nr <RL-1.2.3--1.3.0\ngit-verify-pack -v test-nico-pack-nr-*.pack | tail -n 20\n./git-pack-objects test-nico-pack <RL-1.2.3--1.3.0\ngit-verify-pack -v test-nico-pack-*.pack | tail -n 20\n"},{"id":"19159","messageId":"Pine.LNX.4.64.0604261108430.18520@localhost.localdomain","threadId":"3967","inReplyTo":"7vpsj4sxer.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH/RFC] reverse the pack-objects delta window logic","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-26T15:48:53Z","receivedAt":"2006-04-26T15:48:53Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 25 Apr 2006, Junio C Hamano wrote:\n\n> Nicolas Pitre <nico@cam.org> writes:\n> \n> > Note, this is a RFC particularly to Junio since the resulting pack is \n> > larger than without the patch with git-repack -a -f.  However using a \n> > subsequent git-repack -a brings the pack size down to expected size.  So \n> > I'm not sure I've got everything right.\n> \n> I haven't tested it seriously yet, but there is nothing that\n> looks obviously wrong that might cause the inflation problem,\n> from the cursory look after applying the patch on top of your\n> last round.\n> \n> > +\tif (nr_objects == nr_result && trg_entry->delta_limit >= max_depth)\n> > +\t\treturn 0;\n> \n> The older code was loosening this check only for a delta chain\n> that is already in pack (which is limited to its previous\n> max_depth).  The end result is almost the same -- a thin pack\n> recipient would have deeper delta than it asked. The difference\n> is that the earlier code had implicit 2*max_depth limit,\n\nAh.  Indeed.  Didn't realize that.  I can restore that behavior quite \neasily if necessary.\n\n> but this one makes the chain length unbounded, which I do not think it \n> is necessarily a bad change.\n\nWell as long as the thin pack doesn't carry too many revisions it should \nbe fine since, as the comment in the code sais, those packs are always \nunpacked.\n\nInitially I had a bug where the delta depth was completely ignored.  I \nwas pretty excited when repacking the kernel produced a pack 20% smaller \nalthough I didn't know why at that time.  But when attempting another \ngit-repack -a -f then the initial object counting was sooooooo \nslooooooooow.\n\n> > -\t/*\n> > -\t * NOTE!\n> > -\t *\n> > -\t * We always delta from the bigger to the smaller, since that's\n> > -\t * more space-efficient (deletes don't have to say _what_ they\n> > -\t * delete).\n> > -\t */\n> \n> This comment by Linus still applies, even though the scan order\n> is now reversed; no need to remove it.\n\nThis is not exactly true.  In general it is so, but as we fixed the \ndeltification of objects with the same name but in different directories \nit is well possible to go from smaller to larger and leaving that \ncomment there is misleading.\n\nThis is also why I changed the sizediff rule such that:\n\n\tsizediff = src_size < size ? size - src_size : 0;\n\nSince the src buffer already has its delta index computed, it costs \nalmost nothing to attempt matching much smaller objects against it.  \nHowever if we go from small to larger then the previous logic still \napplies.\n\n> > +\tif (trg_entry->delta) {\n> > +\t\t/*\n> > +\t\t * The target object already has a delta base but we just\n> > +\t\t * found a better one.  Remove it from its former base\n> > +\t\t * childhood and redetermine the base delta_limit (if used).\n> > +\t\t */\n> \n> And you are making the delta chain unbound for thin case, you\n> can probably omit this with the same if() here; the\n> recomputation seems rather expensive.\n\nAh right.  I was doing so partly, but I can skip any tree maintenance \naltogether in that case as well.\n\n> > +\t\tif (!size)\n> > +\t\t\tcontinue;\n> > +\t\tdelta_index = create_delta_index(n->data, size);\n> > +\t\tif (!delta_index)\n> > +\t\t\tdie(\"out of memory\");\n> \n> It might be worth saying \"if (size < 50)\" here as well; no point\n> wasting the delta window for small sources.\n\nGood point.  No real effect on the pack size though.\n\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> \n> I was almost tempted to suggest that the degradation you are\n> seeing might be related to this mystery I did not get around to\n> solve.  By allowing to give chance to try delta against less\n> optimum candidates, it appeared that we ended up making the\n> final pack size bigger than otherwise, which suggests that our\n> choice between plain undeltified and a delta half its size might\n> be favoring delta too much.  But it does not appear to be\n> related to the inflation you are seeing.\n\nCertainly not, since git-repack -a may only delta _more_ and the pack \nsize actualy goes down a lot in my case.\n\nThe mystery I'm facing is why would a second pass with git-repack -a fix \nthings?  It has a different window behavior since objects already \ndeltified do not occupy window space. Hmmm.  That would certainly \nexplain why doing a git-repack -a after a git-repack -a -f produces a \nsmaller pack even currently.\n\n> BTW, have you tried it without --no-reuse-pack on an object list\n> that is not thin?  It appears you are busting the depth limit.\n> \n> Using the same \"git rev-list --objects v1.2.3..v1.3.0\" as input,\n> git-pack-objects without --no-reuse-pack gives this\n> distribution:\n> \n> chain length = 1: 364 objects\n> chain length = 2: 269 objects\n> chain length = 3: 198 objects\n> chain length = 4: 164 objects\n> chain length = 5: 148 objects\n> chain length = 6: 123 objects\n> chain length = 7: 122 objects\n> chain length = 8: 103 objects\n> chain length = 9: 92 objects\n> chain length = 10: 234 objects\n> chain length = 11: 12 objects\n> chain length = 12: 1 object\n> chain length = 13: 2 objects\n\nOops.  OK fixed.\n\n> So it _might_ be that the depth limiting code is subtly broken\n> which is causing you throw away a perfectly good delta base\n> which in turn results in a bad pack.\n\nActually no.  That bug instead allowed each given base to deltify more \ntargets than it should have.\n\n\nNicolas\n"},{"id":"19163","messageId":"Pine.LNX.4.64.0604261341200.18520@localhost.localdomain","threadId":"3967","inReplyTo":"7vpsj4sxer.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH/RFC] reverse the pack-objects delta window logic","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-26T17:48:13Z","receivedAt":"2006-04-26T17:48:13Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 25 Apr 2006, Junio C Hamano wrote:\n\n> Nicolas Pitre <nico@cam.org> writes:\n> \n> > Note, this is a RFC particularly to Junio since the resulting pack is \n> > larger than without the patch with git-repack -a -f.  However using a \n> > subsequent git-repack -a brings the pack size down to expected size.  So \n> > I'm not sure I've got everything right.\n> \n> I haven't tested it seriously yet, but there is nothing that\n> looks obviously wrong that might cause the inflation problem,\n> from the cursory look after applying the patch on top of your\n> last round.\n\nNever mind.  I found a flaw in the determination of delta_limit when \nreparenting a delta target.  The immediate parent's delta_limit is \nreadjusted when its longest delta is moved to another base, but if that \nparent was itself a delta then the delta_limit adjustment is not \npropagated back up to the top.  This means that some objects were \nfalsely credited with too high delta_limit.\n\nAnd actually I'm not sure how to solve that without walking the tree \nup to the top each time, which I want to avoid as much as possible.\n\n\nNicolas\n"},{"id":"19170","messageId":"Pine.LNX.4.64.0604262210120.18520@localhost.localdomain","threadId":"3967","inReplyTo":"Pine.LNX.4.64.0604261341200.18520@localhost.localdomain","subject":"Re: [PATCH/RFC] reverse the pack-objects delta window logic","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-27T03:05:43Z","receivedAt":"2006-04-27T03:05:43Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 26 Apr 2006, Nicolas Pitre wrote:\n\n> On Tue, 25 Apr 2006, Junio C Hamano wrote:\n> \n> > Nicolas Pitre <nico@cam.org> writes:\n> > \n> > > Note, this is a RFC particularly to Junio since the resulting pack is \n> > > larger than without the patch with git-repack -a -f.  However using a \n> > > subsequent git-repack -a brings the pack size down to expected size.  So \n> > > I'm not sure I've got everything right.\n> > \n> > I haven't tested it seriously yet, but there is nothing that\n> > looks obviously wrong that might cause the inflation problem,\n> > from the cursory look after applying the patch on top of your\n> > last round.\n> \n> Never mind.  I found a flaw in the determination of delta_limit when \n> reparenting a delta target.  The immediate parent's delta_limit is \n> readjusted when its longest delta is moved to another base, but if that \n> parent was itself a delta then the delta_limit adjustment is not \n> propagated back up to the top.  This means that some objects were \n> falsely credited with too high delta_limit.\n> \n> And actually I'm not sure how to solve that without walking the tree \n> up to the top each time, which I want to avoid as much as possible.\n\nWell, that seems to be unavoidable.\n\nReversing the window logic isn't that much of a good idea after all.  As \nsoon as we need to control the delta depth we sorta need to maintain \ntrees of deltas and those trees are built from leaves up to the trunk.  \n\nBut each new object in the list is then used as a possible\nnew base for previously created deltas still in the object window.  When \nthe new base is determined to produce a better delta then the \nrelationship with the old base must be broken, which means that the \ninformation about delta length for the old base has to be updated.  And \nif the detached delta chain was the longest for that old base then the \nremaining longest delta chain from that old base has to be found and \nthat information reflected up to the ultimate base in that tree.  And \ndoing so isn't necessarily trivial as can be seen in the patch below.\n\nThen there is the possibility of having a delta \"branch\" with maximum \ndepth meaning that the trunk for that branch may not be deltified. But \nif a later objects to come does constitute a better delta base for the \nobject in the middle of that branch then the branch will be broken in \nthe middle to be transplanted onto the new base as explained previously.  \nWhich means that the initial trunk no longer has a maximum \ndepth and \nsome objects that were skipped because of the depth limit could \nnow have been tested, leading to suboptimal delta matching.  This is why \nrunning pack-objects a second time improved things as it picked up \nthose missed delta opportunities.  But having to run pack-objects \nmultiple times is a bit against the point, and even if pack-objects \nprocessed the object list multiple times it certainly won't be \nfaster than the current code.\n\nIn short, trying to deltify objects by keeping the base object constant \nfor the match window really sucks, even from a theoretical point of \nview.  It does produce sensibly larger \npacks and it does take longer to do so.  I'm therefore dropping that \napproach.  My current patch can be found below.  If someone \nsmarter than me (there are plenty I'm sure) can come with improvements \nto it then be my guest.\n\nTherefore I really think the best approach is to simply keep delta index \ndata along with object data in the match window and keep the current \nwindow direction for matching.  It obviously will take up more memory, \nbut most probably less than if we set the window size = 20.  And \nbuilding delta trees from the trunk to the leaves will always be optimal \nregardless with no delta rebasing needed.  I'll post another patch doing \njust that.\n\n---\n\ndiff --git a/pack-objects.c b/pack-objects.c\nindex c0acc46..17280fb 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -19,19 +19,17 @@ struct object_entry {\n \tunsigned long offset;\t/* offset into the final pack file;\n \t\t\t\t * nonzero if already written.\n \t\t\t\t */\n-\tunsigned int depth;\t/* delta depth */\n-\tunsigned int delta_limit;\t/* base adjustment for in-pack delta */\n+\tunsigned int delta_limit;\t/* deepest delta from this object */\n \tunsigned int hash;\t/* name hint hash */\n \tenum object_type type;\n \tenum object_type in_pack_type;\t/* could be delta */\n \tunsigned long delta_size;\t/* delta data size (uncompressed) */\n \tstruct object_entry *delta;\t/* delta base object */\n-\tstruct packed_git *in_pack; \t/* already in pack */\n-\tunsigned int in_pack_offset;\n \tstruct object_entry *delta_child; /* delitified objects who bases me */\n \tstruct object_entry *delta_sibling; /* other deltified objects who\n-\t\t\t\t\t     * uses the same base as me\n-\t\t\t\t\t     */\n+\t\t\t\t\t       uses the same base as me */\n+\tstruct packed_git *in_pack; \t/* already in pack */\n+\tunsigned int in_pack_offset;\n \tint preferred_base;\t/* we do not pack this, but is encouraged to\n \t\t\t\t * be used as the base objectto delta huge\n \t\t\t\t * objects against.\n@@ -884,17 +882,16 @@ static void check_object(struct object_e\n \t\t    sha1_to_hex(entry->sha1), type);\n }\n \n-static unsigned int check_delta_limit(struct object_entry *me, unsigned int n)\n+static unsigned int find_delta_limit(struct object_entry *me)\n {\n \tstruct object_entry *child = me->delta_child;\n-\tunsigned int m = n;\n \twhile (child) {\n-\t\tunsigned int c = check_delta_limit(child, n + 1);\n-\t\tif (m < c)\n-\t\t\tm = c;\n+\t\tunsigned int c = find_delta_limit(child);\n+\t\tif (me->delta_limit <= c)\n+\t\t\tme->delta_limit = c + 1;\n \t\tchild = child->delta_sibling;\n \t}\n-\treturn m;\n+\treturn me->delta_limit;\n }\n \n static void get_object_details(void)\n@@ -906,11 +903,11 @@ static void get_object_details(void)\n \tfor (i = 0, entry = objects; i < nr_objects; i++, entry++)\n \t\tcheck_object(entry);\n \n-\tif (nr_objects == nr_result) {\n+\tif (!no_reuse_delta && nr_objects == nr_result) {\n \t\t/*\n-\t\t * Depth of objects that depend on the entry -- this\n-\t\t * is subtracted from depth-max to break too deep\n-\t\t * delta chain because of delta data reusing.\n+\t\t * We must determine the maximum depth of reused deltas\n+\t\t * for those objects used as their base before find_deltas()\n+\t\t * starts considering them as potential delta targets.\n \t\t * However, we loosen this restriction when we know we\n \t\t * are creating a thin pack -- it will have to be\n \t\t * expanded on the other end anyway, so do not\n@@ -919,8 +916,7 @@ static void get_object_details(void)\n \t\t */\n \t\tfor (i = 0, entry = objects; i < nr_objects; i++, entry++)\n \t\t\tif (!entry->delta && entry->delta_child)\n-\t\t\t\tentry->delta_limit =\n-\t\t\t\t\tcheck_delta_limit(entry, 1);\n+\t\t\t\tfind_delta_limit(entry);\n \t}\n }\n \n@@ -994,6 +990,7 @@ static int type_size_sort(const struct o\n struct unpacked {\n \tstruct object_entry *entry;\n \tvoid *data;\n+\tint pos;\n };\n \n /*\n@@ -1004,64 +1001,94 @@ struct unpacked {\n  * more importantly, the bigger file is likely the more recent\n  * one.\n  */\n-static int try_delta(struct unpacked *cur, struct unpacked *old, unsigned max_depth)\n+static int try_delta(struct unpacked *trg, struct unpacked *src,\n+\t\t     struct delta_index *src_index, unsigned max_depth)\n {\n-\tstruct object_entry *cur_entry = cur->entry;\n-\tstruct object_entry *old_entry = old->entry;\n-\tunsigned long size, oldsize, delta_size, sizediff;\n-\tlong max_size;\n+\tstruct object_entry *trg_entry = trg->entry;\n+\tstruct object_entry *src_entry = src->entry;\n+\tunsigned long size, src_size, delta_size, sizediff, max_size;\n \tvoid *delta_buf;\n \n \t/* Don't bother doing diffs between different types */\n-\tif (cur_entry->type != old_entry->type)\n+\tif (trg_entry->type != src_entry->type)\n \t\treturn -1;\n \n \t/* We do not compute delta to *create* objects we are not\n \t * going to pack.\n \t */\n-\tif (cur_entry->preferred_base)\n-\t\treturn -1;\n+\tif (trg_entry->preferred_base)\n+\t\treturn 0;\n \n-\t/* If the current object is at pack edge, take the depth the\n-\t * objects that depend on the current object into account --\n-\t * otherwise they would become too deep.\n+\t/*\n+\t * Make sure deltifying this object won't make its deepest delta\n+\t * too deep, but only when not producing a thin pack.\n \t */\n-\tif (cur_entry->delta_child) {\n-\t\tif (max_depth <= cur_entry->delta_limit)\n-\t\t\treturn 0;\n-\t\tmax_depth -= cur_entry->delta_limit;\n-\t}\n-\n-\tsize = cur_entry->size;\n-\toldsize = old_entry->size;\n-\tsizediff = oldsize > size ? oldsize - size : size - oldsize;\n+\tif (trg_entry->delta_limit >= max_depth && nr_objects == nr_result)\n+\t\treturn 0;\n \n+\t/* Now some size filtering euristics. */\n+\tsize = trg_entry->size;\n \tif (size < 50)\n-\t\treturn -1;\n-\tif (old_entry->depth >= max_depth)\n \t\treturn 0;\n-\n-\t/*\n-\t * NOTE!\n-\t *\n-\t * We always delta from the bigger to the smaller, since that's\n-\t * more space-efficient (deletes don't have to say _what_ they\n-\t * delete).\n-\t */\n \tmax_size = size / 2 - 20;\n-\tif (cur_entry->delta)\n-\t\tmax_size = cur_entry->delta_size-1;\n+\tif (trg_entry->delta)\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 \tif (sizediff >= max_size)\n \t\treturn 0;\n-\tdelta_buf = diff_delta(old->data, oldsize,\n-\t\t\t       cur->data, size, &delta_size, max_size);\n+\n+\tdelta_buf = create_delta(src_index, trg->data, size, &delta_size, max_size);\n \tif (!delta_buf)\n \t\treturn 0;\n-\tcur_entry->delta = old_entry;\n-\tcur_entry->delta_size = delta_size;\n-\tcur_entry->depth = old_entry->depth + 1;\n+\n+\tif (trg_entry->delta && nr_objects == nr_result) {\n+\t\t/*\n+\t\t * The target object already has a delta base but we just\n+\t\t * found a better one.  Remove it from its former base\n+\t\t * childhood and redetermine the base delta_limit.\n+\t\t * But again, only when not creating a thin pack.\n+\t\t */\n+\t\tstruct object_entry *base = trg_entry->delta;\n+\t\tstruct object_entry **child_link = &base->delta_child;\n+\t\tunsigned int limit = base->delta_limit;\n+\t\tbase->delta_limit = 0;\n+\t\twhile (*child_link) {\n+\t\t\tif (*child_link == trg_entry) {\n+\t\t\t\t*child_link = trg_entry->delta_sibling;\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tif (base->delta_limit <= (*child_link)->delta_limit)\n+\t\t\t\tbase->delta_limit =\n+\t\t\t\t\t(*child_link)->delta_limit + 1;\n+\t\t\tchild_link = &(*child_link)->delta_sibling;\n+\t\t}\n+\t\tif (base->delta_limit == limit)\n+\t\t\tgoto out;\n+\t\twhile ((base = base->delta) && ++limit == base->delta_limit) {\n+\t\t\tstruct object_entry *child = base->delta_child;\n+\t\t\tbase->delta_limit = 0;\n+\t\t\tdo {\n+\t\t\t\tif(base->delta_limit <= child->delta_limit) {\n+\t\t\t\t\tbase->delta_limit =\n+\t\t\t\t\t\tchild->delta_limit + 1;\n+\t\t\t\t\tif (base->delta_limit == limit)\n+\t\t\t\t\t\tgoto out;\n+\t\t\t\t}\n+\t\t\t\tchild = child->delta_sibling;\n+\t\t\t} while (child);\n+\t\t}\n+\t\tout:;\n+\t}\n+\n+\ttrg_entry->delta = src_entry;\n+\ttrg_entry->delta_size = delta_size;\n+\ttrg_entry->delta_sibling = src_entry->delta_child;\n+\tsrc_entry->delta_child = trg_entry;\n+\tif (src_entry->delta_limit <= trg_entry->delta_limit)\n+\t\tsrc_entry->delta_limit = trg_entry->delta_limit + 1;\n \tfree(delta_buf);\n-\treturn 0;\n+\treturn 1;\n }\n \n static void progress_interval(int signum)\n@@ -1078,14 +1105,15 @@ static void find_deltas(struct object_en\n \tunsigned last_percent = 999;\n \n \tmemset(array, 0, array_size);\n-\ti = nr_objects;\n+\ti = 0;\n \tidx = 0;\n \tif (progress)\n \t\tfprintf(stderr, \"Deltifying %d objects.\\n\", nr_result);\n \n-\twhile (--i >= 0) {\n-\t\tstruct object_entry *entry = list[i];\n+\twhile (i < nr_objects) {\n+\t\tstruct object_entry *entry = list[i++];\n \t\tstruct unpacked *n = array + idx;\n+\t\tstruct delta_index *delta_index;\n \t\tunsigned long size;\n \t\tchar type[10];\n \t\tint j;\n@@ -1109,11 +1137,18 @@ static void find_deltas(struct object_en\n \t\t\t */\n \t\t\tcontinue;\n \n+\t\tif (entry->size < 50)\n+\t\t\tcontinue;\n \t\tfree(n->data);\n+\t\tn->pos = i;\n \t\tn->entry = entry;\n \t\tn->data = read_sha1_file(entry->sha1, type, &size);\n \t\tif (size != entry->size)\n-\t\t\tdie(\"object %s inconsistent object length (%lu vs %lu)\", sha1_to_hex(entry->sha1), size, entry->size);\n+\t\t\tdie(\"object %s inconsistent object length (%lu vs %lu)\",\n+\t\t\t    sha1_to_hex(entry->sha1), size, entry->size);\n+\t\tdelta_index = create_delta_index(n->data, size);\n+\t\tif (!delta_index)\n+\t\t\tdie(\"out of memory\");\n \n \t\tj = window;\n \t\twhile (--j > 0) {\n@@ -1124,18 +1159,10 @@ 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, depth) < 0)\n+\t\t\tif (try_delta(m, n, delta_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\tfree_delta_index(delta_index);\n \t\tidx++;\n \t\tif (idx >= window)\n \t\t\tidx = 0;\n"},{"id":"19171","messageId":"Pine.LNX.4.64.0604262351221.18520@localhost.localdomain","threadId":"3967","inReplyTo":"Pine.LNX.4.64.0604262210120.18520@localhost.localdomain","subject":"[PATCH] use delta index data when finding best delta matches","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-27T03:58:00Z","receivedAt":"2006-04-27T03:58:00Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"\nThis patch allows for computing the delta index for each base object \nonly once and reuse it when trying to find the best delta match.\n\nThis should set the mark and pave the way for possibly better delta \ngenerator algorithms.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n\n---\n\n... as mentioned in my previous post\n\ndiff --git a/pack-objects.c b/pack-objects.c\nindex c0acc46..5b2ef9a 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -994,6 +994,7 @@ static int type_size_sort(const struct o\n struct unpacked {\n \tstruct object_entry *entry;\n \tvoid *data;\n+\tstruct delta_index *index;\n };\n \n /*\n@@ -1004,64 +1005,56 @@ struct unpacked {\n  * more importantly, the bigger file is likely the more recent\n  * one.\n  */\n-static int try_delta(struct unpacked *cur, struct unpacked *old, unsigned max_depth)\n+static int try_delta(struct unpacked *trg, struct unpacked *src,\n+\t\t     struct delta_index *src_index, unsigned max_depth)\n {\n-\tstruct object_entry *cur_entry = cur->entry;\n-\tstruct object_entry *old_entry = old->entry;\n-\tunsigned long size, oldsize, delta_size, sizediff;\n-\tlong max_size;\n+\tstruct object_entry *trg_entry = trg->entry;\n+\tstruct object_entry *src_entry = src->entry;\n+\tunsigned long size, src_size, delta_size, sizediff, max_size;\n \tvoid *delta_buf;\n \n \t/* Don't bother doing diffs between different types */\n-\tif (cur_entry->type != old_entry->type)\n+\tif (trg_entry->type != src_entry->type)\n \t\treturn -1;\n \n \t/* We do not compute delta to *create* objects we are not\n \t * going to pack.\n \t */\n-\tif (cur_entry->preferred_base)\n+\tif (trg_entry->preferred_base)\n \t\treturn -1;\n \n-\t/* If the current object is at pack edge, take the depth the\n+\t/*\n+\t * If the current object is at pack edge, take the depth the\n \t * objects that depend on the current object into account --\n \t * otherwise they would become too deep.\n \t */\n-\tif (cur_entry->delta_child) {\n-\t\tif (max_depth <= cur_entry->delta_limit)\n+\tif (trg_entry->delta_child) {\n+\t\tif (max_depth <= trg_entry->delta_limit)\n \t\t\treturn 0;\n-\t\tmax_depth -= cur_entry->delta_limit;\n+\t\tmax_depth -= trg_entry->delta_limit;\n \t}\n-\n-\tsize = cur_entry->size;\n-\toldsize = old_entry->size;\n-\tsizediff = oldsize > size ? oldsize - size : size - oldsize;\n-\n-\tif (size < 50)\n-\t\treturn -1;\n-\tif (old_entry->depth >= max_depth)\n+\tif (src_entry->depth >= max_depth)\n \t\treturn 0;\n \n-\t/*\n-\t * NOTE!\n-\t *\n-\t * We always delta from the bigger to the smaller, since that's\n-\t * more space-efficient (deletes don't have to say _what_ they\n-\t * delete).\n-\t */\n+\t/* Now some size filtering euristics. */\n+\tsize = trg_entry->size;\n \tmax_size = size / 2 - 20;\n-\tif (cur_entry->delta)\n-\t\tmax_size = cur_entry->delta_size-1;\n+\tif (trg_entry->delta)\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 \tif (sizediff >= max_size)\n \t\treturn 0;\n-\tdelta_buf = diff_delta(old->data, oldsize,\n-\t\t\t       cur->data, size, &delta_size, max_size);\n+\n+\tdelta_buf = create_delta(src_index, trg->data, size, &delta_size, max_size);\n \tif (!delta_buf)\n \t\treturn 0;\n-\tcur_entry->delta = old_entry;\n-\tcur_entry->delta_size = delta_size;\n-\tcur_entry->depth = old_entry->depth + 1;\n+\n+\ttrg_entry->delta = src_entry;\n+\ttrg_entry->delta_size = delta_size;\n+\ttrg_entry->depth = src_entry->depth + 1;\n \tfree(delta_buf);\n-\treturn 0;\n+\treturn 1;\n }\n \n static void progress_interval(int signum)\n@@ -1109,11 +1102,19 @@ static void find_deltas(struct object_en\n \t\t\t */\n \t\t\tcontinue;\n \n+\t\tif (entry->size < 50)\n+\t\t\tcontinue;\n+\t\tif (n->index)\n+\t\t\tfree_delta_index(n->index);\n \t\tfree(n->data);\n \t\tn->entry = entry;\n \t\tn->data = read_sha1_file(entry->sha1, type, &size);\n \t\tif (size != entry->size)\n-\t\t\tdie(\"object %s inconsistent object length (%lu vs %lu)\", sha1_to_hex(entry->sha1), size, entry->size);\n+\t\t\tdie(\"object %s inconsistent object length (%lu vs %lu)\",\n+\t\t\t    sha1_to_hex(entry->sha1), size, entry->size);\n+\t\tn->index = create_delta_index(n->data, size);\n+\t\tif (!n->index)\n+\t\t\tdie(\"out of memory\");\n \n \t\tj = window;\n \t\twhile (--j > 0) {\n@@ -1124,7 +1125,7 @@ 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, depth) < 0)\n+\t\t\tif (try_delta(n, m, m->index, depth) < 0)\n \t\t\t\tbreak;\n \t\t}\n #if 0\n@@ -1144,8 +1145,11 @@ #endif\n \tif (progress)\n \t\tfputc('\\n', stderr);\n \n-\tfor (i = 0; i < window; ++i)\n+\tfor (i = 0; i < window; ++i) {\n+\t\tif (array[i].index)\n+\t\t\tfree_delta_index(array[i].index);\n \t\tfree(array[i].data);\n+\t}\n \tfree(array);\n }\n \n"},{"id":"19172","messageId":"7vejzjmwwr.fsf@assigned-by-dhcp.cox.net","threadId":"3967","inReplyTo":"Pine.LNX.4.64.0604262210120.18520@localhost.localdomain","subject":"Re: [PATCH/RFC] reverse the pack-objects delta window logic","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-27T05:04:36Z","receivedAt":"2006-04-27T05:04:36Z","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>> And actually I'm not sure how to solve that without walking the tree \n>> up to the top each time, which I want to avoid as much as possible.\n>\n> Well, that seems to be unavoidable.\n>\n> Reversing the window logic isn't that much of a good idea after all.\n> ...\n\n> Then there is the possibility of having a delta \"branch\" with maximum \n> depth meaning that the trunk for that branch may not be deltified. But \n> if a later objects to come does constitute a better delta base for the \n> object in the middle of that branch then the branch will be broken in \n> the middle to be transplanted onto the new base as explained previously.  \n> Which means that the initial trunk no longer has a maximum depth and some\n> objects that were skipped because of the depth limit could now have been\n> tested, leading to suboptimal delta matching.\n\nGood analysis, and I tend to agree with your conclusion.\n\nBTW, Geert mentioned on the #git channel that about half the\nfilepair git-pack-objects asks diff_delta() to try have long\nsequences of matching bytes at the beginning and at the end.  It\nmight be worthwhile if we can take an advantage of it, whichever\ndelta algorithm we would use.\n"},{"id":"19209","messageId":"7vy7xqh5g6.fsf@assigned-by-dhcp.cox.net","threadId":"3967","inReplyTo":"Pine.LNX.4.64.0604262351221.18520@localhost.localdomain","subject":"Re: [PATCH] use delta index data when finding best delta matches","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-28T01:08:57Z","receivedAt":"2006-04-28T01:08: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 patch allows for computing the delta index for each base object \n> only once and reuse it when trying to find the best delta match.\n>\n> This should set the mark and pave the way for possibly better delta \n> generator algorithms.\n>\n> Signed-off-by: Nicolas Pitre <nico@cam.org>\n\nMy understanding is that theoretically this should not make any\ndifference to the result, and should run faster when the memory\npressure does not cause the machine to thrash.  However,....\n\nI am seeing some differences.  Even with the smallish \"git.git\"\nrepository, packing is slightly slower, and the end result is\nsmaller.\n\nHere are full packing experiments in a fully unpacked git.git\nrepository.\n\n(\"next\" version)\nTotal 17724, written 17724 (delta 11779), reused 0 (delta 0)\n31.61user 6.24system 0:37.97elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+431995minor)pagefaults 0swaps\n\n 6520520 pack-next-f1fac077a093ffdaf094aab2b7f11859ec0c18f1.pack\n\n(with \"use delta index\" patch)\nTotal 17724, written 17724 (delta 12002), reused 0 (delta 0)\n33.26user 6.00system 0:39.33elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+434451minor)pagefaults 0swaps\n\n 6188418 pack-nico-f1fac077a093ffdaf094aab2b7f11859ec0c18f1.pack\n\nNot that I am complaining that it produces better results with a\nsmall performance penalty.  I am curious because I do not\nunderstand where the differences are coming from, and I was\nreluctant to merge it in \"next\" until I understand what is going\non.\n\nBut I think I know where the differences come from:\n\n-\tsizediff = oldsize > size ? oldsize - size : size - oldsize;\n+\tsizediff = src_size < size ? size - src_size : 0;\n\nThere is another \"omit smaller than 50\" difference but that\nshould not trigger -- we do not have files that small.\n\nThe size-diff change sort-of makes sense -- you are counting how\nmuch the target grew, which you are likely to need to represent\nas additions of literal data, and there is no reason to limit\nthe diff if the size difference that is greater than maxsize is\nin the other direction (deletion).\n\nSo, I \"backported\" that part of the change on top of \"next\" and\ntried the same experiment.\n\n(without \"use delta index\" but the size heuristics part ported to \"next\")\nTotal 17724, written 17724 (delta 12002), reused 0 (delta 0)\n36.92user 6.55system 0:43.75elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+431860minor)pagefaults 0swaps\n\n 6188418 pack-size-f1fac077a093ffdaf094aab2b7f11859ec0c18f1.pack\n\nAnd now the resulting pack is the same as what you produce.\n\nSo comparing 31.61 seconds vs 33.26 seconds and complaining you\nmade it slower is not fair.  You fixed the size heuristic logic\nin the current code to produce 5% smaller pack (which made\nthings slower to spend 36.92 seconds while doing so -- that's\n15% slowdown), and then reusing delta-index brought that penalty\ndown to 5% or so.\n\n\n-- >8 --\n\nThis patch applies on top of \"next\" to match the size heuristics\nused in the \"reuse delta index\" patch.\n\n pack-objects.c |   12 ++++++------\n 1 files changed, 6 insertions(+), 6 deletions(-)\n\ndiff --git a/pack-objects.c b/pack-objects.c\nindex c0acc46..6604338 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -1032,12 +1032,6 @@ static int try_delta(struct unpacked *cu\n \t\tmax_depth -= cur_entry->delta_limit;\n \t}\n \n-\tsize = cur_entry->size;\n-\toldsize = old_entry->size;\n-\tsizediff = oldsize > size ? oldsize - size : size - oldsize;\n-\n-\tif (size < 50)\n-\t\treturn -1;\n \tif (old_entry->depth >= max_depth)\n \t\treturn 0;\n \n@@ -1048,9 +1042,12 @@ static int try_delta(struct unpacked *cu\n \t * more space-efficient (deletes don't have to say _what_ they\n \t * delete).\n \t */\n+\tsize = cur_entry->size;\n \tmax_size = size / 2 - 20;\n \tif (cur_entry->delta)\n \t\tmax_size = cur_entry->delta_size-1;\n+\toldsize = old_entry->size;\n+\tsizediff = oldsize < size ? size - oldsize : 0;\n \tif (sizediff >= max_size)\n \t\treturn 0;\n \tdelta_buf = diff_delta(old->data, oldsize,\n@@ -1109,6 +1106,9 @@ static void find_deltas(struct object_en\n \t\t\t */\n \t\t\tcontinue;\n \n+\t\tif (entry->size < 50)\n+\t\t\tcontinue;\n+\n \t\tfree(n->data);\n \t\tn->entry = entry;\n \t\tn->data = read_sha1_file(entry->sha1, type, &size);\n"},{"id":"19210","messageId":"Pine.LNX.4.64.0604272131410.18816@localhost.localdomain","threadId":"3967","inReplyTo":"7vy7xqh5g6.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] use delta index data when finding best delta matches","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-28T01:56:00Z","receivedAt":"2006-04-28T01:56:00Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 27 Apr 2006, Junio C Hamano wrote:\n\n> Nicolas Pitre <nico@cam.org> writes:\n> \n> > This patch allows for computing the delta index for each base object \n> > only once and reuse it when trying to find the best delta match.\n> >\n> > This should set the mark and pave the way for possibly better delta \n> > generator algorithms.\n> >\n> > Signed-off-by: Nicolas Pitre <nico@cam.org>\n> \n> My understanding is that theoretically this should not make any\n> difference to the result, and should run faster when the memory\n> pressure does not cause the machine to thrash.  However,....\n> \n> I am seeing some differences.  Even with the smallish \"git.git\"\n> repository, packing is slightly slower, and the end result is\n> smaller.\n\nWell, I changed some euristics a bit.\n\n> Not that I am complaining that it produces better results with a\n> small performance penalty.  I am curious because I do not\n> understand where the differences are coming from, and I was\n> reluctant to merge it in \"next\" until I understand what is going\n> on.\n> \n> But I think I know where the differences come from:\n> \n> -\tsizediff = oldsize > size ? oldsize - size : size - oldsize;\n> +\tsizediff = src_size < size ? size - src_size : 0;\n\nRight.  The idea is that when the delta source index has to be computed \neach time, if the target buffer is really small then we spend more time \ncomputing that index than anything else.\n\nBut when the delta index is computed only once and already available \nanyway, we don't lose much attempting a delta with a small target buffer \nsince the delta computation is non-existent at that point and the actual \ndelta generation will be quick if the target buffer is small.\n\n> There is another \"omit smaller than 50\" difference but that\n> should not trigger -- we do not have files that small.\n\nRight.  And if such small files show up they won't waste window space.\n\n\nNicolas\n"}]}