git bisect idea: Asymmetric split points

I was using git bisect today when trying to track down a random kernel hang during boot. Since the hang is random, ie it only hangs during some boots, identifying a bad version is easier than identifying a good version. If it hangs during one boot, the kernel is clearly bad, but if it doesn't hang I can't be sure if it's good or bad. I have to test several times to be reasonably sure that a kernel is good.

In this scenario identifying a bad kernel is easier than identifying a good kernel. This means that if I want to find the guilty commit as fast as possible the best strategy is not to split the remaining commit list in half. In this case it would be better to split closer to a known bad commit.

You can also imagine cases where identifying a bad version is more costly than identifying a good one. One example would be if a bad kernel has nasty side effects, such as file system corruption, that you have to fix up before you can continue bisecting.

To handle these cases more efficiently, I think it would be nice to be able to tell git bisect where the bisection point is wanted, for example by specifying a percentage.

Does this sound like a good idea? Would it be hard to implement?

On Sun, 9 Oct 2006, Peter Osterlund wrote:

It should be very easy to implement.

See builtin-rev-list.c: find_bisection(), which has a _very_ simple way of trying to find the best commit. It just counts the distance from the commit:

	distance = count_distance(p);
	clear_distance(list);

where "distance" is really "how many commits will this cover".

If you wanted to get as close to (say) 75% of the total list of commits as possible, you should just do something like

	optimal = nr * percent / 100;
	how_close = abs(optimal - distance);
	if (how_close < closest) {
		best = p;
		closest = how_close;
	}

instead of what we do now (which is just to say that "since we want to get half-way, we want to make the biggest distance from _both_ 0 and from "nr", which is what it calculates with

 - If we're closer to "nr" than to 0 (ie the difference between nr and 
   distance is smaller than the difference between distance and 0), pick 
   the smaller difference:

	if (nr - distance < distance) 
		distance = nr - distance;

 - if this new distance is larger than any distance we've seen so far, 
   this is the best commit so far:

	if (distance > closest) {
		best = p;
		closest = distance;
	}

and notice how this is really just a special case of the percentage thing when percent is 50%.

			Linus