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

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 <redacted>
---
 builtin-rev-list.c |   27 +++++++++++++++++++++++++--
 git-bisect.sh      |    2 +-
 2 files changed, 26 insertions(+), 3 deletions(-)

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

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;
	}

Ciao,
Dscho

2009/2/17 Johannes Schindelin [off-list ref]:

Hi,

On Tue, 17 Feb 2009, Christian Couder wrote:

quoted

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

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

Hi,

On Tue, 17 Feb 2009, John Tapsell wrote:

2009/2/17 Johannes Schindelin [off-list ref]:

quoted

On Tue, 17 Feb 2009, Christian Couder wrote:

quoted

+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

2009/2/17 Johannes Schindelin [off-list ref]:

Hi,

On Tue, 17 Feb 2009, John Tapsell wrote:

quoted

2009/2/17 Johannes Schindelin [off-list ref]:

quoted

On Tue, 17 Feb 2009, Christian Couder wrote:

quoted

+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 wrote:

quoted

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

Hi,

On Tue, 17 Feb 2009, John Tapsell wrote:

2009/2/17 Johannes Schindelin [off-list ref]:

quoted

On Tue, 17 Feb 2009, John Tapsell wrote:

quoted

2009/2/17 Johannes Schindelin [off-list ref]:

quoted

On Tue, 17 Feb 2009, Christian Couder wrote:

quoted

+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