From: Josef Wolf Date: Fri, 13 Sep 2013 10:09:35 GMT Subject: Re: Re-Transmission of blobs? Message-ID: <20130913100934.GE14259@raven.wolf.lan> In-Reply-To: <20130912194453.GD32069@sigill.intra.peff.net> On Thu, Sep 12, 2013 at 03:44:53PM -0400, Jeff King wrote: > On Thu, Sep 12, 2013 at 12:35:32PM +0200, Josef Wolf wrote: > > > I'm not sure I understand correctly. I see that bitmaps can be used to > > implement set operations. But how comes that walking the graph requires a lot > > of CPU? Isn't it O(n)? > > Yes and no. Your "n" there is the entirety of history. Is this really true? > (and each one needs to be pulled off of the disk, > decompressed, and reconstructed from deltas). While you need to unpack commits/trees to traverse further down, I can't see any reason to unpack/reconstruct blobs just to see whether you need to send it. The SHA is all you need to know, isn't it? > Secondly, the graph traversal ends up seeing the same sha1s over and > over again in tree entries (because most entries in the tree don't > change from commit to commit). Whenever you see an object (whether commit or tree) that you already have seen, you can stop traversing further down this part of the graph/tree, as everything you will see on this part has already be seen before. Why would you see the same commits/trees over and over again? You'd stop traversing on the boundary of the already-seen-territory, leaving the vast majority of the "duplicated" structure under the carpet. Somehow I fail to see the problem here. -- Josef Wolf jw@raven.inka.de