From: Kristofer Karlsson via GitGitGadget Date: Sat, 16 May 2026 15:59:39 GMT Subject: [PATCH v3 0/2] commit-reach: use object flags for tips_reachable_from_bases() Message-ID: In-Reply-To: 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