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. ---