{"thread":{"id":"35113","subject":"pack-object's try_delta fast path for v2 trees?","startedAt":"2013-10-12T03:42:17Z","lastAt":"2013-10-15T02:13:10Z","messageCount":8,"participants":["Duy Nguyen","Nicolas Pitre","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"228769","messageId":"CACsJy8Behb7PW=pFjH=wpjfHjUiyCo8n_ER+KyzcBwCzpyG6pg@mail.gmail.com","threadId":"35113","inReplyTo":null,"subject":"pack-object's try_delta fast path for v2 trees?","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-10-12T03:42:17Z","receivedAt":"2013-10-12T03:42:17Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Hi,\n\nJust wondering if this has been considered and dropped before.\nCurrently we use try_delta() for every object including trees. But\ntrees are special. All tree entries must be unique and sorted. That\nhelps simplify diff algorithm, as demonstrated by diff_tree() and\npv4_encode_tree(). A quick and dirty test with test-delta shows that\ntree_diff only needs half the time of diff_delta(). As trees account\nfor like half the objects in a repo, speeding up delta search might\nhelp performance, I think.\n-- \nDuy\n"},{"id":"228880","messageId":"alpine.LFD.2.03.1310121042290.3023@syhkavp.arg","threadId":"35113","inReplyTo":"CACsJy8Behb7PW=pFjH=wpjfHjUiyCo8n_ER+KyzcBwCzpyG6pg@mail.gmail.com","subject":"Re: pack-object's try_delta fast path for v2 trees?","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-10-12T14:52:50Z","receivedAt":"2013-10-12T14:52:50Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 12 Oct 2013, Duy Nguyen wrote:\n\n> Hi,\n> \n> Just wondering if this has been considered and dropped before.\n> Currently we use try_delta() for every object including trees. But\n> trees are special. All tree entries must be unique and sorted. That\n> helps simplify diff algorithm, as demonstrated by diff_tree() and\n> pv4_encode_tree(). A quick and dirty test with test-delta shows that\n> tree_diff only needs half the time of diff_delta(). As trees account\n> for like half the objects in a repo, speeding up delta search might\n> help performance, I think.\n\nFortaking advantage of the sorted nature of tree objects, you need to \nactually parse those objects to determine tree entry boundaries.  The \ndelta diff code doesn't parse anything and simply do a search into a \nbinary buffer which may or may not end up slicing that buffer on actual \ntree entry boundaries.\n\nSo this could help somewhat, however the need for pre-parsing those tree \nobjects is probably going to counter-balance all the performance gain \nyou might get.\n\nI think the potential for improvements would be greater by moving to \npack v4 (when the right algorithm is in place that is).  Eventually the \nproper pack v4 tree delta diffing code could be made to serve the pack \nv2 case as well.\n\n\nNicolas\n"},{"id":"228984","messageId":"20131015001926.GC10415@sigill.intra.peff.net","threadId":"35113","inReplyTo":"CACsJy8Behb7PW=pFjH=wpjfHjUiyCo8n_ER+KyzcBwCzpyG6pg@mail.gmail.com","subject":"Re: pack-object's try_delta fast path for v2 trees?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-10-15T00:19:26Z","receivedAt":"2013-10-15T00:19:26Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Oct 12, 2013 at 10:42:17AM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> Just wondering if this has been considered and dropped before.\n> Currently we use try_delta() for every object including trees. But\n> trees are special. All tree entries must be unique and sorted. That\n> helps simplify diff algorithm, as demonstrated by diff_tree() and\n> pv4_encode_tree(). A quick and dirty test with test-delta shows that\n> tree_diff only needs half the time of diff_delta(). As trees account\n> for like half the objects in a repo, speeding up delta search might\n> help performance, I think.\n\nNo, as far as I know, it is a novel idea. When we were discussing commit\ncaching a while back, Shawn suggested slicing trees on boundaries and\nstore delta instructions that were pure \"change this entry\", \"add this\nentry\", and \"delete this entry\" chunks. The deltas might end up a little\nbigger, but if the reader knew the writer had sliced in this way, it\ncould get a packv4-style cheap tree-diff, while remaining backwards\ncompatible with implementations that just blindly reassemble the buffer\nfrom delta instructions.\n\nI didn't get far enough to try it, but doing what you propose would be\nthe first step. Now that packv4 is more of a reality, it may not be\nworth pursuing, though.\n\n-Peff\n"},{"id":"228985","messageId":"CACsJy8DgjCR+B+Bvbydns=bCZP5=TU1avPinnuDKqLZXS=4LNQ@mail.gmail.com","threadId":"35113","inReplyTo":"20131015001926.GC10415@sigill.intra.peff.net","subject":"Re: pack-object's try_delta fast path for v2 trees?","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-10-15T00:49:57Z","receivedAt":"2013-10-15T00:49:57Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Oct 15, 2013 at 7:19 AM, Jeff King <peff@peff.net> wrote:\n> On Sat, Oct 12, 2013 at 10:42:17AM +0700, Nguyen Thai Ngoc Duy wrote:\n>\n>> Just wondering if this has been considered and dropped before.\n>> Currently we use try_delta() for every object including trees. But\n>> trees are special. All tree entries must be unique and sorted. That\n>> helps simplify diff algorithm, as demonstrated by diff_tree() and\n>> pv4_encode_tree(). A quick and dirty test with test-delta shows that\n>> tree_diff only needs half the time of diff_delta(). As trees account\n>> for like half the objects in a repo, speeding up delta search might\n>> help performance, I think.\n>\n> No, as far as I know, it is a novel idea. When we were discussing commit\n> caching a while back, Shawn suggested slicing trees on boundaries and\n> store delta instructions that were pure \"change this entry\", \"add this\n> entry\", and \"delete this entry\" chunks. The deltas might end up a little\n> bigger, but if the reader knew the writer had sliced in this way, it\n> could get a packv4-style cheap tree-diff, while remaining backwards\n> compatible with implementations that just blindly reassemble the buffer\n> from delta instructions.\n>\n> I didn't get far enough to try it, but doing what you propose would be\n> the first step. Now that packv4 is more of a reality, it may not be\n> worth pursuing, though.\n\nI see this as pack-objects peformance improvements only. If we could\nmake pack-objects run like 10% faster (even only with -adf), then it\nmay be worth trying. The 10% is a total guess though as I haven't\nchecked how much time we spend in searching deltas.\n-- \nDuy\n"},{"id":"228986","messageId":"20131015005417.GA16502@sigill.intra.peff.net","threadId":"35113","inReplyTo":"CACsJy8DgjCR+B+Bvbydns=bCZP5=TU1avPinnuDKqLZXS=4LNQ@mail.gmail.com","subject":"Re: pack-object's try_delta fast path for v2 trees?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-10-15T00:54:17Z","receivedAt":"2013-10-15T00:54:17Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Oct 15, 2013 at 07:49:57AM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> I see this as pack-objects peformance improvements only. If we could\n> make pack-objects run like 10% faster (even only with -adf), then it\n> may be worth trying. The 10% is a total guess though as I haven't\n> checked how much time we spend in searching deltas.\n\nFor \"repack -ad\", generally we don't spend that much time on deltas. It\ndepends what your pre-repack state is, of course, but I find that most\nof the time goes to \"counting objects\". With \"-adf\", I would guess that\nwe easily spend something like 95% of the time on compressing for a\nlarge repository (just try \"repack -adf\" on the kernel; even with 8\ncores it's a half hour or more on my machine, versus about 25 seconds to\ncount the objects).\n\nSo I think you could potentially get a lot of speedup for the \"-adf\"\ncase (and likewise \"git gc --aggressive\").\n\n-Peff\n"},{"id":"228987","messageId":"alpine.LFD.2.03.1310142141200.1873@syhkavp.arg","threadId":"35113","inReplyTo":"20131015001926.GC10415@sigill.intra.peff.net","subject":"Re: pack-object's try_delta fast path for v2 trees?","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-10-15T01:45:12Z","receivedAt":"2013-10-15T01:45:12Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 14 Oct 2013, Jeff King wrote:\n\n> On Sat, Oct 12, 2013 at 10:42:17AM +0700, Nguyen Thai Ngoc Duy wrote:\n> \n> > Just wondering if this has been considered and dropped before.\n> > Currently we use try_delta() for every object including trees. But\n> > trees are special. All tree entries must be unique and sorted. That\n> > helps simplify diff algorithm, as demonstrated by diff_tree() and\n> > pv4_encode_tree(). A quick and dirty test with test-delta shows that\n> > tree_diff only needs half the time of diff_delta(). As trees account\n> > for like half the objects in a repo, speeding up delta search might\n> > help performance, I think.\n> \n> No, as far as I know, it is a novel idea. When we were discussing commit\n> caching a while back, Shawn suggested slicing trees on boundaries and\n> store delta instructions that were pure \"change this entry\", \"add this\n> entry\", and \"delete this entry\" chunks. The deltas might end up a little\n> bigger, but if the reader knew the writer had sliced in this way, it\n> could get a packv4-style cheap tree-diff, while remaining backwards\n> compatible with implementations that just blindly reassemble the buffer\n> from delta instructions.\n> \n> I didn't get far enough to try it, but doing what you propose would be\n> the first step. Now that packv4 is more of a reality, it may not be\n> worth pursuing, though.\n\nThe \"easy\" way to produce pack v2 tree objects from a pack v4 would be \nexactly that: take the pack v4 tree encoding and do a straight \ntranslation into delta encoding using the base from which the most \nentries are copied from.\n\n\nNicolas\n"},{"id":"228988","messageId":"20131015015113.GA17486@sigill.intra.peff.net","threadId":"35113","inReplyTo":"alpine.LFD.2.03.1310142141200.1873@syhkavp.arg","subject":"Re: pack-object's try_delta fast path for v2 trees?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-10-15T01:51:13Z","receivedAt":"2013-10-15T01:51:13Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Oct 14, 2013 at 09:45:12PM -0400, Nicolas Pitre wrote:\n\n> > No, as far as I know, it is a novel idea. When we were discussing commit\n> > caching a while back, Shawn suggested slicing trees on boundaries and\n> > store delta instructions that were pure \"change this entry\", \"add this\n> > entry\", and \"delete this entry\" chunks. The deltas might end up a little\n> > bigger, but if the reader knew the writer had sliced in this way, it\n> > could get a packv4-style cheap tree-diff, while remaining backwards\n> > compatible with implementations that just blindly reassemble the buffer\n> > from delta instructions.\n> > \n> > I didn't get far enough to try it, but doing what you propose would be\n> > the first step. Now that packv4 is more of a reality, it may not be\n> > worth pursuing, though.\n> \n> The \"easy\" way to produce pack v2 tree objects from a pack v4 would be \n> exactly that: take the pack v4 tree encoding and do a straight \n> translation into delta encoding using the base from which the most \n> entries are copied from.\n\nYeah, that makes a lot of sense.\n\nBy the way, I'm sorry I haven't looked more carefully at the packv4\npatches yet. I am excited about it, but I've just got a long queue of\nother things (and because it's big and challenging, it's easy to put\noff).\n\nOne of the things that makes me most nervous about switching to it on\nthe server side is that we'll have packv2-only clients for a while, and\nI worry that converting to v2 on the fly is going to end up costing a\nlot (even with clever tricks like this, you still have to pay the cost\nto zlib deflate each item). But even if it is slow, the sooner we have\npackv4 readers, the sooner the clocks start ticking for it being a\nreasonable decision for a big server provider to switch.\n\n-Peff\n"},{"id":"228989","messageId":"alpine.LFD.2.03.1310142200380.1873@syhkavp.arg","threadId":"35113","inReplyTo":"20131015015113.GA17486@sigill.intra.peff.net","subject":"Re: pack-object's try_delta fast path for v2 trees?","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-10-15T02:13:10Z","receivedAt":"2013-10-15T02:13:10Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 14 Oct 2013, Jeff King wrote:\n\n> By the way, I'm sorry I haven't looked more carefully at the packv4\n> patches yet. I am excited about it, but I've just got a long queue of\n> other things (and because it's big and challenging, it's easy to put\n> off).\n\n;-)\n\nWhile I consider the format pretty much established at this point, it \nstill has some way to go on the algorithmic side of things.  So there is \ncertainly room for more people toying with the code.\n\n> One of the things that makes me most nervous about switching to it on\n> the server side is that we'll have packv2-only clients for a while, and\n> I worry that converting to v2 on the fly is going to end up costing a\n> lot (even with clever tricks like this, you still have to pay the cost\n> to zlib deflate each item). But even if it is slow, the sooner we have\n> packv4 readers, the sooner the clocks start ticking for it being a\n> reasonable decision for a big server provider to switch.\n\nWell... of course this depends.  What pack v4 brings is super fast tree \nwalking and object enumeration.  We're not there yet with the current \ncode, but in theory this is conceptually cheaper with pack v4.  \nTherefore operations such as partial clones or updates are meant to be \nmuch faster in the preparation phase which should compensate for the \ndeflate cost.\n\nYet a big server could store both v2 and v4 in parallel if disk space is \nnot an issue, and a modified git could lookup the alternate version of \nan object before transcoding it.\n\n\nNicolas\n"}]}