[PATCH 00/16] git bisect improvements

[PATCH 00/16] git bisect improvements

[Stephan Beyer]

Hi,

this set of patches provides improvements for git bisect.

Quick summary of changes
 - relevant for users:
   - `git bisect next` is documented and motivated
   - git bisect implementation becomes much faster
     (or: is now working) for big repositories**
 - relevant for developers:
   - a test for the git bisect algorithm is added
   - fix: bisect.c compiles also if DEBUG_BISECT is set

The ** marked change is the most interesting one.
To be more accurate: the use case is when you want to bisect in a
repository with a huge amount of merge commits (and having these
merge commits relevant for the actual bisect process).
For example, a bisect in the whole git master branch took
~50 seconds, now it takes ~4 seconds.


Note that the patches have finer granularity (especially the performance
improvements are splitted into several preparing commits).
For some patches, there is some more patch-related story as
"cover letter material" in these patches.

Btw: I also wondered about the internationalizaton: no string in bisect.c
is marked for translation. Intentionally?

Cheers

Stephan Beyer (16):
  bisect: write about `bisect next` in documentation
  bisect: add test for the bisect algorithm
  bisect: make bisect compile if DEBUG_BISECT is set
  bisect: make algorithm behavior independent of DEBUG_BISECT
  bisect: get rid of recursion in count_distance()
  bisect: use struct node_data array instead of int array
  bisect: replace clear_distance() by unique markers
  bisect: use commit instead of commit list as arguments when
    appropriate
  bisect: extract get_distance() function from code duplication
  bisect: introduce distance_direction()
  bisect: make total number of commits global
  bisect: rename count_distance() to compute_weight()
  bisect: prepare for different algorithms based on find_all
  bisect: use a modified breadth-first search to find relevant weights
  bisect: compute best bisection in compute_relevant_weights()
  bisect: get back halfway shortcut

 Documentation/git-bisect.txt |  25 +++
 bisect.c                     | 473 ++++++++++++++++++++++++++++---------------
 git-bisect.sh                |  15 +-
 t/t8010-bisect-algorithm.sh  | 162 +++++++++++++++
 4 files changed, 502 insertions(+), 173 deletions(-)
 create mode 100755 t/t8010-bisect-algorithm.sh

-- 
2.7.1.354.gd492730.dirty

[PATCH 01/16] bisect: write about `bisect next` in documentation

[Stephan Beyer]

Mention `bisect next` in the documentation of bisect.
`bisect next` is only useful in rare cases and the result
can also be accomplished using other utilities (like reflog).
However, it is available as a bisect command and should hence be
documented.

Also mention the use case when no good commit is known.
Some user message in git-bisect.sh is changed to reflect that
use case. It is also simplified: there is no need to mention
running `bisect start` explicitly, because it can be done
indirectly using `bisect bad`.

Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
---

This patch considers the source code comment that says to be
"not sure we want 'next' at the UI level anymore", and replies with
"Yes, we want it!". Therefore, the "git bisect next" functionality
is explicitly motivated and documented.

The motivation of "having no good commit" is not made up. I am
working on a big project that is several years old and nearly
no test exists. So I add a test and things go wrong. However,
I know from using (an older version of) the project that a similar
case did work. So...I want to find the bad commit...
However, to make git bisect work, I always first had to find a good
commit, so I ended up doing the whole bisection process manually
(because I did not know that "git bisect next" existed).

I think that this change will help people who are also in these
situations.

 Documentation/git-bisect.txt | 25 +++++++++++++++++++++++++
 git-bisect.sh                | 15 ++++-----------
 2 files changed, 29 insertions(+), 11 deletions(-)

diff --git a/Documentation/git-bisect.txt b/Documentation/git-bisect.txt
index 7e79aae..8045e6d 100644
--- a/Documentation/git-bisect.txt
+++ b/Documentation/git-bisect.txt
@@ -27,6 +27,7 @@ on the subcommand:
  git bisect replay <logfile>
  git bisect log
  git bisect run <cmd>...
+ git bisect next
  git bisect help
 
 This command uses a binary search algorithm to find which commit in
@@ -66,6 +67,15 @@ checks it out, and outputs something similar to the following:
 Bisecting: 675 revisions left to test after this (roughly 10 steps)
 ------------------------------------------------
 
+Note that in cases you do not know a good commit,
+you can also start with:
+
+------------------------------------------------
+$ git bisect start
+$ git bisect bad                 # current version is bad
+$ git bisect next                # check out another commit
+------------------------------------------------
+
 You should now compile the checked-out version and test it. If that
 version works correctly, type
 
@@ -353,6 +363,21 @@ rewind the tree to the pristine state.  Finally the script should exit
 with the status of the real test to let the `git bisect run` command loop
 determine the eventual outcome of the bisect session.
 
+Bisect next
+~~~~~~~~~~~
+
+Sometimes it can be necessary to check out other branches during a bisect
+session. If you want to check out the next commit of the bisection again,
+simply issue the command:
+
+------------
+$ git bisect next
+------------
+
+Another typical use case of this command is when you have marked a commit
+as bad but you do not know a good commit. Instead of crawling through the
+history yourself, let this command check out a commit for you.
+
 OPTIONS
 -------
 --no-checkout::
diff --git a/git-bisect.sh b/git-bisect.sh
index 5d1cb00..5c93a27 100755
--- a/git-bisect.sh
+++ b/git-bisect.sh
@@ -334,16 +334,10 @@ bisect_next_check() {
 	*)
 		bad_syn=$(bisect_voc bad)
 		good_syn=$(bisect_voc good)
-		if test -s "$GIT_DIR/BISECT_START"
-		then
-
-			eval_gettextln "You need to give me at least one \$bad_syn and one \$good_syn revision.
-(You can use \"git bisect \$bad_syn\" and \"git bisect \$good_syn\" for that.)" >&2
-		else
-			eval_gettextln "You need to start by \"git bisect start\".
-You then need to give me at least one \$good_syn and one \$bad_syn revision.
-(You can use \"git bisect \$bad_syn\" and \"git bisect \$good_syn\" for that.)" >&2
-		fi
+		eval_gettextln "You need to give me at least one \$bad_syn revision.
+Use \"git bisect \$bad_syn\" for that. One \$good_syn revision is also helpful
+for bisecting (use \"git bisect \$good_syn\"). If you do not know one \$good_syn
+revision, you can use \"git bisect next\" to find one." >&2
 		exit 1 ;;
 	esac
 }
@@ -677,7 +671,6 @@ case "$#" in
 	skip)
 		bisect_skip "$@" ;;
 	next)
-		# Not sure we want "next" at the UI level anymore.
 		bisect_next "$@" ;;
 	visualize|view)
 		bisect_visualize "$@" ;;
-- 
2.7.1.354.gd492730.dirty

Re: [PATCH 01/16] bisect: write about `bisect next` in documentation

[Jacob Keller]

On Thu, Feb 25, 2016 at 6:04 PM, Stephan Beyer <s-beyer@gmx.net> wrote:
> This patch considers the source code comment that says to be
> "not sure we want 'next' at the UI level anymore", and replies with
> "Yes, we want it!". Therefore, the "git bisect next" functionality
> is explicitly motivated and documented.
>

I did not know about this, but I definitely would have found it useful
in the past.

Thanks,
Jake

Re: [PATCH 01/16] bisect: write about `bisect next` in documentation

[Junio C Hamano]

Stephan Beyer <s-beyer@gmx.net> writes:

> +Bisect next
> +~~~~~~~~~~~
> +
> +Sometimes it can be necessary to check out other branches during a bisect
> +session. If you want to check out the next commit of the bisection again,
> +simply issue the command:
> +
> +------------
> +$ git bisect next
> +------------

Hmph, I am not quite sure what you mean by checking out other
branches during a bisect session.

