{"thread":{"id":"65444","subject":"[PATCH 0/3] rev-list: use merge-base --independent algorithm when possible","startedAt":"2026-04-06T13:27:31Z","lastAt":"2026-04-06T13:27:35Z","messageCount":4,"participants":["Derrick Stolee via GitGitGadget"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"540971","messageId":"pull.2082.git.1775482048.gitgitgadget@gmail.com","threadId":"65444","inReplyTo":null,"subject":"[PATCH 0/3] rev-list: use merge-base --independent algorithm when possible","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-04-06T13:27:25Z","receivedAt":"2026-04-06T13:27:31Z","isPatch":true,"body":"The --maximal-only option was added to git rev-list in b4e8f60a3c (revision:\nadd --maximal-only option, 2026-01-22) and the discussion [1] included talks\nof how 'git rev-list --maximal-only <refs>' acts the same as 'git merge-base\n--independent <refs>' assuming that no other walk modifiers are provided to\nthe revision walk. And with those assumptions, the merge-base algorithm can\nbe faster if the refs have most of their history shared.\n\n[1]\nhttps://lore.kernel.org/git/pull.2032.v2.git.1769097958549.gitgitgadget@gmail.com/\n\nThis series updates the revision walk to use the merge-base algorithm when\npossible. This checks the rev_info struct for options that cause the walk to\nbe different and also looks for negative references. If none of these\nappear, then the merge-base algorithm is used instead.\n\nThe series is broken into three patches that could theoretically be squashed\ninto a single patch.\n\n 1. The first demonstrates the equivalence of these two commands via some\n    tests.\n 2. The second creates a performance test and documents the current\n    behavior.\n 3. The third updates the implementation and demonstrates the improvement in\n    the case of no walk modifiers.\n\nThanks, -Stolee\n\nDerrick Stolee (3):\n  t6600: test --maximal-only and --independent\n  p6011: add perf test for rev-list --maximal-only\n  rev-list: use reduce_heads() for --maximal-only\n\n builtin/rev-list.c               | 59 ++++++++++++++++++++++++++++++++\n t/perf/p6011-rev-list-maximal.sh | 29 ++++++++++++++++\n t/t6000-rev-list-misc.sh         | 31 +++++++++++++++++\n t/t6600-test-reach.sh            | 45 ++++++++++++++++++++++++\n 4 files changed, 164 insertions(+)\n create mode 100755 t/perf/p6011-rev-list-maximal.sh\n\n\nbase-commit: ca1db8a0f7dc0dbea892e99f5b37c5fe5861be71\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2082%2Fderrickstolee%2Fmaximal-faster-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2082/derrickstolee/maximal-faster-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/2082\n-- \ngitgitgadget\n"},{"id":"540972","messageId":"176d1606c824f58443d085c6f5a02ab17a16ca1c.1775482048.git.gitgitgadget@gmail.com","threadId":"65444","inReplyTo":"pull.2082.git.1775482048.gitgitgadget@gmail.com","subject":"[PATCH 1/3] t6600: test --maximal-only and --independent","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-04-06T13:27:26Z","receivedAt":"2026-04-06T13:27:32Z","isPatch":true,"body":"From: Derrick Stolee <stolee@gmail.com>\n\nAdd a test that verifies the 'git rev-list --maximal-only' option\nproduces the same set of commits as 'git merge-base --independent'. This\nequivalence was noted when the feature was first created, but we are\nabout to update the implementation to use a common algorithm in this\ncase where the user intention is identical.\n\nSigned-off-by: Derrick Stolee <stolee@gmail.com>\n---\n t/t6600-test-reach.sh | 45 +++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 45 insertions(+)\n\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex 2613075894..dc0421ed2f 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -837,4 +837,49 @@ test_expect_success 'rev-list --maximal-only (range)' '\n \t\t--first-parent --exclude-first-parent-only\n '\n \n+test_expect_success 'rev-list --maximal-only matches merge-base --independent' '\n+\t# Mix of independent and dependent\n+\tgit merge-base --independent \\\n+\t\trefs/heads/commit-5-2 \\\n+\t\trefs/heads/commit-3-2 \\\n+\t\trefs/heads/commit-2-5 >expect &&\n+\tsort expect >expect.sorted &&\n+\tgit rev-list --maximal-only \\\n+\t\trefs/heads/commit-5-2 \\\n+\t\trefs/heads/commit-3-2 \\\n+\t\trefs/heads/commit-2-5 >actual &&\n+\tsort actual >actual.sorted &&\n+\ttest_cmp expect.sorted actual.sorted &&\n+\n+\t# All independent commits.\n+\tgit merge-base --independent \\\n+\t\trefs/heads/commit-5-2 \\\n+\t\trefs/heads/commit-4-3 \\\n+\t\trefs/heads/commit-3-4 \\\n+\t\trefs/heads/commit-2-5 >expect &&\n+\tsort expect >expect.sorted &&\n+\tgit rev-list --maximal-only \\\n+\t\trefs/heads/commit-5-2 \\\n+\t\trefs/heads/commit-4-3 \\\n+\t\trefs/heads/commit-3-4 \\\n+\t\trefs/heads/commit-2-5 >actual &&\n+\tsort actual >actual.sorted &&\n+\ttest_cmp expect.sorted actual.sorted &&\n+\n+\t# Only one independent.\n+\tgit merge-base --independent \\\n+\t\trefs/heads/commit-1-1 \\\n+\t\trefs/heads/commit-4-2 \\\n+\t\trefs/heads/commit-4-4 \\\n+\t\trefs/heads/commit-8-4 >expect &&\n+\tsort expect >expect.sorted &&\n+\tgit rev-list --maximal-only \\\n+\t\trefs/heads/commit-1-1 \\\n+\t\trefs/heads/commit-4-2 \\\n+\t\trefs/heads/commit-4-4 \\\n+\t\trefs/heads/commit-8-4 >actual &&\n+\tsort actual >actual.sorted &&\n+\ttest_cmp expect.sorted actual.sorted\n+'\n+\n test_done\n-- \ngitgitgadget\n\n"},{"id":"540973","messageId":"40722d7d13c3f19bc6984c11583ff8136dbeea81.1775482048.git.gitgitgadget@gmail.com","threadId":"65444","inReplyTo":"pull.2082.git.1775482048.gitgitgadget@gmail.com","subject":"[PATCH 2/3] p6011: add perf test for rev-list --maximal-only","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-04-06T13:27:27Z","receivedAt":"2026-04-06T13:27:34Z","isPatch":true,"body":"From: Derrick Stolee <stolee@gmail.com>\n\nAdd a performance test that compares 'git rev-list --maximal-only'\nagainst 'git merge-base --independent'. These two commands are asking\nessentially the same thing, but the rev-list implementation is more\ngeneric and hence slower. These performance tests will demonstrate that\nin the current state and also be used to show the equivalence in the\nfuture.\n\nWe also add a case with '--since' to force the generic walk logic for\nrev-list even when we make that future change to use the merge-base\nalgorithm on a simple walk.\n\nWhen run on my copy of git.git, I see these results:\n\n  Test                                      HEAD\n  ----------------------------------------------\n  6011.2: merge-base --independent          0.03\n  6011.3: rev-list --maximal-only           0.06\n  6011.4: rev-list --maximal-only --since   0.06\n\nThese numbers are low, but the --independent calculation is interesting\ndue to having a lot of local branches that are actually independent.\n\nRunning the same test on a fresh clone of the Linux kernel repository\nshows a larger difference between the algorithms, especially because the\n--independent algorithm is extremely fast when there are no independent\nreferences selected:\n\n  Test                                      HEAD\n  ----------------------------------------------\n  6011.2: merge-base --independent          0.00\n  6011.3: rev-list --maximal-only           0.70\n  6011.4: rev-list --maximal-only --since   0.70\n\nSigned-off-by: Derrick Stolee <stolee@gmail.com>\n---\n t/perf/p6011-rev-list-maximal.sh | 29 +++++++++++++++++++++++++++++\n 1 file changed, 29 insertions(+)\n create mode 100755 t/perf/p6011-rev-list-maximal.sh\n\ndiff --git a/t/perf/p6011-rev-list-maximal.sh b/t/perf/p6011-rev-list-maximal.sh\nnew file mode 100755\nindex 0000000000..e868e83ff8\n--- /dev/null\n+++ b/t/perf/p6011-rev-list-maximal.sh\n@@ -0,0 +1,29 @@\n+#!/bin/sh\n+\n+test_description='Test --maximal-only and --independent options'\n+\n+. ./perf-lib.sh\n+\n+test_perf_default_repo\n+\n+test_expect_success 'setup' '\n+\tgit for-each-ref --format=\"%(*objecttype) %(objecttype) %(objectname)\" \\\n+\t\t\"refs/heads/*\" \"refs/tags/*\" |\n+\t\tsed -n -e \"s/^commit commit //p\" -e \"s/^ commit //p\" |\n+\t\thead -n 50 >commits &&\n+\tgit commit-graph write --reachable\n+'\n+\n+test_perf 'merge-base --independent' '\n+\tgit merge-base --independent $(cat commits) >/dev/null\n+'\n+\n+test_perf 'rev-list --maximal-only' '\n+\tgit rev-list --maximal-only $(cat commits) >/dev/null\n+'\n+\n+test_perf 'rev-list --maximal-only --since' '\n+\tgit rev-list --maximal-only --since=2000-01-01 $(cat commits) >/dev/null\n+'\n+\n+test_done\n-- \ngitgitgadget\n\n"},{"id":"540974","messageId":"0bdb88c85eabfa88b97c83a8f20f76cb8ed0489d.1775482048.git.gitgitgadget@gmail.com","threadId":"65444","inReplyTo":"pull.2082.git.1775482048.gitgitgadget@gmail.com","subject":"[PATCH 3/3] rev-list: use reduce_heads() for --maximal-only","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-04-06T13:27:28Z","receivedAt":"2026-04-06T13:27:35Z","isPatch":true,"body":"From: Derrick Stolee <stolee@gmail.com>\n\nThe 'git rev-list --maximal-only' option filters the output to only\nindependent commits. A commit is independent if it is not reachable from\nother listed commits. Currently this is implemented by doing a full\nrevision walk and marking parents with CHILD_VISITED to skip non-maximal\ncommits.\n\nThe 'git merge-base --independent' command computes the same result\nusing reduce_heads(), which uses the more efficient remove_redundant()\nalgorithm. This is significantly faster because it avoids walking the\nentire commit graph.\n\nAdd a fast path in rev-list that detects when --maximal-only is the only\ninteresting option and all input commits are positive (no revision\nranges). In this case, use reduce_heads() directly instead of doing a\nfull revision walk.\n\nIn order to preserve the rest of the output filtering, this computation\nis done opportunistically in a new prepare_maximal_independent() method\nwhen possible. If successful, it populates revs->commits with the list\nof independent commits and set revs->no_walk to prevent any other walk\nfrom occurring. This allows us to have any custom output be handled\nusing the existing output code hidden inside\ntraverse_commit_list_filtered(). A new test is added to demonstrate that\nthis output is preserved.\n\nThe fast path is only used when no other flags complicate the walk or\noutput format: no UNINTERESTING commits, no limiting options (max-count,\nage filters, path filters, grep filters), no output formatting beyond\nplain OIDs, and no object listing flags.\n\nRunning the p6011 performance test for my copy of git.git, I see the\nfollowing improvement with this change:\n\n  Test                                     HEAD~1  HEAD\n  ------------------------------------------------------------\n  6011.2: merge-base --independent          0.03   0.03 +0.0%\n  6011.3: rev-list --maximal-only           0.06   0.03 -50.0%\n  6011.4: rev-list --maximal-only --since   0.06   0.06 +0.0%\n\nAnd for a fresh clone of the Linux kernel repository, I see:\n\n  Test                                     HEAD~1  HEAD\n  ------------------------------------------------------------\n  6011.2: merge-base --independent          0.00   0.00 =\n  6011.3: rev-list --maximal-only           0.70   0.00 -100.0%\n  6011.4: rev-list --maximal-only --since   0.70   0.70 +0.0%\n\nIn both cases, the performance is indeed matching the behavior of 'git\nmerge-base --independent', as expected.\n\nSigned-off-by: Derrick Stolee <stolee@gmail.com>\n---\n builtin/rev-list.c       | 59 ++++++++++++++++++++++++++++++++++++++++\n t/t6000-rev-list-misc.sh | 31 +++++++++++++++++++++\n 2 files changed, 90 insertions(+)\n\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex 854d82ece3..8f63003709 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -25,6 +25,7 @@\n #include \"oidset.h\"\n #include \"oidmap.h\"\n #include \"packfile.h\"\n+#include \"commit-reach.h\"\n #include \"quote.h\"\n #include \"strbuf.h\"\n \n@@ -633,6 +634,61 @@ static int try_bitmap_disk_usage(struct rev_info *revs,\n \treturn 0;\n }\n \n+/*\n+ * If revs->maximal_only is set and no other walk modifiers are provided,\n+ * run a faster computation to filter the independent commits and prepare\n+ * them for output. Set revs->no_walk to prevent later walking.\n+ *\n+ * If this algorithm doesn't apply, then no changes are made to revs.\n+ */\n+static void prepare_maximal_independent(struct rev_info *revs)\n+{\n+\tstruct commit_list *c;\n+\n+\tif (!revs->maximal_only)\n+\t\treturn;\n+\n+\tfor (c = revs->commits; c; c = c->next) {\n+\t\tif (c->item->object.flags & UNINTERESTING)\n+\t\t\treturn;\n+\t}\n+\n+\tif (revs->limited ||\n+\t    revs->topo_order ||\n+\t    revs->first_parent_only ||\n+\t    revs->reverse ||\n+\t    revs->max_count >= 0 ||\n+\t    revs->skip_count >= 0 ||\n+\t    revs->min_age != (timestamp_t)-1 ||\n+\t    revs->max_age != (timestamp_t)-1 ||\n+\t    revs->min_parents > 0 ||\n+\t    revs->max_parents >= 0 ||\n+\t    revs->prune_data.nr ||\n+\t    revs->count ||\n+\t    revs->left_right ||\n+\t    revs->boundary ||\n+\t    revs->tag_objects ||\n+\t    revs->tree_objects ||\n+\t    revs->blob_objects ||\n+\t    revs->filter.choice ||\n+\t    revs->reflog_info ||\n+\t    revs->diff ||\n+\t    revs->grep_filter.pattern_list ||\n+\t    revs->grep_filter.header_list ||\n+\t    revs->verbose_header ||\n+\t    revs->print_parents ||\n+\t    revs->edge_hint ||\n+\t    revs->unpacked ||\n+\t    revs->no_kept_objects ||\n+\t    revs->line_level_traverse)\n+\t\treturn;\n+\n+\treduce_heads_replace(&revs->commits);\n+\n+\t/* Modify 'revs' to only output this commit list. */\n+\trevs->no_walk = 1;\n+}\n+\n int cmd_rev_list(int argc,\n \t\t const char **argv,\n \t\t const char *prefix,\n@@ -875,6 +931,9 @@ int cmd_rev_list(int argc,\n \n \tif (prepare_revision_walk(&revs))\n \t\tdie(\"revision walk setup failed\");\n+\n+\tprepare_maximal_independent(&revs);\n+\n \tif (revs.tree_objects)\n \t\tmark_edges_uninteresting(&revs, show_edge, 0);\n \ndiff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh\nindex d0a2a86610..a95ba576fa 100755\n--- a/t/t6000-rev-list-misc.sh\n+++ b/t/t6000-rev-list-misc.sh\n@@ -263,4 +263,35 @@ test_expect_success 'rev-list --boundary incompatible with --maximal-only' '\n \ttest_grep \"cannot be used together\" err\n '\n \n+test_expect_success 'rev-list --maximal-only and --pretty' '\n+\ttest_when_finished rm -rf repo &&\n+\n+\tgit init repo &&\n+\ttest_commit -C repo 1 &&\n+\toid1=$(git -C repo rev-parse HEAD) &&\n+\ttest_commit -C repo 2 &&\n+\toid2=$(git -C repo rev-parse HEAD) &&\n+\tgit -C repo checkout --detach HEAD~1 &&\n+\ttest_commit -C repo 3 &&\n+\toid3=$(git -C repo rev-parse HEAD) &&\n+\n+\tcat >expect <<-EOF &&\n+\tcommit $oid3\n+\t$oid3\n+\tcommit $oid2\n+\t$oid2\n+\tEOF\n+\n+\tgit -C repo rev-list --pretty=\"%H\" --maximal-only $oid1 $oid2 $oid3 >out &&\n+\ttest_cmp expect out &&\n+\n+\tcat >expect <<-EOF &&\n+\t$oid3\n+\t$oid2\n+\tEOF\n+\n+\tgit -C repo log --pretty=\"%H\" --maximal-only $oid1 $oid2 $oid3 >out &&\n+\ttest_cmp expect out\n+'\n+\n test_done\n-- \ngitgitgadget\n"}]}