threads / patch / 17842

patchrev-list: estimate number of bisection step left

Subject: [PATCH] rev-list: estimate number of bisection step left

## tl;dr

13 messages between Feb 17, 2009 and Feb 19, 2009. Diffs are folded; open one to read it.

replies: 12people: 5as markdown or json

Christian Couder· Feb 17, 2009, 05:09 UTC · lore

This patch teaches "git rev-list --bisect-vars" to output an estimate of the number of bisection step left along with the other variables it already outputs.

The estimate is calculated using log2(all_revisions_left/2 - 1). This is the most straightforward formula and seems to work fine in practice.

We substract 1 to "all_revisions_left/2" because we allready know one bad revision.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 builtin-rev-list.c |   27 +++++++++++++++++++++++++--
 git-bisect.sh      |    2 +-
 2 files changed, 26 insertions(+), 3 deletions(-)
Show changes to 2 files +26 −3

builtin-rev-list.c, git-bisect.sh

diff --git a/builtin-rev-list.c b/builtin-rev-list.c
index 436afa4..ee4abe7 100644
--- a/builtin-rev-list.c
+++ b/builtin-rev-list.c
@@ -574,6 +574,27 @@ static struct commit_list *find_bisection(struct commit_list *list,
 	return best;
 }
 
+/*
+ * Estimate the number of bisect steps left
+ * Taking log2(all_revisions_left/2 - 1) seems to work fine.
+ * "- 1" is because we already know one bad revision.
+ */
+static int estimate_bisect_steps(int all)
+{
+	int log2 = 0;
+	int left = (all >> 1) - 1;
+
+	if (left <= 0)
+		return 0;
+
+	do {
+		left = left >> 1;
+		log2++;
+	} while (left);
+
+	return log2;
+}
+
 int cmd_rev_list(int argc, const char **argv, const char *prefix)
 {
 	struct commit_list *list;
@@ -688,12 +709,14 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 			       "bisect_nr=%d\n"
 			       "bisect_good=%d\n"
 			       "bisect_bad=%d\n"
-			       "bisect_all=%d\n",
+			       "bisect_all=%d\n"
+			       "bisect_steps=%d\n",
 			       hex,
 			       cnt - 1,
 			       all - reaches - 1,
 			       reaches - 1,
-			       all);
+			       all,
+			       estimate_bisect_steps(all));
 			return 0;
 		}
 	}
