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

Reply via email to