first bisection step takes quite a while

first bisection step takes quite a while

[Uwe Kleine-König]

[-- Attachment #1: Type: text/plain, Size: 1008 bytes --]

Hello,

today I did a bisection in the kernel repository:

	linux$ git version
	git version 2.47.1

	linux$ time git bisect start 09fbf3d502050282bf47ab3babe1d4ed54dd1fd8 96d8eab5d0a1a9741a4cae1b3c125d75d1aabedf
	Bisecting: 572238 revisions left to test after this (roughly 19 steps)
	[eafdca4d7010a0e019aaaace3dd71b432a69b54c] Merge tag 'staging-4.18-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/staging

	real	18m41.374s
	user	27m18.306s
	sys	1m0.565s

I was surprised that it took that long to find and checkout the first
revision to check. (That is on a 4 x Intel(R) Core(TM) i5-6440HQ CPU @
2.60GHz, 16 GiB RAM with a Samsung SSD. On a different machine (56 x
Intel(R) Xeon(R) CPU E5-2660 v4 @ 2.00GHz, 256 GiB RAM and (I think a
spinning hard disk)) it took nearly an hour.

I think this isn't my first bisection over that many commits, but I
cannot remember that the first step ever took so long.

Is my expectation (and maybe memory) wrong, or is this a regression?

Best regards
Uwe

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: first bisection step takes quite a while

[D. Ben Knoble]

On Thu, Feb 20, 2025 at 9:38 AM Uwe Kleine-König
<u.kleine-koenig@baylibre.com> wrote:
>
> Hello,
>
> today I did a bisection in the kernel repository:
>
>         linux$ git version
>         git version 2.47.1
>
>         linux$ time git bisect start 09fbf3d502050282bf47ab3babe1d4ed54dd1fd8 96d8eab5d0a1a9741a4cae1b3c125d75d1aabedf
>         Bisecting: 572238 revisions left to test after this (roughly 19 steps)
>         [eafdca4d7010a0e019aaaace3dd71b432a69b54c] Merge tag 'staging-4.18-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/staging
>
>         real    18m41.374s
>         user    27m18.306s
>         sys     1m0.565s
>
> I was surprised that it took that long to find and checkout the first
> revision to check. (That is on a 4 x Intel(R) Core(TM) i5-6440HQ CPU @
> 2.60GHz, 16 GiB RAM with a Samsung SSD. On a different machine (56 x
> Intel(R) Xeon(R) CPU E5-2660 v4 @ 2.00GHz, 256 GiB RAM and (I think a
> spinning hard disk)) it took nearly an hour.

Related thread:
https://lore.kernel.org/git/19461b87a5c.5a2ea74016716.8214238482389812984@zohomail.com/



-- 
D. Ben Knoble

Re: first bisection step takes quite a while

[Junio C Hamano]

"D. Ben Knoble" <ben.knoble@gmail.com> writes:

> On Thu, Feb 20, 2025 at 9:38 AM Uwe Kleine-König
> <u.kleine-koenig@baylibre.com> wrote:
>>
>> Hello,
>>
>> today I did a bisection in the kernel repository:
>>
>>         linux$ git version
>>         git version 2.47.1
>>
>>         linux$ time git bisect start 09fbf3d502050282bf47ab3babe1d4ed54dd1fd8 96d8eab5d0a1a9741a4cae1b3c125d75d1aabedf
>>         Bisecting: 572238 revisions left to test after this (roughly 19 steps)
>>         [eafdca4d7010a0e019aaaace3dd71b432a69b54c] Merge tag 'staging-4.18-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/staging
>>
>>         real    18m41.374s
>>         user    27m18.306s
>>         sys     1m0.565s
>>
>> I was surprised that it took that long to find and checkout the first
>> revision to check. (That is on a 4 x Intel(R) Core(TM) i5-6440HQ CPU @
>> 2.60GHz, 16 GiB RAM with a Samsung SSD. On a different machine (56 x
>> Intel(R) Xeon(R) CPU E5-2660 v4 @ 2.00GHz, 256 GiB RAM and (I think a
>> spinning hard disk)) it took nearly an hour.
>
> Related thread:
> https://lore.kernel.org/git/19461b87a5c.5a2ea74016716.8214238482389812984@zohomail.com/

Indeed.  I haven't had a chance to dig any deeper in the area of the
code since that discussion, but the ideas raised in the messages
near the tail end of the thread may be worth exploring.

THanks for the link.

Re: first bisection step takes quite a while

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> "D. Ben Knoble" <ben.knoble@gmail.com> writes:
>
>> On Thu, Feb 20, 2025 at 9:38 AM Uwe Kleine-König
>> <u.kleine-koenig@baylibre.com> wrote:
>>>
>>> Hello,
>>>
>>> today I did a bisection in the kernel repository:
>>>
>>>         linux$ git version
>>>         git version 2.47.1
>>>
>>>         linux$ time git bisect start 09fbf3d502050282bf47ab3babe1d4ed54dd1fd8 96d8eab5d0a1a9741a4cae1b3c125d75d1aabedf
>>>         Bisecting: 572238 revisions left to test after this (roughly 19 steps)
>>>         [eafdca4d7010a0e019aaaace3dd71b432a69b54c] Merge tag 'staging-4.18-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/staging
>>>
>>>         real    18m41.374s
>>>         user    27m18.306s
>>>         sys     1m0.565s
>>>
>>> I was surprised that it took that long to find and checkout the first
>>> revision to check. (That is on a 4 x Intel(R) Core(TM) i5-6440HQ CPU @
>>> 2.60GHz, 16 GiB RAM with a Samsung SSD. On a different machine (56 x
>>> Intel(R) Xeon(R) CPU E5-2660 v4 @ 2.00GHz, 256 GiB RAM and (I think a
>>> spinning hard disk)) it took nearly an hour.
>>
>> Related thread:
>> https://lore.kernel.org/git/19461b87a5c.5a2ea74016716.8214238482389812984@zohomail.com/
>
> Indeed.  I haven't had a chance to dig any deeper in the area of the
> code since that discussion, but the ideas raised in the messages
> near the tail end of the thread may be worth exploring.
>
> THanks for the link.

So, here is something that _could_ be the beginning of a patch, but
just to illustrate what I tried.

 * In do_find_bisection(), we try each commit on the incoming commit
   list (which is sorted the way rev-list emits, probably reversed)
   and count how many commits in the set each merge commit can reach
   (which is called "weight") in the "honest and stupid" way.  I try
   to collect these merges in a linear array, and try from the
   middle to older and newer.  As the loop to compute weight for
   merges have an early-exit clause that says "oh, this is good
   enough", this may improve our odds to find a good enough merge
   early.

 * The "this is good enough" logic currently allows us to be within
   0.1% of the real halfway point.  Until the candidate set becomes
   small enough, we could loosen the criteria to allow larger, say
   3%, slack.  This code is written but not enabled (with "0 &&").

 * After computing the weight for a merge in "honest and stupid"
   way, we know what other commits in the set it can reach.  If the
   weight we computed is way smaller than the half the number of
   commits in the set, that means these commits we can reach from
   the merge we are looking at would score even lower.  We could
   mark them as not-viable before clearing the list to check next
   merge with "honest and stupid" way.  Again, this code is written
   but not enabled.

So, in short, I have three ideas, and with the first one (that
is the most straightforward and least error prone) alone, it seems
that we gain significant speedup.

The current code took ~20 minutes for me and its result is

$ git bisect start --no-checkout 09fbf3d5020 96d8eab5d0a1
Bisecting: 581164 revisions left to test after this (roughly 19 steps)
[2c71ab4bb465c79a4687cc2fd5012e470aebdb1f] Merge branch 'for-upstre...

There are 1144459 commits in the range, and the point chosen by
bisection can reach 563294 of them.  563294*2 == 1126588, so we are
1144459 - 1126588 = 17871 commits away from the theoretical halfway.

With the "let's try from the midway merges" approach without
changing anything else, I get a different commit (because the
original algorithm is taking "good enough" early exit), and it took
about 30 seconds.

$ git bisect start --no-checkout 09fbf3d5020 96d8eab5d0a1
Bisecting: 572238 revisions left to test after this (roughly 19 steps)
[eafdca4d7010a0e019aaaace3dd71b432a69b54c] Merge tag 'staging-4.18-...

The size of the original range is the same, of course, 1144459
commits, and the point chosen by bisection reaches 572220 of them.
Since 572220*2 = 1144440, we are 1144459 - 1144440 = 19 commits from
the theoretical halfway.

My current thinking is that the heuristics #1 (which is enabled in
my experiment and in the following patch) is good enough, #2
(loosening the "good enough" threshold) is probably not very
effective, and #3 (discard ones that are closer to the good end than
a merge that is known to be not viable) might be interesting to
pursue further but probably tricky to get right.

Comments?


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

diff --git c/bisect.c w/bisect.c
index 7a3c77c6d8..eae8e97958 100644
--- c/bisect.c
+++ w/bisect.c
@@ -23,6 +23,7 @@
 #include "object-store-ll.h"
 #include "path.h"
 #include "dir.h"
+#include "trace2.h"
 
 static struct oid_array good_revs;
 static struct oid_array skipped_revs;
@@ -132,8 +133,10 @@ static inline int approx_halfway(struct commit_list *p, int nr)
 		 * good enough if it's within ~0.1% of the halfway point,
 		 * e.g. 5000 is exactly halfway of 10000, but we consider
 		 * the values [4996, 5004] as halfway as well.
+		 * While we have really large number of commits, we'll
+		 * loosen our target to hit within 3% of the harfway.
 		 */
-		if (abs(diff) < nr / 1024)
+		if ((0 && 10000 < nr && abs(diff) < nr / 64) || abs(diff) < nr / 1024)
 			return 1;
 		return 0;
 	}
@@ -282,11 +285,15 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 					     int nr, int *weights,
 					     unsigned bisect_flags)
 {
-	int n, counted;
+	int n, counted, num_merges;
 	struct commit_list *p;
+	struct commit_list **merge; /* ugh */
 
+	num_merges = 0;
 	counted = 0;
+	num_merges = 0;
 
+	trace2_region_enter("bisect", "do_find_bisection_0", the_repository);
 	for (n = 0, p = list; p; p = p->next) {
 		struct commit *commit = p->item;
 		unsigned commit_flags = commit->object.flags;
@@ -309,16 +316,30 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 			weight_set(p, -1);
 			break;
 		default:
+			num_merges++;
 			weight_set(p, -2);
 			break;
 		}
 	}
+	trace2_region_leave("bisect", "do_find_bisection_0", the_repository);
 
 	show_list("bisection 2 initialize", counted, nr, list);
 
+	/*
+	 * Collect merges into an array.
+	 */
+	CALLOC_ARRAY(merge, num_merges);
+	for (n = 0, p = list; p; p = p->next) {
+		if (weight(p) != -2)
+			continue;
+		merge[n++] = p;
+	}
+	if (num_merges != n)
+		BUG("Whoa!");
+
 	/*
 	 * If you have only one parent in the resulting set
-	 * then you can reach one commit more than that parent
+	 * then you can reach one commit more than your parent
 	 * can reach.  So we do not have to run the expensive
 	 * count_distance() for single strand of pearls.
 	 *
@@ -330,25 +351,73 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 	 * So we will first count distance of merges the usual
 	 * way, and then fill the blanks using cheaper algorithm.
 	 */
-	for (p = list; p; p = p->next) {
-		if (p->item->object.flags & UNINTERESTING)
-			continue;
+	trace2_region_enter("bisect", "do_find_bisection_1", the_repository);
+
+	/*
+	 * Use the element of a list from its midpoint.
+	 * (num_merges == 1) mid = 0; ix = 0
+	 * (num_merges == 2) mid = 0; ix = 0, 1
+	 * (num_merges == 3) mid = 1; ix = 1, 2, 0
+	 * (num_merges == 4) mid = 1; ix = 1, 2, 0, 3
+	 * (num_merges == 5) mid = 2; ix = 2, 3, 1, 4, 0
+	 * (num_merges == 6) mid = 2; ix = 2, 3, 1, 4, 0, 5
+	 */
+	for (n = 0; n < num_merges; n++) {
+		struct commit_list *p;
+		int ix = (num_merges - 1) / 2;
+
+		if (n % 2)
+			ix += (n + 1) / 2;
+		else
+			ix -= n / 2;
+
+		p = merge[ix];
 		if (weight(p) != -2)
 			continue;
 		if (bisect_flags & FIND_BISECTION_FIRST_PARENT_ONLY)
 			BUG("shouldn't be calling count-distance in fp mode");
 		weight_set(p, count_distance(p));
+
+#if 0
+		/* 
+		 * If the current merge can reach way fewer than half
+		 * the commits in the graph, any of its ancestors can
+		 * reach even fewer commits, which means they will not
+		 * make better half-way candidate than this one.
+		 *
+		 * Just as a slack, let's cut at 3/8 not exactly 1/2.
+		 */
+		if (weight(p) * 8 < nr * 3) {
+			for (struct commit_list *q = list; q; q = q->next) {
+				if (q->item->object.flags & UNINTERESTING)
+					continue;
+				if (!(q->item->object.flags & COUNTED))
+					continue;
+				if (weight(q) != -2)
+					continue;
+				/* mark it as not a viable candidate */
+				weight_set(q, 1);
+			}
+		}
+#endif
 		clear_distance(list);
 
 		/* Does it happen to be at half-way? */
 		if (!(bisect_flags & FIND_BISECTION_ALL) &&
-		      approx_halfway(p, nr))
+		    approx_halfway(p, nr)) {
+			trace2_data_string("bisect", the_repository, "early-exit", "do_find_bisection_1");
+			trace2_region_leave("bisect", "do_find_bisection_1", the_repository);
+			free(merge);
 			return p;
+		}
 		counted++;
 	}
+	trace2_region_leave("bisect", "do_find_bisection_1", the_repository);
+	free(merge);
 
 	show_list("bisection 2 count_distance", counted, nr, list);
 
+	trace2_region_enter("bisect", "do_find_bisection_2", the_repository);
 	while (counted < nr) {
 		for (p = list; p; p = p->next) {
 			struct commit_list *q;
@@ -384,10 +453,14 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 
 			/* Does it happen to be at half-way? */
 			if (!(bisect_flags & FIND_BISECTION_ALL) &&
-			      approx_halfway(p, nr))
+			    approx_halfway(p, nr)) {
+			trace2_data_string("bisect", the_repository, "early-exit", "do_find_bisection_2");
+				trace2_region_leave("bisect", "do_find_bisection_2", the_repository);
 				return p;
+			}
 		}
 	}
