Re: [PATCH] commit-reach: use the decoration hash for tips_reachable_from_bases()
- From
Derrick Stolee <stolee@gmail.com>
- Date
- May 16, 2026, 13:46 UTC
- Message-ID
- <5a783514-9d20-429b-8c07-200cf821a35d@gmail.com>
- In-Reply-To
- <CAL71e4NoKiRMGngCc-FYNX9PH5fTd6xpzMsfONefp+JwJ1-3BA@mail.gmail.com>
On 5/16/26 4:23 AM, Kristofer Karlsson wrote:
Show 30 quoted lines
> 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