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

Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted

From
Kristofer Karlsson <krka@spotify.com>
Date
Jun 14, 2026, 11:47 UTC
Message-ID
<CAL71e4Ps-2_0+uuZu43N9pFnXBemoAohPs_eyRJf8taXHJPAXQ@mail.gmail.com>
In-Reply-To
<CABPp-BGq8a-3ocJ+1HCgJutw1SBUvFg6YxtUamryfgEMx3qDYQ@mail.gmail.com>
On Sun, 14 Jun 2026 at 06:32, Elijah Newren <newren@gmail.com> wrote:
Show 6 quoted lines
> Wow...it appears this optimization was discovered by 3 separate
> people in the last month. This optimization was implemented and
> is live at GitHub...but it feels incomplete to me because my
> version doesn't handle both sides having an infinite generation
> number (it just falls back to the old algorithm when that
> happens).

It is nice to know that multiple people converged on the same idea independently -- that gives me a lot of confidence that we are exploiting a real and useful property of the graph/walk structure.

> I uploaded my version at
> https://github.com/gitgitgadget/git/pull/2150.

I uploaded mine at https://github.com/gitgitgadget/git/pull/2149 (draft, still iterating on the series).

I realize this is getting into implementation details before the idea itself has been discussed on the list. I am happy to wait with a formal patch submission until there is more consensus on the approach -- but since you shared your implementation, I wanted to compare notes while it is fresh.

I integrated your new t6600 test cases into my branch -- thanks! They exercise important edge cases that my original tests missed. I also extended the perf test to cover the case where both tips are outside the commit-graph.

After looking at your implementation, I also moved from a max-pointer scheme to per-side counters. We ended up with slightly different implementations, but they are tracking the same underlying condition: whether either paint side still has non-stale exclusive commits remaining.

The main behavioral difference is handling of commits outside the commit-graph. Your version disables the optimization once both sides have touched such commits, while mine only enables the break after the walk reaches the finite-generation region. This still allows the optimization to fire when both tips start outside the graph, as soon as the walk crosses into commits covered by the commit-graph.

> Do you want to take this over, rebase it, and extend to the
> infinite generation number case? Or do you want me to rebase
> and see it through after my vacation? Or some other mixture?

I am happy to keep working on this -- starting from either your branch or mine, or some hybrid. I do not have a strong preference for which version it would be based on, but if either of them lands I would be happy. Enjoy your vacation!

Thanks, Kristofer

Previous: Elijah Newren
Message 10 of 10 in “[RFC] commit-reach: terminate merge-base walk when one paint side is exhausted”
  1. Kristofer KarlssonJun 12, 2026
  2. Derrick StoleeJun 12, 2026
  3. Kristofer KarlssonJun 12, 2026
  4. Derrick StoleeJun 12, 2026
  5. Kristofer KarlssonJun 12, 2026
  6. Derrick StoleeJun 12, 2026
  7. Kristofer KarlssonJun 13, 2026
  8. Kristofer KarlssonJun 13, 2026
  9. Elijah NewrenJun 14, 2026
  10. Kristofer KarlssonJun 14, 2026

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.