+	trace2_region_leave("bisect", "do_find_bisection_2", the_repository);
 
 	show_list("bisection 2 counted all", counted, nr, list);
 

Re: first bisection step takes quite a while

[Christian Couder]

On Fri, Feb 21, 2025 at 2:41 AM Junio C Hamano <gitster@pobox.com> wrote:

> So, here is something that _could_ be the beginning of a patch, but
> just to illustrate what I tried.
>
>  * In do_find_bisection(), we try each commit on the incoming commit
>    list (which is sorted the way rev-list emits, probably reversed)
>    and count how many commits in the set each merge commit can reach
>    (which is called "weight") in the "honest and stupid" way.  I try
>    to collect these merges in a linear array, and try from the
>    middle to older and newer.  As the loop to compute weight for
>    merges have an early-exit clause that says "oh, this is good
>    enough", this may improve our odds to find a good enough merge
>    early.

Yeah, it seems to me that in practice this is a bit like bisecting on
the first parents first. It would be nice if we had added an option to
bisect on the first parents first, so that we could compare your
improvement and that option.

>  * The "this is good enough" logic currently allows us to be within
>    0.1% of the real halfway point.  Until the candidate set becomes
>    small enough, we could loosen the criteria to allow larger, say
>    3%, slack.  This code is written but not enabled (with "0 &&").

