On Thu, Sep 12, 2013 at 03:44:53PM -0400, Jeff King wrote: > 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 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
