Re: Re-Transmission of blobs?

From: Josef Wolf <jw@raven.inka.de>
Date: Sep 12, 2013, 10:35 UTC
Message-ID: <20130912103531.GD14259@raven.wolf.lan>
In-Reply-To: <20130912092339.GA30702@sigill.intra.peff.net>

On Do, Sep 12, 2013 at 05:23:40 -0400, Jeff King wrote:

Show 7 quoted lines

> On Thu, Sep 12, 2013 at 09:42:41AM +0200, Josef Wolf wrote:
>
> I think Junio is referring to the reachability bitmap work. We may know
> that the other side has commit "E" (and therefore every object reachable
> from it), but we do not walk the graph to find the complete set of
> reachable objects. Doing so requires a lot of CPU and I/O, and in most
> cases does not help much.

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)?

> However, if we had an index of reachable objects (e.g., a bitmap) for
> each commit, then we could very cheaply compute the set difference
> between what the other side wants and what they have.

Those bitmaps would be stored in the git metadata? Is it worth it? Storing a bitmap for every commit just to be used once-in-a-while seems to be a pretty big overhead to me. Not to mention the interoperability problems you mentioned below.

Show 7 quoted lines

> JGit has support for pack bitmaps already. There was a patch series a
> few months ago to implement a similar functionality for C git, but the
> on-disk format was not compatible with JGit's. That series has been
> reworked off-list to be compatible with the JGit implementation.
> 
> Those patches need a little cleanup before they are ready for the list,
> but hopefully that should happen soon-ish.

Sounds like you're already almost done and don't really need help anymore. Just out of curiosity, I'd be interested in a pointer anyway ;-)

-- 
Josef Wolf
jw@raven.inka.de