Re: RFE: "git bisect reverse"

From: Ealdwulf Wuffinga <ealdwulf@googlemail.com>
Date: May 27, 2009, 22:07 UTC
Message-ID: <efe2b6d70905271507s187babe9yf19a25268ab0b95e@mail.gmail.com>
In-Reply-To: <20090527211836.GA14841@localhost>

On Wed, May 27, 2009 at 10:18 PM, Clemens Buchacher <drizzd@aon.at> wrote:

Show 19 quoted lines

> On Wed, May 27, 2009 at 10:11:35PM +0100, Ealdwulf Wuffinga wrote:
>> >> Sam Vilain wrote:
>> >> > Oh, yes.  And another thing: 'git bisect run' / 'git bisect skip'
>> >> > doesn't do a very good job of skipping around broken commits (ie when
>> >> > the script returns 126).  It just seems to move to the next one; it
>> >> > would be much better IMHO to first try the commit 1/3rd of the way into
>> >> > the range, then if that fails, the commit 2/3rd of the way through it,
>> >> > etc.
>>
>> As I understand it, the idea is that the probability that a commit is
>> broken is greater if it is close in the DAG to a known-broken commit.
>> I wonder if this can be made more concrete? Can we derive a formula
>> for, or collect empriical data on, these probabilities?
>
> No. The idea is that we want to reduce to bisect as close to the middle as
> possible so we only have to do log2(n) tests. But if a commit is skipped,
> that means we cannot decide whether the test passes or fails for this
> commit. But if we choose a commit close to the skipped one, we will likely
> have to skip the that one for the same reason.

You say 'no', but your explanation does not appear to contradict what I have said. I am not sure what you are disagreeing with?

I agree, the whole point is to do the bisection in as few tests as possible. This means that the test must gain the maximum information possible, which in the deterministic case (git-bisect) means testing in the middle. For the non-deterministic case, in bbchop, I directly calculate the information gain of each potential test, then choose the greatest.

The question is how to avoid skips, which gain no information. You say 'if we choose a commit close to the skipped one, we will likely have to skip the that one'. This is what I meant by 'the idea is that the probability that a commit is broken is greater if it is close in the DAG to a known-broken commit'. Maybe you are reading this as 'bad commit', but this is not the sense in which Sam is using the term.

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.

Ealdwulf