If we want to do this, I think we could loosen the criteria even if
the candidate set is small. Weights are integers so when the number of
candidates is around 33 or less, a 3% criteria will mean an exact
match. Then the last 5 steps or so (as 2^5 = 32) would still be
performed in the same way (with an exact match).

>  * After computing the weight for a merge in "honest and stupid"
>    way, we know what other commits in the set it can reach.  If the
>    weight we computed is way smaller than the half the number of
>    commits in the set, that means these commits we can reach from
>    the merge we are looking at would score even lower.  We could
>    mark them as not-viable before clearing the list to check next
>    merge with "honest and stupid" way.  Again, this code is written
>    but not enabled.
>
> So, in short, I have three ideas, and with the first one (that
> is the most straightforward and least error prone) alone, it seems
> that we gain significant speedup.
>
> The current code took ~20 minutes for me and its result is
>
> $ git bisect start --no-checkout 09fbf3d5020 96d8eab5d0a1
> Bisecting: 581164 revisions left to test after this (roughly 19 steps)
> [2c71ab4bb465c79a4687cc2fd5012e470aebdb1f] Merge branch 'for-upstre...
>
> There are 1144459 commits in the range, and the point chosen by
> bisection can reach 563294 of them.  563294*2 == 1126588, so we are
> 1144459 - 1126588 = 17871 commits away from the theoretical halfway.
>
> With the "let's try from the midway merges" approach without
> changing anything else, I get a different commit (because the
> original algorithm is taking "good enough" early exit), and it took
> about 30 seconds.
>
> $ git bisect start --no-checkout 09fbf3d5020 96d8eab5d0a1
> Bisecting: 572238 revisions left to test after this (roughly 19 steps)
> [eafdca4d7010a0e019aaaace3dd71b432a69b54c] Merge tag 'staging-4.18-...
>
> The size of the original range is the same, of course, 1144459
> commits, and the point chosen by bisection reaches 572220 of them.
> Since 572220*2 = 1144440, we are 1144459 - 1144440 = 19 commits from
> the theoretical halfway.
>
> My current thinking is that the heuristics #1 (which is enabled in
> my experiment and in the following patch) is good enough, #2
> (loosening the "good enough" threshold) is probably not very
> effective, and #3 (discard ones that are closer to the good end than
> a merge that is known to be not viable) might be interesting to
> pursue further but probably tricky to get right.

