Re: RFE: "git bisect reverse"

From: H. Peter Anvin <hpa@zytor.com>
Date: May 28, 2009, 03:11 UTC
Message-ID: <4A1E00F1.4030709@zytor.com>
In-Reply-To: <efe2b6d70905271507s187babe9yf19a25268ab0b95e@mail.gmail.com>

Ealdwulf Wuffinga wrote:

Show 10 quoted lines

> 
> For git-bisect, Sam and H Peter are proposing a heuristic to trade off
> between information gained and likelihood of testing a bad commit. For
> bbchop, I am already doing calculating the information gain directly,
> so if I can incorporate the probability that a commit is broken - has
> to be skipped - then the trade-off will happen automatically.
> Therefore it would be useful to have some plausible theory as to how
> the probability of a broken commit should be calculated, given some
> known-broken and known-not-broken commits.
>

Again, given a bisection, the information gain by "bisecting" at point x
 where 0 < x < 1 is:

	-(x log2 x)-((1-x) log2 (1-x))

At x = 0.5 this gives the optimal 1 bit, but the curve is rather flat near the top. You don't drop to 1/2 bit of information until x = 0.11 or 0.89, and it doesn't drop to 1/4 bit of information until x = 0.04 or 0.96.

Thus, the lack of optimality in searching away from a skip point is much smaller than the potential cost of having to having to skip multiple nearby points.

	-hpa

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