Re: [PATCH v5 09/11] commit: use generation number in remove_redundant()

From: Jakub Narebski <jnareb@gmail.com>
Date: May 3, 2018, 18:45 UTC
Message-ID: <867eokzigo.fsf@gmail.com>
In-Reply-To: <20180501124652.155781-10-dstolee@microsoft.com>

Derrick Stolee <dstolee@microsoft.com> writes:

Show 38 quoted lines

> 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>

Good description.

> ---
>  commit.c | 7 ++++++-
>  1 file changed, 6 insertions(+), 1 deletion(-)
>

Let me extend context a bit to make it easier to review.

Show 9 quoted lines

> 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;

Show 10 quoted lines

>  
>  		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.

Show 7 quoted lines

>  		}
> -		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