# 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 > --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.

**References**:**[PATCH 0/3] Make add_missing_tags() linear***From:*Derrick Stolee via GitGitGadget

**[PATCH 1/3] commit-reach: implement get_reachable_subset***From:*Derrick Stolee via GitGitGadget

**Re: [PATCH 1/3] commit-reach: implement get_reachable_subset***From:*Junio C Hamano

**Re: [PATCH 1/3] commit-reach: implement get_reachable_subset***From:*Derrick Stolee

- Prev by Date:
**git appears to ignore GIT_CONFIG environment variable** - Next by Date:
**Re: [PATCH] send-email: Avoid empty transfer encoding header** - Previous by thread:
**Re: [PATCH 1/3] commit-reach: implement get_reachable_subset** - Next by thread:
**Re: [PATCH 1/3] commit-reach: implement get_reachable_subset** - Index(es):