Re: [RFC PATCH 13/13] commit-reach: use can_all_from_reach

[Stefan Beller <sbeller@google.com>]

Hi Derrick,
On Fri, Jun 29, 2018 at 9:13 AM Derrick Stolee <dstolee@microsoft.com> wrote:
>
> The is_descendant_of method previously used in_merge_bases() to check if
> the commit can reach any of the commits in the provided list. This had
> two performance problems:
>
> 1. The performance is quadratic in worst-case.
>
> 2. A single in_merge_bases() call requires walking beyond the target
>    commit in order to find the full set of boundary commits that may be
>    merge-bases.
>
> The can_all_from_reach method avoids this quadratic behavior and can
> limit the search beyond the target commits using generation numbers. It
> requires a small prototype adjustment to stop using commit-date as a
> cutoff, as that optimization is no longer appropriate here.
>
> Performance was meausured on a copy of the Linux repository using the
> 'test-tool reach is_descendant_of' command using this input:
>
> A:v4.9
> X:v4.10
> X:v4.11
> X:v4.12
> X:v4.13
> X:v4.14
> X:v4.15
> X:v4.16
> X:v4.17
> X.v3.0
>
> Note that this input is tailored to demonstrate the quadratic nature of
> the previous method, as it will compute merge-bases for v4.9 versus all
> of the later versions before checking against v4.1.
>
> Before: 0.31 s
>  After: 0.27 s
>
> Since we previously used the is_descendant_of method in the ref_newer
> method, we also measured performance there using
> 'test-tool reach ref_newer':
>
> Before: 0.12 s
>  After: 0.11 s
>
> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
> ---
>
> One thing I know is missing from this commit is a special-case to use
> the old logic when there is no commit-graph present. The
> can_all_from_reach() algorithm can be worse when we do not have good
> generation number cutoffs. In the previous case of
> can_all_from_reach_with_flags(), we already had an established pattern
> of using commit date as a cutoff, so the generation number is only a
> second cutoff and the algorithm cannot walk more commits than before.

I like this series,
Thanks for writing it!
Stefan