During bisection, you are on a detached HEAD with refs/bisect/*
holding the current state, and "next" indeed is a way to recompute
the commit to be tested based on that state.

But I wonder if it is safe and sane to encourage "checking out other
branches during a bisect session." as you cannot tell what other
crazy things they will do while on "other branches".  I do not think
we even try to (and I do not think we should) handle a case where
the user tries to merge another branch, sees conflicts and says
"bisect next" without cleaning up, for example.

> +Another typical use case of this command is when you have marked a commit
> +as bad but you do not know a good commit. Instead of crawling through the
> +history yourself, let this command check out a commit for you.

I would say this is the only sensible use of "next", but as you
cannot see ;-) in the comment from the pre-context of the patch
below, "have bad but not good. we could bisect althoguh this is less
optimum.", I am not sure if it is a good idea to say "is also helpful"
as if we are encouraging such a usage.

>  OPTIONS
>  -------
>  --no-checkout::
> diff --git a/git-bisect.sh b/git-bisect.sh
> index 5d1cb00..5c93a27 100755
> --- a/git-bisect.sh
> +++ b/git-bisect.sh
> @@ -334,16 +334,10 @@ bisect_next_check() {
>  	*)
>  		bad_syn=$(bisect_voc bad)
>  		good_syn=$(bisect_voc good)
> -		if test -s "$GIT_DIR/BISECT_START"
> -		then
> -
> -			eval_gettextln "You need to give me at least one \$bad_syn and one \$good_syn revision.
> -(You can use \"git bisect \$bad_syn\" and \"git bisect \$good_syn\" for that.)" >&2
> -		else
> -			eval_gettextln "You need to start by \"git bisect start\".
> -You then need to give me at least one \$good_syn and one \$bad_syn revision.
> -(You can use \"git bisect \$bad_syn\" and \"git bisect \$good_syn\" for that.)" >&2
> -		fi
> +		eval_gettextln "You need to give me at least one \$bad_syn revision.
> +Use \"git bisect \$bad_syn\" for that. One \$good_syn revision is also helpful
> +for bisecting (use \"git bisect \$good_syn\"). If you do not know one \$good_syn
> +revision, you can use \"git bisect next\" to find one." >&2
>  		exit 1 ;;
>  	esac
>  }
> @@ -677,7 +671,6 @@ case "$#" in
>  	skip)
>  		bisect_skip "$@" ;;
>  	next)
> -		# Not sure we want "next" at the UI level anymore.
>  		bisect_next "$@" ;;
>  	visualize|view)
>  		bisect_visualize "$@" ;;

Re: [PATCH 01/16] bisect: write about `bisect next` in documentation

[Stephan Beyer]

Hi,

On 02/26/2016 07:47 PM, Junio C Hamano wrote:
> But I wonder if it is safe and sane to encourage "checking out other
> branches during a bisect session." as you cannot tell what other
> crazy things they will do while on "other branches".  I do not think
> we even try to (and I do not think we should) handle a case where
> the user tries to merge another branch, sees conflicts and says
> "bisect next" without cleaning up, for example.

I rephrase it as follows to not encourage checking out another branch
(or commit ;]) but to mention that it works to get back if someone
accidentally did it.

--8<--8<--8<--

Bisect next
~~~~~~~~~~~

In case you have marked a commit as bad but you do not know a good
commit, you do not have to crawl through the commit history yourself to
find a good commit. Simply issue the command:

------------
$ git bisect next
------------

This command is also handy when you accidentally checked out another
commit during a bisection. It computes the commit for the bisection
and checks it out again.

-->8-->8-->8--

Is that better?

Thanks,
Stephan

Re: [PATCH 01/16] bisect: write about `bisect next` in documentation

[Junio C Hamano]

Stephan Beyer <s-beyer@gmx.net> writes:

> I rephrase it as follows to not encourage checking out another branch
> (or commit ;]) but to mention that it works to get back if someone
> accidentally did it.
>
> --8<--8<--8<--
>
> Bisect next
> ~~~~~~~~~~~
>
> In case you have marked a commit as bad but you do not know a good
> commit, you do not have to crawl through the commit history yourself to
> find a good commit. Simply issue the command:
>
> ------------
> $ git bisect next
> ------------
>
> This command is also handy when you accidentally checked out another
> commit during a bisection. It computes the commit for the bisection
> and checks it out again.
>
> -->8-->8-->8--
>
> Is that better?

Thanks, I think it is definitely better than the original patch.

I cannot say it is better than not having that extra paragraph,
though.  An immediate recovery after an accidental checkout can be
done with "git checkout -", and the only case "bisect next" is safe
and better is somebody accidentally checked multiple random commits
out without doing anything else (in which case you'd need to ask
reflog where the HEAD was in order to use "checkout" to go back).

But if they are doing more than just a single "checkout" immediately
followed by "oops that wasn't what I intended--now I want to go
back", they need more than "bisect next" or "checkout $somewhere"
anyway, so...

Re: [PATCH 01/16] bisect: write about `bisect next` in documentation

[Stephan Beyer]

Hi,

On 02/27/2016 07:03 PM, Junio C Hamano wrote:
> Stephan Beyer <s-beyer@gmx.net> writes:
> 
>> This command is also handy when you accidentally checked out another
>> commit during a bisection. It computes the commit for the bisection
>> and checks it out again.
>>
>> -->8-->8-->8--
>>
>> Is that better?
> 
> Thanks, I think it is definitely better than the original patch.
> 
> I cannot say it is better than not having that extra paragraph,
> though.

Okay, I will remove that extra paragraph.

However, it probably should be documented what "git bisect next" does
after you've specified bad and good commits.

For that, I'd like to have an extra informational paragraph.
What about: "In general, the command computes the next commit for the
bisection and checks it out."
This would be neutral, in the meaning that no use case is involved.

Another more "strict" choice could be to change the behavior such that
"git bisect next" dies when invoked after a good (and a bad) commit is
specified. In that case, there is no need to document the behavior ;-)
However, in that case the name of "git bisect next" would be wrong...

Cheers,
Stephan

Re: [PATCH 01/16] bisect: write about `bisect next` in documentation

[Junio C Hamano]

Stephan Beyer <s-beyer@gmx.net> writes:

> However, it probably should be documented what "git bisect next" does
> after you've specified bad and good commits.
>
> For that, I'd like to have an extra informational paragraph.
> What about: "In general, the command computes the next commit for the
> bisection and checks it out."
> This would be neutral, in the meaning that no use case is involved.

Good thinking.  Thanks for being careful; I often pretend to take an
extreme position to invite a well-thought-out rebuttal, and I really
like it when people respond with a good counter-proposal.

[PATCH 02/16] bisect: add test for the bisect algorithm

[Stephan Beyer]

Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
---

To be honest: the test could be better, it could be more "targeted",
i.e. the example commit history could be smaller and just consider
all the cases and corner cases and whatever.
However, I made it first to understand the algorithm and verify the
description of it in the documentation. Then I was too lazy to
improve it. I am sorry that this is no better advertising text. ;)

Moreover, the test does not test one important thing that is
always cared about in the bisect code: TREESAME commits.
Perhaps I got the concept wrong. I tried to obtain TREESAME commits
using 'git commit --allow-empty -m "same tree"'. However, those
commits were never considered being TREESAME. So I gave up (I did
not care much.)
Anyone has an idea how to obtain them?
Or is this a bug that should be fixed?

(Also UNINTERESTING commits are never found by the DEBUG_BISECT
output, but I think this is because they are just filtered out.)

 t/t8010-bisect-algorithm.sh | 162 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 162 insertions(+)
 create mode 100755 t/t8010-bisect-algorithm.sh

diff --git a/t/t8010-bisect-algorithm.sh b/t/t8010-bisect-algorithm.sh
new file mode 100755
index 0000000..bda59da
--- /dev/null
+++ b/t/t8010-bisect-algorithm.sh
@@ -0,0 +1,162 @@
+#!/bin/sh
+#
+# Copyright (c) 2016 Stephan Beyer
+#
+test_description='Tests git bisect algorithm'
+
+exec </dev/null
+
+. ./test-lib.sh
+
+test_expect_success 'set up a history for the test' '
+	test_commit A1 A 1 &&
+	test_commit A2 A 2 &&
+	test_commit A3 A 3 &&
+	test_commit A4 A 4 &&
+	test_commit A5 A 5 &&
+	test_commit A6 A 6 &&
+	git checkout -b b A5 &&
+	test_commit B1 B 1 &&
+	git checkout master &&
+	test_commit A7 A 7 &&
+	git checkout b &&
+	test_commit B2 B 2 &&
+	git checkout master &&
+	test_commit A8 A 8 &&
+	test_merge Bmerge b &&
+	git checkout b &&
+	test_commit B3 B 3 &&
+	git checkout -b c A7 &&
+	test_commit C1 C 1 &&
+	git checkout -b d A3 &&
+	test_commit D1 D 1 &&
+	git checkout c &&
+	test_commit C2 C 2 &&
+	git checkout d &&
+	test_commit D2 D 2 &&
+	git checkout c &&
+	test_commit C3 C 3 &&
+	git checkout master &&
+	git merge -m BCDmerge b c d &&
+	git tag BCDmerge &&
+	test_commit A9 A 9 &&
+	git checkout d &&
+	test_commit D3 &&
+	git checkout master
+'
+
+test_expect_success 'bisect algorithm works in linear history with an odd number of commits' '
+	git bisect start A7 &&
+	git bisect next &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse A3)" \
+	  -o "$(git rev-parse HEAD)" = "$(git rev-parse A4)"
+'
+
+test_expect_success 'bisect algorithm works in linear history with an even number of commits' '
+	git bisect reset &&
+	git bisect start A8 &&
+	git bisect next &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse A4)"
+'
+
+test_expect_success 'bisect algorithm works with a merge' '
+	git bisect reset &&
+	git bisect start Bmerge &&
+	git bisect next &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse A5)" &&
+	git bisect good &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse A8)" &&
+	git bisect good &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse B2)" \
+	  -o "$(git rev-parse HEAD)" = "$(git rev-parse B1)"
+'
+
+#                   | w  min | w  min | w  min | w  min |
+# B---.    BCDmerge | 18  0  | 9    0 | 5    0 | 3    0 |
+# |\ \ \            |        |        |        |        |
+# | | | *  D2       | 5   5  | 2    2 | 2    2*| good   |
+# | | | *  D1       | 4   4  | 1    1 | 1    1 | good   |
+# | | * |  C3       | 10  8  | 1    1 | 1    1 | 1    1*|
+# | | * |  C2       | 9   9 *| good   | good   | good   |
+# | | * |  C1       | 8   8  | good   | good   | good   |
+# | * | |  B3       | 8   8  | 3    3 | 1    1 | 1    1*|
+# * | | |  Bmerge   | 11  7  | 4    4*| good   | good   |
+# |\ \ \ \          |        |        |        |        |
+# | |/ / /          |        |        |        |        |
+# | * | |  B2       | 7   7  | 2    2 | good   | good   |
+# | * | |  B1       | 6   6  | 1    1 | good   | good   |
+# * | | |  A8       | 8   8  | 1    1 | good   | good   |
+# | |/ /            |        |        |        |        |
+# |/| |             |        |        |        |        |
+# * | |   A7        | 7   7  | good   | good   | good   |
+# * | |   A6        | 6   6  | good   | good   | good   |
+# |/ /              |        |        |        |        |
+# * |     A5        | 5   5  | good   | good   | good   |
+# * |     A4        | 4   4  | good   | good   | good   |
+# |/                |        |        |        |        |
+# *       A3        | 3   3  | good   | good   | good   |
+# *       A2        | 2   2  | good   | good   | good   |
+# *       A1        | 1   1  | good   | good   | good   |
+
+test_expect_success 'bisect algorithm works with octopus merge' '
+	git bisect reset &&
+	git bisect start BCDmerge &&
+	git bisect next &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse C2)" &&
+	git bisect good &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse Bmerge)" &&
+	git bisect good &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse D2)" &&
+	git bisect good &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse B3)" \
+	  -o "$(git rev-parse HEAD)" = "$(git rev-parse C3)" &&
+	git bisect good &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse C3)" \
+	  -o "$(git rev-parse HEAD)" = "$(git rev-parse B3)" &&
+	git bisect good > output &&
+	grep "$(git rev-parse BCDmerge) is the first bad commit" output
+'
+
+# G 5a6bcdf        D3       | w  min | w  min |
+# | B 02f2eed      A9       | 14  0  | 7   0  |
+# | *---. 6174c5c  BCDmerge | 13  1  | 6   1  |
+# | |\ \ \                  |        |        |
+# | |_|_|/                  |        |        |
+# |/| | |                   |        |        |
+# G | | | a6d6dab  D2       | good   | good   |
+# * | | | 86414e4  D1       | good   | good   |
+# | | | * c672402  C3       | 7   7 *| good   |
+# | | | * 0555272  C2       | 6   6  | good   |
+# | | | * 28c2b2a  C1       | 5   5  | good   |
+# | | * | 4b5a7d9  B3       | 5   5  | 3   3 *|
+# | * | | a419ab7  Bmerge   | 8   6  | 4   3 *|
+# | |\ \ \                  |        |        |
+# | | |/ /                  |        |        |
+# | | * | 4fa1e39  B2       | 4   4  | 2   2  |
+# | | * | 92a014d  B1       | 3   3  | 1   1  |
+# | * | | 79158c7  A8       | 5   5  | 1   1  |
+# | | |/                    |        |        |
+# | |/|                     |        |        |
+# | * | 237eb73    A7       | 4   4  | good   |
+# | * | 3b2f811    A6       | 3   3  | good   |
+# | |/                      |        |        |
+# | * 0f2b6d2      A5       | 2   2  | good   |
+# | * 1fcdaf0      A4       | 1   1  | good   |
+# |/                        |        |        |
+# * 096648b        A3       | good   | good   |
+# * 1cf01b8        A2       | good   | good   |
+# * 6623165        A1       | good   | good   |
+
+test_expect_success 'bisect algorithm works with good commit on unrelated branch' '
+	git bisect reset &&
+	git bisect start A9 D3 &&
+	test "$(git rev-parse HEAD)" = "$(git merge-base A9 D3)" &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse D2)" &&
+	git bisect good &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse C3)" &&
+	git bisect good &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse B3)" \
+	  -o "$(git rev-parse HEAD)" = "$(git rev-parse Bmerge)"
+'
+
+test_done
-- 
2.7.1.354.gd492730.dirty

Re: [PATCH 02/16] bisect: add test for the bisect algorithm

[Christian Couder]

On Fri, Feb 26, 2016 at 3:04 AM, Stephan Beyer <s-beyer@gmx.net> wrote:
> Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
> ---
>
> To be honest: the test could be better, it could be more "targeted",
> i.e. the example commit history could be smaller and just consider
> all the cases and corner cases and whatever.
> However, I made it first to understand the algorithm and verify the
> description of it in the documentation. Then I was too lazy to
> improve it. I am sorry that this is no better advertising text. ;)
>
> Moreover, the test does not test one important thing that is
> always cared about in the bisect code: TREESAME commits.
> Perhaps I got the concept wrong. I tried to obtain TREESAME commits
> using 'git commit --allow-empty -m "same tree"'. However, those
> commits were never considered being TREESAME. So I gave up (I did
> not care much.)

I didn't care enough to test TREESAME either.

> Anyone has an idea how to obtain them?
> Or is this a bug that should be fixed?
>
> (Also UNINTERESTING commits are never found by the DEBUG_BISECT
> output, but I think this is because they are just filtered out.)

Yeah, I think so.

>  t/t8010-bisect-algorithm.sh | 162 ++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 162 insertions(+)
>  create mode 100755 t/t8010-bisect-algorithm.sh
>
> diff --git a/t/t8010-bisect-algorithm.sh b/t/t8010-bisect-algorithm.sh
> new file mode 100755
> index 0000000..bda59da
> --- /dev/null
> +++ b/t/t8010-bisect-algorithm.sh
> @@ -0,0 +1,162 @@
> +#!/bin/sh
> +#
> +# Copyright (c) 2016 Stephan Beyer
> +#
> +test_description='Tests git bisect algorithm'
> +
> +exec </dev/null
> +
> +. ./test-lib.sh
> +
> +test_expect_success 'set up a history for the test' '
> +       test_commit A1 A 1 &&
> +       test_commit A2 A 2 &&
> +       test_commit A3 A 3 &&
> +       test_commit A4 A 4 &&
> +       test_commit A5 A 5 &&
> +       test_commit A6 A 6 &&
> +       git checkout -b b A5 &&
> +       test_commit B1 B 1 &&
> +       git checkout master &&
> +       test_commit A7 A 7 &&
> +       git checkout b &&
> +       test_commit B2 B 2 &&
> +       git checkout master &&
> +       test_commit A8 A 8 &&
> +       test_merge Bmerge b &&
> +       git checkout b &&
> +       test_commit B3 B 3 &&
> +       git checkout -b c A7 &&
> +       test_commit C1 C 1 &&
> +       git checkout -b d A3 &&
> +       test_commit D1 D 1 &&
> +       git checkout c &&
> +       test_commit C2 C 2 &&
> +       git checkout d &&
> +       test_commit D2 D 2 &&
> +       git checkout c &&
> +       test_commit C3 C 3 &&
> +       git checkout master &&
> +       git merge -m BCDmerge b c d &&
> +       git tag BCDmerge &&
> +       test_commit A9 A 9 &&
> +       git checkout d &&
> +       test_commit D3 &&
> +       git checkout master
> +'
> +
> +test_expect_success 'bisect algorithm works in linear history with an odd number of commits' '
> +       git bisect start A7 &&
> +       git bisect next &&
> +       test "$(git rev-parse HEAD)" = "$(git rev-parse A3)" \
> +         -o "$(git rev-parse HEAD)" = "$(git rev-parse A4)"

I thought that we should not use "-o" and "-a" but instead "|| test"
and "&& test".

> +'
> +
> +test_expect_success 'bisect algorithm works in linear history with an even number of commits' '
> +       git bisect reset &&
> +       git bisect start A8 &&
> +       git bisect next &&
> +       test "$(git rev-parse HEAD)" = "$(git rev-parse A4)"
> +'
> +
> +test_expect_success 'bisect algorithm works with a merge' '
> +       git bisect reset &&
> +       git bisect start Bmerge &&
> +       git bisect next &&
> +       test "$(git rev-parse HEAD)" = "$(git rev-parse A5)" &&
> +       git bisect good &&
> +       test "$(git rev-parse HEAD)" = "$(git rev-parse A8)" &&
> +       git bisect good &&
> +       test "$(git rev-parse HEAD)" = "$(git rev-parse B2)" \
> +         -o "$(git rev-parse HEAD)" = "$(git rev-parse B1)"

Here and in other places too...

Re: [PATCH 02/16] bisect: add test for the bisect algorithm

[Stephan Beyer]

Hi Christian,

On 02/26/2016 07:53 AM, Christian Couder wrote:
>> +test_expect_success 'bisect algorithm works in linear history with an odd number of commits' '
>> +       git bisect start A7 &&
>> +       git bisect next &&
>> +       test "$(git rev-parse HEAD)" = "$(git rev-parse A3)" \
>> +         -o "$(git rev-parse HEAD)" = "$(git rev-parse A4)"
> 
> I thought that we should not use "-o" and "-a" but instead "|| test"
> and "&& test".

Why is this? I understand the && instead of -a thing (test atomicity),
however, for || this results in an ugly

+       git bisect next &&
+       ( test "$(git rev-parse HEAD)" = "$(git rev-parse A3)" ||
+         test "$(git rev-parse HEAD)" = "$(git rev-parse A4)" )

Right? (Otherwise a failure of e.g. "git bisect start A7" would run
the command after || (which may still be fine in some cases but is wrong
in most of the other cases).

However, what do you think about this?

diff --git a/t/t8010-bisect-algorithm.sh b/t/t8010-bisect-algorithm.sh
index bda59da..ae50e7c 100755
--- a/t/t8010-bisect-algorithm.sh
+++ b/t/t8010-bisect-algorithm.sh
@@ -8,6 +8,16 @@ exec </dev/null

 . ./test-lib.sh

+test_compare_rev () {
+       arg="$(git rev-parse "$1")"
+       shift
+       for rev
+       do
+               test "$arg" = "$(git rev-parse "$rev")" && return 0
+       done
+       return 1
+}
+
 test_expect_success 'set up a history for the test' '
        test_commit A1 A 1 &&
        test_commit A2 A 2 &&
@@ -48,27 +58,25 @@ test_expect_success 'set up a history for the test' '
 test_expect_success 'bisect algorithm works in linear history with an
odd number of commits' '
        git bisect start A7 &&
        git bisect next &&
-       test "$(git rev-parse HEAD)" = "$(git rev-parse A3)" \
-         -o "$(git rev-parse HEAD)" = "$(git rev-parse A4)"
+       test_compare_rev HEAD A3 A4
 '

and so on...
See
https://github.com/sbeyer/git/commit/2c224093ccee837a7f0f62f6af6a0a804d07c022

(test_compare_rev() could also go into test-lib.sh)

Cheers
Stephan

Re: [PATCH 02/16] bisect: add test for the bisect algorithm

[Christian Couder]

Hi Stephan,

On Fri, Feb 26, 2016 at 10:38 PM, Stephan Beyer <s-beyer@gmx.net> wrote:
> Hi Christian,
>
> On 02/26/2016 07:53 AM, Christian Couder wrote:
>>> +test_expect_success 'bisect algorithm works in linear history with an odd number of commits' '
>>> +       git bisect start A7 &&
>>> +       git bisect next &&
>>> +       test "$(git rev-parse HEAD)" = "$(git rev-parse A3)" \
>>> +         -o "$(git rev-parse HEAD)" = "$(git rev-parse A4)"
>>
>> I thought that we should not use "-o" and "-a" but instead "|| test"
>> and "&& test".
>
> Why is this?

I think it is because it might not be very portable, but I am not sure
I remember well the previous discussions about this.

> I understand the && instead of -a thing (test atomicity),
> however, for || this results in an ugly
>
> +       git bisect next &&
> +       ( test "$(git rev-parse HEAD)" = "$(git rev-parse A3)" ||
> +         test "$(git rev-parse HEAD)" = "$(git rev-parse A4)" )
>
> Right? (Otherwise a failure of e.g. "git bisect start A7" would run
> the command after || (which may still be fine in some cases but is wrong
> in most of the other cases).

Yeah.

By the way maybe t6030-bisect-porcelain.sh is paranoid, but it does
some of those checks like:

    HASH4=$(git rev-parse --verify HEAD)

and later:

    rev_hash4=$(git rev-parse --verify HEAD) &&
    test "$rev_hash4" = "$HASH4" &&

So it uses "--verify" and also often puts the "git rev-parse" on a
separate line...

> However, what do you think about this?
>
> diff --git a/t/t8010-bisect-algorithm.sh b/t/t8010-bisect-algorithm.sh
> index bda59da..ae50e7c 100755
> --- a/t/t8010-bisect-algorithm.sh
> +++ b/t/t8010-bisect-algorithm.sh
> @@ -8,6 +8,16 @@ exec </dev/null
>
>  . ./test-lib.sh
>
> +test_compare_rev () {
> +       arg="$(git rev-parse "$1")"

...hence I would suggest:

    arg="$(git rev-parse --verify "$1")" || return

> +       shift
> +       for rev
> +       do
> +               test "$arg" = "$(git rev-parse "$rev")" && return 0

...and:

        hash="$(git rev-parse --verify "$rev")" || return
        test "$arg" = "$hash" && return 0

> +       done
> +       return 1
> +}

Otherwise I like test_compare_rev().

Thanks,
Christian.

Re: [PATCH 02/16] bisect: add test for the bisect algorithm

[Matthieu Moy]

Christian Couder <christian.couder@gmail.com> writes:

> Hi Stephan,
>
> On Fri, Feb 26, 2016 at 10:38 PM, Stephan Beyer <s-beyer@gmx.net> wrote:
>> Hi Christian,
>>
>> On 02/26/2016 07:53 AM, Christian Couder wrote:
>>>> +test_expect_success 'bisect algorithm works in linear history with an odd number of commits' '
>>>> +       git bisect start A7 &&
>>>> +       git bisect next &&
>>>> +       test "$(git rev-parse HEAD)" = "$(git rev-parse A3)" \
>>>> +         -o "$(git rev-parse HEAD)" = "$(git rev-parse A4)"
>>>
>>> I thought that we should not use "-o" and "-a" but instead "|| test"
>>> and "&& test".
>>
>> Why is this?
>
> I think it is because it might not be very portable, but I am not sure
> I remember well the previous discussions about this.

See Documentation/CodingGuidelines:

 - We do not write our "test" command with "-a" and "-o" and use "&&"
   or "||" to concatenate multiple "test" commands instead, because
   the use of "-a/-o" is often error-prone.  E.g.

     test -n "$x" -a "$a" = "$b"

   is buggy and breaks when $x is "=", but

     test -n "$x" && test "$a" = "$b"

   does not have such a problem.

Regarding portability, test -a/-o is not strictly POSIX (it's in the XSI
extension), but AFAIK implemented by all reasonable shells.

-- 
Matthieu Moy
http://www-verimag.imag.fr/~moy/

[PATCH 03/16] bisect: make bisect compile if DEBUG_BISECT is set

[Stephan Beyer]

Setting the macro DEBUG_BISECT to 1 enables debugging information
for the bisect algorithm. The code did not compile due to struct
changes.

Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
---
 bisect.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/bisect.c b/bisect.c
index 06ec54e..905e63a 100644
--- a/bisect.c
+++ b/bisect.c
@@ -131,7 +131,7 @@ static void show_list(const char *debug, int counted, int nr,
 		unsigned flags = commit->object.flags;
 		enum object_type type;
 		unsigned long size;
-		char *buf = read_sha1_file(commit->object.sha1, &type, &size);
+		char *buf = read_sha1_file(commit->object.oid.hash, &type, &size);
 		const char *subject_start;
 		int subject_len;
 
@@ -143,10 +143,10 @@ static void show_list(const char *debug, int counted, int nr,
 			fprintf(stderr, "%3d", weight(p));
 		else
 			fprintf(stderr, "---");
-		fprintf(stderr, " %.*s", 8, sha1_to_hex(commit->object.sha1));
+		fprintf(stderr, " %.*s", 8, sha1_to_hex(commit->object.oid.hash));
 		for (pp = commit->parents; pp; pp = pp->next)
 			fprintf(stderr, " %.*s", 8,
-				sha1_to_hex(pp->item->object.sha1));
+				sha1_to_hex(pp->item->object.oid.hash));
 
 		subject_len = find_commit_subject(buf, &subject_start);
 		if (subject_len)
-- 
2.7.1.354.gd492730.dirty

[PATCH 04/16] bisect: make algorithm behavior independent of DEBUG_BISECT

[Stephan Beyer]

If DEBUG_BISECT is set to 1, bisect does not only show debug
information but also changes the algorithm behavior: halfway()
is always false.

This commit makes the algorithm independent of DEBUG_BISECT.

Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
---
 bisect.c | 2 --
 1 file changed, 2 deletions(-)

diff --git a/bisect.c b/bisect.c
index 905e63a..412e2c0 100644
--- a/bisect.c
+++ b/bisect.c
@@ -101,8 +101,6 @@ static inline int halfway(struct commit_list *p, int nr)
 	 */
 	if (p->item->object.flags & TREESAME)
 		return 0;
