Re: [PATCH v4 07/10] commit: use generation numbers for in_merge_bases()

[Jakub Narebski <jnareb@gmail.com>]

Derrick Stolee <dstolee@microsoft.com> writes:

> The containment algorithm for 'git branch --contains' is different
> from that for 'git tag --contains' in that it uses is_descendant_of()
> instead of contains_tag_algo(). The expensive portion of the branch
> algorithm is computing merge bases.
>
> When a commit-graph file exists with generation numbers computed,
> we can avoid this merge-base calculation when the target commit has
> a larger generation number than the initial commits.

Right.

>
> Performance tests were run on a copy of the Linux repository where
> HEAD is contained in v4.13 but no earlier tag. Also, all tags were
> copied to branches and 'git branch --contains' was tested:

I guess that it is equivalent of 'git tag --contains' setup from
previous commit, just for 'git branch --contains', isn't it?

>
> Before: 60.0s
> After:   0.4s
> Rel %: -99.3%

Very nice.

Sidenote: an alternative to using "Rel %" of -99.3% (which is calculated
as (before-after)/before) would be to use "Speedup" of 150 x (calculated
as before/after).  One one hand it might be more readable, on the other
hand it might be a bit misleading.

Yet another alternative would be to use a chart like the following:

           time  Before   After
  Before  60.0s      --  -99.3%
  After    0.4s   +149%      --

Anyway, consistency in presentation in patch series is good.  So I am
for keeping your notation thorough the series.

>
> Reported-by: Jeff King <peff@peff.net>
> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
> ---
>  commit.c | 9 ++++++++-
>  1 file changed, 8 insertions(+), 1 deletion(-)
>
> diff --git a/commit.c b/commit.c
> index 39a3749abd..7bb007f56a 100644
> --- a/commit.c
> +++ b/commit.c
> @@ -1056,12 +1056,19 @@ int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit *

Let's give it a bit more context:

   /*
    * Is "commit" an ancestor of one of the "references"?
    */
   int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit **reference)
>  {
>  	struct commit_list *bases;
>  	int ret = 0, i;
> +	uint32_t min_generation = GENERATION_NUMBER_INFINITY;
>  
>  	if (parse_commit(commit))
>  		return ret;
> -	for (i = 0; i < nr_reference; i++)
> +	for (i = 0; i < nr_reference; i++) {
>  		if (parse_commit(reference[i]))
>  			return ret;

We use parse_commit(), so there is no need for calling
load_commit_graph_info(), like in previous patch.

All right.

> +		if (min_generation > reference[i]->generation)

At first glance, I thought it was wrong; but it is the same as the
following, it is just a matter of taste (which feels more natural):

  +		if (reference[i]->generation < min_generation)

> +			min_generation = reference[i]->generation;
> +	}
> +
> +	if (commit->generation > min_generation)
> +		return ret;

All right, using weak version of generation numbers based negative-cut
nicely handles automatically all corner-cases, including the case where
commit-graaph feature is turned off.

If commit-graph feature is not available, it costs only few memory
access and few comparisons than before, and performance is dominated by
something else anyway.  Negligible and possibly unnoticeable change, I
guess.  Good.

>  
>  	bases = paint_down_to_common(commit, nr_reference, reference);
>  	if (commit->object.flags & PARENT2)