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