git@vger.kernel.org list mirror (unofficial, one of many)
 help / color / mirror / code / Atom feed
From: Derrick Stolee <stolee@gmail.com>
To: git@vger.kernel.org
Cc: git@jeffhostetler.com, stolee@gmail.com, gitster@pobox.com,
	Derrick Stolee <dstolee@microsoft.com>
Subject: [RFC PATCH 6/6] commit-reach: fix first-parent heuristic
Date: Thu,  6 Sep 2018 15:13:09 +0000	[thread overview]
Message-ID: <20180906151309.66712-7-dstolee@microsoft.com> (raw)
In-Reply-To: <20180906151309.66712-1-dstolee@microsoft.com>

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 can see in t6600-test-reach.sh that we
reduce the number of walked commits. This test will prevent a future
performance regression.

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 <dstolee@microsoft.com>
---
 commit-reach.c        | 4 +++-
 t/t6600-test-reach.sh | 2 +-
 2 files changed, 4 insertions(+), 2 deletions(-)

diff --git a/commit-reach.c b/commit-reach.c
index 0a75644653..bd009260b0 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -588,8 +588,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;
 			}
 
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index 98ad25bb45..5e231a5955 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -185,7 +185,7 @@ test_expect_success 'can_all_from_reach:hit' '
 
 test_expect_success 'can_all_from_reach:perf' '
 	cp commit-graph-full .git/objects/info/commit-graph &&
-	run_and_check_trace2 can_all_from_reach_with_flag num_walked 40 input \
+	run_and_check_trace2 can_all_from_reach_with_flag num_walked 19 input \
 		"test-tool reach can_all_from_reach"
 '
 
-- 
2.19.0.rc2


  parent reply	other threads:[~2018-09-06 15:14 UTC|newest]

Thread overview: 26+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-08-31 16:49 [PATCH 0/8] WIP: trace2: a new trace facility Jeff Hostetler via GitGitGadget
2018-08-31 16:49 ` [PATCH 1/8] trace2: create new combined " Jeff Hostetler via GitGitGadget
2018-08-31 17:19   ` Derrick Stolee
2018-09-04 22:12   ` Stefan Beller
2018-09-04 22:30     ` Junio C Hamano
2018-09-05 15:51       ` Jeff Hostetler
2018-09-05 15:01     ` Jeff Hostetler
2018-08-31 16:49 ` [PATCH 2/8] trace2: add trace2 to main Jeff Hostetler via GitGitGadget
2018-08-31 16:49 ` [PATCH 3/8] trace2: demonstrate trace2 regions in wt-status Jeff Hostetler via GitGitGadget
2018-08-31 16:49 ` [PATCH 4/8] trace2: demonstrate trace2 child process classification Jeff Hostetler via GitGitGadget
2018-08-31 16:50 ` [PATCH 5/8] trace2: demonstrate instrumenting do_read_index Jeff Hostetler via GitGitGadget
2018-08-31 16:50 ` [PATCH 6/8] trace2: demonstrate instrumenting threaded preload_index Jeff Hostetler via GitGitGadget
2018-08-31 16:50 ` [PATCH 7/8] trace2: demonstrate setting sub-command parameter in checkout Jeff Hostetler via GitGitGadget
2018-08-31 16:50 ` [PATCH 8/8] trace2: demonstrate use of regions in read_directory_recursive Jeff Hostetler via GitGitGadget
2018-08-31 17:19 ` [PATCH 0/8] WIP: trace2: a new trace facility Derrick Stolee
2018-09-06 15:13   ` [RFC PATCH 0/6] Use trace2 in commit-reach Derrick Stolee
2018-09-06 15:13     ` [RFC PATCH 1/6] commit-reach: add trace2 telemetry and walk count Derrick Stolee
2018-09-06 15:13     ` [RFC PATCH 2/6] comit-reach: use trace2 for commit_contains_tag_algo Derrick Stolee
2018-09-06 15:13     ` [RFC PATCH 3/6] commit-reach: use trace2 in can_all_from_reach Derrick Stolee
2018-09-06 15:13     ` [RFC PATCH 4/6] test-tool: start trace2 environment Derrick Stolee
2018-09-06 15:13     ` [RFC PATCH 5/6] test-lib: add run_and_check_trace2 Derrick Stolee
2018-09-06 15:13     ` Derrick Stolee [this message]
2018-10-11  1:50       ` [RFC PATCH 6/6] commit-reach: fix first-parent heuristic Jonathan Nieder
2018-10-11 11:00         ` Derrick Stolee
2019-01-15  1:05 ` [PATCH 0/8] WIP: trace2: a new trace facility Jonathan Nieder
2019-01-15 17:03   ` Jeff Hostetler

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20180906151309.66712-7-dstolee@microsoft.com \
    --to=stolee@gmail.com \
    --cc=dstolee@microsoft.com \
    --cc=git@jeffhostetler.com \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --subject='Re: [RFC PATCH 6/6] commit-reach: fix first-parent heuristic' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Code repositories for project(s) associated with this inbox:

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).