Re: [PATCH 0/4] make it possible to skip away from broken commits

Christian Couder [off-list ref] writes:

This patch series adds a "--ratio=x/y" option to "git bisect skip" so
that it is possible to skip away from an area were the commits cannot
be tested.

Note that in this series "--ratio=4" means the same as "--ratio=1/4".
But I am not sure if this shortcut is worth it.

Actually my gut feeling is that a tweakable knob itself is worth it,
because the user can never tell what the right value should be.

Especially without any documentation updates that explains what this ratio
refers to ;-), but I suspect, unless the user is very familiar with how
the revision graph bisection internally works, such an explanation would
not help him find a skip ratio that is closer to the optimum than a random
guess.  Why not use a constant ratio (or perhaps a pair of alternating
ratios) on "bisect skip" without any new options?

Junio C Hamano wrote:

Christian Couder [off-list ref] writes:

quoted

This patch series adds a "--ratio=x/y" option to "git bisect skip" so
that it is possible to skip away from an area were the commits cannot
be tested.

Note that in this series "--ratio=4" means the same as "--ratio=1/4".
But I am not sure if this shortcut is worth it.

Actually my gut feeling is that a tweakable knob itself is worth it,
because the user can never tell what the right value should be.

Especially without any documentation updates that explains what this ratio
refers to ;-), but I suspect, unless the user is very familiar with how
the revision graph bisection internally works, such an explanation would
not help him find a skip ratio that is closer to the optimum than a random
guess.  Why not use a constant ratio (or perhaps a pair of alternating
ratios) on "bisect skip" without any new options?

I would agree with this assessment.  It's hard enough to teach a user
how to use "git bisect" as it is... and being able to have a *user*
bisect a problem is worth its weight in gold.

If the algorithm I proposed earlier is too complex, here is a very
simple approximation:

start:
	num = 1
	den = 2

again:
	run test (num/den)
	if (!skip)
		goto start

	num = num + 2
	if (num > den)	
		num = 1
		den = den * 2

	goto again


This creates test ratios in the following sequence:

1/2 1/4 3/4 1/8 3/8 5/8 7/8 1/16 3/16 ...

When one gets down to a small number of points this could get weird, but
as long as skip points are filtered (which looks like it's already being
 done) it should converge.

This is almost certainly suboptimal, because there are at least two
possibilities as to which is better, and this isn't either:

a) one should seek points closer to the periphery, because the
likelihood of a contiguous skip region goes down.

1/2 1/4 3/4 1/8 7/8 1/16 15/16 ...

b) one should seek points closer to the center in the hope of getting
more information; this is better on the assumption that skip points are
generally scattered:

1/2 1/4 3/4 3/8 5/8 1/8 7/8 7/16 9/16 5/16 11/16 ...

However, as before, I think there is every reason to believe something
like that should be plenty good enough.

	-hpa

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

Le Tuesday 02 June 2009, Junio C Hamano a écrit :

Christian Couder [off-list ref] writes:

quoted

This patch series adds a "--ratio=x/y" option to "git bisect skip" so
that it is possible to skip away from an area were the commits cannot
be tested.

Note that in this series "--ratio=4" means the same as "--ratio=1/4".
But I am not sure if this shortcut is worth it.

Actually my gut feeling is that a tweakable knob itself is worth it,
because the user can never tell what the right value should be.

You mean a boolean configuration variable like "bisect.skip_away" or 
a "--skip_away" switch to "git bisect start" or both?

Especially without any documentation updates that explains what this
ratio refers to ;-), but I suspect, unless the user is very familiar with
how the revision graph bisection internally works, such an explanation
would not help him find a skip ratio that is closer to the optimum than a
random guess.  Why not use a constant ratio (or perhaps a pair of
alternating ratios) on "bisect skip" without any new options?

Ok, I will have a look at that too.

Thanks,
Christian.

Le Wednesday 03 June 2009, H. Peter Anvin a écrit :

Junio C Hamano wrote:

quoted

Christian Couder [off-list ref] writes:

quoted

This patch series adds a "--ratio=x/y" option to "git bisect skip" so
that it is possible to skip away from an area were the commits cannot
be tested.

Note that in this series "--ratio=4" means the same as "--ratio=1/4".
But I am not sure if this shortcut is worth it.

Actually my gut feeling is that a tweakable knob itself is worth it,
because the user can never tell what the right value should be.

Especially without any documentation updates that explains what this
ratio refers to ;-), but I suspect, unless the user is very familiar
with how the revision graph bisection internally works, such an
explanation would not help him find a skip ratio that is closer to the
optimum than a random guess.  Why not use a constant ratio (or perhaps
a pair of alternating ratios) on "bisect skip" without any new options?

I would agree with this assessment.  It's hard enough to teach a user
how to use "git bisect" as it is... and being able to have a *user*
bisect a problem is worth its weight in gold.

If the algorithm I proposed earlier is too complex, here is a very
simple approximation:

start:
	num = 1
	den = 2

again:
	run test (num/den)
	if (!skip)
		goto start

	num = num + 2
	if (num > den)
		num = 1
		den = den * 2

	goto again


This creates test ratios in the following sequence:

1/2 1/4 3/4 1/8 3/8 5/8 7/8 1/16 3/16 ...

When one gets down to a small number of points this could get weird, but
as long as skip points are filtered (which looks like it's already being
 done) it should converge.

I agree. I will have a look.

Thanks,
Christian.

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

Junio C Hamano wrote:

quoted

Christian Couder [off-list ref] writes:

quoted

This patch series adds a "--ratio=x/y" option to "git bisect skip" so
that it is possible to skip away from an area were the commits cannot
be tested.

Note that in this series "--ratio=4" means the same as "--ratio=1/4".
But I am not sure if this shortcut is worth it.

Actually my gut feeling is that a tweakable knob itself is worth it,

I meant "is not" worth it.

quoted

because the user can never tell what the right value should be.

...  Why not use a constant ratio (or perhaps a pair of alternating
ratios) on "bisect skip" without any new options?

I would agree with this assessment....

Thanks for reading what I meant to say, even though I said quite opposite
to what I meant to say ;-)

When one gets down to a small number of points this could get weird, but
as long as skip points are filtered (which looks like it's already being
done) it should converge.

Yes; I think "the next point" selection after "skip" is (or at least can
be handled as) a local thing.  As long as the next point selection is not
too close to the known-to-be-untestable commit we will have a reasonable
coverage over the remainder of the history.  Also I suspect that trying to
be too clever will not help us very much and the end result would be
affected more heavily by the distribution of untestable commits than how
well these next points are chosen.