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

[PATCH v3 0/2] commit-reach: use object flags for tips_reachable_from_bases()

From
Kristofer Karlsson via GitGitGadget <gitgitgadget@gmail.com>
Date
May 16, 2026, 15:59 UTC
Message-ID
<pull.2116.v3.git.1778947182.gitgitgadget@gmail.com>
In-Reply-To
<pull.2116.v2.git.1778922993480.gitgitgadget@gmail.com>

This replaces the O(C*T) linear scan in tips_reachable_from_bases() with an O(1) flag check using the RESULT object flag.

The function is called by git for-each-ref --merged and git branch/tag --contains/--no-contains via reach_filter() in ref-filter.c.

Benchmarks on a merge-heavy monorepo (2.3M commits, 10,000 refs):
 * for-each-ref --merged HEAD: 6.6s → 1.6s (4.1x)
 * for-each-ref --no-merged HEAD: 6.7s → 1.7s (4.0x)
On linux.git with 10,000 synthetic branches at the root commit:
 * for-each-ref --merged HEAD: 1.35s → 0.35s (3.9x)
 * for-each-ref --no-merged HEAD: 1.82s → 0.31s (5.9x)
v2 of this patch, addressing Jeff King's feedback:
 * Replaced the decoration hash with the RESULT object flag (simpler, no
   extra data structure, handles duplicate tips naturally)
 * Fixed early-termination bug when multiple refs point to the same commit
   (the decoration API overwrites on duplicate keys)
 * Removed the now-unused index field from struct commit_and_index
 * Diff is +11/-12 lines
Kristofer Karlsson (2):
  commit-reach: use object flags for tips_reachable_from_bases()
  t6600: add tests for duplicate tips in tips_reachable_from_bases()
 commit-reach.c        | 23 +++++++++++-----------
 t/t6600-test-reach.sh | 45 +++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 56 insertions(+), 12 deletions(-)
base-commit: 59ff4886a579f4bc91e976fe18590b9ae02c7a08
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2116%2Fspkrka%2Ftips-reachable-minimal-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2116/spkrka/tips-reachable-minimal-v3
Pull-Request: https://github.com/gitgitgadget/git/pull/2116
Range-diff vs v2:
 1:  7399a12518 = 1:  7399a12518 commit-reach: use object flags for tips_reachable_from_bases()
 -:  ---------- > 2:  4d11ebb79e t6600: add tests for duplicate tips in tips_reachable_from_bases()
-- 
gitgitgadget
Previous: Kristofer Karlsson via GitGitGadgetNext: Kristofer Karlsson via GitGitGadget
Message 6 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.