{"thread":{"id":"64381","subject":"[PATCH] commit-reach: avoid commit_list_insert_by_date()","startedAt":"2025-10-24T16:47:17Z","lastAt":"2025-10-24T16:47:17Z","messageCount":1,"participants":["René Scharfe"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"529616","messageId":"87a00cb8-8faf-48ec-91aa-009e6e906363@web.de","threadId":"64381","inReplyTo":null,"subject":"[PATCH] commit-reach: avoid commit_list_insert_by_date()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-10-24T16:47:10Z","receivedAt":"2025-10-24T16:47:17Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Building a list using commit_list_insert_by_date() has quadratic worst\ncase complexity.  Avoid it by just appending in the loop and sorting at\nthe end.\n\nThe number of merge bases is usually small, so don't expect speedups in\nnormal repositories.  It has no limit, though.  The added perf test\nshows a nice improvement when dealing with 16384 merge bases:\n\nTest                     v2.51.1           HEAD\n-----------------------------------------------------------------\n6010.2: git merge-base   0.55(0.54+0.00)   0.03(0.02+0.00) -94.5%\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\nPatch formatted with --function-context for easier review, particularly\nof paint_down_to_common().\n\n commit-reach.c             |  14 +++--\n t/perf/p6010-merge-base.sh | 101 +++++++++++++++++++++++++++++++++++++\n 2 files changed, 110 insertions(+), 5 deletions(-)\n create mode 100755 t/perf/p6010-merge-base.sh\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex a339e41aa4..cc18c86d3b 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -52,127 +52,130 @@ static int queue_has_nonstale(struct prio_queue *queue)\n /* all input commits in one and twos[] must have been parsed! */\n static int paint_down_to_common(struct repository *r,\n \t\t\t\tstruct commit *one, int n,\n \t\t\t\tstruct commit **twos,\n \t\t\t\ttimestamp_t min_generation,\n \t\t\t\tint ignore_missing_commits,\n \t\t\t\tstruct commit_list **result)\n {\n \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n \tint i;\n \ttimestamp_t last_gen = GENERATION_NUMBER_INFINITY;\n+\tstruct commit_list **tail = result;\n \n \tif (!min_generation && !corrected_commit_dates_enabled(r))\n \t\tqueue.compare = compare_commits_by_commit_date;\n \n \tone->object.flags |= PARENT1;\n \tif (!n) {\n \t\tcommit_list_append(one, result);\n \t\treturn 0;\n \t}\n \tprio_queue_put(&queue, one);\n \n \tfor (i = 0; i < n; i++) {\n \t\ttwos[i]->object.flags |= PARENT2;\n \t\tprio_queue_put(&queue, twos[i]);\n \t}\n \n \twhile (queue_has_nonstale(&queue)) {\n \t\tstruct commit *commit = prio_queue_get(&queue);\n \t\tstruct commit_list *parents;\n \t\tint flags;\n \t\ttimestamp_t generation = commit_graph_generation(commit);\n \n \t\tif (min_generation && generation > last_gen)\n \t\t\tBUG(\"bad generation skip %\"PRItime\" > %\"PRItime\" at %s\",\n \t\t\t    generation, last_gen,\n \t\t\t    oid_to_hex(&commit->object.oid));\n \t\tlast_gen = generation;\n \n \t\tif (generation < min_generation)\n \t\t\tbreak;\n \n \t\tflags = commit->object.flags & (PARENT1 | PARENT2 | STALE);\n \t\tif (flags == (PARENT1 | PARENT2)) {\n \t\t\tif (!(commit->object.flags & RESULT)) {\n \t\t\t\tcommit->object.flags |= RESULT;\n-\t\t\t\tcommit_list_insert_by_date(commit, result);\n+\t\t\t\ttail = commit_list_append(commit, tail);\n \t\t\t}\n \t\t\t/* Mark parents of a found merge stale */\n \t\t\tflags |= STALE;\n \t\t}\n \t\tparents = commit->parents;\n \t\twhile (parents) {\n \t\t\tstruct commit *p = parents->item;\n \t\t\tparents = parents->next;\n \t\t\tif ((p->object.flags & flags) == flags)\n \t\t\t\tcontinue;\n \t\t\tif (repo_parse_commit(r, p)) {\n \t\t\t\tclear_prio_queue(&queue);\n \t\t\t\tfree_commit_list(*result);\n \t\t\t\t*result = NULL;\n \t\t\t\t/*\n \t\t\t\t * At this stage, we know that the commit is\n \t\t\t\t * missing: `repo_parse_commit()` uses\n \t\t\t\t * `OBJECT_INFO_DIE_IF_CORRUPT` and therefore\n \t\t\t\t * corrupt commits would already have been\n \t\t\t\t * dispatched with a `die()`.\n \t\t\t\t */\n \t\t\t\tif (ignore_missing_commits)\n \t\t\t\t\treturn 0;\n \t\t\t\treturn error(_(\"could not parse commit %s\"),\n \t\t\t\t\t     oid_to_hex(&p->object.oid));\n \t\t\t}\n \t\t\tp->object.flags |= flags;\n \t\t\tprio_queue_put(&queue, p);\n \t\t}\n \t}\n \n \tclear_prio_queue(&queue);\n+\tcommit_list_sort_by_date(result);\n \treturn 0;\n }\n \n static int merge_bases_many(struct repository *r,\n \t\t\t    struct commit *one, int n,\n \t\t\t    struct commit **twos,\n \t\t\t    struct commit_list **result)\n {\n-\tstruct commit_list *list = NULL;\n+\tstruct commit_list *list = NULL, **tail = result;\n \tint i;\n \n \tfor (i = 0; i < n; i++) {\n \t\tif (one == twos[i]) {\n \t\t\t/*\n \t\t\t * We do not mark this even with RESULT so we do not\n \t\t\t * have to clean it up.\n \t\t\t */\n \t\t\t*result = commit_list_insert(one, result);\n \t\t\treturn 0;\n \t\t}\n \t}\n \n \tif (!one)\n \t\treturn 0;\n \tif (repo_parse_commit(r, one))\n \t\treturn error(_(\"could not parse commit %s\"),\n \t\t\t     oid_to_hex(&one->object.oid));\n \tfor (i = 0; i < n; i++) {\n \t\tif (!twos[i])\n \t\t\treturn 0;\n \t\tif (repo_parse_commit(r, twos[i]))\n \t\t\treturn error(_(\"could not parse commit %s\"),\n \t\t\t\t     oid_to_hex(&twos[i]->object.oid));\n \t}\n \n \tif (paint_down_to_common(r, one, n, twos, 0, 0, &list)) {\n \t\tfree_commit_list(list);\n \t\treturn -1;\n \t}\n \n \twhile (list) {\n \t\tstruct commit *commit = pop_commit(&list);\n \t\tif (!(commit->object.flags & STALE))\n-\t\t\tcommit_list_insert_by_date(commit, result);\n+\t\t\ttail = commit_list_append(commit, tail);\n \t}\n+\tcommit_list_sort_by_date(result);\n \treturn 0;\n }\n \n@@ -421,47 +424,48 @@ static int remove_redundant(struct repository *r, struct commit **array,\n static int get_merge_bases_many_0(struct repository *r,\n \t\t\t\t  struct commit *one,\n \t\t\t\t  size_t n,\n \t\t\t\t  struct commit **twos,\n \t\t\t\t  int cleanup,\n \t\t\t\t  struct commit_list **result)\n {\n-\tstruct commit_list *list;\n+\tstruct commit_list *list, **tail = result;\n \tstruct commit **rslt;\n \tsize_t cnt, i;\n \tint ret;\n \n \tif (merge_bases_many(r, one, n, twos, result) < 0)\n \t\treturn -1;\n \tfor (i = 0; i < n; i++) {\n \t\tif (one == twos[i])\n \t\t\treturn 0;\n \t}\n \tif (!*result || !(*result)->next) {\n \t\tif (cleanup) {\n \t\t\tclear_commit_marks(one, all_flags);\n \t\t\tclear_commit_marks_many(n, twos, all_flags);\n \t\t}\n \t\treturn 0;\n \t}\n \n \t/* There are more than one */\n \tcnt = commit_list_count(*result);\n \tCALLOC_ARRAY(rslt, cnt);\n \tfor (list = *result, i = 0; list; list = list->next)\n \t\trslt[i++] = list->item;\n \tfree_commit_list(*result);\n \t*result = NULL;\n \n \tclear_commit_marks(one, all_flags);\n \tclear_commit_marks_many(n, twos, all_flags);\n \n \tret = remove_redundant(r, rslt, cnt, &cnt);\n \tif (ret < 0) {\n \t\tfree(rslt);\n \t\treturn -1;\n \t}\n \tfor (i = 0; i < cnt; i++)\n-\t\tcommit_list_insert_by_date(rslt[i], result);\n+\t\ttail = commit_list_append(rslt[i], tail);\n+\tcommit_list_sort_by_date(result);\n \tfree(rslt);\n \treturn 0;\n }\ndiff --git a/t/perf/p6010-merge-base.sh b/t/perf/p6010-merge-base.sh\nnew file mode 100755\nindex 0000000000..54f52fa23e\n--- /dev/null\n+++ b/t/perf/p6010-merge-base.sh\n@@ -0,0 +1,101 @@\n+#!/bin/sh\n+\n+test_description='Test git merge-base'\n+\n+. ./perf-lib.sh\n+\n+test_perf_fresh_repo\n+\n+#\n+# Creates lots of merges to make history traversal costly.  In\n+# particular it creates 2^($max_level-1)-1 2-way merges on top of\n+# 2^($max_level-1) root commits.  E.g., the commit history looks like\n+# this for a $max_level of 3:\n+#\n+#     _1_\n+#    /   \\\n+#   2     3\n+#  / \\   / \\\n+# 4   5 6   7\n+#\n+# The numbers are the fast-import marks, which also are the commit\n+# messages.  1 is the HEAD commit and a merge, 2 and 3 are also merges,\n+# 4-7 are the root commits.\n+#\n+build_history () {\n+\tlocal max_level=\"$1\" &&\n+\tlocal level=\"${2:-1}\" &&\n+\tlocal mark=\"${3:-1}\" &&\n+\tif test $level -eq $max_level\n+\tthen\n+\t\techo \"reset refs/heads/master\" &&\n+\t\techo \"from $ZERO_OID\" &&\n+\t\techo \"commit refs/heads/master\" &&\n+\t\techo \"mark :$mark\" &&\n+\t\techo \"committer C <c@example.com> 1234567890 +0000\" &&\n+\t\techo \"data <<EOF\" &&\n+\t\techo \"$mark\" &&\n+\t\techo \"EOF\"\n+\telse\n+\t\tlocal level1=$((level+1)) &&\n+\t\tlocal mark1=$((2*mark)) &&\n+\t\tlocal mark2=$((2*mark+1)) &&\n+\t\tbuild_history $max_level $level1 $mark1 &&\n+\t\tbuild_history $max_level $level1 $mark2 &&\n+\t\techo \"commit refs/heads/master\" &&\n+\t\techo \"mark :$mark\" &&\n+\t\techo \"committer C <c@example.com> 1234567890 +0000\" &&\n+\t\techo \"data <<EOF\" &&\n+\t\techo \"$mark\" &&\n+\t\techo \"EOF\" &&\n+\t\techo \"from :$mark1\" &&\n+\t\techo \"merge :$mark2\"\n+\tfi\n+}\n+\n+#\n+# Creates a new merge history in the same shape as build_history does,\n+# while reusing the same root commits.  This way the two top commits\n+# have 2^($max_level-1) merge bases between them.\n+#\n+build_history2 () {\n+\tlocal max_level=\"$1\" &&\n+\tlocal level=\"${2:-1}\" &&\n+\tlocal mark=\"${3:-1}\" &&\n+\tif test $level -lt $max_level\n+\tthen\n+\t\tlocal level1=$((level+1)) &&\n+\t\tlocal mark1=$((2*mark)) &&\n+\t\tlocal mark2=$((2*mark+1)) &&\n+\t\tbuild_history2 $max_level $level1 $mark1 &&\n+\t\tbuild_history2 $max_level $level1 $mark2 &&\n+\t\techo \"commit refs/heads/master\" &&\n+\t\techo \"mark :$mark\" &&\n+\t\techo \"committer C <c@example.com> 1234567890 +0000\" &&\n+\t\techo \"data <<EOF\" &&\n+\t\techo \"$mark II\" &&\n+\t\techo \"EOF\" &&\n+\t\techo \"from :$mark1\" &&\n+\t\techo \"merge :$mark2\"\n+\tfi\n+}\n+\n+test_expect_success 'setup' '\n+\tmax_level=15 &&\n+\tbuild_history $max_level | git fast-import --export-marks=marks &&\n+\tgit tag one &&\n+\tbuild_history2 $max_level | git fast-import --import-marks=marks --force &&\n+\tgit tag two &&\n+\tgit gc &&\n+\tgit log --format=%H --no-merges >expect\n+'\n+\n+test_perf 'git merge-base' '\n+\tgit merge-base --all one two >actual\n+'\n+\n+test_expect_success 'verify result' '\n+\ttest_cmp expect actual\n+'\n+\n+test_done\n-- \n2.51.1\n"}]}