Re: [PATCH 1/3] commit-reach: implement get_reachable_subset

From: Junio C Hamano <gitster@pobox.com>
Date: Nov 2, 2018, 01:51 UTC
Message-ID: <xmqqk1lws0vh.fsf@gitster-ct.c.googlers.com>
In-Reply-To: <15ef2018-4bb1-430f-32fd-5676a1b5ac1a@gmail.com>

Derrick Stolee <stolee@gmail.com> writes:

Show 18 quoted lines

> We could do this, but it does come with a performance hit when the following
> are all true:
>
> 1. 'to' is not reachable from any 'from' commits.
>
> 2. The 'to' and 'from' commits are close in commit-date.
>
> 3. Generation numbers are not available, or the topology is skewed to have
>    commits with high commit date and low generation number.
>
> Since in_merge_bases_many() calls paint_down_to_common(), it has the same
> issues with the current generation numbers. This can be fixed when we have
> the next version of generation numbers available.
>
> I'll make a note to have in_merge_bases_many() call get_reachable_subset()
> conditionally (like the generation_numbers_available() trick in the
> --topo-order
> series) after the generation numbers are settled and implemented.

Sounds good.

I wondered how this compares with in_merge_bases_many() primarily because how performance characteristics between two approaches trade off. After all, what it needs to compute is a specialized case of get_reachable_subset() where "to" happens to be a set with only single element. If the latter with a single element "to" has the above performance "issues" compared to paint-down-to-common based approach, it could be possible that, for small enough N>1, running N in_merge_bases_many() traversals is more performant than a single get_reachable_subset() call that works on N-element "to".

I am hoping that an update to better generation numbers to help get_reachable_subset() would help paint-down-to-common the same way, and would eventually allow us to use a single traversal that is best for N==1 and N>1.

Thanks.