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

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
Previous: Jeff KingNext: Derrick Stolee
Message 3 of 10 in “commit-reach: use the decoration hash for tips_reachable_from_bases()”
  1. commit-reach: use the decoration hash for tips_reachable_from_bases()Kristofer Karlsson via GitGitGadget, May 15, 2026
  2. Jeff KingMay 15, 2026
  3. Kristofer KarlssonMay 16, 2026
  4. Derrick StoleeMay 16, 2026
  5. commit-reach: use object flags for tips_reachable_from_bases()Kristofer Karlsson via GitGitGadget, May 16, 2026
  6. 0/2 commit-reach: use object flags for tips_reachable_from_bases()Kristofer Karlsson via GitGitGadget, May 16, 2026
  7. 1/2 commit-reach: use object flags for tips_reachable_from_bases()Kristofer Karlsson via GitGitGadget, May 16, 2026
  8. 2/2 t6600: add tests for duplicate tips in tips_reachable_from_bases()Kristofer Karlsson via GitGitGadget, May 16, 2026
  9. Jeff KingMay 19, 2026
  10. Derrick StoleeMay 21, 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.