Skip to contentSkip to conversation

RFE: "git bisect reverse"

DISCUSSION H. Peter Anvin 7 participants 18 messages Jun 15, 2016

lore
Share & tools
lore
#0 lore raw

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

#1 lore raw

Quoting "H. Peter Anvin" <[email protected]>:

Quoted 9 lines

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

Signature · 2 lines
Nanako Shiraishi
http://ivory.ap.teacup.com/nanako3/
#2 lore raw
Quoted 12 lines · Nanako Shiraishi

Quoting "H. Peter Anvin" <[email protected]>:

Quoted 9 lines

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

Quoted 3 lines

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

Signature · 1 line
Matthieu
#3 lore raw
In reply to H. Peter Anvin
Quoted 10 lines · 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...

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.

#4 lore raw
Quoted 11 lines · Sam Vilain
Quoted 9 lines · 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...

Quoted 3 lines

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/

Quoted 4 lines

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.

#5 lore raw
In reply to Sam Vilain
Quoted 7 lines · Sam Vilain

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&[email protected]

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

-hpa

Signature · 2 lines
H. Peter Anvin, Intel Open Source Technology Center
I work for Intel.  I don't speak on their behalf.
#6 lore raw
Quoted 8 lines · H. Peter Anvin
Quoted 6 lines · Sam Vilain

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.

Quoted 6 lines

I posted about that last year:

http://marc.info/?l=git&[email protected]

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.

#7 lore raw
Quoted 7 lines
Quoted 7 lines
Quoted 6 lines · Sam Vilain

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

#8 lore raw
Quoted 8 lines · Ealdwulf Wuffinga
Quoted 7 lines
Quoted 7 lines
Quoted 6 lines · Sam Vilain

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.

Quoted 4 lines

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.

#9 lore raw
Quoted 14 lines · Clemens Buchacher
Quoted 8 lines · Ealdwulf Wuffinga
Quoted 7 lines
Quoted 7 lines
Quoted 6 lines · Sam Vilain

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.

Quoted 4 lines

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?

Quoted 5 lines

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

#10 lore raw
Quoted 7 lines · Ealdwulf Wuffinga

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.

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

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

#11 lore raw
Quoted 14 lines · Sam Vilain
Quoted 11 lines · Ealdwulf Wuffinga

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

Quoted 1 line

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

#12 lore raw
Quoted 10 lines · Ealdwulf Wuffinga
Quoted 2 lines

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.

Quoted 7 lines

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.

#14 lore raw
In reply to Ealdwulf Wuffinga
Quoted 10 lines · Ealdwulf Wuffinga

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

Signature · 2 lines
H. Peter Anvin, Intel Open Source Technology Center
I work for Intel.  I don't speak on their behalf.
#15 lore raw
Quoted 5 lines · H. Peter Anvin

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

Quoted 8 lines

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

#16 lore raw
Quoted 7 lines · Ealdwulf Wuffinga

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

#13 lore raw
In reply to Sam Vilain
Quoted 4 lines · Sam Vilain

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

#17 lore raw
In reply to H. Peter Anvin
Quoted 6 lines · H. Peter Anvin

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