Re: [PATCH v3 0/3] automatically skip away from broken commits

"H. Peter Anvin" [off-list ref] writes:

The advantage of that -- and I have to admit I don't know if it will
ever matter in practice -- is that using an actual PRNG:

a) is less likely to get into pathological capture behaviors.
b) doesn't make people think later that there is something magic to the
   arbitrary chosen numbers.

My gut feeling agrees with you that both are likely to be true; these are
good points.

Christian, what do you think?

Junio C Hamano wrote:

"H. Peter Anvin" [off-list ref] writes:

quoted

The advantage of that -- and I have to admit I don't know if it will
ever matter in practice -- is that using an actual PRNG:

a) is less likely to get into pathological capture behaviors.
b) doesn't make people think later that there is something magic to the
   arbitrary chosen numbers.

My gut feeling agrees with you that both are likely to be true; these are
good points.

Christian, what do you think?

Note: I do believe we should keep the obvious optimization of "if there
are no skip points in the plausible range, use the best point."  We
don't want a 39% increase in bisect time when not using skip.

	-hpa

On Mon, Jun 8, 2009 at 11:02 PM, Junio C Hamano[off-list ref] wrote:

"H. Peter Anvin" [off-list ref] writes:

quoted

The advantage of that -- and I have to admit I don't know if it will
ever matter in practice -- is that using an actual PRNG:

a) is less likely to get into pathological capture behaviors.
b) doesn't make people think later that there is something magic to the
   arbitrary chosen numbers.

My gut feeling agrees with you that both are likely to be true; these are
good points.

Christian, what do you think?

Here are some reasons why I think my algorithm might be better:

- using HPA's formula I get on average 0.86 bits of information at
each step when alternating (against 0.72 when using a PRNG)
- I think that if the branches in the graph merge often between each
other, then on a big scale it's like when you are on the linear case
- I don't think we should try too hard to avoid pathological capture
behaviors, because I think we can't avoid them anyway in some cases,
like if the first bad commit is near many untestable commits

In the end I think that when you have too many long and completely
untestable branches for example, the right solution would be to have
something that lets you cut them off your graph and bisect on a much
cleaner graph, that's why I started working on "git replace" in the
first place.

I think we should not penalize people who have a quite clean graph
because some other people have a much dirtier one.

So I would be ok to implement a config option or a switch to "git
bisect start" to let people use a PRNG instead of my algorithm but I
think something like my algorithm should be the default.

Best regards,
Christian.

Christian Couder [off-list ref] writes:

On Mon, Jun 8, 2009 at 11:02 PM, Junio C Hamano[off-list ref] wrote:

quoted

"H. Peter Anvin" [off-list ref] writes:

quoted

The advantage of that -- and I have to admit I don't know if it will
ever matter in practice -- is that using an actual PRNG:

a) is less likely to get into pathological capture behaviors.
b) doesn't make people think later that there is something magic to the
   arbitrary chosen numbers.

My gut feeling agrees with you that both are likely to be true; these are
good points.

Christian, what do you think?

Here are some reasons why I think my algorithm might be better:

- using HPA's formula I get on average 0.86 bits of information at
each step when alternating (against 0.72 when using a PRNG)
- I think that if the branches in the graph merge often between each
other, then on a big scale it's like when you are on the linear case
- I don't think we should try too hard to avoid pathological capture
behaviors, because I think we can't avoid them anyway in some cases,
like if the first bad commit is near many untestable commits

By the way, I have asked question about best algorithm for "bisect skip"
on StackOverflow[1], but didn't get (yet) any good responses...

[1]: http://stackoverflow.com/questions/959324/

-- 
Jakub Narebski
Poland
ShadeHawk on #git

On Tue, Jun 9, 2009 at 6:24 AM, Christian
Couder[off-list ref] wrote:

So I would be ok to implement a config option or a switch to "git
bisect start" to let people use a PRNG instead of my algorithm but I
think something like my algorithm should be the default.

