On Mon, Feb 01, 2021 at 12:47:27PM +0000, Derrick Stolee via GitGitGadget wrote:
> From: Derrick Stolee <dstolee@xxxxxxxxxxxxx>
> 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@xxxxxxxxxxxxx>
> ---
> 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
