git bisect idea: Asymmetric split points

git bisect idea: Asymmetric split points

[Peter Osterlund]

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?

-- 
Peter Osterlund - petero2@telia.com
http://web.telia.com/~u89404340

Re: git bisect idea: Asymmetric split points

[Linus Torvalds]

On Sun, 9 Oct 2006, Peter Osterlund wrote:
> 
> Does this sound like a good idea? Would it be hard to implement?

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