Re: [PATCH v3 7/9] commit: add short-circuit to paint_down_to_common()

[Jakub Narebski <jnareb@gmail.com>]

Derrick Stolee <dstolee@microsoft.com> writes:

> When running 'git branch --contains', the in_merge_bases_many()
> method calls paint_down_to_common() to discover if a specific
> commit is reachable from a set of branches. Commits with lower
> generation number are not needed to correctly answer the
> containment query of in_merge_bases_many().

Right. This description is not entirely clear to me, but I don't have a
better proposal. Good enough, I guess.

>
> Add a new parameter, min_generation, to paint_down_to_common() that
> prevents walking commits with generation number strictly less than
> min_generation. If 0 is given, then there is no functional change.

Is it new parameter really needed, i.e. do you really need to change the
signature of this function?  See below for details.

>
> For in_merge_bases_many(), we can pass commit->generation as the
> cutoff,...

This is the only callsite that uses min_generation with non-zero value,
and it uses commit->generation to fill it... while commit itself is one
of exiting parameters.

> [...], and this saves time during 'git branch --contains' queries
> that would otherwise walk "around" the commit we are inspecting.

If I understand the code properly, what happens is that we can now
short-circuit if all commits that are left are lower than the target
commit.

This is because max-order priority queue is used: if the commit with
maximum generation number is below generation number of target commit,
then target commit is not reachable from any commit in the priority
queue (all of which has generation number less or equal than the commit
at head of queue, i.e. all are same level or deeper); compare what I
have written in [1]

[1]: https://public-inbox.org/git/866052dkju.fsf@gmail.com/

Do I have that right?  If so, it looks all right to me.

>
> For a copy of the Linux repository, where HEAD is checked out at
> v4.13~100, we get the following performance improvement for
> 'git branch --contains' over the previous commit:
>
> Before: 0.21s
> After:  0.13s
> Rel %: -38%

Nice.

>
> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
> ---
>  commit.c | 18 ++++++++++++++----
>  1 file changed, 14 insertions(+), 4 deletions(-)
>
> diff --git a/commit.c b/commit.c
> index bceb79c419..a70f120878 100644
> --- a/commit.c
> +++ b/commit.c
> @@ -805,11 +805,14 @@ static int queue_has_nonstale(struct prio_queue *queue)
>  }
>  
>  /* all input commits in one and twos[] must have been parsed! */
> -static struct commit_list *paint_down_to_common(struct commit *one, int n, struct commit **twos)
> +static struct commit_list *paint_down_to_common(struct commit *one, int n,
> +						struct commit **twos,
> +						int min_generation)
>  {
>  	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
>  	struct commit_list *result = NULL;
>  	int i;
> +	uint32_t last_gen = GENERATION_NUMBER_INFINITY;

Do we really need to change the signature of paint_down_to_common(), or
would it be enough to create a local variable min_generation set
initially to one->generation.

 +      uint32_t min_generation = one->generation;
 +	uint32_t last_gen = GENERATION_NUMBER_INFINITY;

>  
>  	one->object.flags |= PARENT1;
>  	if (!n) {
> @@ -828,6 +831,13 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n, struc
>  		struct commit_list *parents;
>  		int flags;
>  
> +		if (commit->generation > last_gen)
> +			BUG("bad generation skip");
> +		last_gen = commit->generation;
> +
> +		if (commit->generation < min_generation)
> +			break;
> +

I think, after looking at the whole post-image code, that it is all
right.

>  		flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
>  		if (flags == (PARENT1 | PARENT2)) {
>  			if (!(commit->object.flags & RESULT)) {
> @@ -876,7 +886,7 @@ static struct commit_list *merge_bases_many(struct commit *one, int n, struct co
>  			return NULL;
>  	}
>  
> -	list = paint_down_to_common(one, n, twos);
> +	list = paint_down_to_common(one, n, twos, 0);
>  
>  	while (list) {
>  		struct commit *commit = pop_commit(&list);
> @@ -943,7 +953,7 @@ static int remove_redundant(struct commit **array, int cnt)
>  			filled_index[filled] = j;
>  			work[filled++] = array[j];
>  		}
> -		common = paint_down_to_common(array[i], filled, work);
> +		common = paint_down_to_common(array[i], filled, work, 0);
>  		if (array[i]->object.flags & PARENT2)
>  			redundant[i] = 1;
>  		for (j = 0; j < filled; j++)
> @@ -1067,7 +1077,7 @@ int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit *
>  	if (commit->generation > min_generation)
>  		return 0;
>  
> -	bases = paint_down_to_common(commit, nr_reference, reference);
> +	bases = paint_down_to_common(commit, nr_reference, reference, commit->generation);

Is it the only case where we would call paint_down_to_common() with
non-zero last parameter?  Would we always use commit->generation where
commit is the first parameter of paint_down_to_common()?

If both are true and will remain true, then in my humble opinion it is
not necessary to change the signature of this function.

>  	if (commit->object.flags & PARENT2)
>  		ret = 1;
>  	clear_commit_marks(commit, all_flags);