From: Linus Torvalds Date: Wed, 14 Sep 2005 01:42:05 GMT Subject: Re: dumb transports not being welcomed.. Message-ID: In-Reply-To: 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