Re: RFE: "git bisect reverse"

["H. Peter Anvin" <hpa@zytor.com>]

Ealdwulf Wuffinga wrote:
> 
> 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.