From: Derrick Stolee <stolee@gmail.com>
Date: Tue, 01 May 2018 15:37:43 GMT
Subject: Re: [PATCH v5 09/11] commit: use generation number in remove_redundant()
Message-ID: <1cfe38f6-925b-d36b-53ae-6b586eed199c@gmail.com>
In-Reply-To: <20180501124652.155781-10-dstolee@microsoft.com>



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@gmail.com>
> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
> ---
>   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++)