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

["Kristofer Karlsson via GitGitGadget" <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