Re: git-rev-list: "--bisect" flag

From: Linus Torvalds <torvalds@osdl.org>
Date: Jun 20, 2005, 03:09 UTC
Message-ID: <Pine.LNX.4.58.0506192002240.2268@ppc970.osdl.org>
In-Reply-To: <2cfc4032050619125537dee354@mail.gmail.com>

On Mon, 20 Jun 2005, Jon Seymour wrote:

Show 8 quoted lines

>
> Yep, ok, so the node you are looking for is one that can reach as
> close to half of the rest of the graph as possible - that's what you
> mean by half-way reachability. If the graph was N nodes deep (no
> fan-out) that would be the literal middle. If it was N nodes wide
> (e.g. fanout N), there is no good node and you basically have to test
> everything since one test doesn't imply anything about the other N-1
> nodes.

Exactly.

> A typical commit graph is worse than O(log2 N) by a factor that is
> determined by some measure of the parallel branching in the graph.

Yes. In many cases it's ok to have parallellism, and the fact that any normal merges will always be two-way (ie there's never a commit in practice that has a very high fan-in), I do believe that you normally get pretty close to that O(log2N) behaviour. In fact, your numbers seemed to say that we're normally within 10% of it.

> I presume  you mean O(N^3)?

Yup again.

> Will you accept a patch that can reduce the worst case cost to some
> lower order? I have a hunch (conceivably wrong, of course) that it can
> be done in O(N).

Well, it depends on how nasty it ends up being. I thought my stupid algorithm would suck horribly, but considering that it can trivially bisect all of the git history so far in basically zero time, it doesn't seem to be that bad. You're more likely to have problems with having to bring in all the commits from disk in the cold-cache case than you are to have problems with the current algorithm performance.

Even at O(N^3) it shouldn't be too nasty even if some crazy person tried to bisect a years worth of development (which really isn't very reasonable behaviour anyway, it's just not sensible to not try a few standard releases in between first).

			Linus