RFE: "git bisect reverse"

RFE: "git bisect reverse"

[H. Peter Anvin]

I would like to request the following feature:

"git bisect reverse"

... does exactly the same thing as "git bisect start", except that it
flips the meaning of "good" and "bad".  It is mentally fairly taxing to
do a reverse bisection (looking for an antiregression) when one has to
flip the meaning of "good" and "bad" (which are very loaded words to our
psyche), and it's even worse to try to get a user to do it...

	-hpa

Re: RFE: "git bisect reverse"

[Sam Vilain]

H. Peter Anvin wrote:
> I would like to request the following feature:
>
> "git bisect reverse"
>
> ... does exactly the same thing as "git bisect start", except that it
> flips the meaning of "good" and "bad".  It is mentally fairly taxing to
> do a reverse bisection (looking for an antiregression) when one has to
> flip the meaning of "good" and "bad" (which are very loaded words to our
> psyche), and it's even worse to try to get a user to do it...
>   

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.

Sam.

Re: RFE: "git bisect reverse"

[H. Peter Anvin]

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

I posted about that last year:

http://marc.info/?l=git&i=48F3DCEB.1060803@zytor.com

At the time, git bisect was still done in the shell and it was deemed
too difficult.

	-hpa

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

Re: RFE: "git bisect reverse"

[Christian Couder]

Le Wednesday 27 May 2009, H. Peter Anvin a écrit :
> 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.
>
> I posted about that last year:
>
> http://marc.info/?l=git&i=48F3DCEB.1060803@zytor.com
>
> At the time, git bisect was still done in the shell and it was deemed
> too difficult.

Yeah, this was also asked by Ingo, and yeah, I think it should be easier to 
do now that most of the "git bisect next" shell code has been ported to C.

I will try to have a look at it soon.

Best regards,
Christian.

Re: RFE: "git bisect reverse"

[Ealdwulf Wuffinga]

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