Another reason to have 2 algorithms is that when you use "git bisect
run" you might want to use the PRNG one because:

- you don't care much if the bisection use some more steps (as long as
it does not get stuck)
- you can't do much if it get stuck

On the other hand, when you bisect manually:

- you probably won't like it if you are asked to test some commits
that won't give a lot of information
- if it get stuck, you can manually use "git bisect visualize" and/or
"git bisect skip <range>" and/or some other manual commands to do
something about it

Regards,
Christian.

Christian Couder wrote:

On Tue, Jun 9, 2009 at 6:24 AM, Christian
Couder[off-list ref] wrote:

quoted

So I would be ok to implement a config option or a switch to "git
bisect start" to let people use a PRNG instead of my algorithm but I
think something like my algorithm should be the default.

Another reason to have 2 algorithms is that when you use "git bisect
run" you might want to use the PRNG one because:

- you don't care much if the bisection use some more steps (as long as
it does not get stuck)
- you can't do much if it get stuck

On the other hand, when you bisect manually:

- you probably won't like it if you are asked to test some commits
that won't give a lot of information
- if it get stuck, you can manually use "git bisect visualize" and/or
"git bisect skip <range>" and/or some other manual commands to do
something about it

Sort-of-kind-of.  I doubt most users will be able to recover from a
stuck situation, and unless we have extremely high cost of testing
(which is true for some applications) then expecting the user to
optimizing manually is really bad user design.

My main objection to the "skip in goodness space" is exactly the same as
Junio's... it doesn't really buy you what it claims to sell.

	-hpa

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

Jakub Narebski wrote:

By the way, I have asked question about best algorithm for "bisect skip"
on StackOverflow[1], but didn't get (yet) any good responses...

[1]: http://stackoverflow.com/questions/959324/

I don't think there is a "best" algorithm, but I concur with the poster
that said broken commits tend to cluster.

	-hpa

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

On Tue, Jun 9, 2009 at 5:25 PM, H. Peter Anvin[off-list ref] wrote:

Christian Couder wrote:

quoted

On Tue, Jun 9, 2009 at 6:24 AM, Christian
Couder[off-list ref] wrote:

quoted

So I would be ok to implement a config option or a switch to "git
bisect start" to let people use a PRNG instead of my algorithm but I
think something like my algorithm should be the default.

Another reason to have 2 algorithms is that when you use "git bisect
run" you might want to use the PRNG one because:

- you don't care much if the bisection use some more steps (as long as
it does not get stuck)
- you can't do much if it get stuck

On the other hand, when you bisect manually:

- you probably won't like it if you are asked to test some commits
that won't give a lot of information
- if it get stuck, you can manually use "git bisect visualize" and/or
"git bisect skip <range>" and/or some other manual commands to do
something about it

Sort-of-kind-of.  I doubt most users will be able to recover from a
stuck situation, and unless we have extremely high cost of testing
(which is true for some applications) then expecting the user to
optimizing manually is really bad user design.

My opinion is that we should not penalize all the people working on
"quite clean" projects and also people working on "not clean" projects
who are able to recover, on the pretence that there are other people
on these "not clean" projects who are not.

I think it's the projects maintainers' responsibility to keep their
projects graphs quite clean (and they have the right to ask git
developers for the tools to do that). If they don't do so, then their
users will suffer anyway. So it's not a big deal to ask them to teach
their users to add a "--prng" option to "git bisect start" for example
or something like that to try to work around the "not cleanliness" of
their graphs.

Best regards,
Christian.

Christian Couder wrote:

quoted

quoted

Sort-of-kind-of.  I doubt most users will be able to recover from a
stuck situation, and unless we have extremely high cost of testing
(which is true for some applications) then expecting the user to
optimizing manually is really bad user design.

