Re: [PATCH v4 08/10] commit: add short-circuit to paint_down_to_common()

From: Jakub Narebski <jnareb@gmail.com>
Date: May 2, 2018, 13:05 UTC
Message-ID: <86a7ti1a4h.fsf@gmail.com>
In-Reply-To: <3e3ae7e4-9efd-3046-c0c2-7b3bf12d0d81@gmail.com>

Derrick Stolee <stolee@gmail.com> writes:

> On 4/30/2018 6:19 PM, Jakub Narebski wrote:
>> Derrick Stolee <dstolee@microsoft.com> writes:

[...]

Show 22 quoted lines

>>> @@ -831,6 +834,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;
>> Shouldn't we provide more information about where the problem is to the
>> user, to make it easier to debug the repository / commit-graph data?
>>
>> Good to have this sanity check here.
>
> This BUG() _should_ only be seen by developers who add callers which
> do not load commits from the commit-graph file. There is a chance that
> there are cases not covered by this patch and the added tests,
> though. Hopefully we catch them all by dogfooding the feature before
> turning it on by default.
>
> I can add the following to help debug these bad situations:
>
> +			BUG("bad generation skip %d > %d at %s",
> +			    commit->generation, last_gen,
> +			    oid_to_hex(&commit->object.oid));

On one hand, after thiking about this a bit, I agree that this BUG() is more about catching the errors in Git code, rather than in repository.

On the other hand, the more detailed information could help determining what the problems is (e.g. that "at <hex>" is at HEAD).

Hopefully we won't see which is which, as it would mean bugs in Git ;))

[...]

Show 22 quoted lines

>>> @@ -946,7 +956,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);
>>
>> Here we are interested not only if "one"/array[i] is reachable from
>> "twos"/work, but also if "twos" is reachable from "one".  Simple cutoff
>> only works in one way, though I wonder if we couldn't use cutoff being
>> minimum generation number of "one" and "twos" together.
>>
>> But that may be left for a separate commit (after checking that the
>> above is correct).
>>
>> Not as simple and obvious as paint_down_to_common() used in
>> in_merge_bases_any(), so it is all right.
>
> Thanks for reporting this. Since we are only concerned about
> reachability in this method, it is a good candidate to use
> min_generation. It is also subtle enough that we should leave it as a
> separate commit.

Thanks for checking this, and for the followup.

Show 26 quoted lines

>                  Also, we can measure performance improvements
> separately, as I will mention in my commit message (but I'll copy it
> here):
>
>     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.

Nice.

I was not expecting as much performance improvements as we got for --contains tests because remove_redundant() is a final step in longer process, dominated by man calculations. Still, nothing to sneeze about.

Best regards,

-- 
Jakub Narębski