Re: [PATCH] commit-reach: use the decoration hash for tips_reachable_from_bases()

[Derrick Stolee <stolee@gmail.com>]

On 5/16/26 4:23 AM, Kristofer Karlsson wrote:
> 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.

This is indeed an interesting case (multiple decorations) that we should
make sure is covered by a test case so we don't fall into this mistake
again.

Thanks,
-Stolee