Re: [PATCH v3 0/3] automatically skip away from broken commits

From: H. Peter Anvin <hpa@zytor.com>
Date: Jun 8, 2009, 06:06 UTC
Message-ID: <4A2CAA56.1030707@zytor.com>
In-Reply-To: <200906070932.36913.chriscool@tuxfamily.org>

Christian Couder wrote:

Show 14 quoted lines

>>
>> I think this shows that the "skip ratio" heuristics based on the distance
>> in the "goodness scale" space does not help in avoiding commits that are
>> close in topological space.  There may be cases where the version with
>> patch gives fewer rounds especially when the history is very linear, but
>> I was mostly interested in the number of commits at least in the
>> thousands, which I think is what we should optimize things for, not a toy
>> history of linear 100 commits.
> 
> I get the same results as yours, and I think that in these tests cases "git 
> bisect" was not stuck with having only untestable commits with the 
> highest "goodness" values. So in these cases the original behavior does 
> quite well and that's why the updated behavior can't do better.
>

It's not entirely clear to me that this is any better than simply randomly picking a commit from the list of plausible commits -- in other words, eliminate the commits we can totally rule out, and then just pick a random commit among the list of plausible commits. This is not *quite* as crazy as it sounds; it has the advantage of being an extremely simple algorithm which shouldn't have any pathological behaviours.

The average information gain for a randomly picked commit is 1/(2 ln 2) =~ 0.7213 bits, or an increase in the total bisect time by 39% over a pure binary search.

	-hpa

-- 
H. Peter Anvin, Intel Open Source Technology Center
I work for Intel.  I don't speak on their behalf.