I agree that #1 is probably good enough.

About #2, I think it could be worth implementing as an option if it is
effective in some cases, but the criteria should be loosened even if
the candidate set is small. The amount of code to implement it is very
small and it's possible that, for some users, having to sometimes
perform one more step of testing is not a big deal, compared to
bisecting speed.

About #3, I think that implementing an option to bisect on the first
parents first is likely more useful than implementing it.

Thanks.

Re: first bisection step takes quite a while

[Uwe Kleine-König]

[-- Attachment #1: Type: text/plain, Size: 718 bytes --]

Hello Junio,

On Thu, Feb 20, 2025 at 05:40:53PM -0800, Junio C Hamano wrote:
> Comments?

It's long time ago that I looked into the git source code and I guess
many things have changed since then.

Anyhow, here comes my thought about how finding a bisection point could
work.

Pick the middle commit of `git rev-list --topo-order $bad ^$allgood`.
Lets assume this are 10000 commits. Check the weight of commit[5000].
Depending on how much the weight is off from 5000 make a bigger or a
smaller step up or down to find the next commit to check. So a scaled
bisection on the topo-order commit list. I think that doesn't
necessarily finds a best bisection point, but I havn't thought about
that a lot.

Best regards
Uwe

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: first bisection step takes quite a while

[Junio C Hamano]

Uwe Kleine-König <u.kleine-koenig@baylibre.com> writes:

> Hello Junio,
>
> On Thu, Feb 20, 2025 at 05:40:53PM -0800, Junio C Hamano wrote:
>> Comments?
>
> It's long time ago that I looked into the git source code and I guess
> many things have changed since then.

;-)  Apparently not much has changed around this area.  I was amazed
how things haven't changed around the code since I wrote it in 2007
with "the clever trick" to improve what Linus called "truly stupid"
algorithm.  No, I didn't improve the stupid algorithm.  The clever
trick was to reduce the need to call it.

