Derrick Stolee <dstolee@xxxxxxxxxxxxx> 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 <jnareb@xxxxxxxxx>
> Signed-off-by: Derrick Stolee <dstolee@xxxxxxxxxxxxx>
Good description.
> ---
> commit.c | 7 ++++++-
> 1 file changed, 6 insertions(+), 1 deletion(-)
>
Let me extend context a bit to make it easier to review.
> 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;
>
> 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
