Re: [PATCH v5 09/11] commit: use generation number in remove_redundant()
From: Jakub Narebski <hidden>
Date: 2018-05-03 18:45:37
Derrick Stolee [off-list ref] writes:
The static remove_redundant() method is used to filter a list of commits by removing those that are reachable from another commit in the list. This is used to remove all possible merge- bases except a maximal, mutually independent set. To determine these commits are independent, we use a number of paint_down_to_common() walks and use the PARENT1, PARENT2 flags to determine reachability. Since we only care about reachability and not the full set of merge-bases between 'one' and 'twos', we can use the 'min_generation' parameter to short-circuit the walk. When no commit-graph exists, there is no change in behavior. For a copy of the Linux repository, we measured the following performance improvements: git merge-base v3.3 v4.5 Before: 234 ms After: 208 ms Rel %: -11% git merge-base v4.3 v4.5 Before: 102 ms After: 83 ms Rel %: -19% The experiments above were chosen to demonstrate that we are improving the filtering of the merge-base set. In the first example, more time is spent walking the history to find the set of merge bases before the remove_redundant() call. The starting commits are closer together in the second example, therefore more time is spent in remove_redundant(). The relative change in performance differs as expected. Reported-by: Jakub Narebski <redacted> Signed-off-by: Derrick Stolee <redacted>
Good description.
--- commit.c | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-)
Let me extend context a bit to make it easier to review.
quoted hunk
diff --git a/commit.c b/commit.c index 9875feec01..5064db4e61 100644 --- a/commit.c +++ b/commit.c@@ -949,6 +949,7 @@ static int remove_redundant(struct commit **array, int cnt) parse_commit(array[i]); for (i = 0; i < cnt; i++) { struct commit_list *common; + uint32_t min_generation = GENERATION_NUMBER_INFINITY;
As you have noticed, and how it is already fixed in 'pu' it should be + uint32_t min_generation = array[i]->generation;
quoted hunk
if (redundant[i]) continue;@@ -957,8 +958,12 @@ static int remove_redundant(struct commit **array, int cnt) continue; filled_index[filled] = j; work[filled++] = array[j]; + + if (array[j]->generation < min_generation) + min_generation = array[j]->generation;
remove_redundant() checks if i-th commit is reachable from commits i+1..cnt, and vice versa - via checking PARENT1 and PARENT2 flag, respectively. As you have noticed this means that the min_generation cutoff should be minimum of array[i]->generation, and all of array[j]->generation for j=i+1..cnt. There is no reason going further down if we are interested only in reachability, and not actually in merge bases.
} - common = paint_down_to_common(array[i], filled, work, 0); + common = paint_down_to_common(array[i], filled, work, + min_generation); if (array[i]->object.flags & PARENT2) redundant[i] = 1; for (j = 0; j < filled; j++)
if (work[j]->object.flags & PARENT1) redundant[filled_index[j]] = 1; Beside this issue, nice and simple speedup. Good. Best, -- Jakub Narębski