Re: [PATCH 0/3] Make add_missing_tags() linear
- From
Junio C Hamano <gitster@pobox.com>
- Date
- Oct 31, 2018, 03:05 UTC
- Message-ID
- <xmqq7ehyzugy.fsf@gitster-ct.c.googlers.com>
- In-Reply-To
- <pull.60.git.gitgitgadget@gmail.com>
"Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:
Show 6 quoted lines
> Add a new method in commit-reach.c called get_reachable_subset() which does > a many-to-many reachability test. Starting at the 'from' commits, walk until > the generation is below the smallest generation in the 'to' commits, or all > 'to' commits have been discovered. This performs only one commit walk for > the entire add_missing_tags() method, giving linear performance in the worst > case.
;-)
I think in_merge_bases_many() was an attempt to do one half of this (i.e. it checks only one 'to' against main 'from' to see if any of them reach). I wonder why we didn't extend it to multiple 'to' back when we invented it.
In any case, good to see this code optimized.
Thanks.