{"thread":{"id":"29356","subject":"thin packs ending up fat","startedAt":"2012-01-12T22:15:23Z","lastAt":"2012-01-13T15:55:36Z","messageCount":12,"participants":["Jeff King","Nicolas Pitre","Junio C Hamano","Ævar Arnfjörð Bjarmason"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"182470","messageId":"20120112221523.GA3663@sigill.intra.peff.net","threadId":"29356","inReplyTo":null,"subject":"thin packs ending up fat","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-01-12T22:15:23Z","receivedAt":"2012-01-12T22:15:23Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"[This ended up long; the gist of it is that we often fail to find thin\n deltas, making small fetches much bigger than they could be. Read on\n for details].\n\nRecently I was doing some work related to bundles containing thin packs,\nand I wanted to generate some thin packs. Much to my surprise, all of my\npacks ended up having no thin objects!\n\nIt turns out that when packing a subset of a fully packed repo (as we do\nfor a bundle or for a fetch), we tend not to make thin packs at all.\nThe culprit is this logic in try_delta:\n\n        /*\n         * We do not bother to try a delta that we discarded\n         * on an earlier try, but only when reusing delta data.\n         */\n        if (reuse_delta && trg_entry->in_pack &&\n            trg_entry->in_pack == src_entry->in_pack &&\n            trg_entry->in_pack_type != OBJ_REF_DELTA &&\n            trg_entry->in_pack_type != OBJ_OFS_DELTA)\n                return 0;\n\nThis does not try to delta objects which are found in the same pack,\nunder the assumption that we would have tried them last time and found\nthat they didn't work. For a complete repack, it works well. We don't\nmiss useful deltas, and it saves a lot of CPU time.\n\nFor a thin pack, though, it means we'll typically fail to actually use\nthe boundary objects. I think what happens is this:\n\n  1. You start at commit C which contains a file with content A. You\n     build commit C', which contains content A'.\n\n  2. You repack the repository, putting A and A' in the pack. Our delta\n     rules tend to create deltas in reverse-recency order, so A\n     typically is stored as a delta based on A', and A' is stored\n     whole.\n\n  3. You try to create a thin pack (e.g., with \"git bundle create\n     foo.bundle C..C'\"). We know that we want to send A', and that we\n     can assume the other side has A to use as a base in our thin pack.\n\n     But the logic above says \"A and A' are both in the same pack, and\n     we didn't find a delta for A'. They must not be a good match\". But\n     in this case it is because our deltas go in the reverse direction,\n     and we never tried them.\n\nSo I did a little experimenting (scripts and inputs are at the end of\nthe email). I generated a thin pack for a subset of objects from my\nfully packed repo, measuring the size of the resulting pack and the CPU\ntime used. I did this both with stock git, and a version of git with the\nabove optimization removed.\n\nI used two datasets to generate the input to pack-objects. In the first,\nI used the reflog entries from my refs/remotes/origin/master ref. That\nsimulates the workload of upload-packs performed for me by kernel.org\nover the last month or so. In the second dataset, I took packed the\nobjects between git v1.0.0 and v1.1.0, between v1.1.0 and v1.2.0, and so\non. This was an attempt to simulate somebody who fetches much less\nfrequently, or perhaps somebody who generates bundles to sneaker-net\nindividual versions.\n\nFor each dataset, I calculated the average size (in bytes) over all of\nthe generated packs in the dataset and the average CPU time used per\npack (in seconds).\n\n                  dataset\n            | fetches | tags\n---------------------------------\n     before | 53358   | 2750977\nsize  after | 32315   | 2652939\n     change |   -39%  |      -4%\n---------------------------------\n     before |  0.18   | 1.12\nCPU   after |  0.19   | 1.50\n     change |    +5%  |     +33%\n\nFor the case of small, frequent packs, we saved a lot of space for a\nlittle bit of extra CPU. But for larger packs, our savings were much\nmore limited, and we spent a lot more CPU time.  That makes sense; this\nis really beneficial for finding extra matches at the boundaries, and\nfor cases where you can avoid sending an entire undeltified object at\nall for a given path.\n\nSo I think this is worth pursuing as an optimization to save bandwidth\non transfers, but it would require figuring out the right times to turn\nit on. My initial idea was that we would want it off whenever we were\ndoing a thin pack. But the \"tags\" dataset shows that it's probably not\nworth the trouble for large packs due to the extra CPU time.\n\nI have a feeling that the case it is generally catching is this \"reverse\ndelta\" case. I.e., A is based off of B, we are including B, but A is\navailable as a thin base. But that can probably be extended into a delta\nchain (A is based from B which is based on C; we want to include B and\nC, but can build off of A as a base. We'll keep the delta from B to C,\nbut we would want to delta C off of A). So detecting that they are part\nof the same chain might require walking the chains.\n\nMaybe it is enough to simply turn off this optimization if the potential\ndelta source is not being included in the pack (i.e., we are using\n--thin and it is a boundary object). Because if both objects are being\nsent, we will just end up reusing the delta that goes in the reverse\ndirection anyway.\n\nOr maybe there is some other clever way of detecting this situation. I'm\nopen to suggestions.\n\n-Peff\n\n---\nThis is the test script I used (feed the dataset files on stdin, get\nlines of sizes and CPU times on stdout):\n\n-- >8 --\n#!/bin/sh\n\nwhile read revs; do\n\tfor i in $revs; do\n\t\techo $i\n\tdone >input\n\techo >&2 \"==> $revs\"\n\ttime -o time.out -f \"%e\" \\\n\t\tgit pack-objects --thin --revs --stdout <input >pack.out\n\techo \"`stat --format=%s pack.out` `cat time.out`\"\ndone\n-- 8< --\n\nand the \"fetch\" dataset:\n\n-- >8 --\n8b0e15fa95e11965f18c8d2585dc8ffd9bfc9356 ^7f41b6bbe3181dc4d1687db036bf22316997a1bf\n34c4461ae3b353e8c931565d5527b98ed12e3735 ^8b0e15fa95e11965f18c8d2585dc8ffd9bfc9356\n463b0ea22b5b9a882e8140d0308433d8cbd0d1fe ^34c4461ae3b353e8c931565d5527b98ed12e3735\n288396994f077eec7e7db0017838a5afbfbf81e3 ^463b0ea22b5b9a882e8140d0308433d8cbd0d1fe\n05f6edcd2a418a88eeb953d51408a6aeef312f5c ^288396994f077eec7e7db0017838a5afbfbf81e3\n08cfdbb88cd6225b4fc4b8a3cecd0e01758c835d ^05f6edcd2a418a88eeb953d51408a6aeef312f5c\n87009edcbd0b4987ccb7ba050a1efe368a315753 ^08cfdbb88cd6225b4fc4b8a3cecd0e01758c835d\n8963314c77af9a4eda5dcbdbab3d4001af83ad81 ^87009edcbd0b4987ccb7ba050a1efe368a315753\n10b2a48113b8ab6b8f48229eb40fc3637ce025ae ^8963314c77af9a4eda5dcbdbab3d4001af83ad81\n997a1946a55cafb992c4ba8e5e0795aa73f5a4a9 ^10b2a48113b8ab6b8f48229eb40fc3637ce025ae\ne8e1c29021da446d0c50573ef9619bf74f515c20 ^997a1946a55cafb992c4ba8e5e0795aa73f5a4a9\n87bf9a7048c623b3567f612ca3e67a0d412fc83d ^e8e1c29021da446d0c50573ef9619bf74f515c20\nee6dfb2d83ba1b057943e705f707fa27e34e47f9 ^87bf9a7048c623b3567f612ca3e67a0d412fc83d\n4cb6764227173a6483edbdad09121651bc0b01c3 ^ee6dfb2d83ba1b057943e705f707fa27e34e47f9\n8a042478967679b0dab3137f5f18367a0ffdc48a ^4cb6764227173a6483edbdad09121651bc0b01c3\n248dbbe83256202f0edd6e1468d01cfbe27fd733 ^8a042478967679b0dab3137f5f18367a0ffdc48a\nbc1bbe0c19a6ff39522b4fa3259f34150e308e1f ^248dbbe83256202f0edd6e1468d01cfbe27fd733\n4d2440fe0daa9ad1556dfd220af8b3a883cf849d ^bc1bbe0c19a6ff39522b4fa3259f34150e308e1f\nf56ef114eeefee755f422e6cbef2d83974cb90f1 ^4d2440fe0daa9ad1556dfd220af8b3a883cf849d\ne14d63198867c545d0662afc00bf7be048bf2231 ^f56ef114eeefee755f422e6cbef2d83974cb90f1\n017d1e134545db0d162908f3538077eaa1f34fb6 ^e14d63198867c545d0662afc00bf7be048bf2231\nfc14b89a7e6899b8ac3b5751ec2d8c98203ea4c2 ^017d1e134545db0d162908f3538077eaa1f34fb6\n406da7803217998ff6bf5dc69c55b1613556c2f4 ^fc14b89a7e6899b8ac3b5751ec2d8c98203ea4c2\n7e02a6c63a183270b726bb21640059ae16fa48ae ^406da7803217998ff6bf5dc69c55b1613556c2f4\n4cb5d10b14dcbe0155bed9c45ccb94e83bd4c599 ^7e02a6c63a183270b726bb21640059ae16fa48ae\n9859a023fef30ffebdd22ad9639c587ac720b8b6 ^4cb5d10b14dcbe0155bed9c45ccb94e83bd4c599\n57526fde5df201a99afa6d122c3266b3a1c5673a ^9859a023fef30ffebdd22ad9639c587ac720b8b6\n73c6b3575bc638b7096ec913bd91193707e2265d ^57526fde5df201a99afa6d122c3266b3a1c5673a\n10f4eb652ee4e592f91f638e579d1afcb96c0408 ^73c6b3575bc638b7096ec913bd91193707e2265d\nee228024933069b93ce23a1bd5eeb7ae12c792f2 ^10f4eb652ee4e592f91f638e579d1afcb96c0408\nd16520499d2652b5b59dfb25f9cf2d56a4c6913a ^ee228024933069b93ce23a1bd5eeb7ae12c792f2\n876a6f4991abdd72ea707b193b4f2b831096ad3c ^d16520499d2652b5b59dfb25f9cf2d56a4c6913a\n8d68493f20db71abeb77adc251b2a116fe45cdaa ^876a6f4991abdd72ea707b193b4f2b831096ad3c\n3daff7c31998faedbe0dd7e2b8651e351be40d64 ^8d68493f20db71abeb77adc251b2a116fe45cdaa\ne443bdfe1e8e1ef8b3665cfd1c1295bd73e13773 ^3daff7c31998faedbe0dd7e2b8651e351be40d64\n5d6dfc7cb140a6eb90138334fab2245b69bc8bc4 ^e443bdfe1e8e1ef8b3665cfd1c1295bd73e13773\nec330158ec04849fe5ff2cb8749797cd63ae592b ^5d6dfc7cb140a6eb90138334fab2245b69bc8bc4\n17b4e93d5b849293e6a3659bbc4075ed8a6e97e2 ^ec330158ec04849fe5ff2cb8749797cd63ae592b\n4570aeb0d85f3b5ff274b6d5a651c2ee06d25d76 ^17b4e93d5b849293e6a3659bbc4075ed8a6e97e2\n247f9d23da8cfd255533433ad2aa07d172afac0b ^4570aeb0d85f3b5ff274b6d5a651c2ee06d25d76\neac2d83247ea0a265d923518c26873bb12c33778 ^247f9d23da8cfd255533433ad2aa07d172afac0b\nbeecc7ab65b31c5471331e64acaa3f722125ea67 ^eac2d83247ea0a265d923518c26873bb12c33778\n7e521640c80b4bb871bca7a9259621a7abb303e7 ^beecc7ab65b31c5471331e64acaa3f722125ea67\n0e1cfc52de002e2d9b0e6562e8672fee3bf45a67 ^7e521640c80b4bb871bca7a9259621a7abb303e7\n-- 8< --\n\nand the \"tags\" dataset:\n\n-- >8 --\nv1.1.0 ^v1.0.0\nv1.2.0 ^v1.1.0\nv1.3.0 ^v1.2.0\nv1.4.0 ^v1.3.0\nv1.5.0 ^v1.4.0\nv1.6.0 ^v1.5.0\nv1.7.0 ^v1.6.0\n-- 8< --\n"},{"id":"182471","messageId":"20120112223234.GA4949@sigill.intra.peff.net","threadId":"29356","inReplyTo":"20120112221523.GA3663@sigill.intra.peff.net","subject":"Re: thin packs ending up fat","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-01-12T22:32:34Z","receivedAt":"2012-01-12T22:32:34Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 12, 2012 at 05:15:23PM -0500, Jeff King wrote:\n\n> It turns out that when packing a subset of a fully packed repo (as we do\n> for a bundle or for a fetch), we tend not to make thin packs at all.\n> The culprit is this logic in try_delta:\n> \n>         /*\n>          * We do not bother to try a delta that we discarded\n>          * on an earlier try, but only when reusing delta data.\n>          */\n>         if (reuse_delta && trg_entry->in_pack &&\n>             trg_entry->in_pack == src_entry->in_pack &&\n>             trg_entry->in_pack_type != OBJ_REF_DELTA &&\n>             trg_entry->in_pack_type != OBJ_OFS_DELTA)\n>                 return 0;\n> [...]\n> Maybe it is enough to simply turn off this optimization if the potential\n> delta source is not being included in the pack (i.e., we are using\n> --thin and it is a boundary object). Because if both objects are being\n> sent, we will just end up reusing the delta that goes in the reverse\n> direction anyway.\n\nHmm. It turns out this is really easy, because we have already marked\nsuch objects as preferred bases.\n\nSo with this patch:\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 96c1680..d05e228 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1439,6 +1439,7 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \t */\n \tif (reuse_delta && trg_entry->in_pack &&\n \t    trg_entry->in_pack == src_entry->in_pack &&\n+\t    !src_entry->preferred_base &&\n \t    trg_entry->in_pack_type != OBJ_REF_DELTA &&\n \t    trg_entry->in_pack_type != OBJ_OFS_DELTA)\n \t\treturn 0;\n\nhere are the numbers I get:\n\n                  dataset\n            | fetches | tags\n---------------------------------\n     before | 53358   | 2750977\nsize  after | 32398   | 2668479\n     change |   -39%  |      -3%\n---------------------------------\n     before |  0.18   | 1.12\nCPU   after |  0.18   | 1.15\n     change |    +0%  |      +3%\n\nSo nearly all of the size benefit, but very little CPU change (even the\n3% on the larger-pack case is close to the levels of run-to-run noise).\nObviously the size benefit in the larger-pack case isn't impressive, but\nI think the \"fetches\" case is much more indicative of a real server\nload.\n\n-Peff\n"},{"id":"182472","messageId":"alpine.LFD.2.02.1201121852120.2722@xanadu.home","threadId":"29356","inReplyTo":"20120112223234.GA4949@sigill.intra.peff.net","subject":"Re: thin packs ending up fat","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2012-01-12T23:54:59Z","receivedAt":"2012-01-12T23:54:59Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 12 Jan 2012, Jeff King wrote:\n\n> On Thu, Jan 12, 2012 at 05:15:23PM -0500, Jeff King wrote:\n> \n> > It turns out that when packing a subset of a fully packed repo (as we do\n> > for a bundle or for a fetch), we tend not to make thin packs at all.\n> > The culprit is this logic in try_delta:\n> > \n> >         /*\n> >          * We do not bother to try a delta that we discarded\n> >          * on an earlier try, but only when reusing delta data.\n> >          */\n> >         if (reuse_delta && trg_entry->in_pack &&\n> >             trg_entry->in_pack == src_entry->in_pack &&\n> >             trg_entry->in_pack_type != OBJ_REF_DELTA &&\n> >             trg_entry->in_pack_type != OBJ_OFS_DELTA)\n> >                 return 0;\n> > [...]\n> > Maybe it is enough to simply turn off this optimization if the potential\n> > delta source is not being included in the pack (i.e., we are using\n> > --thin and it is a boundary object). Because if both objects are being\n> > sent, we will just end up reusing the delta that goes in the reverse\n> > direction anyway.\n> \n> Hmm. It turns out this is really easy, because we have already marked\n> such objects as preferred bases.\n\nThat's exactly what I was about to suggest after reading your first \nemail.\n\n> So with this patch:\n> \n> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\n> index 96c1680..d05e228 100644\n> --- a/builtin/pack-objects.c\n> +++ b/builtin/pack-objects.c\n> @@ -1439,6 +1439,7 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n>  \t */\n>  \tif (reuse_delta && trg_entry->in_pack &&\n>  \t    trg_entry->in_pack == src_entry->in_pack &&\n> +\t    !src_entry->preferred_base &&\n>  \t    trg_entry->in_pack_type != OBJ_REF_DELTA &&\n>  \t    trg_entry->in_pack_type != OBJ_OFS_DELTA)\n>  \t\treturn 0;\n\nAcked-by: Nicolas Pitre <nico@fluxnic.net>\n\n> here are the numbers I get:\n> \n>                   dataset\n>             | fetches | tags\n> ---------------------------------\n>      before | 53358   | 2750977\n> size  after | 32398   | 2668479\n>      change |   -39%  |      -3%\n> ---------------------------------\n>      before |  0.18   | 1.12\n> CPU   after |  0.18   | 1.15\n>      change |    +0%  |      +3%\n> \n> So nearly all of the size benefit, but very little CPU change (even the\n> 3% on the larger-pack case is close to the levels of run-to-run noise).\n> Obviously the size benefit in the larger-pack case isn't impressive, but\n> I think the \"fetches\" case is much more indicative of a real server\n> load.\n\nIndeed.  Please make sure to capture those numbers in the commit log.\n\n\nNicolas\n"},{"id":"182473","messageId":"7vboq81msn.fsf@alter.siamese.dyndns.org","threadId":"29356","inReplyTo":"20120112223234.GA4949@sigill.intra.peff.net","subject":"Re: thin packs ending up fat","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-01-13T00:14:16Z","receivedAt":"2012-01-13T00:14:16Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> Hmm. It turns out this is really easy, because we have already marked\n> such objects as preferred bases.\n>\n> So with this patch:\n>\n> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\n> index 96c1680..d05e228 100644\n> --- a/builtin/pack-objects.c\n> +++ b/builtin/pack-objects.c\n> @@ -1439,6 +1439,7 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n>  \t */\n>  \tif (reuse_delta && trg_entry->in_pack &&\n>  \t    trg_entry->in_pack == src_entry->in_pack &&\n> +\t    !src_entry->preferred_base &&\n>  \t    trg_entry->in_pack_type != OBJ_REF_DELTA &&\n>  \t    trg_entry->in_pack_type != OBJ_OFS_DELTA)\n>  \t\treturn 0;\n\nYeah, I was wondering why this one-liner was not in the original message\n;-)\n\n> here are the numbers I get:\n>\n>                   dataset\n>             | fetches | tags\n> ---------------------------------\n>      before | 53358   | 2750977\n> size  after | 32398   | 2668479\n>      change |   -39%  |      -3%\n> ---------------------------------\n>      before |  0.18   | 1.12\n> CPU   after |  0.18   | 1.15\n>      change |    +0%  |      +3%\n\nLooks good.\n"},{"id":"182474","messageId":"7vwr8wz8u9.fsf@alter.siamese.dyndns.org","threadId":"29356","inReplyTo":"20120112223234.GA4949@sigill.intra.peff.net","subject":"Re: thin packs ending up fat","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-01-13T01:31:42Z","receivedAt":"2012-01-13T01:31:42Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"From: Jeff King <peff@peff.net>\nSubject: [PATCH] thin-pack: try harder to create delta against preferred base\n\nWhen creating a pack using objects that reside in existing packs, we try\nto avoid recomputing futile delta between an object (trg) and a candidate\nfor its base object (src) if they are stored in the same packfile, and trg\nis not recorded as a delta already. This heuristics makes sense because it\nis likely that we tried to express trg as a delta based on src but it did\nnot produce a good delta when we created the existing pack.\n\nAs the pack heuristics prefer producing delta to remove data, and Linus's\nlaw dictates that the size of a file grows over time, we tend to record\nthe newest version of the file as inflated, and older ones as delta\nagainst it.\n\nWhen creating a thin-pack to transfer recent history, it is likely that we\nwill try to send an object that is recorded in full, as it is newer.  But\nthe heuristics to avoid recomputing futile delta effectively forbids us\nfrom attempting to express such an object as a delta based on another\nobject. Sending an object in full is often more expensive than sending a\nsuboptimal delta based on other objects, and it is even more so if we\ncould use an object we know the receiving end already has (i.e. referred\nbase object) as the delta base.\n\nTweak the recomputation avoidance logic, so that we do not punt on\ncomputing delta against a preferred base object.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n\n builtin/pack-objects.c |    9 +++++++--\n 1 files changed, 7 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex c6e2d87..8bfe3a6 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1248,11 +1248,16 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \t\treturn -1;\n \n \t/*\n-\t * We do not bother to try a delta that we discarded\n-\t * on an earlier try, but only when reusing delta data.\n+\t * We do not bother to try a delta that we discarded on an\n+\t * earlier try, but only when reusing delta data.  Note that\n+\t * src_entry that is marked as the preferred_base should always\n+\t * be considered, as even if we produce a suboptimal delta against\n+\t * it, we will still save the transfer cost, as we already know\n+\t * the other side has it and we won't send src_entry at all.\n \t */\n \tif (reuse_delta && trg_entry->in_pack &&\n \t    trg_entry->in_pack == src_entry->in_pack &&\n+\t    !src_entry->preferred_base &&\n \t    trg_entry->in_pack_type != OBJ_REF_DELTA &&\n \t    trg_entry->in_pack_type != OBJ_OFS_DELTA)\n \t\treturn 0;\n-- \n1.7.9.rc0.53.gc8bc2\n"},{"id":"182475","messageId":"20120113015117.GA8245@sigill.intra.peff.net","threadId":"29356","inReplyTo":"7vwr8wz8u9.fsf@alter.siamese.dyndns.org","subject":"Re: thin packs ending up fat","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-01-13T01:51:17Z","receivedAt":"2012-01-13T01:51:17Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 12, 2012 at 05:31:42PM -0800, Junio C Hamano wrote:\n\n> From: Jeff King <peff@peff.net>\n> Subject: [PATCH] thin-pack: try harder to create delta against preferred base\n\nI just sat down to write a nicer commit message, and behold, it was done\nfor me. Thanks.\n\n> When creating a thin-pack to transfer recent history, it is likely that we\n> will try to send an object that is recorded in full, as it is newer.  But\n> the heuristics to avoid recomputing futile delta effectively forbids us\n> from attempting to express such an object as a delta based on another\n> object. Sending an object in full is often more expensive than sending a\n> suboptimal delta based on other objects, and it is even more so if we\n> could use an object we know the receiving end already has (i.e. referred\n> base object) as the delta base.\n\ns/referred/preferred/\n\n> Tweak the recomputation avoidance logic, so that we do not punt on\n> computing delta against a preferred base object.\n> \n> Signed-off-by: Junio C Hamano <gitster@pobox.com>\n\nOther than that, it looks good to me.\n\nSigned-off-by: Jeff King <peff@peff.net>\n\nI'll try to deploy this to GitHub in the near future. I doubt we'll see\nmuch of a dent in our bandwidth, though, as small fetches that this\nhelps are probably lost in the noise of clones.\n\n-Peff\n"},{"id":"182476","messageId":"20120113015920.GB8245@sigill.intra.peff.net","threadId":"29356","inReplyTo":"20120113015117.GA8245@sigill.intra.peff.net","subject":"Re: thin packs ending up fat","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-01-13T01:59:20Z","receivedAt":"2012-01-13T01:59:20Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 12, 2012 at 08:51:17PM -0500, Jeff King wrote:\n\n> > Tweak the recomputation avoidance logic, so that we do not punt on\n> > computing delta against a preferred base object.\n> > \n> > Signed-off-by: Junio C Hamano <gitster@pobox.com>\n> \n> Other than that, it looks good to me.\n> \n> Signed-off-by: Jeff King <peff@peff.net>\n\nActually, Nicolas asked for the numbers to go into the\ncommit message (and gave his acked-by).  So maybe append:\n\nThe effect of this patch can be seen on two simulated\nupload-pack workloads. The first is based on 44 reflog\nentries from my git.git origin/master reflog, and represents\nthe packs that kernel.org produced to send me git updates\nfor the past month or two. The second workload represents\nmuch larger fetches, going from git's v1.0.0 tag to v1.1.0,\nthen v1.1.0 to v1.2.0, and so on.\n\nThe table below shows the average generated pack size and\nthe average CPU time consumed for each dataset, both before\nand after the patch:\n\n                  dataset\n            | reflog | tags\n---------------------------------\n     before | 53358  | 2750977\nsize  after | 32398  | 2668479\n     change |   -39% |      -3%\n---------------------------------\n     before |  0.18  | 1.12\nCPU   after |  0.18  | 1.15\n     change |    +0% |      +3%\n\nThis patch makes a much bigger difference for packs with a\nshorter slice of history (since its effect is seen at the\nboundaries of the pack) though it has some benefit even for\nlarger packs.\n\nAcked-by: Nicolas Pitre <nico@fluxnic.net>\n"},{"id":"182477","messageId":"alpine.LFD.2.02.1201122118530.2722@xanadu.home","threadId":"29356","inReplyTo":"7vwr8wz8u9.fsf@alter.siamese.dyndns.org","subject":"Re: thin packs ending up fat","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2012-01-13T02:19:29Z","receivedAt":"2012-01-13T02:19:29Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 12 Jan 2012, Junio C Hamano wrote:\n\n> From: Jeff King <peff@peff.net>\n> Subject: [PATCH] thin-pack: try harder to create delta against preferred base\n> \n> When creating a pack using objects that reside in existing packs, we try\n> to avoid recomputing futile delta between an object (trg) and a candidate\n> for its base object (src) if they are stored in the same packfile, and trg\n> is not recorded as a delta already. This heuristics makes sense because it\n> is likely that we tried to express trg as a delta based on src but it did\n> not produce a good delta when we created the existing pack.\n> \n> As the pack heuristics prefer producing delta to remove data, and Linus's\n> law dictates that the size of a file grows over time, we tend to record\n> the newest version of the file as inflated, and older ones as delta\n> against it.\n> \n> When creating a thin-pack to transfer recent history, it is likely that we\n> will try to send an object that is recorded in full, as it is newer.  But\n> the heuristics to avoid recomputing futile delta effectively forbids us\n> from attempting to express such an object as a delta based on another\n> object. Sending an object in full is often more expensive than sending a\n> suboptimal delta based on other objects, and it is even more so if we\n> could use an object we know the receiving end already has (i.e. referred\n> base object) as the delta base.\n> \n> Tweak the recomputation avoidance logic, so that we do not punt on\n> computing delta against a preferred base object.\n> \n> Signed-off-by: Junio C Hamano <gitster@pobox.com>\n\nAcked-by: Nicolas Pitre <nico@fluxnic.net>\n\n> ---\n> \n>  builtin/pack-objects.c |    9 +++++++--\n>  1 files changed, 7 insertions(+), 2 deletions(-)\n> \n> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\n> index c6e2d87..8bfe3a6 100644\n> --- a/builtin/pack-objects.c\n> +++ b/builtin/pack-objects.c\n> @@ -1248,11 +1248,16 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n>  \t\treturn -1;\n>  \n>  \t/*\n> -\t * We do not bother to try a delta that we discarded\n> -\t * on an earlier try, but only when reusing delta data.\n> +\t * We do not bother to try a delta that we discarded on an\n> +\t * earlier try, but only when reusing delta data.  Note that\n> +\t * src_entry that is marked as the preferred_base should always\n> +\t * be considered, as even if we produce a suboptimal delta against\n> +\t * it, we will still save the transfer cost, as we already know\n> +\t * the other side has it and we won't send src_entry at all.\n>  \t */\n>  \tif (reuse_delta && trg_entry->in_pack &&\n>  \t    trg_entry->in_pack == src_entry->in_pack &&\n> +\t    !src_entry->preferred_base &&\n>  \t    trg_entry->in_pack_type != OBJ_REF_DELTA &&\n>  \t    trg_entry->in_pack_type != OBJ_OFS_DELTA)\n>  \t\treturn 0;\n> -- \n> 1.7.9.rc0.53.gc8bc2\n> \n"},{"id":"182480","messageId":"7vmx9sysqe.fsf@alter.siamese.dyndns.org","threadId":"29356","inReplyTo":"20120113015117.GA8245@sigill.intra.peff.net","subject":"Re: thin packs ending up fat","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-01-13T07:19:37Z","receivedAt":"2012-01-13T07:19:37Z","isPatch":false,"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, Jan 12, 2012 at 05:31:42PM -0800, Junio C Hamano wrote:\n>\n>> From: Jeff King <peff@peff.net>\n>> Subject: [PATCH] thin-pack: try harder to create delta against preferred base\n>\n> I just sat down to write a nicer commit message, and behold, it was done\n> for me. Thanks.\n\nThank _you_ for a quick response and correction.\n\nI wanted to make sure I understood the root cause of the issue and the\napproach the patch takes to address it, instead of committing something\nthat smelled correct. And the only way I know to do so is to write it\ndown.\n\nEspeciallly, before coming up with the description, I was wondering if\nthis kind of symptom appears in non-thin cases, but after writing down the\njustification for this patch, it became clear that we wouldn't have to\nworry too much about that case. In a non-thin pack, we need to record one\nobject at least in a delta family in inflated base form, so we may as well\nsend that one near the tip that is already in that form for that, letting\nthe existing \"avoid futile delta\" heuristics to kick in. Other objects in\nthe same delta family will delta against it.\n"},{"id":"182492","messageId":"CACBZZX567mHKXDtTcb+zFKtr2ZvcssF+O=w-x86PfNh+5tTpRg@mail.gmail.com","threadId":"29356","inReplyTo":"20120112221523.GA3663@sigill.intra.peff.net","subject":"Re: thin packs ending up fat","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2012-01-13T08:28:43Z","receivedAt":"2012-01-13T08:28:43Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Thu, Jan 12, 2012 at 23:15, Jeff King <peff@peff.net> wrote:\n\nI'd be interested in testing this on some other repos I have. How\nexactly did you get this:\n\n> -- >8 --\n> 8b0e15fa95e11965f18c8d2585dc8ffd9bfc9356 ^7f41b6bbe3181dc4d1687db036bf22316997a1bf\n> 34c4461ae3b353e8c931565d5527b98ed12e3735 ^8b0e15fa95e11965f18c8d2585dc8ffd9bfc9356\n> 463b0ea22b5b9a882e8140d0308433d8cbd0d1fe ^34c4461ae3b353e8c931565d5527b98ed12e3735\n> 288396994f077eec7e7db0017838a5afbfbf81e3 ^463b0ea22b5b9a882e8140d0308433d8cbd0d1fe\n> 05f6edcd2a418a88eeb953d51408a6aeef312f5c ^288396994f077eec7e7db0017838a5afbfbf81e3\n> 08cfdbb88cd6225b4fc4b8a3cecd0e01758c835d ^05f6edcd2a418a88eeb953d51408a6aeef312f5c\n\n>From this:\n\n> In the first, I used the reflog entries from my\n> refs/remotes/origin/master ref.\n\nI can't make \"git reflog refs/remotes/...\" show me anything similar.\n"},{"id":"182498","messageId":"20120113151545.GA9373@sigill.intra.peff.net","threadId":"29356","inReplyTo":"7vmx9sysqe.fsf@alter.siamese.dyndns.org","subject":"Re: thin packs ending up fat","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-01-13T15:15:45Z","receivedAt":"2012-01-13T15:15:45Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 12, 2012 at 11:19:37PM -0800, Junio C Hamano wrote:\n\n> I wanted to make sure I understood the root cause of the issue and the\n> approach the patch takes to address it, instead of committing something\n> that smelled correct. And the only way I know to do so is to write it\n> down.\n\nI use something of the same technique myself...\n\n> Especiallly, before coming up with the description, I was wondering if\n> this kind of symptom appears in non-thin cases, but after writing down the\n> justification for this patch, it became clear that we wouldn't have to\n> worry too much about that case. In a non-thin pack, we need to record one\n> object at least in a delta family in inflated base form, so we may as well\n> send that one near the tip that is already in that form for that, letting\n> the existing \"avoid futile delta\" heuristics to kick in. Other objects in\n> the same delta family will delta against it.\n\nExactly. You asked earlier why my one-liner patch was not in the first\nmessage. It's because it was only through writing the first message that\nI came to the same realization. :)\n\n-Peff\n"},{"id":"182500","messageId":"20120113155536.GB9373@sigill.intra.peff.net","threadId":"29356","inReplyTo":"CACBZZX567mHKXDtTcb+zFKtr2ZvcssF+O=w-x86PfNh+5tTpRg@mail.gmail.com","subject":"Re: thin packs ending up fat","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-01-13T15:55:36Z","receivedAt":"2012-01-13T15:55:36Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jan 13, 2012 at 09:28:43AM +0100, Ævar Arnfjörð Bjarmason wrote:\n\n> On Thu, Jan 12, 2012 at 23:15, Jeff King <peff@peff.net> wrote:\n> \n> I'd be interested in testing this on some other repos I have. How\n> exactly did you get this:\n> \n> > -- >8 --\n> > 8b0e15fa95e11965f18c8d2585dc8ffd9bfc9356 ^7f41b6bbe3181dc4d1687db036bf22316997a1bf\n> > 34c4461ae3b353e8c931565d5527b98ed12e3735 ^8b0e15fa95e11965f18c8d2585dc8ffd9bfc9356\n> > 463b0ea22b5b9a882e8140d0308433d8cbd0d1fe ^34c4461ae3b353e8c931565d5527b98ed12e3735\n> > 288396994f077eec7e7db0017838a5afbfbf81e3 ^463b0ea22b5b9a882e8140d0308433d8cbd0d1fe\n> > 05f6edcd2a418a88eeb953d51408a6aeef312f5c ^288396994f077eec7e7db0017838a5afbfbf81e3\n> > 08cfdbb88cd6225b4fc4b8a3cecd0e01758c835d ^05f6edcd2a418a88eeb953d51408a6aeef312f5c\n> \n> From this:\n> \n> > In the first, I used the reflog entries from my\n> > refs/remotes/origin/master ref.\n> \n> I can't make \"git reflog refs/remotes/...\" show me anything similar.\n\nI just looked in the reflog file directly:\n\n  perl -alne 'print \"$F[1] ^$F[0]\"' \\\n    .git/logs/refs/remotes/origin/master\n\nNote that these are just an approximation of what was fetched each time.\nThe real fetches packed objects for other refs, too. But with respect to\nthis patch, the result should be the same (since the interesting thing\nis the graph boundaries that are packed, so the size of the slice of\nhistory is what's important).\n\nThe other slight inaccuracy is that my tests repack the whole repo, and\nthen simulate old fetches from that repo. When I actually fetched\n7f415b6..8b0e15fa from upstream, all of those later commits didn't\nactually exist yet. And therefore the blobs in those tip commits were\nactually more likely to be non-delta, and therefore this optimization is\nmore likely to help (because we already re-tried deltas if the target\nobject was delta'd against something else).\n\nAt least in theory. In practice, the variance of the improvement it\nprovides to each pack is so quite high. Some packs don't benefit at all,\nbecause the preferred bases simply aren't that useful, or are perhaps\nalready being used. Some packs can have improvements in the 70-80%\nrange.\n\nThe numbers I reported were averaged over all of the packs in the\ndataset. You can see individual packs with the script I provided\nearlier:\n\n  # before patch\n  ./test-pack <dataset-fetch >output-fetch-before\n  # after patch\n  ./test-pack <dataset-fetch >output-fetch-after\n\n  # collate results\n  paste output-fetch-{before,after} |\n  perl -alne 'print \"$F[0] $F[2] \" .\n                int(0.5 + (($F[0] - $F[2]) / $F[0] * 100))'\n\nThe output is below. You can also feed the percentages through this poor\nman's graph generator to see just how wildly it varies:\n\n  perl -alne 'print \"*\" x $F[2]'\n\n-Peff\n\n-- >8 --\n154471 92495 40\n41970 24681 41\n102816 71062 31\n21089 21089 0\n57900 13345 77\n75666 61518 19\n163516 107785 34\n44913 15795 65\n85452 77832 9\n102034 93336 9\n10095 8283 18\n86078 65495 24\n1854 1854 0\n16079 8125 49\n13830 7119 49\n1283 1283 0\n4697 2633 44\n4584 3818 17\n21535 18953 12\n3800 3800 0\n13963 10215 27\n4453 4073 9\n1029 598 42\n111233 68267 39\n879 879 0\n96628 86206 11\n3287 3287 0\n71212 20832 71\n132916 100268 25\n170716 40959 76\n1830 1262 31\n243950 133932 45\n64588 31546 51\n1108 1108 0\n6488 6488 0\n101179 64014 37\n114760 18969 83\n23443 19445 17\n28207 28080 0\n2317 2317 0\n110890 53555 52\n5660 5543 2\n18683 18683 0\n4709 4709 0\n"}]}