-	if (DEBUG_BISECT)
-		return 0;
 	/*
 	 * 2 and 3 are halfway of 5.
 	 * 3 is halfway of 6 but 2 and 4 are not.
-- 
2.7.1.354.gd492730.dirty

[PATCH 05/16] bisect: get rid of recursion in count_distance()

[Stephan Beyer]

Large repositories with a huge amount of merge commits in the
bisection process could lead to stack overflows in git bisect.
In order to prevent this, this commit uses an *iterative* version
for counting the number of ancestors of a commit.

Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
---

In the cover letter I promised that bisect will be faster.
It's not rocket science to know that replacing a simple recursion
by an iterative version involving a list (with alloc'ing and stuff)
makes the code slower.

For my git master branch test, this changed the running time
from ~50 to ~60 seconds. However, for a smaller stack size,
this changes the running time from <crash> to ~60 seconds.
That's a win ;-)

 bisect.c | 55 ++++++++++++++++++++++---------------------------------
 1 file changed, 22 insertions(+), 33 deletions(-)

diff --git a/bisect.c b/bisect.c
index 412e2c0..03e7660 100644
--- a/bisect.c
+++ b/bisect.c
@@ -26,33 +26,23 @@ static const char *term_good;
 /* Remember to update object flag allocation in object.h */
 #define COUNTED		(1u<<16)
 
