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

Re: [PATCH] commit-reach: remove get_reachable_subset()

From
Kristofer Karlsson <krka@spotify.com>
Date
Jun 10, 2026, 18:25 UTC
Message-ID
<CAL71e4NqCD0P_=qnT2R9ThNHEQx6qo27i_7Wj3Xnb9Xg0kcM2A@mail.gmail.com>
In-Reply-To
<xmqqbjdixupc.fsf@gitster.g>
Junio C Hamano <gitster@pobox.com> writes:
Show 5 quoted lines
> "should not matter in practice" because...?
>
> And of course the worst case scenario is by definition not a typical
> case that appear in practice, so it does not make a good explanation
> for "should not matter in practice".

You are right, that was hand-wavy. I started with writing a somewhat long analysis but after finding a clean way of supporting both DFS and priority queue modes it feels somewhat unnecessary - I will still include it here, but the short summary is that it's fixable.

Since the prio_queue struct supports both LIFO and heap mode, it's actually quite easy to plug this into tips_reachable_from_bases. I just need to switch away from using the stack structure and pass a mode to choose between LIFO and heap. This preserves the old behavior while still reducing the code size and unifying the code more.

I will submit a v2 of the patch shortly.

I will also include the original analysis I wrote before finding the simple fix.

Thanks for the review! Kristofer

--- I will refer to the prio_queue approach in get_reachable_subset as PQ for brevity, and the DFS in tips_reachable_from_bases as simply DFS.

tips_reachable_from_bases() was designed for --merged queries where the targets (branches/tags) can be deep ancestors of the base. DFS is a natural fit there: it dives deep along first-parent quickly, and with generation numbers the dynamic floor raising prunes aggressively.

add_missing_tags() has the opposite shape: the bases are branch tips being pushed (near the top) and the targets are tag commits the remote does not have yet, which tend to be relatively close to those tips. PQ ordered by commit date is a better fit here because it sweeps down from the top and finds nearby targets early, while DFS might take a long detour down a side branch before coming back.

With a commit-graph this difference mostly disappears since the generation floor keeps DFS from going too far off track. Without a commit-graph, neither approach prunes anything (generation is GENERATION_NUMBER_INFINITY for all commits) so the traversal order is the only thing that matters, and PQ has the edge for shallow targets.

So the current code actually has each caller matched to the traversal strategy that fits its typical workload. My patch traded that away for code reduction.

That said, in practice the difference is limited: repositories large enough for this to matter typically have a commit-graph, and small repositories are fast either way. ---

Previous: Junio C HamanoNext: Derrick Stolee
Message 3 of 14 in “commit-reach: remove get_reachable_subset()”
  1. commit-reach: remove get_reachable_subset()Kristofer Karlsson via GitGitGadget, Jun 9, 2026
  2. Junio C HamanoJun 10, 2026
  3. Kristofer KarlssonJun 10, 2026
  4. Derrick StoleeJun 10, 2026
  5. commit-reach: remove get_reachable_subset()Kristofer Karlsson via GitGitGadget, Jun 11, 2026
  6. Derrick StoleeJun 11, 2026
  7. Kristofer KarlssonJun 11, 2026
  8. Derrick StoleeJun 11, 2026
  9. Junio C HamanoJun 11, 2026
  10. Weijie YuanJun 12, 2026
  11. Junio C HamanoJun 12, 2026
  12. Weijie YuanJun 12, 2026
  13. Weijie YuanJun 12, 2026
  14. Kristofer KarlssonJun 15, 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.