[PATCH 0/3] rev-list: use merge-base --independent algorithm when possible

["Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com>]

The --maximal-only option was added to git rev-list in b4e8f60a3c (revision:
add --maximal-only option, 2026-01-22) and the discussion [1] included talks
of how 'git rev-list --maximal-only <refs>' acts the same as 'git merge-base
--independent <refs>' assuming that no other walk modifiers are provided to
the revision walk. And with those assumptions, the merge-base algorithm can
be faster if the refs have most of their history shared.

[1]
https://lore.kernel.org/git/pull.2032.v2.git.1769097958549.gitgitgadget@gmail.com/

This series updates the revision walk to use the merge-base algorithm when
possible. This checks the rev_info struct for options that cause the walk to
be different and also looks for negative references. If none of these
appear, then the merge-base algorithm is used instead.

The series is broken into three patches that could theoretically be squashed
into a single patch.

 1. The first demonstrates the equivalence of these two commands via some
    tests.
 2. The second creates a performance test and documents the current
    behavior.
 3. The third updates the implementation and demonstrates the improvement in
    the case of no walk modifiers.

Thanks, -Stolee

Derrick Stolee (3):
  t6600: test --maximal-only and --independent
  p6011: add perf test for rev-list --maximal-only
  rev-list: use reduce_heads() for --maximal-only

 builtin/rev-list.c               | 59 ++++++++++++++++++++++++++++++++
 t/perf/p6011-rev-list-maximal.sh | 29 ++++++++++++++++
 t/t6000-rev-list-misc.sh         | 31 +++++++++++++++++
 t/t6600-test-reach.sh            | 45 ++++++++++++++++++++++++
 4 files changed, 164 insertions(+)
 create mode 100755 t/perf/p6011-rev-list-maximal.sh


base-commit: ca1db8a0f7dc0dbea892e99f5b37c5fe5861be71
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2082%2Fderrickstolee%2Fmaximal-faster-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2082/derrickstolee/maximal-faster-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/2082
-- 
gitgitgadget