On 5/1/2018 8:47 AM, Derrick Stolee wrote:
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@xxxxxxxxx>
Signed-off-by: Derrick Stolee <dstolee@xxxxxxxxxxxxx>
---
commit.c | 7 ++++++-
1 file changed, 6 insertions(+), 1 deletion(-)
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;
This initialization should be
uint32_t min_generation = array[i]->generation;
since the assignment (using j) below skips the ith commit.
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++)
