[1/1] commit-reach: fix first-parent heuristic

Commit Message

Linus Arver via GitGitGadget Oct. 18, 2018, 5:24 p.m. UTC

From: Derrick Stolee <[e-mail]>

The algorithm in can_all_from_reach_with_flags() performs a depth-
first-search, terminated by generation number, intending to use
a hueristic that "important" commits are found in the first-parent
history. This heuristic is valuable in scenarios like fetch
negotiation.

However, there is a problem! After the search finds a target commit,
it should pop all commits off the stack and mark them as "can reach".
This logic is incorrect, so the algorithm instead walks all reachable
commits above the generation-number cutoff.

The existing algorithm is still an improvement over the previous
algorithm, as the worst-case complexity went from quadratic to linear.
The performance measurement at the time was good, but not dramatic.
By fixing this heuristic, we reduce the number of walked commits.

We can also re-run the performance tests from commit 4fbcca4e
"commit-reach: make can_all_from_reach... linear".

Performance was measured on the Linux repository using
'test-tool reach can_all_from_reach'. The input included rows seeded by
tag values. The "small" case included X-rows as v4.[0-9]* and Y-rows as
v3.[0-9]*. This mimics a (very large) fetch that says "I have all major
v3 releases and want all major v4 releases." The "large" case included
X-rows as "v4.*" and Y-rows as "v3.*". This adds all release-candidate
tags to the set, which does not greatly increase the number of objects
that are considered, but does increase the number of 'from' commits,
demonstrating the quadratic nature of the previous code.

Small Case:

4fbcca4e~1: 0.85 s
  4fbcca4e: 0.26 s (num_walked: 1,011,035)
      HEAD: 0.14 s (num_walked:     8,601)

Large Case:

4fbcca4e~1: 24.0  s
  4fbcca4e:  0.12 s (num_walked:  503,925)
      HEAD:  0.06 s (num_walked:  217,243)

Signed-off-by: Derrick Stolee <[e-mail]>
---
 commit-reach.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

Comments

Junio C Hamano Oct. 19, 2018, 5:24 a.m. UTC | #1

"Derrick Stolee via GitGitGadget" <[e-mail]> writes:

> We can also re-run the performance tests from commit 4fbcca4e
> "commit-reach: make can_all_from_reach... linear".
>
> Performance was measured on the Linux repository using
> 'test-tool reach can_all_from_reach'. The input included rows seeded by
> tag values. The "small" case included X-rows as v4.[0-9]* and Y-rows as
> v3.[0-9]*. This mimics a (very large) fetch that says "I have all major
> v3 releases and want all major v4 releases." The "large" case included
> X-rows as "v4.*" and Y-rows as "v3.*". This adds all release-candidate
> tags to the set, which does not greatly increase the number of objects
> that are considered, but does increase the number of 'from' commits,
> demonstrating the quadratic nature of the previous code.

These micro-benchmarks are interesting, but we should also remember
to describe the impact of the bug being fixed in the larger picture.
What end-user visible operations are affected?  Computing merge-base?
Finding if a push fast-forwards?  Something else?

Derrick Stolee Oct. 19, 2018, 12:32 p.m. UTC | #2

On 10/19/2018 1:24 AM, Junio C Hamano wrote:
> "Derrick Stolee via GitGitGadget" <[e-mail]> writes:
>
>> We can also re-run the performance tests from commit 4fbcca4e
>> "commit-reach: make can_all_from_reach... linear".
>>
>> Performance was measured on the Linux repository using
>> 'test-tool reach can_all_from_reach'. The input included rows seeded by
>> tag values. The "small" case included X-rows as v4.[0-9]* and Y-rows as
>> v3.[0-9]*. This mimics a (very large) fetch that says "I have all major
>> v3 releases and want all major v4 releases." The "large" case included
>> X-rows as "v4.*" and Y-rows as "v3.*". This adds all release-candidate
>> tags to the set, which does not greatly increase the number of objects
>> that are considered, but does increase the number of 'from' commits,
>> demonstrating the quadratic nature of the previous code.
> These micro-benchmarks are interesting, but we should also remember
> to describe the impact of the bug being fixed in the larger picture.
> What end-user visible operations are affected?  Computing merge-base?
> Finding if a push fast-forwards?  Something else?

Sorry about that. Here is a description that could be inserted into the 
commit message:

The can_all_from_reach() method synthesizes the logic for one iteration 
of can_all_from_reach_with_flags() which is used by the server during 
fetch negotiation to determine if more haves/wants are needed. The logic 
is also used by is_descendant_of() which is used to check if a 
force-push is required and in 'git branch --contains'.

Thanks,
-Stolee

Junio C Hamano Oct. 22, 2018, 2:29 a.m. UTC | #3

Derrick Stolee <[e-mail]> writes:

> On 10/19/2018 1:24 AM, Junio C Hamano wrote:
>> "Derrick Stolee via GitGitGadget" <[e-mail]> writes:
>>
>>> We can also re-run the performance tests from commit 4fbcca4e
>>> "commit-reach: make can_all_from_reach... linear".
>>>
>>> Performance was measured on the Linux repository using
>>> 'test-tool reach can_all_from_reach'. The input included rows seeded by
>>> tag values. The "small" case included X-rows as v4.[0-9]* and Y-rows as
>>> v3.[0-9]*. This mimics a (very large) fetch that says "I have all major
>>> v3 releases and want all major v4 releases." The "large" case included
>>> X-rows as "v4.*" and Y-rows as "v3.*". This adds all release-candidate
>>> tags to the set, which does not greatly increase the number of objects
>>> that are considered, but does increase the number of 'from' commits,
>>> demonstrating the quadratic nature of the previous code.
>> These micro-benchmarks are interesting, but we should also remember
>> to describe the impact of the bug being fixed in the larger picture.
>> What end-user visible operations are affected?  Computing merge-base?
>> Finding if a push fast-forwards?  Something else?
>
> Sorry about that. Here is a description that could be inserted into
> the commit message:
>
> The can_all_from_reach() method synthesizes the logic for one
> iteration of can_all_from_reach_with_flags() which is used by the
> server during fetch negotiation to determine if more haves/wants are
> needed. The logic is also used by is_descendant_of() which is used to
> check if a force-push is required and in 'git branch --contains'.

I am afraid that it is still not end-user serving enough.  The level
of "larger picture" I had in mind was those that would appear as an
entry in the release notes, e.g. (this is for illustration purposes
only; I do not claim its actual contents is correct).

	We started using commit generation numbers in various
	reachability computations, but due to a bug, negitiation
	between the "git fetch" and the server started to require
	30% more roundtrips than necessary, and it has become less
	efficient to see if a commit is a descendant of another
	commit in certain cases, which has been corrected in this
	release.

Thanks.

Patch

diff --git a/commit-reach.c b/commit-reach.c
index 9f79ce0a22..79419be8af 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -593,8 +593,10 @@  int can_all_from_reach_with_flag(struct object_array *from,
 		while (stack) {
 			struct commit_list *parent;
 
-			if (stack->item->object.flags & with_flag) {
+			if (stack->item->object.flags & (with_flag | RESULT)) {
 				pop_commit(&stack);
+				if (stack)
+					stack->item->object.flags |= RESULT;
 				continue;
 			}