Re: Re-Transmission of blobs?

From: Josef Wolf <jw@raven.inka.de>
Date: Sep 13, 2013, 10:09 UTC
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:

Show 7 quoted lines

> 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