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

From: Linus Torvalds <torvalds@osdl.org>
Date: Jun 19, 2005, 05:03 UTC
Message-ID: <Pine.LNX.4.58.0506182141400.2268@ppc970.osdl.org>
In-Reply-To: <Pine.LNX.4.58.0506182022130.2268@ppc970.osdl.org>

On Sat, 18 Jun 2005, Linus Torvalds wrote:

> 
> Now, I say "roughly", because there may not _be_ any commit that exactly 
> bisects the case. For a trivial case, let's say that we know that 'A' is 
> bad, and 'B' is good, but the graph in between them looks like this:

Let's make a different case, just to make it even more obvious.

Let's say that the graph is

and we know that "A" is bad, and "B" is good, but we don't know which of a1-a9/b1-b9 are buggy.

Where do we start testing?

We start testing at either 'a1' or 'b1', because those are the two values that bisect the list either into the "a1-a9" series, or the "b1-b9" series. Any other starting point would be a bug.

Or, let's say that the graph is

and in this case the right place to pick is 'b4', because that's the one that reaches 6 commits (b4-b9), while it leaves 6 commits unreachable (a1-a3, b1-b3): that's a perfect bisection, and now it's totally unambiguous (in the previous case a1 and b1 were equally good choices, in this case there is only one valid choice).

It gets more interesting when you have intermediate merges:

The above graph _looks_ very similar, but now the right place to bisect is 'b5', because that reaches six commits (a3 + b5-b9), and again there are six commits unreachable (a1-a2 + b1-b4). Again, this is unambiguous - there is one clearly superior choice.

The current --bisect algorithm may not always pick that best choice: I think I should subtract one from the total number of commits, since right now it counts the "good" commit too, ie 'A'. But I think it's at most off-by-one.

The bigger problem is that the algorithm is something like O(N^3) in cost
- albeit with a fairly cheap constant factor. In other words, it might not
be worthwhile bisecting three years worth of development with it, and you
migth be better off starting with a rougher half-way-point algorithm
("let's try some release a year and a half ago first").

The performance problem seems to really be pretty theoretical: I can bisect the developemnt from 2.6.12-rc2 to current head in 0.59 seconds, so it's not like it's horribly slow for something like a couple of months worth of development.

			Linus