git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 0/2] Accelerate "git merge-base --is-ancestor"

From
Junio C Hamano <gitster@pobox.com>
Date
Jun 17, 2020, 20:46 UTC
Message-ID
<xmqqzh91s9mn.fsf@gitster.c.googlers.com>
In-Reply-To
<pull.664.git.1592414670.gitgitgadget@gmail.com>
"Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:
Show 13 quoted lines
> 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@szeder.dev/
>
> [2] https://lore.kernel.org/git/87608bawoa.fsf@evledraar.gmail.com/
>
> 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?

Previous: Derrick Stolee via GitGitGadgetNext: Derrick Stolee
Message 6 of 8 in “Accelerate "git merge-base --is-ancestor"”
  1. 0/2 Accelerate "git merge-base --is-ancestor"Derrick Stolee via GitGitGadget, Jun 17, 2020
  2. 1/2 commit-reach: create repo_is_descendant_of()Derrick Stolee via GitGitGadget, Jun 17, 2020
  3. Taylor BlauJun 29, 2020
  4. Derrick StoleeJun 30, 2020
  5. 2/2 commit-reach: use fast logic in repo_in_merge_baseDerrick Stolee via GitGitGadget, Jun 17, 2020
  6. Junio C HamanoJun 17, 2020
  7. Derrick StoleeJun 18, 2020
  8. Abhishek KumarJun 19, 2020

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.