RFE: "git bisect reverse"

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

H. Peter Anvin 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.

Sam.

Sam Vilain wrote:

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

Le Wednesday 27 May 2009, H. Peter Anvin a écrit :

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.

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

On Wed, May 27, 2009 at 10:11:35PM +0100, Ealdwulf Wuffinga wrote:

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.

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

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

Ealdwulf Wuffinga wrote:

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

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

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

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

Sam.

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

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

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

	-hpa

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

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

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

	-hpa

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

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

Le Wednesday 27 May 2009, Sam Vilain a écrit :

s/126/125/

Regards, Christian.

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

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 <nanako3@lavabit.com> writes:

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