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
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

Previous: Kristofer KarlssonNext: Kristofer Karlsson via GitGitGadget
Message 4 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.