The reason I ask is that I am wondering how this feature might be
implemented in bbchop
(http://github.com/Ealdwulf/bbchop/tree/master) which is an extension
of git-bisect
to the case where the bug is intermittent. It works by calculating the
probability that the
bug was introduced at each commit, and asking about that commit which
has the largest
expected information gain. Currently if there is a skip I just set the
probability
for that commit to zero, so the algorithm is likely to ask next about
an adjacent one,
just as in git-bisect. A natural way to extend bbchop to this use case
would be for
the information gain calculation to take into account the probability
that a commit is broken.

So I would need some plausible way of calculating that probability. It
is not immediately
obvious to me what that would be, or what assumptions would be useful.

Ealdwulf

Re: RFE: "git bisect reverse"

[Clemens Buchacher]

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.

Re: RFE: "git bisect reverse"

[Ealdwulf Wuffinga]

On Wed, May 27, 2009 at 10:18 PM, Clemens Buchacher <drizzd@aon.at> wrote:
> 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

Re: RFE: "git bisect reverse"

[Sam Vilain]

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

Sounds like interesting stuff, can you make a patch out of it?

Actually it occurs to me that for projects which can successfully
rebuild with just 'make' for each new revision and have a stable commit
policy, walking through commits forwards like that is probably the right
thing to do, because it's relatively cheap and should make progress in
the lowest amount of time.  So the current behaviour should probably
still be available.

Sam

Re: RFE: "git bisect reverse"

[Ealdwulf Wuffinga]

On Thu, May 28, 2009 at 12:08 AM, Sam Vilain <sam@vilain.net> wrote:
> Ealdwulf Wuffinga wrote:

>> [some time back] http://github.com/Ealdwulf/bbchop/tree/master

>> 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.
>>
>
> Sounds like interesting stuff, can you make a patch out of it?

The code as it stands will actually work with an unmodified git.
What it doesn't yet have is a 'git-bisect'-like frontend, which is the only
part which would actually require modifying (or just adding to) git itself.

It does already interface to the git plumbing, so you can try it out if you
don't mind using a slightly ungitlike  interface.

I assume it's not worth doing a patch which would just copy my tree
into the git source tree?

There was also, last time I mentioned this on the list, some question
as to whether it was acceptable to add something written in python to
git.

Ealdwulf

Re: RFE: "git bisect reverse"

[Sam Vilain]

Ealdwulf Wuffinga wrote:
>> Sounds like interesting stuff, can you make a patch out of it?
>>     
>
> The code as it stands will actually work with an unmodified git.
> What it doesn't yet have is a 'git-bisect'-like frontend, which is the only
> part which would actually require modifying (or just adding to) git itself.
>
> It does already interface to the git plumbing, so you can try it out if you
> don't mind using a slightly ungitlike  interface.
>
> I assume it's not worth doing a patch which would just copy my tree
> into the git source tree?
>
> There was also, last time I mentioned this on the list, some question
> as to whether it was acceptable to add something written in python to
> git.
>   

I mean, can you port your algorithm from python to the git-bisect C
source and therefore make something of benefit to existing 'git bisect'
users ?

Sam.

Re: RFE: "git bisect reverse"

[Ealdwulf Wuffinga]

On Fri, May 29, 2009 at 5:20 AM, Sam Vilain <sam@vilain.net> wrote:

>
> I mean, can you port your algorithm from python to the git-bisect C
> source and therefore make something of benefit to existing 'git bisect'
> users ?

I haven't really looked at the git bisect code yet, but the algorithms
are so different that it would likely make the most sense to just add
my algorithm in parallel, rather than trying to combine them.
(Although my algorithm can handle the deterministic case as well,
you'd want to keep the original one too, because mine starts to get a
bit sluggish deciding which commit to test for larger commit ranges. )
It could still be driven by git-bisect script, though.

Converting it to C wouldn't be a trivial task, though, so I may not
get around to it. I'll probably write a more git-like frontend, and
maybe submit a patch to add it to  the contrib directory, to get a
better idea of whether
there are actually any users for this feature, before deciding whether
to do the conversion.

Ealdwulf

Re: RFE: "git bisect reverse"

[H. Peter Anvin]

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.

Re: RFE: "git bisect reverse"

[Ealdwulf Wuffinga]

On Thu, May 28, 2009 at 4:11 AM, H. Peter Anvin <hpa@zytor.com> wrote:

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


I understand that. I didn't mean to imply that there was anything
wrong with your proposal, indeed, it makes sense for git-bisect.

What I am interested in is how to extend bisection to the case of
intermittent bugs; where a test which observes the fault means that it
cannot have been introduced in subsequent commits, but a test which
does not observe the fault cannot guarantee that it must have been
introduced in a subsequent commit.

The simplest way to deal with this is to try to reduce it to the
deterministic case
by repeating the test some number of times. It turns out, that this is
rather inefficient.

In bbchop, the search algorithm does not assume that the test is deterministic.
Therefore, it has to calculate the probabilities in order to know when it has
accumulated enough evidence to accuse a particular commit. It turns
out that it is not much more expensive to calculate which commit we
can expect to  gain the most information from by testing it next.

How can I incorporate your skipping feature into this model? The problem is that
while (just thinking about the linear case for the moment) there is a
fixed boundary at one end - where we actually saw a fault - on the
other side there are a bunch of fuzzy probabilities, ultimately
bounded by wherever we decided the limit of the search was.
So when we get a skip we could hop half way toward the limit. That
would be reasonable toward the beginning of the search, but towards
the end when most of the probability is concentrated in a small number
of commits, it would make no sense.

It would fit a lot better into this algorithm to have some model of
the probability that a commit will cause a skip. It doesn't actually
have to be a very good one, because if it's poor it will only make the
search slightly less efficient, not affect the reliability of the
final result.

Ealdwulf

Re: RFE: "git bisect reverse"

[H. Peter Anvin]

Ealdwulf Wuffinga wrote:
> 
> It would fit a lot better into this algorithm to have some model of
> the probability that a commit will cause a skip. It doesn't actually
> have to be a very good one, because if it's poor it will only make the
> search slightly less efficient, not affect the reliability of the
> final result.
> 

How about simply modelling it linearly, with 100% probability for known
skip point, 0% for a known good/bad point, and a linear gradient in
between?  It's probably a good enough model.  In practice, it will
vastly overestimate the probability of a skip, so if a linear model
turns out to be too conservative, I would probably just try to model it
as a higher-order power function.

	-hpa

Re: RFE: "git bisect reverse"

[Ealdwulf Wuffinga]

On Thu, May 28, 2009 at 10:54 PM, H. Peter Anvin <hpa@zytor.com> wrote:

> How about simply modelling it linearly, with 100% probability for known
> skip point, 0% for a known good/bad point, and a linear gradient in
> between?  It's probably a good enough model.  In practice, it will
> vastly overestimate the probability of a skip, so if a linear model
> turns out to be too conservative, I would probably just try to model it
> as a higher-order power function.

Sounds plausible. It's not obvious how to generalise it to a DAG, though.

What's easier to implement is simple geometric decay (from a
probability of 1 at the commit of an actual skip).  It even has a
plausible rationale - the probability that someone notices the
brokenness
and fixes it is probably a constant, which would lead to geometric
decay. That probably doesn't reflect what happens when someone breaks
a whole swath of stuff retrospectively somehow, though.

