Re: Re-Transmission of blobs?

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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
jw@xxxxxxxxxxxxx
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html




[Index of Archives]     [Linux Kernel Development]     [Gcc Help]     [IETF Annouce]     [DCCP]     [Netdev]     [Networking]     [Security]     [V4L]     [Bugtraq]     [Yosemite]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Linux SCSI]     [Fedora Users]