> Anyhow, here comes my thought about how finding a bisection point could
> work.
>
> Pick the middle commit of `git rev-list --topo-order $bad ^$allgood`.
> Lets assume this are 10000 commits. Check the weight of commit[5000].
> Depending on how much the weight is off from 5000 make a bigger or a
> smaller step up or down to find the next commit to check. So a scaled
> bisection on the topo-order commit list. I think that doesn't
> necessarily finds a best bisection point, but I havn't thought about
> that a lot.

Since the name of the game is to find "a" good enough point in the
earlier part of a huge bisection session, that certainly is good way
to think about the problem space.  The commit[] array you have may
not be a linear single-strand-of-pearls history, and a naïve
bisection would not work well in such a case, so we have to be a bit
more careful here.

The code I touched in the illustration needs to either find a merge
commit that is really good enough and leave early, or if there is no
such merge commit, compute how many other commits in the range each
and every merge commit in the range that can be the ancestor of 
the best non-merge commit on a single-strand-of-pearls history.

Thanks.

Re: first bisection step takes quite a while

[Junio C Hamano]

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

> Yeah, it seems to me that in practice this is a bit like bisecting on
> the first parents first. It would be nice if we had added an option to
> bisect on the first parents first, so that we could compare your
> improvement and that option.

Unless you are talking about something entirely different, I am
afraid you are confused.  We added first-parent bisection in mid
2020.

