Re: dumb transports not being welcomed..

On Tue, 13 Sep 2005, Linus Torvalds wrote:

That said, I do think that --objects handling is _very_ CPU-hungry. The 
offender is this old commit of mine:

No, never mind. Even without that, we end up walking a _lot_ of really
uninterestng "internal" trees (ie trees where all parents were
uninteresting, and they were parsed just because we had to parse a lot of 
commits to determine what they reached). 

To explain it a bit better, let's see a common case:


HEAD:		a
	       / \
	      b   \
	     / \   \
	    c   d   \
	   /   / \   \
	  e   f   g   x
	   \ /   /   /
	    h   i   /
	     \ /   /
	      j   /
	       \ /
Old history:    k


Now, imagine that we do 

	git-rev-list b..a

which results in just two commits: 'x' and 'a' (everything else is
reachable from 'b'). This is actually not that uncommon. However, in order 
to realize that, we had to walk through _all_ of a..k and x before we saw 
that 'b'..'k' were all uninteresting, and there was nothing else reachable 
that migt be interesting.

Now, that's pretty cheap per se. git-rev-list is optimized for this case, 
and hey, it's usually just a few hundred objects. Not a big deal - 
generating the commit list takes a small fraction of a second.

However, now the true cost of "--objects" is clear: we will walk the two
"positive" trees ('a' and 'x') and look up all their objects (about 35,000
of them) interesting. So far so good. Just another fraction of a second. 

HOWEVER, then we walk _every_single_uninteresting_commit_ and walk _their_
objects to say "we've got this already". And the uninteresting commits are
often many more than the interesting ones - we might have had to go
several weeks back to list them all. The above example is not at all
extreme: we might have something like 20 interesting commits, and several
hundreds of the uninteresting ones.

Now, the way to optimize things is to realize that there are two "classes" 
of uninteresting commits. There are the uninteresting commits that are 
adjacent to an interesting one (in the above example, they are "b" and 
"k"), and there are the uninteresting commits that are only reachable from 
-other- uninteresting commits ('c'..'j'). Let's call the latter class 
"doubly uninteresting commits", and the former class "uninteresting edge 
commits".

And we really don't need to walk the "doubly uninteresting" trees. But we
do. Because we don't have another phase to discover the edge (we can't do
that during the initial discovery phase, because we don't know if a commit
is going to end up interesting in the end - we migth have another commit
that we haven't seen yet that might be the parent of a commit that _looks_
interesting right now, but ends up being uninteresting because that
eventually seen parent ended up being uninteresting).

In other words: I bet I could make "git-rev-list --objects" go from ten
seconds to a single second if I did that edge discovery for most small
incremental updates. Instead, I'm lazy, and I'm describing the problem on 
the list as an "educational experience", and am callously hoping that 
somebody will see it as an interesting challenge ;)

Btw, the above is definitely not made up. If I did my statistics right,
doing "git-rev-list v2.6.14-rc1.." with the current tree results in 178
"interesting" commits, and 6251 "uninteresting" ones. And I bet 99% of
those uninteresting ones are "doubly uninteresting" - and we're just
wasting CPU time looking at what objects are reachable from them..

		Linus