diff --git a/git-bisect.sh b/git-bisect.sh
index 85db4ba..6b23439 100755
--- a/git-bisect.sh
+++ b/git-bisect.sh
@@ -500,7 +500,7 @@ bisect_next() {
 	# commit is also a "skip" commit (see above).
 	exit_if_skipped_commits "$bisect_rev"
 
-	bisect_checkout "$bisect_rev" "$bisect_nr revisions left to test after this"
+	bisect_checkout "$bisect_rev" "$bisect_nr revisions left to test after this (roughtly $bisect_steps steps)"
 }
 
 bisect_visualize() {

-- 
1.6.2.rc0.90.g0753.dirty
Junio C Hamano· Feb 17, 2009, 07:28 UTC · re: Christian Couder · lore

Re: [PATCH] rev-list: estimate number of bisection step left

Christian Couder <chriscool@tuxfamily.org> writes:
Show 26 quoted lines
> +static int estimate_bisect_steps(int all)
> +{
> +	int log2 = 0;
> +	int left = (all >> 1) - 1;
> +
> +	if (left <= 0)
> +		return 0;
> +
> +	do {
> +		left = left >> 1;
> +		log2++;
> +	} while (left);
> +
> +	return log2;
> +}
> ...
> diff --git a/git-bisect.sh b/git-bisect.sh
> index 85db4ba..6b23439 100755
> --- a/git-bisect.sh
> +++ b/git-bisect.sh
> @@ -500,7 +500,7 @@ bisect_next() {
>  	# commit is also a "skip" commit (see above).
>  	exit_if_skipped_commits "$bisect_rev"
>  
> -	bisect_checkout "$bisect_rev" "$bisect_nr revisions left to test after this"
> +	bisect_checkout "$bisect_rev" "$bisect_nr revisions left to test after this (roughtly $bisect_steps steps)"
"roughly".

all left 0 0 1 0 2 0 3 0 4 1 5 1 6 2 7 2 8 2 9 2

It seems that at the very low end the estimate is a bit too optimistic. How about showing this number from the Porcelain only when $bisect_steps is more than 2 (or all is more than 9)?

Christian Couder· Feb 19, 2009, 05:16 UTC · re: Junio C Hamano · lore

Re: [PATCH] rev-list: estimate number of bisection step left

Le mardi 17 février 2009, Junio C Hamano a écrit :
Show 30 quoted lines
> Christian Couder <chriscool@tuxfamily.org> writes:
> > +static int estimate_bisect_steps(int all)
> > +{
> > +	int log2 = 0;
> > +	int left = (all >> 1) - 1;
> > +
> > +	if (left <= 0)
> > +		return 0;
> > +
> > +	do {
> > +		left = left >> 1;
> > +		log2++;
> > +	} while (left);
> > +
> > +	return log2;
> > +}
> > ...
> > diff --git a/git-bisect.sh b/git-bisect.sh
> > index 85db4ba..6b23439 100755
> > --- a/git-bisect.sh
> > +++ b/git-bisect.sh
> > @@ -500,7 +500,7 @@ bisect_next() {
> >  	# commit is also a "skip" commit (see above).
> >  	exit_if_skipped_commits "$bisect_rev"
> >
> > -	bisect_checkout "$bisect_rev" "$bisect_nr revisions left to test
> > after this" +	bisect_checkout "$bisect_rev" "$bisect_nr revisions left
> > to test after this (roughtly $bisect_steps steps)"
>
> "roughly".
Yes, thanks.
Show 15 quoted lines
> all	left
> 0	0
> 1	0
> 2	0
> 3	0
> 4	1
> 5	1
> 6	2
> 7	2
> 8	2
> 9	2
>
> It seems that at the very low end the estimate is a bit too optimistic.
> How about showing this number from the Porcelain only when $bisect_steps
> is more than 2 (or all is more than 9)?
I think it's more consistent to always show it.

Now for the algorithm, first please note that we are looking for an estimate of the number of bisect steps left _after the current one_, and that git bisect currently only displays an estimate of the number of revisions left to test _after the current one_.

Here is a table to help analyse what should be the best estimate for the number of bisect steps left.

N : linear case --> probabilities --> best | v1 ------------------------------------------------------------------ 1 : G-B --> 0 --> 0 | 0 2 : G-U1-B --> 0 --> 0 | 0 3 : G-U1-U2-B --> 0(1/3) 1(2/3) --> 1 | 0 4 : G-U1-U2-U3-B --> 1 --> 1 | 1 5 : G-U1-U2-U3-U4-B --> 1(3/5) 2(2/5) --> 1 | 1 6 : G-U1-U2-U3-U4-U5-B --> 1(2/6) 2(4/6) --> 2 | 2 7 : G-U1-U2-U3-U4-U5-U6-B --> 1(1/7) 2(6/7) --> 2 | 2 8 : G-U1-U2-U3-U4-U5-U6-U7-B --> 2 --> 2 | 2 9 : G-U1-U2-U3-U4-U5-U6-U7-U8-B --> 2(7/9) 3(2/9) --> 2 | 2 10: G-U1-U2-U3-U4-U5-U6-U7-U8-U9-B --> 2(6/10)3(4/10)--> 2 | 3

In the column "N", there is the number of revisions that could _now_ be the first bad commit we are looking for.

The "linear case" column describes the linear history corresponding to the number in column N. G means good, B means bad, and Ux means unknown. Note that the first bad revision we are looking for can be any Ux or B.

In the "probabilities" column, there are the different outcomes in number of steps with the odds of each outcome in parenthesis corresponding to the linear case.

The "best" column gives the most accurate estimate among the different outcomes in the "probabilities" column.

The "v1" column gives the estimates according my first patch.
Now looking at the table, we have the following:
best(2^n) == n - 1

and for any x between 0 included and 2^n excluded, the probability for n - 1 steps left looks like:

P(2^n + x) == (2^n - x) / (2^n + x) 
If P(2^n + x) < 0.5 we should return n and otherwise n - 1.
But P(2^n + x) < 0.5 means:
2 * (2^n - x) < (2^n + x)
that is: 2^n < 3x
So the improved algorithm could be something like:
static int estimate_bisect_steps(int all)
{
	int n, x, e;
	float p;
	if (all < 3)
		return 0;
	n = log2(all);
	e = exp2(n);
	x = all - e;
	return (e < 3 * x) ? n : n - 1 ;
}
But on Linux, log2 and exp2 are defined in "math.h" and available with:
_XOPEN_SOURCE >= 600 || _ISOC99_SOURCE; or cc -std=c99
and we must link with -lm, but I don't know about the other platforms.
So I don't know what to do about them. Please advise.

Thanks in advance, Christian.

Christian Couder· Feb 19, 2009, 05:26 UTC · re: Christian Couder · lore

Re: [PATCH] rev-list: estimate number of bisection step left

Le jeudi 19 février 2009, Christian Couder a écrit :
Show 6 quoted lines
> So the improved algorithm could be something like:
>
> static int estimate_bisect_steps(int all)
> {
> 	int n, x, e;
> 	float p;
Oops, the line above is not needed.
Show 9 quoted lines
> 	if (all < 3)
> 		return 0;
>
> 	n = log2(all);
> 	e = exp2(n);
> 	x = all - e;
>
> 	return (e < 3 * x) ? n : n - 1 ;
> }
Christian Couder· Feb 19, 2009, 05:32 UTC · re: Christian Couder · lore

Re: [PATCH] rev-list: estimate number of bisection step left

Le jeudi 19 février 2009, Christian Couder a écrit :
Show 8 quoted lines
>
> But on Linux, log2 and exp2 are defined in "math.h" and available with:
>
> _XOPEN_SOURCE >= 600 || _ISOC99_SOURCE; or cc -std=c99
>
> and we must link with -lm, but I don't know about the other platforms.
>
> So I don't know what to do about them. Please advise.
What I mean is that log2 is just something like:
int log2 = 0;
for (; n > 1; n >>= 1)
	log2++;

and exp2 is just "1 << n", so I wonder if it's really necessary to add a lot of stuff in the Makefile for these 2 really short functions.

Regards, Christian.

John Tapsell· Feb 19, 2009, 06:02 UTC · re: Christian Couder · lore

Re: [PATCH] rev-list: estimate number of bisection step left

2009/2/19 Christian Couder <chriscool@tuxfamily.org>:
> Le jeudi 19 février 2009, Christian Couder a écrit :
>>
>> But on Linux, log2 and exp2 are defined in "math.h" and available with:

log2 in math.h is for doubles, when we only want an integer answer. There's no need for math.h here.

Christian Couder· Feb 19, 2009, 06:49 UTC · re: John Tapsell · lore

Re: [PATCH] rev-list: estimate number of bisection step left

Le jeudi 19 février 2009, John Tapsell a écrit :
Show 7 quoted lines
> 2009/2/19 Christian Couder <chriscool@tuxfamily.org>:
> > Le jeudi 19 février 2009, Christian Couder a écrit :
> >> But on Linux, log2 and exp2 are defined in "math.h" and available
> >> with:
>
> log2 in math.h is for doubles, when we only want an integer answer.
> There's no need for math.h here.
Yeah, you are right. Sorry about the noise. I will send a patch soon.

Thanks, Christian.

Johannes Schindelin· Feb 17, 2009, 14:44 UTC · re: Christian Couder · lore

Re: [PATCH] rev-list: estimate number of bisection step left

Hi,
On Tue, 17 Feb 2009, Christian Couder wrote:
Show 15 quoted lines
> +static int estimate_bisect_steps(int all)
> +{
> +	int log2 = 0;
> +	int left = (all >> 1) - 1;
> +
> +	if (left <= 0)
> +		return 0;
> +
> +	do {
> +		left = left >> 1;
> +		log2++;
> +	} while (left);
> +
> +	return log2;
> +}
How about this instead, calling it from cmd_rev_list directly?
	static int log2(int n)
	{
		int log2;
		for (log2 = 0; n > 1; log2++)
			n >>= 1;
		return log2;
	}

Ciao, Dscho

John Tapsell· Feb 17, 2009, 15:11 UTC · re: Johannes Schindelin · lore

Re: [PATCH] rev-list: estimate number of bisection step left

2009/2/17 Johannes Schindelin <Johannes.Schindelin@gmx.de>:
Show 31 quoted lines
> Hi,
>
> On Tue, 17 Feb 2009, Christian Couder wrote:
>
>> +static int estimate_bisect_steps(int all)
>> +{
>> +     int log2 = 0;
>> +     int left = (all >> 1) - 1;
>> +
>> +     if (left <= 0)
>> +             return 0;
>> +
>> +     do {
>> +             left = left >> 1;
>> +             log2++;
>> +     } while (left);
>> +
>> +     return log2;
>> +}
>
> How about this instead, calling it from cmd_rev_list directly?
>
>        static int log2(int n)
>        {
>                int log2;
>
>                for (log2 = 0; n > 1; log2++)
>                        n >>= 1;
>
>                return log2;
>        }
This would work, if you want a non-iterative solution

unsigned int log2_integer_approximate(unsigned int n){ *((float*)&n) = (float)n; return ((n & (~((1<<23) - 1))) >> 23) - 127; }

(It's correct up to 2^25, then it's off by 1 for a few.)
Show 7 quoted lines
> Ciao,
> Dscho
> --
> To unsubscribe from this list: send the line "unsubscribe git" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>
Johannes Schindelin· Feb 17, 2009, 15:31 UTC · re: John Tapsell · lore

Re: [PATCH] rev-list: estimate number of bisection step left

Hi,
On Tue, 17 Feb 2009, John Tapsell wrote:
Show 38 quoted lines
> 2009/2/17 Johannes Schindelin <Johannes.Schindelin@gmx.de>:
>
> > On Tue, 17 Feb 2009, Christian Couder wrote:
> >
> >> +static int estimate_bisect_steps(int all)
> >> +{
> >> +     int log2 = 0;
> >> +     int left = (all >> 1) - 1;
> >> +
> >> +     if (left <= 0)
> >> +             return 0;
> >> +
> >> +     do {
> >> +             left = left >> 1;
> >> +             log2++;
> >> +     } while (left);
> >> +
> >> +     return log2;
> >> +}
> >
> > How about this instead, calling it from cmd_rev_list directly?
> >
> >        static int log2(int n)
> >        {
> >                int log2;
> >
> >                for (log2 = 0; n > 1; log2++)
> >                        n >>= 1;
> >
> >                return log2;
> >        }
> 
> This would work, if you want a non-iterative solution
> 
> unsigned int log2_integer_approximate(unsigned int n){
> *((float*)&n) = (float)n;
> return ((n & (~((1<<23) - 1))) >> 23) - 127;
> }
That assumes that your floats are IEEE floats, right?

Ciao, Dscho

John Tapsell· Feb 17, 2009, 15:36 UTC · re: Johannes Schindelin · lore

Re: [PATCH] rev-list: estimate number of bisection step left

2009/2/17 Johannes Schindelin <Johannes.Schindelin@gmx.de>:
Show 44 quoted lines
> Hi,
>
> On Tue, 17 Feb 2009, John Tapsell wrote:
>
>> 2009/2/17 Johannes Schindelin <Johannes.Schindelin@gmx.de>:
>>
>> > On Tue, 17 Feb 2009, Christian Couder wrote:
>> >
>> >> +static int estimate_bisect_steps(int all)
>> >> +{
>> >> +     int log2 = 0;
>> >> +     int left = (all >> 1) - 1;
>> >> +
>> >> +     if (left <= 0)
>> >> +             return 0;
>> >> +
>> >> +     do {
>> >> +             left = left >> 1;
>> >> +             log2++;
>> >> +     } while (left);
>> >> +
>> >> +     return log2;
>> >> +}
>> >
>> > How about this instead, calling it from cmd_rev_list directly?
>> >
>> >        static int log2(int n)
>> >        {
>> >                int log2;
>> >
>> >                for (log2 = 0; n > 1; log2++)
>> >                        n >>= 1;
>> >
>> >                return log2;
>> >        }
>>
>> This would work, if you want a non-iterative solution
>>
>> unsigned int log2_integer_approximate(unsigned int n){
>> *((float*)&n) = (float)n;
>> return ((n & (~((1<<23) - 1))) >> 23) - 127;
>> }
>
> That assumes that your floats are IEEE floats, right?
Yeah.  Is it a bad assumption? Does git run on any system in which they aren't?
>
> Ciao,
> Dscho
>
Johannes Schindelin· Feb 17, 2009, 15:39 UTC · re: John Tapsell · lore

Re: [PATCH] rev-list: estimate number of bisection step left

Hi,
On Tue, 17 Feb 2009, John Tapsell wrote:
Show 47 quoted lines
> 2009/2/17 Johannes Schindelin <Johannes.Schindelin@gmx.de>:
>
> > On Tue, 17 Feb 2009, John Tapsell wrote:
> >
> >> 2009/2/17 Johannes Schindelin <Johannes.Schindelin@gmx.de>:
> >>
> >> > On Tue, 17 Feb 2009, Christian Couder wrote:
> >> >
> >> >> +static int estimate_bisect_steps(int all)
> >> >> +{
> >> >> +     int log2 = 0;
> >> >> +     int left = (all >> 1) - 1;
> >> >> +
> >> >> +     if (left <= 0)
> >> >> +             return 0;
> >> >> +
> >> >> +     do {
> >> >> +             left = left >> 1;
> >> >> +             log2++;
> >> >> +     } while (left);
> >> >> +
> >> >> +     return log2;
> >> >> +}
> >> >
> >> > How about this instead, calling it from cmd_rev_list directly?
> >> >
> >> >        static int log2(int n)
> >> >        {
> >> >                int log2;
> >> >
> >> >                for (log2 = 0; n > 1; log2++)
> >> >                        n >>= 1;
> >> >
> >> >                return log2;
> >> >        }
> >>
> >> This would work, if you want a non-iterative solution
> >>
> >> unsigned int log2_integer_approximate(unsigned int n){
> >> *((float*)&n) = (float)n;
> >> return ((n & (~((1<<23) - 1))) >> 23) - 127;
> >> }
> >
> > That assumes that your floats are IEEE floats, right?
> 
> Yeah.  Is it a bad assumption? Does git run on any system in which they 
> aren't?
Only when you are porting Git to embedded devices.

Don't moan: there exists a git-daemon for iPhone. Oh, wait! /me scribbles that down for the UGFWIINI contest.

Ciao, Dscho

Thomas Rast· Feb 17, 2009, 15:39 UTC · re: Johannes Schindelin · lore

Re: [PATCH] rev-list: estimate number of bisection step left

Johannes Schindelin wrote:
> > unsigned int log2_integer_approximate(unsigned int n){
[...]
> That assumes that your floats are IEEE floats, right?

For extra weird code, you could the standard 5-line bit order inverter and apply ffs().

;-)
-- 
Thomas Rast
trast@{inf,student}.ethz.ch

← back to recent threads