Re: [PATCH 1/3] commit-reach: implement get_reachable_subset
- Date: Fri, 02 Nov 2018 10:51:14 +0900
- From: Junio C Hamano <gitster@xxxxxxxxx>
- Subject: Re: [PATCH 1/3] commit-reach: implement get_reachable_subset
Derrick Stolee <stolee@xxxxxxxxx> writes:
> 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
> series) after the generation numbers are settled and implemented.
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.