Re: The behaviour of git bisect skip

From: Christian Couder <chriscool@tuxfamily.org>
Date: Oct 15, 2008, 06:54 UTC
Message-ID: <200810150854.49830.chriscool@tuxfamily.org>
In-Reply-To: <48F3DCEB.1060803@zytor.com>

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.

Show 27 quoted lines

> 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.

Show 5 quoted lines

> 	-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