The behaviour of git bisect skip

The behaviour of git bisect skip

[H. Peter Anvin]

I recently had the unhappy experience of trying to bisect a tree with a 
large region of the history obscured by auxilliary bugs.  "git bisect 
skip" will stay in the central region, thus being largely useless.

I was thinking about how to possibly do it better.  This is something I 
came up with, and thought it might be interesing.

a. we obviously cannot move the start and end (good and bad) markers, 
since they have not been shown one way or the other.

b. however, the practice of testing the centermost point is merely the 
*optimal*, corresponding to 1 bit of information per iteration.  An 
off-center test is also possible (as long as the value depends on both 
endpoints, and isn't fixed from one of the endpoints; in that case we 
have a linear search), corresponding to a smaller amount of information 
- for example, sampling at the one-quarter point corresponds to 
3/4*log2(3/4) + 1/4*log2(1/4) =~ 0.811 bits of information.

I would suggest something based on the following algorithm:

Given an interval with a certain number of skip points, subdivide the 
interval into subintervals each separated by a skip point.  Pick the 
centermost point of the *largest* of these intervals.  If there is more 
than one largest interval, choose the one centermost point that ends up 
being centermost in the overall interval.

This algorithm obviously needs some adjustment (as does plain binary 
search) in order to deal with a branched history, but I thought it might 
be an interesting starting point.  It has the desirable property that it 
can make forward progress even in the presence of skip points, and that 
it avoids needlessly searching close to skip points.

	-hpa

Re: The behaviour of git bisect skip

[Christian Couder]

Le mardi 14 octobre 2008, H. Peter Anvin a écrit :
> I recently had the unhappy experience of trying to bisect a tree with a
> large region of the history obscured by auxilliary bugs.  "git bisect
> skip" will stay in the central region, thus being largely useless.

Yeah, it tries to find the first non skipped commit among the best possible 
bisection points. And if you have a linear history the best bisection 
points are in the middle of the good and bad commits.

> I was thinking about how to possibly do it better.  This is something I
> came up with, and thought it might be interesing.
>
> a. we obviously cannot move the start and end (good and bad) markers,
> since they have not been shown one way or the other.
>
> b. however, the practice of testing the centermost point is merely the
> *optimal*, corresponding to 1 bit of information per iteration.  An
> off-center test is also possible (as long as the value depends on both
> endpoints, and isn't fixed from one of the endpoints; in that case we
> have a linear search), corresponding to a smaller amount of information
> - for example, sampling at the one-quarter point corresponds to
> 3/4*log2(3/4) + 1/4*log2(1/4) =~ 0.811 bits of information.
>
> I would suggest something based on the following algorithm:
>
> Given an interval with a certain number of skip points, subdivide the
> interval into subintervals each separated by a skip point.  Pick the
> centermost point of the *largest* of these intervals.  If there is more
> than one largest interval, choose the one centermost point that ends up
> being centermost in the overall interval.
>
> This algorithm obviously needs some adjustment (as does plain binary
> search) in order to deal with a branched history, but I thought it might
> be an interesting starting point.  It has the desirable property that it
> can make forward progress even in the presence of skip points, and that
> it avoids needlessly searching close to skip points.

It looks like a great alternative algorithm but as the current bisect skip 
is implemented in shell, I think that it might be too difficult or 
inefficient to implement something like that in shell.

I think it might be better to try a more simple alternative algorithm first 
like removing all skipped commits from the sorted list of possible 
bisection point (the list is sorted because best commits from a bisection 
point are first) and trying the commit at one third (or another fixed 
ration) of the best commit.

Regards,
Christian.
 

> 	-hpa
> --
> To unsubscribe from this list: send the line "unsubscribe git" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html