And the first-parent bisection does make things easy, by making it
totally unnecessary to call the "truly stupid" count_distance() at
all.  We can pretend as if we have a single-strand-of-pearls, give
the "good" end of the history "1" as its weight, its direct
descendant (and there is only one direct descendant when we are
doing first-parent bisection, since there always is only one active
"bad" end of the range in our bisection session) "2" as its weight,
and so on.  The commit that gets N/2 weight is the midway and we
need O(N) computation.

Unfortunatly Uwe's original problem description was not about
first-parent bisection being slow.

>>  * The "this is good enough" logic currently allows us to be within
>>    0.1% of the real halfway point.  Until the candidate set becomes
>>    small enough, we could loosen the criteria to allow larger, say
>>    3%, slack.  This code is written but not enabled (with "0 &&").
>
> If we want to do this, I think we could loosen the criteria even if
> the candidate set is small. Weights are integers so when the number of
> candidates is around 33 or less, a 3% criteria will mean an exact
> match. Then the last 5 steps or so (as 2^5 = 32) would still be
> performed in the same way (with an exact match).

The above follows the same reasoning why we chose "division by 1024"
in the first place.  The illustration patch postulates that we could
be way more aggressive than 0.1% while the set is large by dividing
64, without wanting to loosen the criteria near the end of the
bisection session when the remaining set is reasonably small like
1000 commits.  So we cannot rely on integer division truncating.

>>  * After computing the weight for a merge in "honest and stupid"
>>    way, we know what other commits in the set it can reach.  If the
>>    weight we computed is way smaller than the half the number of
>>    commits in the set, that means these commits we can reach from
>>    the merge we are looking at would score even lower.  We could
>>    mark them as not-viable before clearing the list to check next
>>    merge with "honest and stupid" way.  Again, this code is written
>>    but not enabled.
>> ...

> About #2, I think it could be worth implementing as an option if it is
> effective in some cases, but the criteria should be loosened even if
> the candidate set is small. The amount of code to implement it is very
> small and it's possible that, for some users, having to sometimes
> perform one more step of testing is not a big deal, compared to
> bisecting speed.

The reason why I think #2 would not be effective is quite different,
but I'd not go into that, as your conclusion is the same ;-)

> About #3, I think that implementing an option to bisect on the first
> parents first is likely more useful than implementing it.

Sorry, but is very much orthogonal to the issue at hand.  We already
have the first-parent bisection.

The last optimization is all about how to reduce needless calls to
count_distance() by rejecting merge commits that can never be an
ancestor that a single-strand-of-pearls history from a non-merge
commit with the best "score" could reach.  And it is relevant only
if we want to improve performance of non-first-parent bisection.