I've implemented geometric (and arithmetic) decay in bbchop, with a
configurable decay factor. With a factor sufficiently close to one
(eg, 0.99) it can be persuaded to hop a reasonable distance, which
seems to scale to a certain extent with the number of commits left, so
hopefully it won't be necessary to fiddle with the factor a lot.

http://github.com/Ealdwulf/bbchop/tree/master

Ealdwulf

Re: RFE: "git bisect reverse"

[Christian Couder]

Le Wednesday 27 May 2009, Sam Vilain a écrit :
> H. Peter Anvin wrote:
> > I would like to request the following feature:
> >
> > "git bisect reverse"
> >
> > ... does exactly the same thing as "git bisect start", except that it
> > flips the meaning of "good" and "bad".  It is mentally fairly taxing to
> > do a reverse bisection (looking for an antiregression) when one has to
> > flip the meaning of "good" and "bad" (which are very loaded words to
> > our psyche), and it's even worse to try to get a user to do it...
>
> 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).

s/126/125/

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

Regards,
Christian.

Re: RFE: "git bisect reverse"

[Nanako Shiraishi]

Quoting "H. Peter Anvin" <hpa@zytor.com>:

> I would like to request the following feature:
>
> "git bisect reverse"
>
> ... does exactly the same thing as "git bisect start", except that it
> flips the meaning of "good" and "bad".  It is mentally fairly taxing to
> do a reverse bisection (looking for an antiregression) when one has to
> flip the meaning of "good" and "bad" (which are very loaded words to our
> psyche), and it's even worse to try to get a user to do it...

There was a discussion on "fixed" and "unfixed" aliases to find a commit that fixed an old breakage.

  http://thread.gmane.org/gmane.comp.version-control.git/86063/focus=86563

-- 
Nanako Shiraishi
http://ivory.ap.teacup.com/nanako3/

Re: RFE: "git bisect reverse"

[Matthieu Moy]

Nanako Shiraishi <nanako3@lavabit.com> writes:

> Quoting "H. Peter Anvin" <hpa@zytor.com>:
>
>> I would like to request the following feature:
>>
>> "git bisect reverse"
>>
>> ... does exactly the same thing as "git bisect start", except that it
>> flips the meaning of "good" and "bad".  It is mentally fairly taxing to
>> do a reverse bisection (looking for an antiregression) when one has to
>> flip the meaning of "good" and "bad" (which are very loaded words to our
>> psyche), and it's even worse to try to get a user to do it...
>
> There was a discussion on "fixed" and "unfixed" aliases to find a commit that fixed an old breakage.
>
>   http://thread.gmane.org/gmane.comp.version-control.git/86063/focus=86563

I think the bzr "bisect" plugin uses "yes" and "no" instead for this
reason. I find it mentally easier to adapt it to both cases ("yes,
it's fixed" or "yes, it's broken" depending on what you search).

-- 
Matthieu