[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