Thanks.

Re: first bisection step takes quite a while

[Christian Couder]

On Fri, Feb 21, 2025 at 6:47 PM Junio C Hamano <gitster@pobox.com> wrote:
>
> Christian Couder <christian.couder@gmail.com> writes:
>
> > Yeah, it seems to me that in practice this is a bit like bisecting on
> > the first parents first. It would be nice if we had added an option to
> > bisect on the first parents first, so that we could compare your
> > improvement and that option.
>
> Unless you are talking about something entirely different, I am
> afraid you are confused.  We added first-parent bisection in mid
> 2020.

Yeah, I know that. But I don't think there is a mode which performs
first-parent bisection first and then continues bisecting normally (so
not only on the first parents). That's why I called it an option that
does "first parents first" and not just "first parent".

> And the first-parent bisection does make things easy, by making it
> totally unnecessary to call the "truly stupid" count_distance() at
> all.  We can pretend as if we have a single-strand-of-pearls, give
> the "good" end of the history "1" as its weight, its direct
> descendant (and there is only one direct descendant when we are
> doing first-parent bisection, since there always is only one active
> "bad" end of the range in our bisection session) "2" as its weight,
> and so on.  The commit that gets N/2 weight is the midway and we
> need O(N) computation.

Yeah, that's why a mode that does first parent bisection and then
continues to bisect normally would likely perform well. Because when
first-parent bisection is done, then hopefully the set of commits to
bisect has been reduced enough that further bisection is fast.

> Unfortunatly Uwe's original problem description was not about
> first-parent bisection being slow.
>
> >>  * The "this is good enough" logic currently allows us to be within
> >>    0.1% of the real halfway point.  Until the candidate set becomes
> >>    small enough, we could loosen the criteria to allow larger, say
> >>    3%, slack.  This code is written but not enabled (with "0 &&").
> >
> > If we want to do this, I think we could loosen the criteria even if
> > the candidate set is small. Weights are integers so when the number of
> > candidates is around 33 or less, a 3% criteria will mean an exact
> > match. Then the last 5 steps or so (as 2^5 = 32) would still be
> > performed in the same way (with an exact match).
>
> The above follows the same reasoning why we chose "division by 1024"
> in the first place.  The illustration patch postulates that we could
> be way more aggressive than 0.1% while the set is large by dividing
> 64, without wanting to loosen the criteria near the end of the
> bisection session when the remaining set is reasonably small like
> 1000 commits.  So we cannot rely on integer division truncating.

The code you posted above uses 10000 as the threshold, not 1000:

10000 < nr && abs(diff) < nr / 64) || abs(diff) < nr / 1024)

10000 is between 2^14 and 2^13. This means that the last 13 to 14
bisection steps likely don't benefit from the "way more aggressive"
criteria of 3% vs 0.1%. I know that the last steps are the fastest as
there are fewer commits to take into account, but still it seems to me
that we could make all the steps (except the last 5 or so because then
the criteria change likely doesn't change anything) benefit.

You say that we cannot rely on integer division truncation, but when
comparing integers, we could be careful enough so that there is no
difference between comparing them to a truncated number versus
comparing them to the same number not truncated. So I think we could
be able to rely on integer division.

So maybe just something like:

criteria = user_priority_is_bisect_speed ? 64 : 1024;
if (abs(diff) <= nr / criteria)
     return 1;

Thanks for working on this.

Re: first bisection step takes quite a while

[Christian Couder]

On Fri, Feb 21, 2025 at 9:24 PM Christian Couder
<christian.couder@gmail.com> wrote:
>
> On Fri, Feb 21, 2025 at 6:47 PM Junio C Hamano <gitster@pobox.com> wrote:

> > >>  * The "this is good enough" logic currently allows us to be within
> > >>    0.1% of the real halfway point.  Until the candidate set becomes
> > >>    small enough, we could loosen the criteria to allow larger, say
> > >>    3%, slack.  This code is written but not enabled (with "0 &&").
> >
> > The above follows the same reasoning why we chose "division by 1024"
> > in the first place.  The illustration patch postulates that we could
> > be way more aggressive than 0.1% while the set is large by dividing
> > 64, without wanting to loosen the criteria near the end of the
> > bisection session when the remaining set is reasonably small like
> > 1000 commits.  So we cannot rely on integer division truncating.
>
> The code you posted above uses 10000 as the threshold, not 1000:
>
> 10000 < nr && abs(diff) < nr / 64) || abs(diff) < nr / 1024)

