Subject: Re: Re-Transmission of blobs?

From: Josef Wolf <[email-masked]>
Date: Thu, 12 Sep 2013 12:35:32 +0200

On Do, Sep 12, 2013 at 05:23:40 -0400, Jeff King wrote:
> 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.

> 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
[email-masked]