commit: use generation number in remove_redundant()

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 <jnareb@gmail.com>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/commit.c b/commit.c
index 9875feec01e31d3cca01caedb5ddcf8a9c7aaef8..1d28677dfb701824f1afb4c51e673d57606c2d4e 100644 (file)
--- 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 = array[i]->generation;
 
                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;
                }
-               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++)