From: Derrick Stolee Date: Sat, 16 May 2026 13:46:56 GMT Subject: Re: [PATCH] commit-reach: use the decoration hash for tips_reachable_from_bases() Message-ID: <5a783514-9d20-429b-8c07-200cf821a35d@gmail.com> In-Reply-To: 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