Re: [RFC PATCH 6/6] commit-reach: fix first-parent heuristic
On 10/10/2018 9:50 PM, Jonathan Nieder wrote: Hi, Derrick Stolee wrote: commit-reach.c| 4 +++- t/t6600-test-reach.sh | 2 +- 2 files changed, 4 insertions(+), 2 deletions(-) I like this testing technique, and the test passes for me. Except: if I put CC = cc -m32 NO_OPENSSL = YesPlease NO_CURL = YesPlease in config.mak (the first line to force 32-bit pointers, the others to avoid some dependencies on libs that I don't have 32-bit versions of), then the test fails for me: $ ./t6600-test-reach.sh -v -x -i [...] expecting success: cp commit-graph-full .git/objects/info/commit-graph && run_and_check_trace2 can_all_from_reach_with_flag num_walked 19 input \ "test-tool reach can_all_from_reach" ++ cp commit-graph-full .git/objects/info/commit-graph ++ run_and_check_trace2 can_all_from_reach_with_flag num_walked 19 input 'test-tool reach can_all_from_r each' ++ CATEGORY=can_all_from_reach_with_flag ++ KEY=num_walked ++ VALUE=19 ++ INPUT=input ++ COMMAND='test-tool reach can_all_from_reach' +++ pwd ++ GIT_TR2_PERFORMANCE='/usr/local/google/home/jrn/src/git/t/trash directory.t6600-test-reach/perf-log.t xt' ++ test-tool reach can_all_from_reach can_all_from_reach(X,Y):1 ++ cat perf-log.txt ++ grep 'category:can_all_from_reach_with_flag key:num_walked value:19' error: last command exited with $?=1 not ok 11 - 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 19 input \ # "test-tool reach can_all_from_reach" # When I cat perf-log.txt, I see ..category:can_all_from_reach_with_flag key:num_walked value:20 instead of the expected 19. It is possible this is related to the sort-order problem reported and fixed by Rene [1]. I'll look into it in any case. [1] https://public-inbox.org/git/dca35e44-a763-bcf0-f457-b8dab5381...@web.de/
Re: [RFC PATCH 6/6] commit-reach: fix first-parent heuristic
Hi, Derrick Stolee wrote: > commit-reach.c| 4 +++- > t/t6600-test-reach.sh | 2 +- > 2 files changed, 4 insertions(+), 2 deletions(-) I like this testing technique, and the test passes for me. Except: if I put CC = cc -m32 NO_OPENSSL = YesPlease NO_CURL = YesPlease in config.mak (the first line to force 32-bit pointers, the others to avoid some dependencies on libs that I don't have 32-bit versions of), then the test fails for me: $ ./t6600-test-reach.sh -v -x -i [...] expecting success: cp commit-graph-full .git/objects/info/commit-graph && run_and_check_trace2 can_all_from_reach_with_flag num_walked 19 input \ "test-tool reach can_all_from_reach" ++ cp commit-graph-full .git/objects/info/commit-graph ++ run_and_check_trace2 can_all_from_reach_with_flag num_walked 19 input 'test-tool reach can_all_from_r each' ++ CATEGORY=can_all_from_reach_with_flag ++ KEY=num_walked ++ VALUE=19 ++ INPUT=input ++ COMMAND='test-tool reach can_all_from_reach' +++ pwd ++ GIT_TR2_PERFORMANCE='/usr/local/google/home/jrn/src/git/t/trash directory.t6600-test-reach/perf-log.t xt' ++ test-tool reach can_all_from_reach can_all_from_reach(X,Y):1 ++ cat perf-log.txt ++ grep 'category:can_all_from_reach_with_flag key:num_walked value:19' error: last command exited with $?=1 not ok 11 - 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 19 input \ # "test-tool reach can_all_from_reach" # When I cat perf-log.txt, I see ..category:can_all_from_reach_with_flag key:num_walked value:20 instead of the expected 19. Known issue? Thanks, Jonathan
[RFC PATCH 6/6] commit-reach: fix first-parent heuristic
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
---
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();
+ 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