My opinion is that we should not penalize all the people working on
"quite clean" projects and also people working on "not clean" projects
who are able to recover, on the pretence that there are other people
on these "not clean" projects who are not.

I think it's the projects maintainers' responsibility to keep their
projects graphs quite clean (and they have the right to ask git
developers for the tools to do that).

No, it's not.  This is saying "it's the user's responsibility to make up
for shortcomings in the tools", which is completely bass-ackwards.

If they don't do so, then their
users will suffer anyway. So it's not a big deal to ask them to teach
their users to add a "--prng" option to "git bisect start" for example
or something like that to try to work around the "not cleanliness" of
their graphs.

Let's see... we can penalize the default user by 19% (the amount of
difference) if and only if they have skip points (at which point your
"project manager's responsibility" has already failed) or we can risk an
inexperienced user getting stuck?

	-hpa

On Tue, 9 June 2009, H. Peter Anvin wrote:

Jakub Narebski wrote:

quoted

By the way, I have asked question about best algorithm for "bisect skip"
on StackOverflow[1], but didn't get (yet) any good responses...

[1]: http://stackoverflow.com/questions/959324/

I don't think there is a "best" algorithm, but I concur with the poster
that said broken commits tend to cluster.

Well, I guess that there might be, at least if we had some reasonable
assumption on probability distribution of bad commits.


Note: the idea sketched below is just handwaving currently...

Let us assume that we are currently at some untestable commit. Let us
also assume that we have some halfway reasonable model of probability
that a given commit is untestable, given it distance from known
untestable commit. "git rev-list --bisect-all" (or its inner equivalent)
would give us list of commits in the searched range, sorted in 
descending order by distance from edges (endpoints) of range:

  commit    "goodness" 
  --------------------
  c21d2e5*  (dist=60)
  94d6d14   (dist=59)
  ccb06f4   (dist=59)
  d1a1610   (dist=58)
  d4bf4b4   (dist=58)
  16c5646   (dist=57)

Let us assume that "c21d2e5" is untestable, and that we can easily 
calculate distance from it, substituting 0/0 (undef) if a commit
is not in straight line from "c21d2e5".

  commit    "goodness"  d
  -------------------------
  c21d2e5*  (dist=60)   0
  94d6d14   (dist=59)   1
  ccb06f4   (dist=59)   --
  d1a1610   (dist=58)   --
  d4bf4b4   (dist=58)   2
  16c5646   (dist=57)   3

Let us also assume that we have some model of probability that a commit
is untestable. In the example below numbers are ad hoc, and unrealistic.

  commit    "goodness"  d   P(untestable)
  ----------------------------------------
  c21d2e5*  (dist=60)   0   100%
  94d6d14   (dist=59)   1    75%
  ccb06f4   (dist=59)   --    0%
  d1a1610   (dist=58)   --    0%
  d4bf4b4   (dist=58)   2    33%
  16c5646   (dist=57)   3    25%

We can now calculate average number of bits of information would bring
(IIRC it was HPA and Christian that was writing about 'average information
gain' and 'bits of information at each step'; I don't quote know how it
is to be calculated)

  commit    "goodness"  d   P(untestable)  avg. gain
  ----------------------------------------
  c21d2e5*  (dist=60)   0   100%           0.0001
  94d6d14   (dist=59)   1    75%           0.45
  ccb06f4   (dist=59)   --    0%           0.98
  d1a1610   (dist=58)   --    0%           0.95
  d4bf4b4   (dist=58)   2    33%           0.65
  16c5646   (dist=57)   3    25%           0.66

Here 'avg. gain' numbers are totally handwaving... but the idea is to
pick up as next test point the commit with mist average information
gain.

What do you think of this algorithm (after of course it is made into
proper algorithm :-))?
-- 
Jakub Narebski
Poland

Jakub Narebski wrote:

Let us also assume that we have some model of probability that a commit
is untestable. In the example below numbers are ad hoc, and unrealistic.

