On 6/17/2020 4:46 PM, Junio C Hamano wrote: > "Derrick Stolee via GitGitGadget" <gitgitgadget@xxxxxxxxx> writes: > >> It was recently [1] reported (and not-so-recently [2] reported) that "git >> merge-base --is-ancestor" can be pretty slow. In fact, it is regularly >> slower than "git branch --contains" or "git tag --contains", which are >> answering a "harder" query. >> >> [1] https://lore.kernel.org/git/20200607195347.GA8232@xxxxxxxxxx/ >> >> [2] https://lore.kernel.org/git/87608bawoa.fsf@xxxxxxxxxxxxxxxxxxx/ >> >> The root cause is that the in_merge_base() implementation is skipping the >> fast can_all_from_reach() implementation and using paint_down_to_common() >> instead. Note that these are equivalent: a commit A is in the set of >> merge-bases between A and B if and only if B can reach A. > > OK, so in short, this codepath was not taking advantage of the > generation numbers and that was the difference? Correct. We now use generation numbers more often, when available. All callers of in_merge_bases() will become faster, which includes callers in these builtins: - branch - fetch - log - merge-base - receive-pack and these libgit files: - fast-import.c - http-push.c - merge-recursive.c (several!) - pack-bitmap-write.c Thanks, -Stolee
