Re: [PATCH v2 5/5] commit-reach: stale commits may prune generation further

[Taylor Blau <me@ttaylorr.com>]

On Mon, Feb 01, 2021 at 12:47:27PM +0000, Derrick Stolee via GitGitGadget wrote:
> From: Derrick Stolee <dstolee@microsoft.com>
> Note that these are only modest improvements for the case where the two
> independent commits are not in the commit-graph (not until v5.10). All
> algorithms get faster as more commits are indexed, which is not a
> surprise. However, the cost of walking extra commits is more and more
> prevalent in relative terms as more commits are indexed. Finally, the
> last case allows us to jump to the minimum generation between the last
> two commits (that are actually independent) so we greatly reduce the
> cost in that case.

Very nice. The explanation and implementation makes sense to me.

> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
> ---
>  commit-reach.c | 28 +++++++++++++++++++++-------
>  1 file changed, 21 insertions(+), 7 deletions(-)
>
> diff --git a/commit-reach.c b/commit-reach.c
> index d3a6e2bdd04..c2e0747fea4 100644
> --- a/commit-reach.c
> +++ b/commit-reach.c
> @@ -237,15 +237,27 @@ static int remove_redundant_with_gen(struct repository *r,
>  {
>  	int i, count_non_stale = 0, count_still_independent = cnt;
>  	timestamp_t min_generation = GENERATION_NUMBER_INFINITY;
> -	struct commit **walk_start;
> +	struct commit **walk_start, **sorted;
>  	size_t walk_start_nr = 0, walk_start_alloc = cnt;
> +	int min_gen_pos = 0;
> +
> +	/*
> +	 * Sort the input by generation number, ascending. This allows
> +	 * us to increase the "min_generation" limit when we discover
> +	 * the commit with lowest generation is STALE. The index
> +	 * min_gen_pos points to the current position within 'array'
> +	 * that is not yet known to be STALE.
> +	 */
> +	ALLOC_ARRAY(sorted, cnt);
> +	COPY_ARRAY(sorted, array, cnt);
> +	QSORT(sorted, cnt, compare_commits_by_gen);
> +	min_generation = commit_graph_generation(sorted[0]);

This line caught my eye, but we return early in
commit-reach.c:reduce_heads() before even calling remove_redundant()
(which itself calls remove_redundant_with_gen()), so it's always OK to
assume that we have at least one element in 'array'.

This patch and the others in v2 all look good to me.

Thanks,
Taylor