What I mostly meant was that there simply is no such model that will be
ideal (since we simply don't have that information, almost by
definition), so therefore the overall algorithm can't be ideal, either.

However, Christian and you do make a very good point that instead of a
linear-probability random selection, it probably makes sense to bias the
randomness in favor of the commits that are more likely to provide
higher information gain.  This is effectively what Christian's patch
does in a somewhat clumsy way.

One of the nice things about combining a random algorithm with bias is
that the bias doesn't have to be perfect, it just have to be good
enough.  For example, we can take dramatic shortcuts like not taking
topology into accounts.

A logical bias function would indeed be an estimate of the information
gain.  One way we can calculate the effective information gain is by
take the list in "goodness order" that we already have, and treat it as
if it had originally been a linear history -- this will usually not be
the case, but we're probabilistically getting away with murder here.

The sorting in "goodness order" of a linear history means sorting
middlemost first, so the modified information density function with x
being the position in the list (x = 0 for best, x = 1 for worst) looks like:

- 1/(2 ln 2) * [ (1-x) ln (1-x) + (1+x) ln (1+x) - 2 ln 2 ]

I'd have to brush up some more of my calculus in order to remember how
to come up with a transformation function which would take a random
number and give us this exact probability distribution, but again, I
don't think it's hugely important; I suspect any function which gives us
a probability distribution that's even in the right neighborhood would
give us excellent results.

	-hpa

On Tue, Jun 9, 2009 at 9:32 PM, H. Peter Anvin[off-list ref] wrote:

Christian Couder wrote:

quoted

quoted

quoted

Sort-of-kind-of.  I doubt most users will be able to recover from a
stuck situation, and unless we have extremely high cost of testing
(which is true for some applications) then expecting the user to
optimizing manually is really bad user design.

My opinion is that we should not penalize all the people working on
"quite clean" projects and also people working on "not clean" projects
who are able to recover, on the pretence that there are other people
on these "not clean" projects who are not.

By the way, if for example you have a project with 10% chance to land
in a "stuck area" of the graph, then with my algorithm the chance to
get stuck when you hit an untestable commit is 0.1^3 that is 0.1%. So
in this kind of projects the chance that the first bad commit is near
a lot untestable commits is much higher than that.

In fact I think that it's probably very hard to find a kind of project
where the chance to get stuck when using my algorithm is not dwarfed
by the chance of the first bad commit to be near or among many
untestable commits.

quoted

I think it's the projects maintainers' responsibility to keep their
projects graphs quite clean (and they have the right to ask git
developers for the tools to do that).

No, it's not.  This is saying "it's the user's responsibility to make up
for shortcomings in the tools", which is completely bass-ackwards.

I think that what I said is just the opposite that. If you find
shortcomings in the tools then you are welcome to ask us to fix them.

And if users find shortcomings in the cleanliness of the project
graph, they should be welcome to ask the maintainers to provide them
with ways to work around them, like for example a file that contains
many commits and range of commits that should always be skipped and
that can be used like for example:

$ git bisect start
$ git bisect skip $(cat always_skipped_file)
$ git bisect good ...
$ git bisect bad ...
...

Or the maintainers can in turn ask git developers what's going on with
"git replace" if they would prefer using that instead of such a
file...

quoted

If they don't do so, then their
users will suffer anyway. So it's not a big deal to ask them to teach
their users to add a "--prng" option to "git bisect start" for example
or something like that to try to work around the "not cleanliness" of
their graphs.

Let's see... we can penalize the default user by 19% (the amount of
difference) if and only if they have skip points (at which point your
"project manager's responsibility" has already failed) or we can risk an
inexperienced user getting stuck?

I am not sure I understand you very well but as I said above I think
with a "reasonably clean" graph the risk of the inexperienced user
getting stuck because of my algorithm is very low compared to the risk
of getting stuck because the first bad commit happens to be near many
untestable ones.

Best regards,
Christian.