-/*
- * This is a truly stupid algorithm, but it's only
- * used for bisection, and we just don't care enough.
- *
- * We care just barely enough to avoid recursing for
- * non-merge entries.
- */
 static int count_distance(struct commit_list *entry)
 {
 	int nr = 0;
+	struct commit_list *todo = NULL;
+	commit_list_append(entry->item, &todo);
 
-	while (entry) {
-		struct commit *commit = entry->item;
-		struct commit_list *p;
+	while (todo) {
+		struct commit *commit = pop_commit(&todo);
 
-		if (commit->object.flags & (UNINTERESTING | COUNTED))
-			break;
-		if (!(commit->object.flags & TREESAME))
-			nr++;
-		commit->object.flags |= COUNTED;
-		p = commit->parents;
-		entry = p;
-		if (p) {
-			p = p->next;
-			while (p) {
-				nr += count_distance(p);
-				p = p->next;
+		if (!(commit->object.flags & (UNINTERESTING | COUNTED))) {
+			struct commit_list *p;
+			if (!(commit->object.flags & TREESAME))
+				nr++;
+			commit->object.flags |= COUNTED;
+
+			for (p = commit->parents; p; p = p->next) {
+				commit_list_insert(p->item, &todo);
 			}
 		}
 	}
@@ -287,7 +277,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 	 * can reach.  So we do not have to run the expensive
 	 * count_distance() for single strand of pearls.
 	 *
-	 * However, if you have more than one parents, you cannot
+	 * However, if you have more than one parent, you cannot
 	 * just add their distance and one for yourself, since
 	 * they usually reach the same ancestor and you would
 	 * end up counting them twice that way.
@@ -296,17 +286,16 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 	 * way, and then fill the blanks using cheaper algorithm.
 	 */
 	for (p = list; p; p = p->next) {
-		if (p->item->object.flags & UNINTERESTING)
-			continue;
-		if (weight(p) != -2)
-			continue;
-		weight_set(p, count_distance(p));
-		clear_distance(list);
+		if (!(p->item->object.flags & UNINTERESTING)
+		 && (weight(p) == -2)) {
+			weight_set(p, count_distance(p));
+			clear_distance(list);
 
-		/* Does it happen to be at exactly half-way? */
-		if (!find_all && halfway(p, nr))
-			return p;
-		counted++;
+			/* Does it happen to be at exactly half-way? */
+			if (!find_all && halfway(p, nr))
+				return p;
+			counted++;
+		}
 	}
 
 	show_list("bisection 2 count_distance", counted, nr, list);
-- 
2.7.1.354.gd492730.dirty

[PATCH 06/16] bisect: use struct node_data array instead of int array

[Stephan Beyer]

This is a preparation for subsequent changes.
During a bisection process, we want to augment commits with
further information to improve speed.

Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
---
 bisect.c | 61 ++++++++++++++++++++++++++++++-------------------------------
 1 file changed, 30 insertions(+), 31 deletions(-)

diff --git a/bisect.c b/bisect.c
index 03e7660..bcb58ed 100644
--- a/bisect.c
+++ b/bisect.c
@@ -23,9 +23,21 @@ static const char *argv_show_branch[] = {"show-branch", NULL, NULL};
 static const char *term_bad;
 static const char *term_good;
 
+struct node_data {
+	int weight;
+};
+
 /* Remember to update object flag allocation in object.h */
 #define COUNTED		(1u<<16)
 
+#define DEBUG_BISECT 0
+
+static inline struct node_data *node_data(struct commit *elem)
+{
+	assert(elem->util);
+	return (struct node_data *)elem->util;
+}
+
 static int count_distance(struct commit_list *entry)
 {
 	int nr = 0;
@@ -59,18 +71,6 @@ static void clear_distance(struct commit_list *list)
 	}
 }
 
-#define DEBUG_BISECT 0
-
-static inline int weight(struct commit_list *elem)
-{
-	return *((int*)(elem->item->util));
-}
-
-static inline void weight_set(struct commit_list *elem, int weight)
-{
-	*((int*)(elem->item->util)) = weight;
-}
-
 static int count_interesting_parents(struct commit *commit)
 {
 	struct commit_list *p;
@@ -95,7 +95,7 @@ static inline int halfway(struct commit_list *p, int nr)
 	 * 2 and 3 are halfway of 5.
 	 * 3 is halfway of 6 but 2 and 4 are not.
 	 */
-	switch (2 * weight(p) - nr) {
+	switch (2 * node_data(p->item)->weight - nr) {
 	case -1: case 0: case 1:
 		return 1;
 	default:
@@ -128,7 +128,7 @@ static void show_list(const char *debug, int counted, int nr,
 			(flags & UNINTERESTING) ? 'U' : ' ',
 			(flags & COUNTED) ? 'C' : ' ');
 		if (commit->util)
-			fprintf(stderr, "%3d", weight(p));
+			fprintf(stderr, "%3d", node_data(commit)->weight);
 		else
 			fprintf(stderr, "---");
 		fprintf(stderr, " %.*s", 8, sha1_to_hex(commit->object.oid.hash));
@@ -156,7 +156,7 @@ static struct commit_list *best_bisection(struct commit_list *list, int nr)
 
 		if (flags & TREESAME)
 			continue;
-		distance = weight(p);
+		distance = node_data(p->item)->weight;
 		if (nr - distance < distance)
 			distance = nr - distance;
 		if (distance > best_distance) {
@@ -196,7 +196,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
 
 		if (flags & TREESAME)
 			continue;
-		distance = weight(p);
+		distance = node_data(p->item)->weight;
 		if (nr - distance < distance)
 			distance = nr - distance;
 		array[cnt].commit = p->item;
@@ -234,7 +234,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
  * or positive distance.
  */
 static struct commit_list *do_find_bisection(struct commit_list *list,
-					     int nr, int *weights,
+					     int nr, struct node_data *weights,
 					     int find_all)
 {
 	int n, counted;
@@ -246,11 +246,11 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 		struct commit *commit = p->item;
 		unsigned flags = commit->object.flags;
 
-		p->item->util = &weights[n++];
+		commit->util = &weights[n++];
 		switch (count_interesting_parents(commit)) {
 		case 0:
 			if (!(flags & TREESAME)) {
-				weight_set(p, 1);
+				node_data(commit)->weight = 1;
 				counted++;
 				show_list("bisection 2 count one",
 					  counted, nr, list);
@@ -261,10 +261,10 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 			 */
 			break;
 		case 1:
-			weight_set(p, -1);
+			node_data(commit)->weight = -1;
 			break;
 		default:
-			weight_set(p, -2);
+			node_data(commit)->weight = -2;
 			break;
 		}
 	}
@@ -287,8 +287,8 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 	 */
 	for (p = list; p; p = p->next) {
 		if (!(p->item->object.flags & UNINTERESTING)
-		 && (weight(p) == -2)) {
-			weight_set(p, count_distance(p));
+		 && (node_data(p->item)->weight == -2)) {
+			node_data(p->item)->weight = count_distance(p);
 			clear_distance(list);
 
 			/* Does it happen to be at exactly half-way? */
@@ -305,12 +305,12 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 			struct commit_list *q;
 			unsigned flags = p->item->object.flags;
 
-			if (0 <= weight(p))
+			if (0 <= node_data(p->item)->weight)
 				continue;
 			for (q = p->item->parents; q; q = q->next) {
 				if (q->item->object.flags & UNINTERESTING)
 					continue;
-				if (0 <= weight(q))
+				if (0 <= node_data(q->item)->weight)
 					break;
 			}
 			if (!q)
@@ -321,14 +321,13 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 			 * add one for p itself if p is to be counted,
 			 * otherwise inherit it from q directly.
 			 */
+			node_data(p->item)->weight = node_data(q->item)->weight;
 			if (!(flags & TREESAME)) {
-				weight_set(p, weight(q)+1);
+				node_data(p->item)->weight++;
 				counted++;
 				show_list("bisection 2 count one",
 					  counted, nr, list);
 			}
-			else
-				weight_set(p, weight(q));
 
 			/* Does it happen to be at exactly half-way? */
 			if (!find_all && halfway(p, nr))
@@ -350,7 +349,7 @@ struct commit_list *find_bisection(struct commit_list *list,
 {
 	int nr, on_list;
 	struct commit_list *p, *best, *next, *last;
-	int *weights;
+	struct node_data *weights;
 
 	show_list("bisection 2 entry", 0, 0, list);
 
@@ -376,14 +375,14 @@ struct commit_list *find_bisection(struct commit_list *list,
 	show_list("bisection 2 sorted", 0, nr, list);
 
 	*all = nr;
-	weights = xcalloc(on_list, sizeof(*weights));
+	weights = (struct node_data *)xcalloc(on_list, sizeof(*weights));
 
 	/* Do the real work of finding bisection commit. */
 	best = do_find_bisection(list, nr, weights, find_all);
 	if (best) {
 		if (!find_all)
 			best->next = NULL;
-		*reaches = weight(best);
+		*reaches = node_data(best->item)->weight;
 	}
 	free(weights);
 	return best;
-- 
2.7.1.354.gd492730.dirty

[PATCH 07/16] bisect: replace clear_distance() by unique markers

[Stephan Beyer]

clear_distance() was a O(#commits)-time function to clear the COUNTED
flag from commits counted in count_distance().
The functions count_distance() and clear_distance() were called for
each merge commit.

This commit gets rid of the clear_distance() function by making
count_distance() use unique marker ids that do not need to be
cleared afterwards. This speeds up the bisecting process on
large repositories with a huge amount of merges.

Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
---

Yaaay, this is our first gain of performance!
My test: ~30 seconds

 bisect.c | 29 +++++++++++------------------
 1 file changed, 11 insertions(+), 18 deletions(-)

diff --git a/bisect.c b/bisect.c
index bcb58ed..6df13b0 100644
--- a/bisect.c
+++ b/bisect.c
@@ -23,13 +23,13 @@ static const char *argv_show_branch[] = {"show-branch", NULL, NULL};
 static const char *term_bad;
 static const char *term_good;
 
+static unsigned marker;
+
 struct node_data {
 	int weight;
+	unsigned marked;
 };
 
-/* Remember to update object flag allocation in object.h */
-#define COUNTED		(1u<<16)
-
 #define DEBUG_BISECT 0
 
 static inline struct node_data *node_data(struct commit *elem)
@@ -43,15 +43,17 @@ static int count_distance(struct commit_list *entry)
 	int nr = 0;
 	struct commit_list *todo = NULL;
 	commit_list_append(entry->item, &todo);
+	marker++;
 
 	while (todo) {
 		struct commit *commit = pop_commit(&todo);
 
-		if (!(commit->object.flags & (UNINTERESTING | COUNTED))) {
+		if (!(commit->object.flags & UNINTERESTING)
+		 && node_data(commit)->marked != marker) {
 			struct commit_list *p;
 			if (!(commit->object.flags & TREESAME))
 				nr++;
-			commit->object.flags |= COUNTED;
+			node_data(commit)->marked = marker;
 
 			for (p = commit->parents; p; p = p->next) {
 				commit_list_insert(p->item, &todo);
@@ -62,15 +64,6 @@ static int count_distance(struct commit_list *entry)
 	return nr;
 }
 
-static void clear_distance(struct commit_list *list)
-{
-	while (list) {
-		struct commit *commit = list->item;
-		commit->object.flags &= ~COUNTED;
-		list = list->next;
-	}
-}
-
 static int count_interesting_parents(struct commit *commit)
 {
 	struct commit_list *p;
@@ -123,10 +116,9 @@ static void show_list(const char *debug, int counted, int nr,
 		const char *subject_start;
 		int subject_len;
 
-		fprintf(stderr, "%c%c%c ",
+		fprintf(stderr, "%c%c ",
 			(flags & TREESAME) ? ' ' : 'T',
-			(flags & UNINTERESTING) ? 'U' : ' ',
-			(flags & COUNTED) ? 'C' : ' ');
+			(flags & UNINTERESTING) ? 'U' : ' ');
 		if (commit->util)
 			fprintf(stderr, "%3d", node_data(commit)->weight);
 		else
@@ -289,7 +281,6 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 		if (!(p->item->object.flags & UNINTERESTING)
 		 && (node_data(p->item)->weight == -2)) {
 			node_data(p->item)->weight = count_distance(p);
-			clear_distance(list);
 
 			/* Does it happen to be at exactly half-way? */
 			if (!find_all && halfway(p, nr))
@@ -351,6 +342,8 @@ struct commit_list *find_bisection(struct commit_list *list,
 	struct commit_list *p, *best, *next, *last;
 	struct node_data *weights;
 
+	marker = 0;
+
 	show_list("bisection 2 entry", 0, 0, list);
 
 	/*
-- 
2.7.1.354.gd492730.dirty

[PATCH 08/16] bisect: use commit instead of commit list as arguments when appropriate

[Stephan Beyer]

It makes no sense that the argument for count_distance() and
halfway() is a commit list when only its first commit is relevant.

Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
---

This is just some kind of minor code cleanup.
The typical "while at it", you know it, I guess.

 bisect.c | 16 ++++++++--------
 1 file changed, 8 insertions(+), 8 deletions(-)

diff --git a/bisect.c b/bisect.c
index 6df13b0..76f2445 100644
--- a/bisect.c
+++ b/bisect.c
@@ -38,11 +38,11 @@ static inline struct node_data *node_data(struct commit *elem)
 	return (struct node_data *)elem->util;
 }
 
-static int count_distance(struct commit_list *entry)
+static int count_distance(struct commit *entry)
 {
 	int nr = 0;
 	struct commit_list *todo = NULL;
-	commit_list_append(entry->item, &todo);
+	commit_list_append(entry, &todo);
 	marker++;
 
 	while (todo) {
@@ -77,18 +77,18 @@ static int count_interesting_parents(struct commit *commit)
 	return count;
 }
 
-static inline int halfway(struct commit_list *p, int nr)
+static inline int halfway(struct commit *commit, int nr)
 {
 	/*
 	 * Don't short-cut something we are not going to return!
 	 */
-	if (p->item->object.flags & TREESAME)
+	if (commit->object.flags & TREESAME)
 		return 0;
 	/*
 	 * 2 and 3 are halfway of 5.
 	 * 3 is halfway of 6 but 2 and 4 are not.
 	 */
-	switch (2 * node_data(p->item)->weight - nr) {
+	switch (2 * node_data(commit)->weight - nr) {
 	case -1: case 0: case 1:
 		return 1;
 	default:
@@ -280,10 +280,10 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 	for (p = list; p; p = p->next) {
 		if (!(p->item->object.flags & UNINTERESTING)
 		 && (node_data(p->item)->weight == -2)) {
-			node_data(p->item)->weight = count_distance(p);
+			node_data(p->item)->weight = count_distance(p->item);
 
 			/* Does it happen to be at exactly half-way? */
-			if (!find_all && halfway(p, nr))
+			if (!find_all && halfway(p->item, nr))
 				return p;
 			counted++;
 		}
@@ -321,7 +321,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 			}
 
 			/* Does it happen to be at exactly half-way? */
-			if (!find_all && halfway(p, nr))
+			if (!find_all && halfway(p->item, nr))
 				return p;
 		}
 	}
-- 
2.7.1.354.gd492730.dirty

Re: [PATCH 08/16] bisect: use commit instead of commit list as arguments when appropriate

[Junio C Hamano]

Stephan Beyer <s-beyer@gmx.net> writes:

> It makes no sense that the argument for count_distance() and
> halfway() is a commit list when only its first commit is relevant.
>
> Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
> ---
>
> This is just some kind of minor code cleanup.
> The typical "while at it", you know it, I guess.

If you are doing while-at-it, please rename the variable to commit
or something.  "entry" refers to one element in the list, but the
entity the updated code works on is no longer that.

>
>  bisect.c | 16 ++++++++--------
>  1 file changed, 8 insertions(+), 8 deletions(-)
>
> diff --git a/bisect.c b/bisect.c
> index 6df13b0..76f2445 100644
> --- a/bisect.c
> +++ b/bisect.c
> @@ -38,11 +38,11 @@ static inline struct node_data *node_data(struct commit *elem)
>  	return (struct node_data *)elem->util;
>  }
>  
> -static int count_distance(struct commit_list *entry)
> +static int count_distance(struct commit *entry)
>  {
>  	int nr = 0;
>  	struct commit_list *todo = NULL;
> -	commit_list_append(entry->item, &todo);
> +	commit_list_append(entry, &todo);
>  	marker++;
>  
>  	while (todo) {
> @@ -77,18 +77,18 @@ static int count_interesting_parents(struct commit *commit)
>  	return count;
>  }
>  
> -static inline int halfway(struct commit_list *p, int nr)
> +static inline int halfway(struct commit *commit, int nr)
>  {
>  	/*
>  	 * Don't short-cut something we are not going to return!
>  	 */
> -	if (p->item->object.flags & TREESAME)
> +	if (commit->object.flags & TREESAME)
>  		return 0;
>  	/*
>  	 * 2 and 3 are halfway of 5.
>  	 * 3 is halfway of 6 but 2 and 4 are not.
>  	 */
> -	switch (2 * node_data(p->item)->weight - nr) {
> +	switch (2 * node_data(commit)->weight - nr) {
>  	case -1: case 0: case 1:
>  		return 1;
>  	default:
> @@ -280,10 +280,10 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
>  	for (p = list; p; p = p->next) {
>  		if (!(p->item->object.flags & UNINTERESTING)
>  		 && (node_data(p->item)->weight == -2)) {
> -			node_data(p->item)->weight = count_distance(p);
> +			node_data(p->item)->weight = count_distance(p->item);
>  
>  			/* Does it happen to be at exactly half-way? */
> -			if (!find_all && halfway(p, nr))
> +			if (!find_all && halfway(p->item, nr))
>  				return p;
>  			counted++;
>  		}
> @@ -321,7 +321,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
>  			}
>  
>  			/* Does it happen to be at exactly half-way? */
> -			if (!find_all && halfway(p, nr))
> +			if (!find_all && halfway(p->item, nr))
>  				return p;
>  		}
>  	}

[PATCH 09/16] bisect: extract get_distance() function from code duplication

[Stephan Beyer]

Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
---

We will also use that function more often later.

 bisect.c | 16 ++++++++++------
 1 file changed, 10 insertions(+), 6 deletions(-)

diff --git a/bisect.c b/bisect.c
index 76f2445..afdd1c4 100644
--- a/bisect.c
+++ b/bisect.c
@@ -38,6 +38,14 @@ static inline struct node_data *node_data(struct commit *elem)
 	return (struct node_data *)elem->util;
 }
 
+static inline int get_distance(struct commit *commit, int total)
+{
+	int distance = node_data(commit)->weight;
+	if (total - distance < distance)
+		distance = total - distance;
+	return distance;
+}
+
 static int count_distance(struct commit *entry)
 {
 	int nr = 0;
@@ -148,9 +156,7 @@ static struct commit_list *best_bisection(struct commit_list *list, int nr)
 
 		if (flags & TREESAME)
 			continue;
-		distance = node_data(p->item)->weight;
-		if (nr - distance < distance)
-			distance = nr - distance;
+		distance = get_distance(p->item, nr);
 		if (distance > best_distance) {
 			best = p;
 			best_distance = distance;
@@ -188,9 +194,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
 
 		if (flags & TREESAME)
 			continue;
-		distance = node_data(p->item)->weight;
-		if (nr - distance < distance)
-			distance = nr - distance;
+		distance = get_distance(p->item, nr);
 		array[cnt].commit = p->item;
 		array[cnt].distance = distance;
 		cnt++;
-- 
2.7.1.354.gd492730.dirty

[PATCH 10/16] bisect: introduce distance_direction()

[Stephan Beyer]

We introduce the concept of rising and falling distances
(in addition to a halfway distance).
This will be useful in subsequent commits.

Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
---
 bisect.c | 33 +++++++++++++++++++++++----------
 1 file changed, 23 insertions(+), 10 deletions(-)

diff --git a/bisect.c b/bisect.c
index afdd1c4..a09a410 100644
--- a/bisect.c
+++ b/bisect.c
@@ -46,6 +46,28 @@ static inline int get_distance(struct commit *commit, int total)
 	return distance;
 }
 
+/*
+ * Return -1 if the distance is falling.
+ * (A falling distance means that the distance of the
+ *  given commit is larger than the distance of its
+ *  child commits.)
+ * Return 0 if the distance is halfway.
+ * Return 1 if the distance is rising.
+ */
+static inline int distance_direction(struct commit *commit, int total)
+{
+	int doubled_diff = 2 * node_data(commit)->weight - total;
+	if (doubled_diff < -1)
+		return 1;
+	if (doubled_diff > 1)
+		return -1;
+	/*
+	 * 2 and 3 are halfway of 5.
+	 * 3 is halfway of 6 but 2 and 4 are not.
+	 */
+	return 0;
+}
+
 static int count_distance(struct commit *entry)
 {
 	int nr = 0;
@@ -92,16 +114,7 @@ static inline int halfway(struct commit *commit, int nr)
 	 */
 	if (commit->object.flags & TREESAME)
 		return 0;
-	/*
-	 * 2 and 3 are halfway of 5.
-	 * 3 is halfway of 6 but 2 and 4 are not.
-	 */
-	switch (2 * node_data(commit)->weight - nr) {
-	case -1: case 0: case 1:
-		return 1;
-	default:
-		return 0;
-	}
+	return !distance_direction(commit, nr);
 }
 
 #if !DEBUG_BISECT
-- 
2.7.1.354.gd492730.dirty

[PATCH 11/16] bisect: make total number of commits global

[Stephan Beyer]

The total number of commits in a bisect process is a property of
the bisect process. Making this property global helps to make the code
clearer.

Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
---
 bisect.c | 74 ++++++++++++++++++++++++++++++++++------------------------------
 1 file changed, 39 insertions(+), 35 deletions(-)

diff --git a/bisect.c b/bisect.c
index a09a410..3a3a728 100644
--- a/bisect.c
+++ b/bisect.c
@@ -23,6 +23,8 @@ static const char *argv_show_branch[] = {"show-branch", NULL, NULL};
 static const char *term_bad;
 static const char *term_good;
 
+static int total;
+
 static unsigned marker;
 
 struct node_data {
@@ -38,7 +40,7 @@ static inline struct node_data *node_data(struct commit *elem)
 	return (struct node_data *)elem->util;
 }
 
-static inline int get_distance(struct commit *commit, int total)
+static inline int get_distance(struct commit *commit)
 {
 	int distance = node_data(commit)->weight;
 	if (total - distance < distance)
@@ -54,7 +56,7 @@ static inline int get_distance(struct commit *commit, int total)
  * Return 0 if the distance is halfway.
  * Return 1 if the distance is rising.
  */
-static inline int distance_direction(struct commit *commit, int total)
+static inline int distance_direction(struct commit *commit)
 {
 	int doubled_diff = 2 * node_data(commit)->weight - total;
 	if (doubled_diff < -1)
@@ -107,25 +109,25 @@ static int count_interesting_parents(struct commit *commit)
 	return count;
 }
 
-static inline int halfway(struct commit *commit, int nr)
+static inline int halfway(struct commit *commit)
 {
 	/*
 	 * Don't short-cut something we are not going to return!
 	 */
 	if (commit->object.flags & TREESAME)
 		return 0;
-	return !distance_direction(commit, nr);
+	return !distance_direction(commit);
 }
 
 #if !DEBUG_BISECT
-#define show_list(a,b,c,d) do { ; } while (0)
+#define show_list(a,b,c) do { ; } while (0)
 #else
-static void show_list(const char *debug, int counted, int nr,
+static void show_list(const char *debug, int counted,
 		      struct commit_list *list)
 {
 	struct commit_list *p;
 
-	fprintf(stderr, "%s (%d/%d)\n", debug, counted, nr);
+	fprintf(stderr, "%s (%d/%d)\n", debug, counted, total);
 
 	for (p = list; p; p = p->next) {
 		struct commit_list *pp;
@@ -157,7 +159,7 @@ static void show_list(const char *debug, int counted, int nr,
 }
 #endif /* DEBUG_BISECT */
 
-static struct commit_list *best_bisection(struct commit_list *list, int nr)
+static struct commit_list *best_bisection(struct commit_list *list)
 {
 	struct commit_list *p, *best;
 	int best_distance = -1;
@@ -169,7 +171,7 @@ static struct commit_list *best_bisection(struct commit_list *list, int nr)
 
 		if (flags & TREESAME)
 			continue;
-		distance = get_distance(p->item, nr);
+		distance = get_distance(p->item);
 		if (distance > best_distance) {
 			best = p;
 			best_distance = distance;
@@ -195,10 +197,10 @@ static int compare_commit_dist(const void *a_, const void *b_)
 	return oidcmp(&a->commit->object.oid, &b->commit->object.oid);
 }
 
-static struct commit_list *best_bisection_sorted(struct commit_list *list, int nr)
+static struct commit_list *best_bisection_sorted(struct commit_list *list)
 {
 	struct commit_list *p;
-	struct commit_dist *array = xcalloc(nr, sizeof(*array));
+	struct commit_dist *array = xcalloc(total, sizeof(*array));
 	int cnt, i;
 
 	for (p = list, cnt = 0; p; p = p->next) {
@@ -207,7 +209,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
 
 		if (flags & TREESAME)
 			continue;
-		distance = get_distance(p->item, nr);
+		distance = get_distance(p->item);
 		array[cnt].commit = p->item;
 		array[cnt].distance = distance;
 		cnt++;
@@ -243,7 +245,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
  * or positive distance.
  */
 static struct commit_list *do_find_bisection(struct commit_list *list,
-					     int nr, struct node_data *weights,
+					     struct node_data *weights,
 					     int find_all)
 {
 	int n, counted;
@@ -262,7 +264,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 				node_data(commit)->weight = 1;
 				counted++;
 				show_list("bisection 2 count one",
-					  counted, nr, list);
+					  counted, list);
 			}
 			/*
 			 * otherwise, it is known not to reach any
@@ -278,7 +280,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 		}
 	}
 
-	show_list("bisection 2 initialize", counted, nr, list);
+	show_list("bisection 2 initialize", counted, list);
 
 	/*
 	 * If you have only one parent in the resulting set
@@ -300,15 +302,15 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 			node_data(p->item)->weight = count_distance(p->item);
 
 			/* Does it happen to be at exactly half-way? */
-			if (!find_all && halfway(p->item, nr))
+			if (!find_all && halfway(p->item))
 				return p;
 			counted++;
 		}
 	}
 
-	show_list("bisection 2 count_distance", counted, nr, list);
+	show_list("bisection 2 count_distance", counted, list);
 
-	while (counted < nr) {
+	while (counted < total) {
 		for (p = list; p; p = p->next) {
 			struct commit_list *q;
 			unsigned flags = p->item->object.flags;
@@ -334,40 +336,41 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 				node_data(p->item)->weight++;
 				counted++;
 				show_list("bisection 2 count one",
-					  counted, nr, list);
+					  counted, list);
 			}
 
 			/* Does it happen to be at exactly half-way? */
-			if (!find_all && halfway(p->item, nr))
+			if (!find_all && halfway(p->item))
 				return p;
 		}
 	}
 
-	show_list("bisection 2 counted all", counted, nr, list);
+	show_list("bisection 2 counted all", counted, list);
 
 	if (!find_all)
-		return best_bisection(list, nr);
+		return best_bisection(list);
 	else
-		return best_bisection_sorted(list, nr);
+		return best_bisection_sorted(list);
 }
 
 struct commit_list *find_bisection(struct commit_list *list,
 					  int *reaches, int *all,
 					  int find_all)
 {
-	int nr, on_list;
+	int on_list;
 	struct commit_list *p, *best, *next, *last;
 	struct node_data *weights;
 
+	total = 0;
 	marker = 0;
 
-	show_list("bisection 2 entry", 0, 0, list);
+	show_list("bisection 2 entry", 0, list);
 
 	/*
 	 * Count the number of total and tree-changing items on the
 	 * list, while reversing the list.
 	 */
-	for (nr = on_list = 0, last = NULL, p = list;
+	for (on_list = 0, last = NULL, p = list;
 	     p;
 	     p = next) {
 		unsigned flags = p->item->object.flags;
@@ -378,23 +381,24 @@ struct commit_list *find_bisection(struct commit_list *list,
 		p->next = last;
 		last = p;
 		if (!(flags & TREESAME))
-			nr++;
+			total++;
 		on_list++;
 	}
 	list = last;
-	show_list("bisection 2 sorted", 0, nr, list);
+	show_list("bisection 2 sorted", 0, list);
 
-	*all = nr;
+	*all = total;
 	weights = (struct node_data *)xcalloc(on_list, sizeof(*weights));
 
 	/* Do the real work of finding bisection commit. */
-	best = do_find_bisection(list, nr, weights, find_all);
+	best = do_find_bisection(list, weights, find_all);
 	if (best) {
 		if (!find_all)
 			best->next = NULL;
 		*reaches = node_data(best->item)->weight;
 	}
 	free(weights);
+
 	return best;
 }
 
@@ -931,7 +935,7 @@ int bisect_next_all(const char *prefix, int no_checkout)
 {
 	struct rev_info revs;
 	struct commit_list *tried;
-	int reaches = 0, all = 0, nr, steps;
+	int reaches = 0, nr, steps;
 	const unsigned char *bisect_rev;
 
 	read_bisect_terms(&term_bad, &term_good);
@@ -945,7 +949,7 @@ int bisect_next_all(const char *prefix, int no_checkout)
 
 	bisect_common(&revs);
 
-	revs.commits = find_bisection(revs.commits, &reaches, &all,
+	revs.commits = find_bisection(revs.commits, &reaches, &total,
 				       !!skipped_revs.nr);
 	revs.commits = managed_skipped(revs.commits, &tried);
 
@@ -963,7 +967,7 @@ int bisect_next_all(const char *prefix, int no_checkout)
 		exit(1);
 	}
 
-	if (!all) {
+	if (!total) {
 		fprintf(stderr, "No testable commit found.\n"
 			"Maybe you started with bad path parameters?\n");
 		exit(4);
@@ -980,8 +984,8 @@ int bisect_next_all(const char *prefix, int no_checkout)
 		exit(10);
 	}
 
-	nr = all - reaches - 1;
-	steps = estimate_bisect_steps(all);
+	nr = total - reaches - 1;
+	steps = estimate_bisect_steps(total);
 	printf("Bisecting: %d revision%s left to test after this "
 	       "(roughly %d step%s)\n", nr, (nr == 1 ? "" : "s"),
 	       steps, (steps == 1 ? "" : "s"));
-- 
2.7.1.354.gd492730.dirty

[PATCH 12/16] bisect: rename count_distance() to compute_weight()

[Stephan Beyer]

Let us use the term "weight" for the number of ancestors
of each commit, and "distance" for the number
min{weight, #commits - weight}. (Bisect finds the commit
with maximum distance.)

In these terms, "count_distance()" is the wrong name of
the function. So it is renamed to "compute_weight()",
and it also directly sets the computed weight.

Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
---
 bisect.c | 11 ++++++-----
 1 file changed, 6 insertions(+), 5 deletions(-)

diff --git a/bisect.c b/bisect.c
index 3a3a728..a9387a7 100644
--- a/bisect.c
+++ b/bisect.c
@@ -70,7 +70,7 @@ static inline int distance_direction(struct commit *commit)
 	return 0;
 }
 
-static int count_distance(struct commit *entry)
+static int compute_weight(struct commit *entry)
 {
 	int nr = 0;
 	struct commit_list *todo = NULL;
@@ -93,6 +93,7 @@ static int count_distance(struct commit *entry)
 		}
 	}
 
+	node_data(entry)->weight = nr;
 	return nr;
 }
 
@@ -241,7 +242,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list)
  * be computed.
  *
  * weight = -2 means it has more than one parent and its distance is
- * unknown.  After running count_distance() first, they will get zero
+ * unknown.  After running compute_weight() first, they will get zero
  * or positive distance.
  */
 static struct commit_list *do_find_bisection(struct commit_list *list,
@@ -286,7 +287,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 	 * If you have only one parent in the resulting set
 	 * then you can reach one commit more than that parent
 	 * can reach.  So we do not have to run the expensive
-	 * count_distance() for single strand of pearls.
+	 * compute_weight() for single strand of pearls.
 	 *
 	 * However, if you have more than one parent, you cannot
 	 * just add their distance and one for yourself, since
@@ -299,7 +300,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 	for (p = list; p; p = p->next) {
 		if (!(p->item->object.flags & UNINTERESTING)
 		 && (node_data(p->item)->weight == -2)) {
-			node_data(p->item)->weight = count_distance(p->item);
+			compute_weight(p->item);
 
 			/* Does it happen to be at exactly half-way? */
 			if (!find_all && halfway(p->item))
@@ -308,7 +309,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 		}
 	}
 
-	show_list("bisection 2 count_distance", counted, list);
+	show_list("bisection 2 compute_weight", counted, list);
 
 	while (counted < total) {
 		for (p = list; p; p = p->next) {
-- 
2.7.1.354.gd492730.dirty

[PATCH 13/16] bisect: prepare for different algorithms based on find_all

[Stephan Beyer]

This is a preparation commit with copy-and-paste involved.
The function do_find_bisection() is changed and copied to
two almost similar functions compute_all_weights() and
compute_relevant_weights().

The function compute_relevant_weights() stops when a
"halfway" commit is found.

To keep the code clean, the halfway commit is not returned
and has to be found by best_bisection() afterwards.
This results in a singular additional O(#commits)-time
overhead but this will be outweighed by the following
changes to compute_relevant_weights().

It is necessary to keep compute_all_weights() for the
"git rev-list --bisect-all" command. All other bisect-related
commands will use compute_relevant_weights().

Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
---
 bisect.c | 116 ++++++++++++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 97 insertions(+), 19 deletions(-)

diff --git a/bisect.c b/bisect.c
index a9387a7..1d1f61c 100644
--- a/bisect.c
+++ b/bisect.c
@@ -179,6 +179,7 @@ static struct commit_list *best_bisection(struct commit_list *list)
 		}
 	}
 
+	best->next = NULL;
 	return best;
 }
 
@@ -245,9 +246,8 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list)
  * unknown.  After running compute_weight() first, they will get zero
  * or positive distance.
  */
-static struct commit_list *do_find_bisection(struct commit_list *list,
-					     struct node_data *weights,
-					     int find_all)
+static void compute_all_weights(struct commit_list *list,
+				struct node_data *weights)
 {
 	int n, counted;
 	struct commit_list *p;
@@ -301,10 +301,88 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 		if (!(p->item->object.flags & UNINTERESTING)
 		 && (node_data(p->item)->weight == -2)) {
 			compute_weight(p->item);
+			counted++;
+		}
+	}
+
+	show_list("bisection 2 compute_weight", counted, list);
+
+	while (counted < total) {
+		for (p = list; p; p = p->next) {
+			struct commit_list *q;
+			unsigned flags = p->item->object.flags;
+
+			if (0 <= node_data(p->item)->weight)
+				continue;
+			for (q = p->item->parents; q; q = q->next) {
+				if (q->item->object.flags & UNINTERESTING)
+					continue;
+				if (0 <= node_data(q->item)->weight)
+					break;
+			}
+			if (!q)
+				continue;
+
+			/*
+			 * weight for p is unknown but q is known.
+			 * add one for p itself if p is to be counted,
+			 * otherwise inherit it from q directly.
+			 */
+			node_data(p->item)->weight = node_data(q->item)->weight;
+			if (!(flags & TREESAME)) {
+				node_data(p->item)->weight++;
+				counted++;
+				show_list("bisection 2 count one",
+					  counted, list);
+			}
+		}
+	}
+	show_list("bisection 2 counted all", counted, list);
+}
+
+/* At the moment this is basically the same as compute_all_weights()
+ * but with a halfway shortcut */
+static void compute_relevant_weights(struct commit_list *list,
+				     struct node_data *weights)
+{
+	int n, counted;
+	struct commit_list *p;
+
+	counted = 0;
+
+	for (n = 0, p = list; p; p = p->next) {
+		struct commit *commit = p->item;
+		unsigned flags = commit->object.flags;
+
+		commit->util = &weights[n++];
+		switch (count_interesting_parents(commit)) {
+		case 0:
+			if (!(flags & TREESAME)) {
+				node_data(commit)->weight = 1;
+				counted++;
+				show_list("bisection 2 count one",
+					  counted, list);
+			}
+			break;
+		case 1:
+			node_data(commit)->weight = -1;
+			break;
+		default:
+			node_data(commit)->weight = -2;
+			break;
+		}
+	}
+
+	show_list("bisection 2 initialize", counted, list);
+
+	for (p = list; p; p = p->next) {
+		if (!(p->item->object.flags & UNINTERESTING)
+		 && (node_data(p->item)->weight == -2)) {
+			compute_weight(p->item);
 
 			/* Does it happen to be at exactly half-way? */
-			if (!find_all && halfway(p->item))
-				return p;
+			if (halfway(p->item))
+				return;
 			counted++;
 		}
 	}
@@ -341,17 +419,11 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 			}
 
 			/* Does it happen to be at exactly half-way? */
-			if (!find_all && halfway(p->item))
-				return p;
+			if (halfway(p->item))
+				return;
 		}
 	}
-
 	show_list("bisection 2 counted all", counted, list);
-
-	if (!find_all)
-		return best_bisection(list);
-	else
-		return best_bisection_sorted(list);
 }
 
 struct commit_list *find_bisection(struct commit_list *list,
@@ -365,6 +437,9 @@ struct commit_list *find_bisection(struct commit_list *list,
 	total = 0;
 	marker = 0;
 
+	if (!list)
+		return NULL;
+
 	show_list("bisection 2 entry", 0, list);
 
 	/*
@@ -391,13 +466,16 @@ struct commit_list *find_bisection(struct commit_list *list,
 	*all = total;
 	weights = (struct node_data *)xcalloc(on_list, sizeof(*weights));
 
-	/* Do the real work of finding bisection commit. */
-	best = do_find_bisection(list, weights, find_all);
-	if (best) {
-		if (!find_all)
-			best->next = NULL;
-		*reaches = node_data(best->item)->weight;
+	if (find_all) {
+		compute_all_weights(list, weights);
+		best = best_bisection_sorted(list);
+	} else {
+		compute_relevant_weights(list, weights);
+		best = best_bisection(list);
 	}
+	assert(best);
+	*reaches = node_data(best->item)->weight;
+
 	free(weights);
 
 	return best;
-- 
2.7.1.354.gd492730.dirty

[PATCH 14/16] bisect: use a modified breadth-first search to find relevant weights

[Stephan Beyer]

The idea is to reverse the DAG and perform a modified breadth-first search
on it, starting on all sources of the reversed DAG.
Before each visit of a commit, its weight is induced.
This only works for non-merge commits, so the BFS stops prematurely on
merge commits (that are collected in a list).
Merge commits from that collection are considered for further visits
as soon as all their parents have been visited.
Their weights are computed using compute_weight().
Each BFS walk ends when the computed weight is falling or halfway.

Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
---

In other words: walk the history up, compute the weight of each
commit and stop when you know a better commit cannot follow.

This way, the expensive "compute_weight()" function is not called
on merge commits that will not help to find the maximum distance.

I have to mention that I also had a more complex idea, involving
a binary search on specifically ordered merge commits, and then
inducing the weights of the commits between those merge commits.
However, this is pretty nontrivial, error-prone by definition,
and the compute_weight() calls during the binary search can be more
expensive than during the "bottom-up" BFS walk.
So this is clearly the better idea. (And also follows the KISS rule.)

For the ads: ~3-4 seconds

 bisect.c | 246 ++++++++++++++++++++++++++++++++++++++++-----------------------
 1 file changed, 158 insertions(+), 88 deletions(-)

diff --git a/bisect.c b/bisect.c
index 1d1f61c..827a82a 100644
--- a/bisect.c
+++ b/bisect.c
@@ -30,6 +30,9 @@ static unsigned marker;
 struct node_data {
 	int weight;
 	unsigned marked;
+	unsigned parents;
+	unsigned visited : 1;
+	struct commit_list *children;
 };
 
 #define DEBUG_BISECT 0
@@ -110,16 +113,6 @@ static int count_interesting_parents(struct commit *commit)
 	return count;
 }
 
-static inline int halfway(struct commit *commit)
-{
-	/*
-	 * Don't short-cut something we are not going to return!
-	 */
-	if (commit->object.flags & TREESAME)
-		return 0;
-	return !distance_direction(commit);
-}
-
 #if !DEBUG_BISECT
 #define show_list(a,b,c) do { ; } while (0)
 #else
@@ -340,90 +333,167 @@ static void compute_all_weights(struct commit_list *list,
 	show_list("bisection 2 counted all", counted, list);
 }
 
-/* At the moment this is basically the same as compute_all_weights()
- * but with a halfway shortcut */
+static struct commit_list *build_reversed_dag(struct commit_list *list,
+					      struct node_data *nodes)
+{
+	struct commit_list *sources = NULL;
+	struct commit_list *p;
+	int n = 0;
+	for (p = list; p; p = p->next)
+		p->item->util = &nodes[n++];
+	for (p = list; p; p = p->next) {
+		struct commit_list *parent;
+		struct commit *commit = p->item;
+		for (parent = commit->parents; parent; parent = parent->next) {
+			if (!(parent->item->object.flags & UNINTERESTING)) {
+				struct commit_list **next = &node_data(parent->item)->children;
+				commit_list_insert(commit, next);
+				node_data(commit)->parents++;
+			}
+		}
+	}
+
+	/* find all sources */
+	for (p = list; p; p = p->next) {
+		if (node_data(p->item)->parents == 0)
+			commit_list_insert(p->item, &sources);
+	}
+
+	return sources;
+}
+
+static void commit_list_insert_unique(struct commit *item,
+				      struct commit_list **list)
+{
+	if (!*list || item < (*list)->item) /* empty list or item will be first */
+		commit_list_insert(item, list);
+	else if (item != (*list)->item) { /* item will not be first or not inserted */
+		struct commit_list *p = *list;
+		for (; p->next && p->next->item < item; p = p->next);
+		if (!p->next || item != p->next->item) /* not already inserted */
+			commit_list_insert(item, &p->next);
+	}
+}
+
+/* do a BFS on the reversed DAG (starting from commits in queue), stop at merge commits */
+static void bfs_up_to_merges(struct commit_list *queue,
+			     struct commit_list **merges)
+{
+	assert(queue);
+	struct commit_list **last;
+	for (last = &queue->next; *last; last = &(*last)->next);
+
+	while (queue) {
+		struct commit *top = queue->item;
+		struct commit_list *p;
+
+		if (distance_direction(top) > 0) {
+			node_data(top)->visited = 1;
+
+			/* queue children */
+			for (p = node_data(top)->children; p; p = p->next) {
+				if (node_data(p->item)->parents > 1) /* child is a merge */
+					commit_list_insert_unique(p->item, merges);
+				else {
+					node_data(p->item)->weight = node_data(top)->weight;
+					if (!(p->item->object.flags & TREESAME))
+						node_data(p->item)->weight++;
+					last = commit_list_append(p->item, last);
+				}
+			}
+		}
+
+		pop_commit(&queue);
+	}
+}
+
+static int all_parents_are_visited(struct commit *merge)
+{
+	struct commit_list *p;
+	for (p = merge->parents; p; p = p->next) {
+		if (p->item->util && !node_data(p->item)->visited)
+			return 0;
+	}
+	return 1;
+}
+
+static struct commit *extract_merge_to_queue(struct commit_list **merges)
+{
+	assert(merges);
+
+	struct commit_list *p, *q;
+	struct commit *found;
+
+	/* find a merge that is ready, i.e. all parents have been computed */
+	for (q = NULL, p = *merges; p && !all_parents_are_visited(p->item);
+	     q = p, p = p->next);
+	if (!p)
+		return NULL;
+
+	/* remove that commit from the list and return it */
+	if (q) {
+		assert(q->next == p);
+		q->next = p->next;
+	} else /* found first element of list */
+		*merges = p->next;
+	found = p->item;
+	free(p);
+
+	return found;
+}
+
+static int find_new_queue_from_merges(struct commit_list **queue,
+				      struct commit_list **merges)
+{
+	if (*merges) {
+		struct commit *merge = extract_merge_to_queue(merges);
+		*queue = NULL;
+		if (merge) {
+			commit_list_insert(merge, queue);
+			return 1;
+		}
+	}
+	return 0;
+}
+
+static void compute_merge_weights(struct commit_list *merges)
+{
+	struct commit_list *p;
+	for (p = merges; p; p = p->next)
+		compute_weight(p->item);
+}
+
+static void modified_bfs(struct commit_list *queue)
+{
+	struct commit_list *merges = NULL;
+	bfs_up_to_merges(queue, &merges);
+	while (find_new_queue_from_merges(&queue, &merges)) {
+		compute_merge_weights(queue);
+		bfs_up_to_merges(queue, &merges);
+	}
+}
+
+/* The idea is to reverse the DAG and perform a modified breadth-first search
+ * on it, starting on all sources of the reversed DAG.
+ * Before each visit of a commit, its weight is induced.
+ * This only works for non-merge commits, so the BFS stops prematurely on
+ * merge commits (that are collected in a list).
+ * Merge commits from that collection are considered for further visits
+ * as soon as all parents have been visited.
+ * Their weights are computed using compute_weight().
+ * Each BFS branch ends when the computed weight is falling or halfway.
+ */
 static void compute_relevant_weights(struct commit_list *list,
 				     struct node_data *weights)
 {
-	int n, counted;
 	struct commit_list *p;
+	struct commit_list *sources = build_reversed_dag(list, weights);
 
-	counted = 0;
+	for (p = sources; p; p = p->next)
+		node_data(p->item)->weight = 1;
+	modified_bfs(sources);
 
-	for (n = 0, p = list; p; p = p->next) {
-		struct commit *commit = p->item;
-		unsigned flags = commit->object.flags;
-
-		commit->util = &weights[n++];
-		switch (count_interesting_parents(commit)) {
-		case 0:
-			if (!(flags & TREESAME)) {
-				node_data(commit)->weight = 1;
-				counted++;
-				show_list("bisection 2 count one",
-					  counted, list);
-			}
-			break;
-		case 1:
-			node_data(commit)->weight = -1;
-			break;
-		default:
-			node_data(commit)->weight = -2;
-			break;
-		}
-	}
-
-	show_list("bisection 2 initialize", counted, list);
-
-	for (p = list; p; p = p->next) {
-		if (!(p->item->object.flags & UNINTERESTING)
-		 && (node_data(p->item)->weight == -2)) {
-			compute_weight(p->item);
-
-			/* Does it happen to be at exactly half-way? */
-			if (halfway(p->item))
-				return;
-			counted++;
-		}
-	}
-
-	show_list("bisection 2 compute_weight", counted, list);
-
-	while (counted < total) {
-		for (p = list; p; p = p->next) {
-			struct commit_list *q;
-			unsigned flags = p->item->object.flags;
-
-			if (0 <= node_data(p->item)->weight)
-				continue;
-			for (q = p->item->parents; q; q = q->next) {
-				if (q->item->object.flags & UNINTERESTING)
-					continue;
-				if (0 <= node_data(q->item)->weight)
-					break;
-			}
-			if (!q)
-				continue;
-
-			/*
-			 * weight for p is unknown but q is known.
-			 * add one for p itself if p is to be counted,
-			 * otherwise inherit it from q directly.
-			 */
-			node_data(p->item)->weight = node_data(q->item)->weight;
-			if (!(flags & TREESAME)) {
-				node_data(p->item)->weight++;
-				counted++;
-				show_list("bisection 2 count one",
-					  counted, list);
-			}
-
-			/* Does it happen to be at exactly half-way? */
-			if (halfway(p->item))
-				return;
-		}
-	}
-	show_list("bisection 2 counted all", counted, list);
+	show_list("bisection 3 result", total, list);
 }
 
 struct commit_list *find_bisection(struct commit_list *list,
-- 
2.7.1.354.gd492730.dirty

Re: [PATCH 14/16] bisect: use a modified breadth-first search to find relevant weights

[Junio C Hamano]

Stephan Beyer <s-beyer@gmx.net> writes:

> The idea is to reverse the DAG and perform a modified breadth-first search
> on it, starting on all sources of the reversed DAG.
> Before each visit of a commit, its weight is induced.
> This only works for non-merge commits, so the BFS stops prematurely on
> merge commits (that are collected in a list).
> Merge commits from that collection are considered for further visits
> as soon as all their parents have been visited.
> Their weights are computed using compute_weight().
> Each BFS walk ends when the computed weight is falling or halfway.
>
> Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
> ---
>
> In other words: walk the history up, compute the weight of each
> commit and stop when you know a better commit cannot follow.
>
> This way, the expensive "compute_weight()" function is not called
> on merge commits that will not help to find the maximum distance.

Interesting.  So you walk from the bottom commits, incrementing the
weight while walking on a part of the graph that is single strand of
pearls, or doing the "count the reachable ones the hard way" when
you hit a merge [*1*], but either way, once you know the commit you
are looking at is above the mid-way, i.e. reaches more than half of
the graph, then stop walking because its children will never be
better than that commit?

This is doubly clever idea [*2*].  It cuts the search space in half
for one thing, and more importantly, because "count the reachable
ones the hard way" counting has to traverse the graph from a merge
to the bottom boundary, the computation for a merge commit in the
more recent half of the history is more expensive than the
computation for a merge comit in the older half of the history, and
what you are avoiding is to waste the cycles on that more expensive
half.

I like it.

I haven't studied the code carefully, but your mention of BFS makes
me wonder if you can "narrow" down the search space even more.  In
an earlier step of the series, you introduced a work queue to
replace the recursion.  The recursion forces the algorithm to work
along the topology of the history, but you have more latitude in
selecting the commit to dig further with a work queue.

I wonder if you can sort the elements on the work queue based on
their distance (i.e. by using a priority queue).  You know the total
upfront, so you may find a commit whose weight is exactly half of it
before traversing all the bottom half of the history and it may turn
out to be even more efficient.  After all, you are only looking for
just one such commit, not trying to find all the commits with the
best weight.


[Footnote]

*1* A merge between a commit that reaches N commits and another that
reaches M commits may have weight smaller than the sum of N and M,
and that is why I left the original "truly stupid algorithm" Linus
wrote as-is when I did the obvious optimization for the linear parts
of the history.

*2* Whenever I revisited the bisection in my head, I thought about
ways to improve that "truly stupid" counting, but never thought
about an approach to simply reduce the number of times the "truly
stupid" counting has to be done.

Re: [PATCH 14/16] bisect: use a modified breadth-first search to find relevant weights

[Stephan Beyer]

Hi,

On 02/26/2016 04:09 AM, Junio C Hamano wrote:
> Interesting.  So you walk from the bottom commits, incrementing the
> weight while walking on a part of the graph that is single strand of
> pearls, or doing the "count the reachable ones the hard way" when
> you hit a merge [*1*], but either way, once you know the commit you
> are looking at is above the mid-way, i.e. reaches more than half of
> the graph, then stop walking because its children will never be
> better than that commit?

Exactly. Maybe that's an even better description for the commit message l-)

> I haven't studied the code carefully, but your mention of BFS makes
> me wonder if you can "narrow" down the search space even more.

I had an idea that aimed at accomplishing this by finding the
highest-distance merge commit using binary search. (The BFS collected
all merge commits, in that order, then you could do binary search.)
So you have O(log(#mergecommits)) "do it the hard way" weight computations.
However, in the worst case (or even in every case, I did not thoroughly
think about the cases that can occur), it could happen that it also had
to do these "do it the hard way" computations for all merge commits with
smaller weight... That's why I dropped this idea in favor of the more
simple approach that I sent to the list.

> In an earlier step of the series, you introduced a work queue to
> replace the recursion.  The recursion forces the algorithm to work
> along the topology of the history, but you have more latitude in
> selecting the commit to dig further with a work queue.
> 
> I wonder if you can sort the elements on the work queue based on
> their distance (i.e. by using a priority queue).  You know the total
> upfront, so you may find a commit whose weight is exactly half of it
> before traversing all the bottom half of the history and it may turn
> out to be even more efficient.  After all, you are only looking for
> just one such commit, not trying to find all the commits with the
> best weight.

For the compute_weight() function (the "doing it the hard way"
function), this would not make sense since all parent commits (of a
merge commit we call compute_weight() on) will have smaller distance.

However, your idea can help:
I just noticed that it's not important that I use a *B*FS because of the
acyclity. So I could also use a DFS that is "more greedy" going towards
high numbers.
Note that the traversal is always on trees because the merge commits are
cut out. So whenever a branching (a commit with more than one child)
occurs, the DFS should follow the branch of maximum length to its leaf.
(These maximum lengths can be saved during build_reversed_dag().)
Then, if there is a halfway commit, we stop. If not, we can just go on
with the remaining DFS...
I think I only rethought and rephrased your idea. :) Sounds good to me.
I'm going to add commits for that.

> [Footnote]
> 
> *1* A merge between a commit that reaches N commits and another that
> reaches M commits may have weight smaller than the sum of N and M,
> and that is why I left the original "truly stupid algorithm" Linus
> wrote as-is when I did the obvious optimization for the linear parts
> of the history.

Yes. In fact, the "truly stupid algorithm" is not truly stupid. I'm not
quite sure, but I think it's still the best algorithm known so far for
that problem. (But maybe the problem is just not very interesting in
science.)

> *2* Whenever I revisited the bisection in my head, I thought about
> ways to improve that "truly stupid" counting, but never thought
> about an approach to simply reduce the number of times the "truly
> stupid" counting has to be done.

Well, I also improved that "truly stupid" counting a little in a former
commit (patch 7). But it's just the implementation that I improved
(time/memory trade-off), not the algorithm. :)

Cheers,
  Stephan

[PATCH 15/16] bisect: compute best bisection in compute_relevant_weights()

[Stephan Beyer]

This commit gets rid of the O(#commits) extra overhead of
the best_bisection() function.

Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
---
 bisect.c | 43 ++++++++++++++++++-------------------------
 1 file changed, 18 insertions(+), 25 deletions(-)

diff --git a/bisect.c b/bisect.c
index 827a82a..185a3cf 100644
--- a/bisect.c
+++ b/bisect.c
@@ -27,6 +27,8 @@ static int total;
 
 static unsigned marker;
 
+static struct commit_list best_bisection;
+
 struct node_data {
 	int weight;
 	unsigned marked;
@@ -73,6 +75,14 @@ static inline int distance_direction(struct commit *commit)
 	return 0;
 }
 
+static inline void update_best_bisection(struct commit *commit)
+{
+	if (distance_direction(commit) >= 0
+	 && node_data(commit)->weight > node_data(best_bisection.item)->weight) {
+		best_bisection.item = commit;
+	}
+}
+
 static int compute_weight(struct commit *entry)
 {
 	int nr = 0;
@@ -153,29 +163,6 @@ static void show_list(const char *debug, int counted,
 }
 #endif /* DEBUG_BISECT */
 
-static struct commit_list *best_bisection(struct commit_list *list)
-{
-	struct commit_list *p, *best;
-	int best_distance = -1;
-
-	best = list;
-	for (p = list; p; p = p->next) {
-		int distance;
-		unsigned flags = p->item->object.flags;
-
-		if (flags & TREESAME)
-			continue;
-		distance = get_distance(p->item);
-		if (distance > best_distance) {
-			best = p;
-			best_distance = distance;
-		}
-	}
-
-	best->next = NULL;
-	return best;
-}
-
 struct commit_dist {
 	struct commit *commit;
 	int distance;
@@ -403,6 +390,7 @@ static void bfs_up_to_merges(struct commit_list *queue,
 			}
 		}
 
+		update_best_bisection(top);
 		pop_commit(&queue);
 	}
 }
@@ -459,8 +447,10 @@ static int find_new_queue_from_merges(struct commit_list **queue,
 static void compute_merge_weights(struct commit_list *merges)
 {
 	struct commit_list *p;
-	for (p = merges; p; p = p->next)
+	for (p = merges; p; p = p->next) {
 		compute_weight(p->item);
+		update_best_bisection(p->item);
+	}
 }
 
 static void modified_bfs(struct commit_list *queue)
@@ -489,6 +479,9 @@ static void compute_relevant_weights(struct commit_list *list,
 	struct commit_list *p;
 	struct commit_list *sources = build_reversed_dag(list, weights);
 
+	best_bisection.item = sources->item;
+	best_bisection.next = NULL;
+
 	for (p = sources; p; p = p->next)
 		node_data(p->item)->weight = 1;
 	modified_bfs(sources);
@@ -541,7 +534,7 @@ struct commit_list *find_bisection(struct commit_list *list,
 		best = best_bisection_sorted(list);
 	} else {
 		compute_relevant_weights(list, weights);
-		best = best_bisection(list);
+		best = &best_bisection;
 	}
 	assert(best);
 	*reaches = node_data(best->item)->weight;
-- 
2.7.1.354.gd492730.dirty

[PATCH 16/16] bisect: get back halfway shortcut

[Stephan Beyer]

The documentation says that when the maximum possible distance
is found, the algorithm stops immediately. That feature is
reestablished by this commit.

Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
---

In my tests, I have not seen any gain of performance by
doing this... but it's fast now anyway, who cares ;-)

 bisect.c | 17 ++++++++++++-----
 1 file changed, 12 insertions(+), 5 deletions(-)

diff --git a/bisect.c b/bisect.c
index 185a3cf..0153d9a 100644
--- a/bisect.c
+++ b/bisect.c
@@ -363,8 +363,8 @@ static void commit_list_insert_unique(struct commit *item,
 }
 
 /* do a BFS on the reversed DAG (starting from commits in queue), stop at merge commits */
-static void bfs_up_to_merges(struct commit_list *queue,
-			     struct commit_list **merges)
+static int bfs_up_to_merges(struct commit_list *queue,
+			    struct commit_list **merges)
 {
 	assert(queue);
 	struct commit_list **last;
@@ -391,8 +391,13 @@ static void bfs_up_to_merges(struct commit_list *queue,
 		}
 
 		update_best_bisection(top);
+		if (distance_direction(top) == 0) { // halfway
+			assert(!(top->object.flags & TREESAME));
+			return 1;
+		}
 		pop_commit(&queue);
 	}
+	return 0;
 }
 
 static int all_parents_are_visited(struct commit *merge)
@@ -456,10 +461,12 @@ static void compute_merge_weights(struct commit_list *merges)
 static void modified_bfs(struct commit_list *queue)
 {
 	struct commit_list *merges = NULL;
-	bfs_up_to_merges(queue, &merges);
-	while (find_new_queue_from_merges(&queue, &merges)) {
+	int halfway_found = bfs_up_to_merges(queue, &merges);
+
+	while (!halfway_found
+	    && find_new_queue_from_merges(&queue, &merges)) {
 		compute_merge_weights(queue);
-		bfs_up_to_merges(queue, &merges);
+		halfway_found &= bfs_up_to_merges(queue, &merges);
 	}
 }
 
-- 
2.7.1.354.gd492730.dirty

Re: [PATCH 00/16] git bisect improvements

[Pranit Bauva]

I have been recently following this series of patches and it seems a
bit stale. These patches haven't been followed up with improvement
patches. If it is okay with you then can I work more upon these
patches in my GSoC project. These really seem interesting and Git
could really benefit from this.

Regards,
Pranit Bauva

On Fri, Feb 26, 2016 at 7:34 AM, Stephan Beyer <s-beyer@gmx.net> wrote:
> Hi,
>
> this set of patches provides improvements for git bisect.
>
> Quick summary of changes
>  - relevant for users:
>    - `git bisect next` is documented and motivated
>    - git bisect implementation becomes much faster
>      (or: is now working) for big repositories**
>  - relevant for developers:
>    - a test for the git bisect algorithm is added
>    - fix: bisect.c compiles also if DEBUG_BISECT is set
>
> The ** marked change is the most interesting one.
> To be more accurate: the use case is when you want to bisect in a
> repository with a huge amount of merge commits (and having these
> merge commits relevant for the actual bisect process).
> For example, a bisect in the whole git master branch took
> ~50 seconds, now it takes ~4 seconds.
>
>
> Note that the patches have finer granularity (especially the performance
> improvements are splitted into several preparing commits).
> For some patches, there is some more patch-related story as
> "cover letter material" in these patches.
>
> Btw: I also wondered about the internationalizaton: no string in bisect.c
> is marked for translation. Intentionally?
>
> Cheers
>
> Stephan Beyer (16):
>   bisect: write about `bisect next` in documentation
>   bisect: add test for the bisect algorithm
>   bisect: make bisect compile if DEBUG_BISECT is set
>   bisect: make algorithm behavior independent of DEBUG_BISECT
>   bisect: get rid of recursion in count_distance()
>   bisect: use struct node_data array instead of int array
>   bisect: replace clear_distance() by unique markers
>   bisect: use commit instead of commit list as arguments when
>     appropriate
>   bisect: extract get_distance() function from code duplication
>   bisect: introduce distance_direction()
>   bisect: make total number of commits global
>   bisect: rename count_distance() to compute_weight()
>   bisect: prepare for different algorithms based on find_all
>   bisect: use a modified breadth-first search to find relevant weights
>   bisect: compute best bisection in compute_relevant_weights()
>   bisect: get back halfway shortcut
>
>  Documentation/git-bisect.txt |  25 +++
>  bisect.c                     | 473 ++++++++++++++++++++++++++++---------------
>  git-bisect.sh                |  15 +-
>  t/t8010-bisect-algorithm.sh  | 162 +++++++++++++++
>  4 files changed, 502 insertions(+), 173 deletions(-)
>  create mode 100755 t/t8010-bisect-algorithm.sh
>
> --
> 2.7.1.354.gd492730.dirty
>
> --
> 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

Re: [PATCH 00/16] git bisect improvements

[Stephan Beyer]

Hi Pranit,

On 03/20/2016 07:50 PM, Pranit Bauva wrote:
> I have been recently following this series of patches and it seems a
> bit stale. These patches haven't been followed up with improvement
> patches.

I'm on vacation at the moment.

Patchset v1 contains some bugs. So I just updated the branch on
github[1] for you which is the state-of-the-art for patchset v2. Note
that it also contains an odd bug (which seems to exist before my patches
but turns to light after my patches) but I haven't found time to
investigate it further before my vacation started. (That's also why I
didn't post any updates on that topic to the list.)

1. https://github.com/sbeyer/git/commits/bisect

Also sorry, I am not following the list so I didn't know there was a
GSoC project for bisect.

> If it is okay with you then can I work more upon these
> patches in my GSoC project.

I'm totally fine with that, of course. :)

Thanks,
Stephan

Re: [PATCH 00/16] git bisect improvements

[Christian Couder]

On Mon, Mar 21, 2016 at 11:22 PM, Stephan Beyer <s-beyer@gmx.net> wrote:
>
> Also sorry, I am not following the list so I didn't know there was a
> GSoC project for bisect.
>
>> If it is okay with you then can I work more upon these
>> patches in my GSoC project.
>
> I'm totally fine with that, of course. :)

You are the Stephan Beyer who did a GSoC project on the sequencer
around 2009, right?

It's nice to see you back on the list :-)

Re: [PATCH 00/16] git bisect improvements

[Pranit Bauva]

On Tue, Mar 22, 2016 at 3:52 AM, Stephan Beyer <s-beyer@gmx.net> wrote:
>> If it is okay with you then can I work more upon these
>> patches in my GSoC project.
>
> I'm totally fine with that, of course. :)

Thanks! :)
I will try and fix the left over bug if time persists.

Regards,
Pranit Bauva