Also if "division by 1024" means within 0.1% of the real halfway
point, then division by 64 means 0.1 * 1024 / 64 = 1.6 % not 3%.

Re: first bisection step takes quite a while

[Junio C Hamano]

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

> On Fri, Feb 21, 2025 at 9:24 PM Christian Couder
> <christian.couder@gmail.com> wrote:
>>
>> On Fri, Feb 21, 2025 at 6:47 PM Junio C Hamano <gitster@pobox.com> wrote:
>
>> > >>  * The "this is good enough" logic currently allows us to be within
>> > >>    0.1% of the real halfway point.  Until the candidate set becomes
>> > >>    small enough, we could loosen the criteria to allow larger, say
>> > >>    3%, slack.  This code is written but not enabled (with "0 &&").
>> >
>> > The above follows the same reasoning why we chose "division by 1024"
>> > in the first place.  The illustration patch postulates that we could
>> > be way more aggressive than 0.1% while the set is large by dividing
>> > 64, without wanting to loosen the criteria near the end of the
>> > bisection session when the remaining set is reasonably small like
>> > 1000 commits.  So we cannot rely on integer division truncating.
>>
>> The code you posted above uses 10000 as the threshold, not 1000:
>>
>> 10000 < nr && abs(diff) < nr / 64) || abs(diff) < nr / 1024)
>
> Also if "division by 1024" means within 0.1% of the real halfway
> point, then division by 64 means 0.1 * 1024 / 64 = 1.6 % not 3%.

Heh, I suck at arithmetic (but that is why I have you guys around
for correction ;-).

The current code makes sure that we do not punt with an inexact
result below nr for which nr/1024 is truncated away.  The overly
loose cutoff that uses nr/64 needs to stop kicking in way before
that happens to make sure we do not affect correctness with the
change to optimize, and that is the only reason why 10000 was
arbitrary chosen.  The threashold could have been set at 5000, or
100000.

Exact numbers do not matter as much as the real issue, i.e.,
limiting the possible damage to correctness from the change near the
end of a bisect session.

Thanks.

Re: first bisection step takes quite a while

[D. Ben Knoble]

On Fri, Feb 21, 2025 at 3:25 PM Christian Couder
<christian.couder@gmail.com> wrote:
>
> On Fri, Feb 21, 2025 at 6:47 PM Junio C Hamano <gitster@pobox.com> wrote:
> >
> > Christian Couder <christian.couder@gmail.com> writes:
> >
> > > Yeah, it seems to me that in practice this is a bit like bisecting on
> > > the first parents first. It would be nice if we had added an option to
> > > bisect on the first parents first, so that we could compare your
> > > improvement and that option.
> >
> > Unless you are talking about something entirely different, I am
> > afraid you are confused.  We added first-parent bisection in mid
> > 2020.
>
> Yeah, I know that. But I don't think there is a mode which performs
> first-parent bisection first and then continues bisecting normally (so
> not only on the first parents). That's why I called it an option that
> does "first parents first" and not just "first parent".

This was also how I read your original reply, and I think it would be
a nice addition. It automates something I've done a few times when
bisecting in large repos where the good reference is far away in terms
of commits, and where automated build+test (bisect run) can be slow.

Essentially
1. bisect with --first-parent to find a bad merge M
2. bisect between M^1 and M^@ (maybe this is the set M^-2, if I'm
reading "git help revisions" correctly?)

with the idea that (1) is fast but coarse (but also helps skip
unrelated, potentially bad commits in the merge parents) and (2) is
fine-grained but still fast because the set of commits is hopefully
small.

(Most readers know the previous justification, I expect, but I figured
I would spell it out.)

> Thanks for working on this.

Seconded!

-- 
D. Ben Knoble