Re: [PATCH] commit-reach: use the decoration hash for tips_reachable_from_bases()
- From
Kristofer Karlsson <krka@spotify.com>
- Date
- May 16, 2026, 08:23 UTC
- Message-ID
- <CAL71e4NoKiRMGngCc-FYNX9PH5fTd6xpzMsfONefp+JwJ1-3BA@mail.gmail.com>
- In-Reply-To
- <20260515211459.GA158762@coredump.intra.peff.net>
Thanks for testing this, Jeff! You're right, the patch as posted regresses on your synthetic test case.
The issue is that when multiple refs point to the same commit, add_decoration overwrites earlier entries, so only one index gets stored. The marking itself is correct (the flag is on the shared commit object, so all duplicates get marked), but the j == min_generation_index check never fires for the minimum tip, so early termination breaks. The DFS walks the entire graph instead of stopping when all tips are found.
I have a fix for the early-termination bug (checking the flag at min_generation_index instead of comparing indices), but your suggestions about the API are well taken, I don't think the decoration hash is the right tool here. Since we only need set membership ("is this commit a tip?"), not a mapping, an object-flags bit or commit-slab would indeed be simpler and avoid the (void *)(i + 1) hack entirely.
I fixed it locally now for the linux test case and got a 4x speedup there too - the problem was failing the early termination. Some numbers when running against the linux repo on my machine:
Command │ Baseline │ V1 (broken) │ V2 (fixed) │ --no-merged HEAD │ 1.33s │ 2.01s (1.5x slower) │ 0.31s (4.3x faster) │ --merged HEAD │ 1.35s │ 1.96s (1.5x slower) │ 0.31s (4.3x faster) │
However, I'll still need to rethink the decoration map - I will come back with a better patch shortly.
- Kristofer
On Fri, 15 May 2026 at 23:15, Jeff King <peff@peff.net> wrote:
Show 67 quoted lines
> > On Fri, May 15, 2026 at 06:07:43PM +0000, Kristofer Karlsson via GitGitGadget wrote: > > > From: Kristofer Karlsson <krka@spotify.com> > > > > tips_reachable_from_bases() walks the commit graph from a set of base > > commits to find which tip commits are reachable. The inner loop does > > a linear scan over the tips array to check whether each visited commit > > is a tip, making the overall cost O(C * T) where C is commits walked > > and T is the number of tips. > > > > Replace the linear scan with the decoration hash for lookups, reducing > > the per-commit tip check from O(T) to O(1) and the overall cost from > > O(C * T) to O(C + T). > > > > This function is called by `git for-each-ref --merged` and > > `git branch/tag --contains/--no-contains` via reach_filter() in > > ref-filter.c. > > > > Benchmark on a merge-heavy monorepo (2.3M commits, 10,000 refs): > > > > Command Before After Speedup > > for-each-ref --merged HEAD 6.64s 1.66s 4.0x > > for-each-ref --no-merged HEAD 6.75s 1.74s 3.9x > > branch --merged HEAD 0.68s 0.61s 10% > > branch --no-merged HEAD 0.65s 0.61s 8% > > tag --merged HEAD 0.12s 0.12s - > > > > The large speedup for for-each-ref is because it checks all 10,000 > > refs as tips, making the O(T) inner loop expensive. The branch > > subcommand only checks local branches (fewer tips), so the improvement > > is smaller. > > Hmm, I couldn't reproduce the speedup on something like linux.git (~1.4M > commits) with a lot of synthetic branches. I'd think that old branches > would be the most expensive, so I did: > > old=$(git rev-list --reverse HEAD | head -n1) > seq --format="update refs/heads/branch%g $old" 10000 | > git update-ref --stdin > > Running "git for-each-ref --no-merged HEAD" takes ~650ms with stock Git. > But with your patch, it goes to ~830ms! > > So what am I missing about your repo that it is so slow in the first > place? > > > * Hacking the array index into the decoration value as (void *)(i + 1) > > instead of storing a proper pointer > > The decoration API is not the most generic option here. There's an > oidmap type, but you have to embed the hashmap bits into your struct, > which is a lot of boilerplate if you're just storing an int. You can > define a khash with a custom value type, and I think the existing > oid_pos uses an int, which might be enough. All of those will store an > extra copy of the oid, though for the sizes we're talking about that's > not the end of the world. > > Since we're always mapping commits, you could define a commit-slab (each > commit struct gets a unique id which we then index into a big array). > See commit-slab.h for an example. > > I'm not very familiar with this code, but I wonder if we actually need > to map at all. It looks like we are mostly interested in set inclusion, > so perhaps an oidset() would work. Or even a bit in the object-flags. > > -Peff