{"thread":{"id":"63797","subject":"[PATCH 0/3] commit: convert pop_most_recent_commit() to prio_queue","startedAt":"2025-07-15T14:35:11Z","lastAt":"2025-08-04T19:56:36Z","messageCount":41,"participants":["René Scharfe","Junio C Hamano","Justin Tobler","Jeff King","Lidong Yan","SZEDER Gábor","Johannes Schindelin"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"522001","messageId":"bc079b3c-a472-4f5d-95ca-390f9de25196@web.de","threadId":"63797","inReplyTo":null,"subject":"[PATCH 0/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-07-15T14:35:07Z","receivedAt":"2025-07-15T14:35:11Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Use prio_queue to improve worst-case performance at the cost of slightly\nworse best-case performance. Then add and use prio_queue_replace() to\nrecover that loss.\n\n commit: convert pop_most_recent_commit() to prio_queue\n prio-queue: add prio_queue_replace()\n commit: use prio_queue_replace() in pop_most_recent_commit()\n\n commit.c | 14 ++++++--\n commit.h | 8 ++---\n fetch-pack.c | 13 +++++---\n object-name.c | 10 +++---\n prio-queue.c | 45 +++++++++++++++++--------\n prio-queue.h | 8 +++++\n t/perf/p1501-rev-parse-oneline.sh | 55 +++++++++++++++++++++++++++++++\n t/unit-tests/u-prio-queue.c | 23 +++++++++++++\n walker.c | 11 ++++---\n 9 files changed, 153 insertions(+), 34 deletions(-)\n create mode 100755 t/perf/p1501-rev-parse-oneline.sh\n\n-- \n2.50.1\n"},{"id":"522002","messageId":"bfb0a65d-c9dd-47d9-a88d-9fec43538b0c@web.de","threadId":"63797","inReplyTo":"bc079b3c-a472-4f5d-95ca-390f9de25196@web.de","subject":"[PATCH 1/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-07-15T14:51:07Z","receivedAt":"2025-07-15T14:51:16Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"pop_most_recent_commit() calls commit_list_insert_by_date(), which and\nis itself called in a loop, which can lead to quadratic complexity.\nReplace the commit_list with a prio_queue to ensure logarithmic worst\ncase complexity and convert all three users.\n\nAdd a performance test that exercises one of them using a pathological\nhistory that consists of 50% merges and 50% root commits to demonstrate\nthe speedup:\n\n Test v2.50.1 HEAD\n ----------------------------------------------------------------------\n 1501.2: rev-parse ':/65535' 2.48(2.47+0.00) 0.20(0.19+0.00) -91.9%\n\nAlas, sane histories don't benefit from the conversion much, and\ntraversing Git's own history takes a 1% performance hit on my machine:\n\n $ hyperfine -w3 -L git ./git_2.50.1,./git '{git} rev-parse :/^Initial.revision'\n Benchmark 1: ./git_2.50.1 rev-parse :/^Initial.revision\n Time (mean ± σ): 1.071 s ± 0.004 s [User: 1.052 s, System: 0.017 s]\n Range (min … max): 1.067 s … 1.078 s 10 runs\n\n Benchmark 2: ./git rev-parse :/^Initial.revision\n Time (mean ± σ): 1.079 s ± 0.003 s [User: 1.060 s, System: 0.017 s]\n Range (min … max): 1.074 s … 1.083 s 10 runs\n\n Summary\n ./git_2.50.1 rev-parse :/^Initial.revision ran\n 1.01 ± 0.00 times faster than ./git rev-parse :/^Initial.revision\n\nSigned-off-by: René Scharfe \n---\n commit.c | 7 ++--\n commit.h | 8 ++---\n fetch-pack.c | 13 +++++---\n object-name.c | 10 +++---\n t/perf/p1501-rev-parse-oneline.sh | 55 +++++++++++++++++++++++++++++++\n walker.c | 11 ++++---\n 6 files changed, 83 insertions(+), 21 deletions(-)\n create mode 100755 t/perf/p1501-rev-parse-oneline.sh\n\ndiff --git a/commit.c b/commit.c\nindex e915b2b9a1..0200759aaa 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -31,6 +31,7 @@\n #include \"parse.h\"\n #include \"object-file.h\"\n #include \"object-file-convert.h\"\n+#include \"prio-queue.h\"\n \n static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **);\n \n@@ -738,17 +739,17 @@ void commit_list_sort_by_date(struct commit_list **list)\n \tcommit_list_sort(list, commit_list_compare_by_date);\n }\n \n-struct commit *pop_most_recent_commit(struct commit_list **list,\n+struct commit *pop_most_recent_commit(struct prio_queue *queue,\n \t\t\t\t unsigned int mark)\n {\n-\tstruct commit *ret = pop_commit(list);\n+\tstruct commit *ret = prio_queue_get(queue);\n \tstruct commit_list *parents = ret->parents;\n \n \twhile (parents) {\n \t\tstruct commit *commit = parents->item;\n \t\tif (!repo_parse_commit(the_repository, commit) && !(commit->object.flags & mark)) {\n \t\t\tcommit->object.flags |= mark;\n-\t\t\tcommit_list_insert_by_date(commit, list);\n+\t\t\tprio_queue_put(queue, commit);\n \t\t}\n \t\tparents = parents->next;\n \t}\ndiff --git a/commit.h b/commit.h\nindex 70c870dae4..9630c076d6 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -201,10 +201,10 @@ const char *repo_logmsg_reencode(struct repository *r,\n \n const char *skip_blank_lines(const char *msg);\n \n-/** Removes the first commit from a list sorted by date, and adds all\n- * of its parents.\n- **/\n-struct commit *pop_most_recent_commit(struct commit_list **list,\n+struct prio_queue;\n+\n+/* Removes the first commit from a prio_queue and adds its parents. */\n+struct commit *pop_most_recent_commit(struct prio_queue *queue,\n \t\t\t\t unsigned int mark);\n \n struct commit *pop_commit(struct commit_list **stack);\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex fa4231fee7..6afe2f964e 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -34,6 +34,7 @@\n #include \"commit-graph.h\"\n #include \"sigchain.h\"\n #include \"mergesort.h\"\n+#include \"prio-queue.h\"\n \n static int transfer_unpack_limit = -1;\n static int fetch_unpack_limit = -1;\n@@ -600,7 +601,7 @@ static int find_common(struct fetch_negotiator *negotiator,\n \treturn count ? retval : 0;\n }\n \n-static struct commit_list *complete;\n+static struct prio_queue complete = { compare_commits_by_commit_date };\n \n static int mark_complete(const struct object_id *oid)\n {\n@@ -608,7 +609,7 @@ static int mark_complete(const struct object_id *oid)\n \n \tif (commit && !(commit->object.flags & COMPLETE)) {\n \t\tcommit->object.flags |= COMPLETE;\n-\t\tcommit_list_insert(commit, &complete);\n+\t\tprio_queue_put(&complete, commit);\n \t}\n \treturn 0;\n }\n@@ -625,9 +626,12 @@ static int mark_complete_oid(const char *refname UNUSED,\n static void mark_recent_complete_commits(struct fetch_pack_args *args,\n \t\t\t\t\t timestamp_t cutoff)\n {\n-\twhile (complete && cutoff <= complete->item->date) {\n+\twhile (complete.nr) {\n+\t\tstruct commit *item = prio_queue_peek(&complete);\n+\t\tif (item->date < cutoff)\n+\t\t\tbreak;\n \t\tprint_verbose(args, _(\"Marking %s as complete\"),\n-\t\t\t oid_to_hex(&complete->item->object.oid));\n+\t\t\t oid_to_hex(&item->object.oid));\n \t\tpop_most_recent_commit(&complete, COMPLETE);\n \t}\n }\n@@ -797,7 +801,6 @@ static void mark_complete_and_common_ref(struct fetch_negotiator *negotiator,\n \t\trefs_for_each_rawref(get_main_ref_store(the_repository),\n \t\t\t\t mark_complete_oid, NULL);\n \t\tfor_each_cached_alternate(NULL, mark_alternate_complete);\n-\t\tcommit_list_sort_by_date(&complete);\n \t\tif (cutoff)\n \t\t\tmark_recent_complete_commits(args, cutoff);\n \t}\ndiff --git a/object-name.c b/object-name.c\nindex 851858975f..ab57722146 100644\n--- a/object-name.c\n+++ b/object-name.c\n@@ -28,6 +28,7 @@\n #include \"commit-reach.h\"\n #include \"date.h\"\n #include \"object-file-convert.h\"\n+#include \"prio-queue.h\"\n \n static int get_oid_oneline(struct repository *r, const char *, struct object_id *,\n \t\t\t const struct commit_list *);\n@@ -1461,7 +1462,7 @@ static int get_oid_oneline(struct repository *r,\n \t\t\t const char *prefix, struct object_id *oid,\n \t\t\t const struct commit_list *list)\n {\n-\tstruct commit_list *copy = NULL, **copy_tail = ©\n+\tstruct prio_queue copy = { compare_commits_by_commit_date };\n \tconst struct commit_list *l;\n \tint found = 0;\n \tint negative = 0;\n@@ -1483,9 +1484,9 @@ static int get_oid_oneline(struct repository *r,\n \n \tfor (l = list; l; l = l->next) {\n \t\tl->item->object.flags |= ONELINE_SEEN;\n-\t\tcopy_tail = &commit_list_insert(l->item, copy_tail)->next;\n+\t\tprio_queue_put(©, l->item);\n \t}\n-\twhile (copy) {\n+\twhile (copy.nr) {\n \t\tconst char *p, *buf;\n \t\tstruct commit *commit;\n \t\tint matches;\n@@ -1507,7 +1508,7 @@ static int get_oid_oneline(struct repository *r,\n \tregfree(®ex);\n \tfor (l = list; l; l = l->next)\n \t\tclear_commit_marks(l->item, ONELINE_SEEN);\n-\tfree_commit_list(copy);\n+\tclear_prio_queue(©);\n \treturn found ? 0 : -1;\n }\n \n@@ -2061,7 +2062,6 @@ static enum get_oid_result get_oid_with_context_1(struct repository *repo,\n \t\t\tcb.list = &list;\n \t\t\trefs_for_each_ref(get_main_ref_store(repo), handle_one_ref, &cb);\n \t\t\trefs_head_ref(get_main_ref_store(repo), handle_one_ref, &cb);\n-\t\t\tcommit_list_sort_by_date(&list);\n \t\t\tret = get_oid_oneline(repo, name + 2, oid, list);\n \n \t\t\tfree_commit_list(list);\ndiff --git a/t/perf/p1501-rev-parse-oneline.sh b/t/perf/p1501-rev-parse-oneline.sh\nnew file mode 100755\nindex 0000000000..ae0f553be5\n--- /dev/null\n+++ b/t/perf/p1501-rev-parse-oneline.sh\n@@ -0,0 +1,55 @@\n+#!/bin/sh\n+\n+test_description='Test :/ object name notation'\n+\n+. ./perf-lib.sh\n+\n+test_perf_fresh_repo\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 1234567890 +0000\" &&\n+\t\techo \"data < 1234567890 +0000\" &&\n+\t\techo \"data <commits &&\n+\tsed -n -e \"s/ .*$//p\" -e \"q\" expect &&\n+\tsed -n -e \"s/^.* //p\" -e \"q\" needle\n+'\n+\n+test_perf \"rev-parse ':/$(cat needle)'\" \"\n+\tgit rev-parse ':/$(cat needle)' >actual\n+\"\n+\n+test_expect_success 'verify result' '\n+\ttest_cmp expect actual\n+'\n+\n+test_done\ndiff --git a/walker.c b/walker.c\nindex b470d43e54..c6d0e20c72 100644\n--- a/walker.c\n+++ b/walker.c\n@@ -14,6 +14,7 @@\n #include \"blob.h\"\n #include \"refs.h\"\n #include \"progress.h\"\n+#include \"prio-queue.h\"\n \n static struct object_id current_commit_oid;\n \n@@ -78,7 +79,7 @@ static int process_tree(struct walker *walker, struct tree *tree)\n #define SEEN\t\t(1U << 1)\n #define TO_SCAN\t\t(1U << 2)\n \n-static struct commit_list *complete = NULL;\n+static struct prio_queue complete = { compare_commits_by_commit_date };\n \n static int process_commit(struct walker *walker, struct commit *commit)\n {\n@@ -87,7 +88,10 @@ static int process_commit(struct walker *walker, struct commit *commit)\n \tif (repo_parse_commit(the_repository, commit))\n \t\treturn -1;\n \n-\twhile (complete && complete->item->date >= commit->date) {\n+\twhile (complete.nr) {\n+\t\tstruct commit *item = prio_queue_peek(&complete);\n+\t\tif (item->date < commit->date)\n+\t\t\tbreak;\n \t\tpop_most_recent_commit(&complete, COMPLETE);\n \t}\n \n@@ -233,7 +237,7 @@ static int mark_complete(const char *path UNUSED,\n \n \tif (commit) {\n \t\tcommit->object.flags |= COMPLETE;\n-\t\tcommit_list_insert(commit, &complete);\n+\t\tprio_queue_put(&complete, commit);\n \t}\n \treturn 0;\n }\n@@ -302,7 +306,6 @@ int walker_fetch(struct walker *walker, int targets, char **target,\n \tif (!walker->get_recover) {\n \t\trefs_for_each_ref(get_main_ref_store(the_repository),\n \t\t\t\t mark_complete, NULL);\n-\t\tcommit_list_sort_by_date(&complete);\n \t}\n \n \tfor (i = 0; i < targets; i++) {\n-- \n2.50.1\n"},{"id":"522003","messageId":"cbabed69-b44a-4920-9a56-e81b404be2de@web.de","threadId":"63797","inReplyTo":"bc079b3c-a472-4f5d-95ca-390f9de25196@web.de","subject":"[PATCH 2/3] prio-queue: add prio_queue_replace()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-07-15T14:51:22Z","receivedAt":"2025-07-15T14:51:34Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Add a function to replace the top element of the queue that basically\ndoes the same as prio_queue_get() followed by prio_queue_put(), but\nwithout the work by prio_queue_get() to rebalance the heap. It can be\nused to optimize loops that get one element and then immediately add\nanother one. That's common e.g., with commit history traversal, where\nwe get out a commit and then put in its parents.\n\nSigned-off-by: René Scharfe \n---\n prio-queue.c | 45 ++++++++++++++++++++++++++-----------\n prio-queue.h | 8 +++++++\n t/unit-tests/u-prio-queue.c | 23 +++++++++++++++++++\n 3 files changed, 63 insertions(+), 13 deletions(-)\n\ndiff --git a/prio-queue.c b/prio-queue.c\nindex ec33ac27db..9748528ce6 100644\n--- a/prio-queue.c\n+++ b/prio-queue.c\n@@ -58,22 +58,10 @@ void prio_queue_put(struct prio_queue *queue, void *thing)\n \t}\n }\n \n-void *prio_queue_get(struct prio_queue *queue)\n+static void sift_down_root(struct prio_queue *queue)\n {\n-\tvoid *result;\n \tsize_t ix, child;\n \n-\tif (!queue->nr)\n-\t\treturn NULL;\n-\tif (!queue->compare)\n-\t\treturn queue->array[--queue->nr].data; /* LIFO */\n-\n-\tresult = queue->array[0].data;\n-\tif (!--queue->nr)\n-\t\treturn result;\n-\n-\tqueue->array[0] = queue->array[queue->nr];\n-\n \t/* Push down the one at the root */\n \tfor (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {\n \t\tchild = ix * 2 + 1; /* left */\n@@ -86,6 +74,23 @@ void *prio_queue_get(struct prio_queue *queue)\n \n \t\tswap(queue, child, ix);\n \t}\n+}\n+\n+void *prio_queue_get(struct prio_queue *queue)\n+{\n+\tvoid *result;\n+\n+\tif (!queue->nr)\n+\t\treturn NULL;\n+\tif (!queue->compare)\n+\t\treturn queue->array[--queue->nr].data; /* LIFO */\n+\n+\tresult = queue->array[0].data;\n+\tif (!--queue->nr)\n+\t\treturn result;\n+\n+\tqueue->array[0] = queue->array[queue->nr];\n+\tsift_down_root(queue);\n \treturn result;\n }\n \n@@ -97,3 +102,17 @@ void *prio_queue_peek(struct prio_queue *queue)\n \t\treturn queue->array[queue->nr - 1].data;\n \treturn queue->array[0].data;\n }\n+\n+void prio_queue_replace(struct prio_queue *queue, void *thing)\n+{\n+\tif (!queue->nr) {\n+\t\tprio_queue_put(queue, thing);\n+\t} else if (!queue->compare) {\n+\t\tqueue->array[queue->nr - 1].ctr = queue->insertion_ctr++;\n+\t\tqueue->array[queue->nr - 1].data = thing;\n+\t} else {\n+\t\tqueue->array[0].ctr = queue->insertion_ctr++;\n+\t\tqueue->array[0].data = thing;\n+\t\tsift_down_root(queue);\n+\t}\n+}\ndiff --git a/prio-queue.h b/prio-queue.h\nindex 38d032636d..da7fad2f1f 100644\n--- a/prio-queue.h\n+++ b/prio-queue.h\n@@ -52,6 +52,14 @@ void *prio_queue_get(struct prio_queue *);\n */\n void *prio_queue_peek(struct prio_queue *);\n \n+/*\n+ * Replace the \"thing\" that compares the smallest with a new \"thing\",\n+ * like prio_queue_get()+prio_queue_put() would do, but in a more\n+ * efficient way. Does the same as prio_queue_put() if the queue is\n+ * empty.\n+ */\n+void prio_queue_replace(struct prio_queue *queue, void *thing);\n+\n void clear_prio_queue(struct prio_queue *);\n \n /* Reverse the LIFO elements */\ndiff --git a/t/unit-tests/u-prio-queue.c b/t/unit-tests/u-prio-queue.c\nindex 145e689c9c..63e58114ae 100644\n--- a/t/unit-tests/u-prio-queue.c\n+++ b/t/unit-tests/u-prio-queue.c\n@@ -13,6 +13,7 @@ static int intcmp(const void *va, const void *vb, void *data UNUSED)\n #define STACK\t -3\n #define GET\t -4\n #define REVERSE -5\n+#define REPLACE -6\n \n static int show(int *v)\n {\n@@ -51,6 +52,15 @@ static void test_prio_queue(int *input, size_t input_size,\n \t\tcase REVERSE:\n \t\t\tprio_queue_reverse(&pq);\n \t\t\tbreak;\n+\t\tcase REPLACE:\n+\t\t\tpeek = prio_queue_peek(&pq);\n+\t\t\tcl_assert(i + 1 < input_size);\n+\t\t\tcl_assert(input[i + 1] >= 0);\n+\t\t\tcl_assert(j < result_size);\n+\t\t\tcl_assert_equal_i(result[j], show(peek));\n+\t\t\tj++;\n+\t\t\tprio_queue_replace(&pq, &input[++i]);\n+\t\t\tbreak;\n \t\tdefault:\n \t\t\tprio_queue_put(&pq, &input[i]);\n \t\t\tbreak;\n@@ -81,6 +91,13 @@ void test_prio_queue__empty(void)\n \t\t ((int []){ 1, 2, MISSING, 1, 2, MISSING }));\n }\n \n+void test_prio_queue__replace(void)\n+{\n+\tTEST_INPUT(((int []){ REPLACE, 6, 2, 4, REPLACE, 5, 7, GET,\n+\t\t\t REPLACE, 1, DUMP }),\n+\t\t ((int []){ MISSING, 2, 4, 5, 1, 6, 7 }));\n+}\n+\n void test_prio_queue__stack(void)\n {\n \tTEST_INPUT(((int []){ STACK, 8, 1, 5, 4, 6, 2, 3, DUMP }),\n@@ -92,3 +109,9 @@ void test_prio_queue__reverse_stack(void)\n \tTEST_INPUT(((int []){ STACK, 1, 2, 3, 4, 5, 6, REVERSE, DUMP }),\n \t\t ((int []){ 1, 2, 3, 4, 5, 6 }));\n }\n+\n+void test_prio_queue__replace_stack(void)\n+{\n+\tTEST_INPUT(((int []){ STACK, 8, 1, 5, REPLACE, 4, 6, 2, 3, DUMP }),\n+\t\t ((int []){ 5, 3, 2, 6, 4, 1, 8 }));\n+}\n-- \n2.50.1\n"},{"id":"522004","messageId":"aa89082f-34ab-4ec7-bdce-70f0a33815e6@web.de","threadId":"63797","inReplyTo":"bc079b3c-a472-4f5d-95ca-390f9de25196@web.de","subject":"[PATCH 3/3] commit: use prio_queue_replace() in pop_most_recent_commit()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-07-15T14:51:28Z","receivedAt":"2025-07-15T14:51:36Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Optimize pop_most_recent_commit() by adding the first parent using the\nmore efficient prio_queue_peek() and prio_queue_replace() instead of\nprio_queue_get() and prio_queue_put().\n\nOn my machine this neutralizes the performance hit it took in Git's own\nrepository when we converted it to prio_queue two patches ago (git_pq):\n\n $ hyperfine -w3 -L git ./git_2.50.1,./git_pq,./git '{git} rev-parse :/^Initial.revision'\n Benchmark 1: ./git_2.50.1 rev-parse :/^Initial.revision\n Time (mean ± σ): 1.073 s ± 0.003 s [User: 1.053 s, System: 0.019 s]\n Range (min … max): 1.069 s … 1.078 s 10 runs\n\n Benchmark 2: ./git_pq rev-parse :/^Initial.revision\n Time (mean ± σ): 1.077 s ± 0.002 s [User: 1.057 s, System: 0.018 s]\n Range (min … max): 1.072 s … 1.079 s 10 runs\n\n Benchmark 3: ./git rev-parse :/^Initial.revision\n Time (mean ± σ): 1.069 s ± 0.003 s [User: 1.049 s, System: 0.018 s]\n Range (min … max): 1.065 s … 1.074 s 10 runs\n\n Summary\n ./git rev-parse :/^Initial.revision ran\n 1.00 ± 0.00 times faster than ./git_2.50.1 rev-parse :/^Initial.revision\n 1.01 ± 0.00 times faster than ./git_pq rev-parse :/^Initial.revision\n\nSigned-off-by: René Scharfe \n---\n commit.c | 11 +++++++++--\n 1 file changed, 9 insertions(+), 2 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex 0200759aaa..8244221b30 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -742,17 +742,24 @@ void commit_list_sort_by_date(struct commit_list **list)\n struct commit *pop_most_recent_commit(struct prio_queue *queue,\n \t\t\t\t unsigned int mark)\n {\n-\tstruct commit *ret = prio_queue_get(queue);\n+\tstruct commit *ret = prio_queue_peek(queue);\n+\tint delete_pending = 1;\n \tstruct commit_list *parents = ret->parents;\n \n \twhile (parents) {\n \t\tstruct commit *commit = parents->item;\n \t\tif (!repo_parse_commit(the_repository, commit) && !(commit->object.flags & mark)) {\n \t\t\tcommit->object.flags |= mark;\n-\t\t\tprio_queue_put(queue, commit);\n+\t\t\tif (delete_pending)\n+\t\t\t\tprio_queue_replace(queue, commit);\n+\t\t\telse\n+\t\t\t\tprio_queue_put(queue, commit);\n+\t\t\tdelete_pending = 0;\n \t\t}\n \t\tparents = parents->next;\n \t}\n+\tif (delete_pending)\n+\t\tprio_queue_get(queue);\n \treturn ret;\n }\n \n-- \n2.50.1\n"},{"id":"522038","messageId":"xmqqldopgsw1.fsf@gitster.g","threadId":"63797","inReplyTo":"bfb0a65d-c9dd-47d9-a88d-9fec43538b0c@web.de","subject":"Re: [PATCH 1/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-07-15T19:23:42Z","receivedAt":"2025-07-15T19:23:45Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> pop_most_recent_commit() calls commit_list_insert_by_date(), which and\n> is itself called in a loop, which can lead to quadratic complexity.\n> Replace the commit_list with a prio_queue to ensure logarithmic worst\n> case complexity and convert all three users.\n>\n> Add a performance test that exercises one of them using a pathological\n> history that consists of 50% merges and 50% root commits to demonstrate\n> the speedup:\n>\n> Test v2.50.1 HEAD\n> ----------------------------------------------------------------------\n> 1501.2: rev-parse ':/65535' 2.48(2.47+0.00) 0.20(0.19+0.00) -91.9%\n>\n> Alas, sane histories don't benefit from the conversion much, and\n> traversing Git's own history takes a 1% performance hit on my machine:\n\n;-)\n\n> $ hyperfine -w3 -L git ./git_2.50.1,./git '{git} rev-parse :/^Initial.revision'\n> Benchmark 1: ./git_2.50.1 rev-parse :/^Initial.revision\n> Time (mean ± σ): 1.071 s ± 0.004 s [User: 1.052 s, System: 0.017 s]\n> Range (min … max): 1.067 s … 1.078 s 10 runs\n>\n> Benchmark 2: ./git rev-parse :/^Initial.revision\n> Time (mean ± σ): 1.079 s ± 0.003 s [User: 1.060 s, System: 0.017 s]\n> Range (min … max): 1.074 s … 1.083 s 10 runs\n>\n> Summary\n> ./git_2.50.1 rev-parse :/^Initial.revision ran\n> 1.01 ± 0.00 times faster than ./git rev-parse :/^Initial.revision\n"},{"id":"522041","messageId":"xmqqh5zdgp6r.fsf@gitster.g","threadId":"63797","inReplyTo":"aa89082f-34ab-4ec7-bdce-70f0a33815e6@web.de","subject":"Re: [PATCH 3/3] commit: use prio_queue_replace() in pop_most_recent_commit()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-07-15T20:43:40Z","receivedAt":"2025-07-15T20:43:43Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> Optimize pop_most_recent_commit() by adding the first parent using the\n> more efficient prio_queue_peek() and prio_queue_replace() instead of\n> prio_queue_get() and prio_queue_put().\n>\n> On my machine this neutralizes the performance hit it took in Git's own\n> repository when we converted it to prio_queue two patches ago (git_pq):\n\nGiven that our history has more merges than other projects, and the\n_replace() optimization would help primarily single-strand-of-pearls\n(and the first parent of a merge), that result is very good.\n\n> diff --git a/commit.c b/commit.c\n> index 0200759aaa..8244221b30 100644\n> --- a/commit.c\n> +++ b/commit.c\n> @@ -742,17 +742,24 @@ void commit_list_sort_by_date(struct commit_list **list)\n> struct commit *pop_most_recent_commit(struct prio_queue *queue,\n> \t\t\t\t unsigned int mark)\n> {\n> -\tstruct commit *ret = prio_queue_get(queue);\n> +\tstruct commit *ret = prio_queue_peek(queue);\n> +\tint delete_pending = 1;\n\nBriefly I was puzzled by the name (I would have called first-parent\nsince the logic was \"we treat first parent specially by using\nreplace instead of get/put\"), but the variable signals \"instead of\nget to remove the item from the queue, we just peeked, so we need to\nremove it later\" with its name, which is understandable.\n\n> \tstruct commit_list *parents = ret->parents;\n> \n> \twhile (parents) {\n> \t\tstruct commit *commit = parents->item;\n> \t\tif (!repo_parse_commit(the_repository, commit) && !(commit->object.flags & mark)) {\n> \t\t\tcommit->object.flags |= mark;\n> -\t\t\tprio_queue_put(queue, commit);\n> +\t\t\tif (delete_pending)\n> +\t\t\t\tprio_queue_replace(queue, commit);\n> +\t\t\telse\n> +\t\t\t\tprio_queue_put(queue, commit);\n> +\t\t\tdelete_pending = 0;\n> \t\t}\n> \t\tparents = parents->next;\n> \t}\n> +\tif (delete_pending)\n> +\t\tprio_queue_get(queue);\n> \treturn ret;\n> }\n"},{"id":"522044","messageId":"d2myew7nonfrelrwplpypexvcrktmjdlsccobjvx3dydvhnlar@bin5ol2vj3xs","threadId":"63797","inReplyTo":"bfb0a65d-c9dd-47d9-a88d-9fec43538b0c@web.de","subject":"Re: [PATCH 1/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"Justin Tobler","fromEmail":"jltobler@gmail.com","sentAt":"2025-07-15T20:47:11Z","receivedAt":"2025-07-15T20:52:54Z","isPatch":true,"sender":{"key":"jltobler@gmail.com","avatar":"https://avatars.githubusercontent.com/u/53454972?v=4"},"body":"On 25/07/15 04:51PM, René Scharfe wrote:\n> pop_most_recent_commit() calls commit_list_insert_by_date(), which and\n\nDid you mean?\n\ns/which and/which/\n\n> is itself called in a loop, which can lead to quadratic complexity.\n> Replace the commit_list with a prio_queue to ensure logarithmic worst\n> case complexity and convert all three users.\n\nIf I understand correctly, `pop_most_recent_commit()` removes the most\nrecent commit from a list of commits sorted by date and then inserts\neach of the removed commit's parents into the list while maintaining\ndate order. Iterating through `struct commit_list` every time to find\nwhere to insert each parent parent leads to quadratic complexity. For\nrepositories with many merge commits, this could scale poorly.\n\n> Add a performance test that exercises one of them using a pathological\n> history that consists of 50% merges and 50% root commits to demonstrate\n> the speedup:\n> \n> Test v2.50.1 HEAD\n> ----------------------------------------------------------------------\n> 1501.2: rev-parse ':/65535' 2.48(2.47+0.00) 0.20(0.19+0.00) -91.9%\n> \n> Alas, sane histories don't benefit from the conversion much, and\n> traversing Git's own history takes a 1% performance hit on my machine:\n\nAs \"normal\" repositories don't benefit here, it might be nice to more\nexplicitly mention the the types of repositories that do benefit.\n\n> $ hyperfine -w3 -L git ./git_2.50.1,./git '{git} rev-parse :/^Initial.revision'\n> Benchmark 1: ./git_2.50.1 rev-parse :/^Initial.revision\n> Time (mean ± σ): 1.071 s ± 0.004 s [User: 1.052 s, System: 0.017 s]\n> Range (min … max): 1.067 s … 1.078 s 10 runs\n> \n> Benchmark 2: ./git rev-parse :/^Initial.revision\n> Time (mean ± σ): 1.079 s ± 0.003 s [User: 1.060 s, System: 0.017 s]\n> Range (min … max): 1.074 s … 1.083 s 10 runs\n> \n> Summary\n> ./git_2.50.1 rev-parse :/^Initial.revision ran\n> 1.01 ± 0.00 times faster than ./git rev-parse :/^Initial.revision\n> \n> Signed-off-by: René Scharfe \n> ---\n> commit.c | 7 ++--\n> commit.h | 8 ++---\n> fetch-pack.c | 13 +++++---\n> object-name.c | 10 +++---\n> t/perf/p1501-rev-parse-oneline.sh | 55 +++++++++++++++++++++++++++++++\n> walker.c | 11 ++++---\n> 6 files changed, 83 insertions(+), 21 deletions(-)\n> create mode 100755 t/perf/p1501-rev-parse-oneline.sh\n> \n> diff --git a/commit.c b/commit.c\n> index e915b2b9a1..0200759aaa 100644\n> --- a/commit.c\n> +++ b/commit.c\n> @@ -31,6 +31,7 @@\n> #include \"parse.h\"\n> #include \"object-file.h\"\n> #include \"object-file-convert.h\"\n> +#include \"prio-queue.h\"\n> \n> static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **);\n> \n> @@ -738,17 +739,17 @@ void commit_list_sort_by_date(struct commit_list **list)\n> \tcommit_list_sort(list, commit_list_compare_by_date);\n> }\n> \n> -struct commit *pop_most_recent_commit(struct commit_list **list,\n> +struct commit *pop_most_recent_commit(struct prio_queue *queue,\n> \t\t\t\t unsigned int mark)\n> {\n> -\tstruct commit *ret = pop_commit(list);\n> +\tstruct commit *ret = prio_queue_get(queue);\n> \tstruct commit_list *parents = ret->parents;\n> \n> \twhile (parents) {\n> \t\tstruct commit *commit = parents->item;\n> \t\tif (!repo_parse_commit(the_repository, commit) && !(commit->object.flags & mark)) {\n> \t\t\tcommit->object.flags |= mark;\n> -\t\t\tcommit_list_insert_by_date(commit, list);\n> +\t\t\tprio_queue_put(queue, commit);\n> \t\t}\n> \t\tparents = parents->next;\n> \t}\n> diff --git a/commit.h b/commit.h\n> index 70c870dae4..9630c076d6 100644\n> --- a/commit.h\n> +++ b/commit.h\n> @@ -201,10 +201,10 @@ const char *repo_logmsg_reencode(struct repository *r,\n> \n> const char *skip_blank_lines(const char *msg);\n> \n> -/** Removes the first commit from a list sorted by date, and adds all\n> - * of its parents.\n> - **/\n> -struct commit *pop_most_recent_commit(struct commit_list **list,\n> +struct prio_queue;\n> +\n> +/* Removes the first commit from a prio_queue and adds its parents. */\n> +struct commit *pop_most_recent_commit(struct prio_queue *queue,\n> \t\t\t\t unsigned int mark);\n\nPreviously, `pop_most_recent_commit()` would ensure commits inserted in\nthe list were done it date order. Now this depends on how the caller has\nconfigured the `struct prio_queue`. This is fine though as previously\nthe caller was required to ensure the list was sorted to begin with\notherwise it wouldn't work properly.\n\n-Justin\n"},{"id":"522059","messageId":"xmqqv7ntdmlx.fsf@gitster.g","threadId":"63797","inReplyTo":"bc079b3c-a472-4f5d-95ca-390f9de25196@web.de","subject":"Re: [PATCH 0/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-07-16T00:07:38Z","receivedAt":"2025-07-16T00:07:41Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> Use prio_queue to improve worst-case performance at the cost of slightly\n> worse best-case performance. Then add and use prio_queue_replace() to\n> recover that loss.\n\nWould change in the tiebreaking behaviour (aka sort stability) also\na cost of this change, as this swaps use of sorted linearly linked\nlist with priority queue?\n"},{"id":"522067","messageId":"20250716050540.GB1396022@coredump.intra.peff.net","threadId":"63797","inReplyTo":"bfb0a65d-c9dd-47d9-a88d-9fec43538b0c@web.de","subject":"Re: [PATCH 1/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-07-16T05:05:40Z","receivedAt":"2025-07-16T05:05:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 15, 2025 at 04:51:07PM +0200, René Scharfe wrote:\n\n> pop_most_recent_commit() calls commit_list_insert_by_date(), which and\n> is itself called in a loop, which can lead to quadratic complexity.\n> Replace the commit_list with a prio_queue to ensure logarithmic worst\n> case complexity and convert all three users.\n\nI guess I'm cc'd because of my frequent complains about the quadratic\nnature of our commit lists? :)\n\nMostly I asked because I had to look at pop_most_recent_commit() to see\nwhat operation would be made faster here. Looks like it's mostly \":/\",\nbut maybe also fetch's mark_recent_complete_commits()? I guess we might\nhit that if you have a huge number of refs?\n\nAnyway, I am in support of the direction regardless.\n\nI actually have a series turning rev_info.commits into a prio_queue\nwhich I need to polish up (mostly just writing commit messages; I've\nbeen running with it for almost 2 years without trouble). Ironically it\ndoes not touch this spot, as these commit lists are formed on their own.\n\nThe patch itself looks reasonable. I think here:\n\n> @@ -1461,7 +1462,7 @@ static int get_oid_oneline(struct repository *r,\n> \t\t\t const char *prefix, struct object_id *oid,\n> \t\t\t const struct commit_list *list)\n> {\n> -\tstruct commit_list *copy = NULL, **copy_tail = ©\n> +\tstruct prio_queue copy = { compare_commits_by_commit_date };\n> \tconst struct commit_list *l;\n> \tint found = 0;\n> \tint negative = 0;\n> @@ -1483,9 +1484,9 @@ static int get_oid_oneline(struct repository *r,\n> \n> \tfor (l = list; l; l = l->next) {\n> \t\tl->item->object.flags |= ONELINE_SEEN;\n> -\t\tcopy_tail = &commit_list_insert(l->item, copy_tail)->next;\n> +\t\tprio_queue_put(©, l->item);\n> \t}\n> -\twhile (copy) {\n> +\twhile (copy.nr) {\n> \t\tconst char *p, *buf;\n> \t\tstruct commit *commit;\n> \t\tint matches;\n\nour callers are always generating and passing in a list. So we could\navoid the overhead of allocating the list in the first place by just\ntaking a prio_queue. But maybe it gets weird with clearing the\nONELINE_SEEN marks? We make a copy even in the current code so that we\ncan call clear_commit_marks() on the complete set.\n\nI guess we could add them to an array or something, but that probably\nends up being roughly the same amount of work.\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 1234567890 +0000\" &&\n> +\t\techo \"data < +\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 1234567890 +0000\" &&\n> +\t\techo \"data < +\t\techo \"$mark\" &&\n> +\t\techo \"EOF\" &&\n> +\t\techo \"from :$mark1\" &&\n> +\t\techo \"merge :$mark2\"\n> +\tfi\n> +}\n\nThis took some brain cycles to decipher. It looks like we'll make\n2^$level commits in a filled tree? It might be worth a brief comment\ndescribing the goal (and maybe even giving an example graph drawing for\nN=3 or something, though it gets out of hand quickly).\n\n> +test_perf \"rev-parse ':/$(cat needle)'\" \"\n> +\tgit rev-parse ':/$(cat needle)' >actual\n> +\"\n\nHmm, usually we frown on putting snippets inside double-quotes because\nit's so easy to accidentally interpolate outside of the test_eval. But\nmaybe this is short enough to be OK. I guess you did it here especially\nso that the title is a nice \":/65535\" and not the opaque \"$(cat\nneedle)\".\n\n-Peff\n"},{"id":"522069","messageId":"20250716050933.GC1396022@coredump.intra.peff.net","threadId":"63797","inReplyTo":"cbabed69-b44a-4920-9a56-e81b404be2de@web.de","subject":"Re: [PATCH 2/3] prio-queue: add prio_queue_replace()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-07-16T05:09:33Z","receivedAt":"2025-07-16T05:09:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 15, 2025 at 04:51:22PM +0200, René Scharfe wrote:\n\n> Add a function to replace the top element of the queue that basically\n> does the same as prio_queue_get() followed by prio_queue_put(), but\n> without the work by prio_queue_get() to rebalance the heap. It can be\n> used to optimize loops that get one element and then immediately add\n> another one. That's common e.g., with commit history traversal, where\n> we get out a commit and then put in its parents.\n\nHmm. But surely we still need to rebalance the heap after adding an\nelement? And indeed, we still call the new sift_down_root() function.\n\nBut I guess we are getting away without the \"bubble up\" operation that\nput would do? So we are doing half as much work (but still big-O the\nsame)?\n\n-Peff\n"},{"id":"522070","messageId":"20250716051533.GD1396022@coredump.intra.peff.net","threadId":"63797","inReplyTo":"xmqqv7ntdmlx.fsf@gitster.g","subject":"Re: [PATCH 0/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-07-16T05:15:33Z","receivedAt":"2025-07-16T05:15:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 15, 2025 at 05:07:38PM -0700, Junio C Hamano wrote:\n\n> René Scharfe writes:\n> \n> > Use prio_queue to improve worst-case performance at the cost of slightly\n> > worse best-case performance. Then add and use prio_queue_replace() to\n> > recover that loss.\n> \n> Would change in the tiebreaking behaviour (aka sort stability) also\n> a cost of this change, as this swaps use of sorted linearly linked\n> list with priority queue?\n\nThe prio_queue uses insertion order as a tie-breaker for stability (with\nearlier entries coming first). For building the initial queue from the\nlist, I think that is obviously fine (we feed them in sorted order,\nwhich the prio queue will retain). For inserting while we walk the list,\nwe'll produce the same results as long as the original code always\ninserted new entries after existing ones (in the case of a tie on commit\ndate, that is).\n\nAnd I think that is the case, since commit_list_insert_by_date() does\nthis:\n\n while ((p = *pp) != NULL) {\n if (p->item->date < item->date) {\n break;\n }\n pp = &p->next;\n }\n return commit_list_insert(item, pp);\n\nSo we only insert once we have found an item in the list _after_ us,\nretaining the same order.\n\nBut hopefully somebody can double check my logic, as it is quite\npossible I got something reversed above. ;)\n\n-Peff\n"},{"id":"522079","messageId":"298dd1d6-7756-4ecb-9202-d77491541253@web.de","threadId":"63797","inReplyTo":"20250716050933.GC1396022@coredump.intra.peff.net","subject":"Re: [PATCH 2/3] prio-queue: add prio_queue_replace()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-07-16T09:38:44Z","receivedAt":"2025-07-16T09:38:52Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"On 7/16/25 7:09 AM, Jeff King wrote:\n> On Tue, Jul 15, 2025 at 04:51:22PM +0200, René Scharfe wrote:\n> \n>> Add a function to replace the top element of the queue that basically\n>> does the same as prio_queue_get() followed by prio_queue_put(), but\n>> without the work by prio_queue_get() to rebalance the heap. It can be\n>> used to optimize loops that get one element and then immediately add\n>> another one. That's common e.g., with commit history traversal, where\n>> we get out a commit and then put in its parents.\n> \n> Hmm. But surely we still need to rebalance the heap after adding an\n> element? And indeed, we still call the new sift_down_root() function.\n\nYes.\n\n> But I guess we are getting away without the \"bubble up\" operation that\n> put would do? So we are doing half as much work (but still big-O the\n> same)?\n\nYes.\n\nI thought about building this optimization into prio_queue_get(), but\nthat would require prio_queue_peek() and prio_queue_put() to be adjusted\nas well and all prio_queue users would have to be either made aware of\nthe not-fully-heapified state, or prevented from accessing prio_queue\nproperties like .nr and .array. Adding a new function seemed like the\nsimplest and safest way for now.\n\nRené\n\n"},{"id":"522080","messageId":"5a25d830-0825-4b28-8763-2be342d2b6a3@web.de","threadId":"63797","inReplyTo":"20250716051533.GD1396022@coredump.intra.peff.net","subject":"Re: [PATCH 0/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-07-16T09:38:39Z","receivedAt":"2025-07-16T09:38:53Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"On 7/16/25 7:15 AM, Jeff King wrote:\n> On Tue, Jul 15, 2025 at 05:07:38PM -0700, Junio C Hamano wrote:\n> \n>> René Scharfe writes:\n>>\n>>> Use prio_queue to improve worst-case performance at the cost of slightly\n>>> worse best-case performance. Then add and use prio_queue_replace() to\n>>> recover that loss.\n>>\n>> Would change in the tiebreaking behaviour (aka sort stability) also\n>> a cost of this change, as this swaps use of sorted linearly linked\n>> list with priority queue?\n> \n> The prio_queue uses insertion order as a tie-breaker for stability (with\n> earlier entries coming first). For building the initial queue from the\n> list, I think that is obviously fine (we feed them in sorted order,\n> which the prio queue will retain). For inserting while we walk the list,\n> we'll produce the same results as long as the original code always\n> inserted new entries after existing ones (in the case of a tie on commit\n> date, that is).\n> \n> And I think that is the case, since commit_list_insert_by_date() does\n> this:\n> \n> while ((p = *pp) != NULL) {\n> if (p->item->date < item->date) {\n> break;\n> }\n> pp = &p->next;\n> }\n> return commit_list_insert(item, pp);\n> \n> So we only insert once we have found an item in the list _after_ us,\n> retaining the same order.\n> \n> But hopefully somebody can double check my logic, as it is quite\n> possible I got something reversed above. ;)\nYes, commit_list_insert_by_date() is stable, as it inserts commits after\nones with the same date. Items are popped from the top, so this ensures\nFIFO behavior for commits with the same date.\n\nprio_queue ensures stability using an ID and favors lower ones, so it\nprovides the same order.\n\nWe should add unit tests for that, no?\n\nRené\n\n"},{"id":"522081","messageId":"2cec288f-e632-431d-aba0-e98798b833ad@web.de","threadId":"63797","inReplyTo":"xmqqh5zdgp6r.fsf@gitster.g","subject":"Re: [PATCH 3/3] commit: use prio_queue_replace() in pop_most_recent_commit()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-07-16T09:38:46Z","receivedAt":"2025-07-16T09:38:57Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"On 7/15/25 10:43 PM, Junio C Hamano wrote:\n> René Scharfe writes:\n> \n>> diff --git a/commit.c b/commit.c\n>> index 0200759aaa..8244221b30 100644\n>> --- a/commit.c\n>> +++ b/commit.c\n>> @@ -742,17 +742,24 @@ void commit_list_sort_by_date(struct commit_list **list)\n>> struct commit *pop_most_recent_commit(struct prio_queue *queue,\n>> \t\t\t\t unsigned int mark)\n>> {\n>> -\tstruct commit *ret = prio_queue_get(queue);\n>> +\tstruct commit *ret = prio_queue_peek(queue);\n>> +\tint delete_pending = 1;\n> \n> Briefly I was puzzled by the name (I would have called first-parent\n> since the logic was \"we treat first parent specially by using\n> replace instead of get/put\"), but the variable signals \"instead of\n> get to remove the item from the queue, we just peeked, so we need to\n> remove it later\" with its name, which is understandable.\n\nIndeed, we're just interested in the removal part of prio_queue_get()\nhere, as we have done the cheap half (the peeking) already. We don't\nhave a prio_queue_delete(). Adding one would perhaps add some clarity\nhere, but also widen the interface and probably not bring much of a\nperformance gain.\n\nSo perhaps calling the variable get_pending like the prio_queue_get()\nthat we end up invoking would reduce the initial puzzlement?\n\n> \n>> \tstruct commit_list *parents = ret->parents;\n>> \n>> \twhile (parents) {\n>> \t\tstruct commit *commit = parents->item;\n>> \t\tif (!repo_parse_commit(the_repository, commit) && !(commit->object.flags & mark)) {\n>> \t\t\tcommit->object.flags |= mark;\n>> -\t\t\tprio_queue_put(queue, commit);\n>> +\t\t\tif (delete_pending)\n>> +\t\t\t\tprio_queue_replace(queue, commit);\n>> +\t\t\telse\n>> +\t\t\t\tprio_queue_put(queue, commit);\n>> +\t\t\tdelete_pending = 0;\n>> \t\t}\n>> \t\tparents = parents->next;\n>> \t}\n>> +\tif (delete_pending)\n>> +\t\tprio_queue_get(queue);\n>> \treturn ret;\n>> }\n\n"},{"id":"522086","messageId":"3f24210a-cd96-4c2c-9d55-1f0ebd7bbff5@web.de","threadId":"63797","inReplyTo":"d2myew7nonfrelrwplpypexvcrktmjdlsccobjvx3dydvhnlar@bin5ol2vj3xs","subject":"Re: [PATCH 1/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-07-16T09:39:29Z","receivedAt":"2025-07-16T09:39:31Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"On 7/15/25 10:47 PM, Justin Tobler wrote:\n> On 25/07/15 04:51PM, René Scharfe wrote:\n>> pop_most_recent_commit() calls commit_list_insert_by_date(), which and\n> \n> Did you mean?\n> \n> s/which and/which/\n\nOh, yes.\n\n>> is itself called in a loop, which can lead to quadratic complexity.\n>> Replace the commit_list with a prio_queue to ensure logarithmic worst\n>> case complexity and convert all three users.\n> \n> If I understand correctly, `pop_most_recent_commit()` removes the most\n> recent commit from a list of commits sorted by date and then inserts\n> each of the removed commit's parents into the list while maintaining\n> date order. Iterating through `struct commit_list` every time to find\n> where to insert each parent parent leads to quadratic complexity. For\n> repositories with many merge commits, this could scale poorly.\n\nRight.\n\n>> Add a performance test that exercises one of them using a pathological\n>> history that consists of 50% merges and 50% root commits to demonstrate\n>> the speedup:\n>>\n>> Test v2.50.1 HEAD\n>> ----------------------------------------------------------------------\n>> 1501.2: rev-parse ':/65535' 2.48(2.47+0.00) 0.20(0.19+0.00) -91.9%\n>>\n>> Alas, sane histories don't benefit from the conversion much, and\n>> traversing Git's own history takes a 1% performance hit on my machine:\n> \n> As \"normal\" repositories don't benefit here, it might be nice to more\n> explicitly mention the the types of repositories that do benefit.\n\nGood idea.\n\n>> diff --git a/commit.h b/commit.h\n>> index 70c870dae4..9630c076d6 100644\n>> --- a/commit.h\n>> +++ b/commit.h\n>> @@ -201,10 +201,10 @@ const char *repo_logmsg_reencode(struct repository *r,\n>> \n>> const char *skip_blank_lines(const char *msg);\n>> \n>> -/** Removes the first commit from a list sorted by date, and adds all\n>> - * of its parents.\n>> - **/\n>> -struct commit *pop_most_recent_commit(struct commit_list **list,\n>> +struct prio_queue;\n>> +\n>> +/* Removes the first commit from a prio_queue and adds its parents. */\n>> +struct commit *pop_most_recent_commit(struct prio_queue *queue,\n>> \t\t\t\t unsigned int mark);\n> \n> Previously, `pop_most_recent_commit()` would ensure commits inserted in\n> the list were done it date order. Now this depends on how the caller has\n> configured the `struct prio_queue`. This is fine though as previously\n> the caller was required to ensure the list was sorted to begin with\n> otherwise it wouldn't work properly.\n\nIndeed.\n\nRené\n\n"},{"id":"522087","messageId":"b0950e32-b4fa-4aff-8b5c-58c734b880b2@web.de","threadId":"63797","inReplyTo":"20250716050540.GB1396022@coredump.intra.peff.net","subject":"Re: [PATCH 1/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-07-16T09:39:49Z","receivedAt":"2025-07-16T09:39:52Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"On 7/16/25 7:05 AM, Jeff King wrote:\n> On Tue, Jul 15, 2025 at 04:51:07PM +0200, René Scharfe wrote:\n> \n>> pop_most_recent_commit() calls commit_list_insert_by_date(), which and\n>> is itself called in a loop, which can lead to quadratic complexity.\n>> Replace the commit_list with a prio_queue to ensure logarithmic worst\n>> case complexity and convert all three users.\n> \n> I guess I'm cc'd because of my frequent complains about the quadratic\n> nature of our commit lists? :)\n\nAnd because you introduced prio_queue.\n\n> Mostly I asked because I had to look at pop_most_recent_commit() to see\n> what operation would be made faster here. Looks like it's mostly \":/\",\n> but maybe also fetch's mark_recent_complete_commits()? I guess we might\n> hit that if you have a huge number of refs?\n\nThe :/ handling was the easiest to test for me. fetch_pack() and\nwalker_fetch() require some server side to set up, which seems not worth\nit just to demonstrate quadratic behavior. Having thousands of refs\nwould make the list long enough to notice, as would having lots of\nmerges.\n\nMy general idea is to get rid of commit_list_insert_by_date() eventually\nto avoid quadratic complexity.\n\n> I actually have a series turning rev_info.commits into a prio_queue\n> which I need to polish up (mostly just writing commit messages; I've\n> been running with it for almost 2 years without trouble). Ironically it\n> does not touch this spot, as these commit lists are formed on their own.\n\nThat is not a coincidence. I had a look at that series and tried to\nreach its goals while keeping rev_info.commits a commit_list. Why?\nMostly being vaguely uncomfortable with prio_queue' memory overhead,\nlack of type safety and dual use as a stack. I still used it, but only\nas local variable, not in the central struct rev_info.\n\nAnyway, I failed; revision.c::get_revision_1() took an 8% performance\nhit in my versions and none in yours, and I couldn't figure out why.\nPerhaps I should revisit it with the new prio_queue_replace() in hand,\nhmm.. For now I try to salvage the commit_list_insert_by_date()\nreplacement work outside of revision.c from that effort. \n\n> The patch itself looks reasonable. I think here:\n> \n>> @@ -1461,7 +1462,7 @@ static int get_oid_oneline(struct repository *r,\n>> \t\t\t const char *prefix, struct object_id *oid,\n>> \t\t\t const struct commit_list *list)\n>> {\n>> -\tstruct commit_list *copy = NULL, **copy_tail = ©\n>> +\tstruct prio_queue copy = { compare_commits_by_commit_date };\n>> \tconst struct commit_list *l;\n>> \tint found = 0;\n>> \tint negative = 0;\n>> @@ -1483,9 +1484,9 @@ static int get_oid_oneline(struct repository *r,\n>> \n>> \tfor (l = list; l; l = l->next) {\n>> \t\tl->item->object.flags |= ONELINE_SEEN;\n>> -\t\tcopy_tail = &commit_list_insert(l->item, copy_tail)->next;\n>> +\t\tprio_queue_put(©, l->item);\n>> \t}\n>> -\twhile (copy) {\n>> +\twhile (copy.nr) {\n>> \t\tconst char *p, *buf;\n>> \t\tstruct commit *commit;\n>> \t\tint matches;\n> \n> our callers are always generating and passing in a list. So we could\n> avoid the overhead of allocating the list in the first place by just\n> taking a prio_queue. But maybe it gets weird with clearing the\n> ONELINE_SEEN marks? We make a copy even in the current code so that we\n> can call clear_commit_marks() on the complete set.\n> \n> I guess we could add them to an array or something, but that probably\n> ends up being roughly the same amount of work.\nRight, if get_oid_oneline() gets handed a prio_queue, it would need to\ncopy all commits to a list or array for marks clearing at the end. I\ndon't see a way around having both. And I doubt there would be much of\na difference between list and array here, but could be convinced by\nnumbers. ;)\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 1234567890 +0000\" &&\n>> +\t\techo \"data <> +\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 1234567890 +0000\" &&\n>> +\t\techo \"data <> +\t\techo \"$mark\" &&\n>> +\t\techo \"EOF\" &&\n>> +\t\techo \"from :$mark1\" &&\n>> +\t\techo \"merge :$mark2\"\n>> +\tfi\n>> +}\n> \n> This took some brain cycles to decipher. It looks like we'll make\n> 2^$level commits in a filled tree? It might be worth a brief comment\n> describing the goal (and maybe even giving an example graph drawing for\n> N=3 or something, though it gets out of hand quickly).\n\nThe goal is to have lots of merges, to make the list that\npop_most_recent_commit() works on long (each pop adds back two parents).\n\nThe script builds a binary tree of merges, with root commits (without\nparents) as leaf nodes. (The nomenclature is a bit weird because we\ncall the child nodes parent commits.) So it creates 2^($level-1) root\ncommits and 2^($level-1)-1 two-way merges stacked on top.\n\n _1_\n / \\\n 2 3\n / \\ / \\\n4 5 6 7\n\nThe numbers are the marks; 1 to 3 are merges (have two parents), 4 to 7\nare root commits.\n\n>> +test_perf \"rev-parse ':/$(cat needle)'\" \"\n>> +\tgit rev-parse ':/$(cat needle)' >actual\n>> +\"\n> \n> Hmm, usually we frown on putting snippets inside double-quotes because\n> it's so easy to accidentally interpolate outside of the test_eval. But\n> maybe this is short enough to be OK. I guess you did it here especially\n> so that the title is a nice \":/65535\" and not the opaque \"$(cat\n> needle)\".\nThe first one allowed me to check whether the setup step created the\nexpected number of commits and seems kind of interesting for people\nrunning the test. The second one could be switched to be evaluated at\ntest_eval time, but that would make it harder to see that title and\ntest do the same. We could strip out the quotes:\n\n test_perf \"rev-parse :/$(cat needle)\" '\n git rev-parse :/$(cat needle) >actual\n '\n\nRené\n\n"},{"id":"522112","messageId":"xmqqldoodwcw.fsf@gitster.g","threadId":"63797","inReplyTo":"20250716051533.GD1396022@coredump.intra.peff.net","subject":"Re: [PATCH 0/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-07-16T14:49:19Z","receivedAt":"2025-07-16T14:49:22Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Tue, Jul 15, 2025 at 05:07:38PM -0700, Junio C Hamano wrote:\n>\n>> René Scharfe writes:\n>> \n>> > Use prio_queue to improve worst-case performance at the cost of slightly\n>> > worse best-case performance. Then add and use prio_queue_replace() to\n>> > recover that loss.\n>> \n>> Would change in the tiebreaking behaviour (aka sort stability) also\n>> a cost of this change, as this swaps use of sorted linearly linked\n>> list with priority queue?\n>\n> The prio_queue uses insertion order as a tie-breaker for stability (with\n> earlier entries coming first). For building the initial queue from the\n> list, I think that is obviously fine (we feed them in sorted order,\n> which the prio queue will retain).\n\nOK, then everything looks great. Thanks.\n"},{"id":"522132","messageId":"xmqqtt3b93ls.fsf@gitster.g","threadId":"63797","inReplyTo":"bfb0a65d-c9dd-47d9-a88d-9fec43538b0c@web.de","subject":"Re: [PATCH 1/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-07-16T22:23:59Z","receivedAt":"2025-07-16T22:24:02Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> t/perf/p1501-rev-parse-oneline.sh | 55 +++++++++++++++++++++++++++++++\n> create mode 100755 t/perf/p1501-rev-parse-oneline.sh\n\nThis unfortunately calls for something like.\n\nTonight's integration cycle I have this on top of your series\nin 'seen'.\n\nSubject: [PATCH] fixup! commit: convert pop_most_recent_commit() to prio_queue\n\n t/meson.build | 1 +\n 1 file changed, 1 insertion(+)\n\ndiff --git a/t/meson.build b/t/meson.build\nindex d052fc3e23..b39f6d008d 100644\n--- a/t/meson.build\n+++ b/t/meson.build\n@@ -1117,6 +1117,7 @@ benchmarks = [\n 'perf/p1450-fsck.sh',\n 'perf/p1451-fsck-skip-list.sh',\n 'perf/p1500-graph-walks.sh',\n+ 'perf/p1501-rev-parse-oneline.sh',\n 'perf/p2000-sparse-operations.sh',\n 'perf/p3400-rebase.sh',\n 'perf/p3404-rebase-interactive.sh',\n-- \n2.50.1-447-g1e759a1f67\n\n"},{"id":"522177","messageId":"03b2e5db-1fb8-4c38-8448-ad320ab7f70f@web.de","threadId":"63797","inReplyTo":"b0950e32-b4fa-4aff-8b5c-58c734b880b2@web.de","subject":"Re: [PATCH 1/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-07-17T08:22:36Z","receivedAt":"2025-07-17T08:22:39Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"On 7/16/25 11:39 AM, René Scharfe wrote:\n> On 7/16/25 7:05 AM, Jeff King wrote:\n> \n>> I actually have a series turning rev_info.commits into a prio_queue\n>> which I need to polish up (mostly just writing commit messages; I've\n>> been running with it for almost 2 years without trouble). Ironically it\n>> does not touch this spot, as these commit lists are formed on their own.\n> \n> That is not a coincidence. I had a look at that series and tried to\n> reach its goals while keeping rev_info.commits a commit_list. Why?\n> Mostly being vaguely uncomfortable with prio_queue' memory overhead,\n> lack of type safety and dual use as a stack. I still used it, but only\n> as local variable, not in the central struct rev_info.\n> \n> Anyway, I failed; revision.c::get_revision_1() took an 8% performance\n> hit in my versions and none in yours, and I couldn't figure out why.\n> Perhaps I should revisit it with the new prio_queue_replace() in hand,\n> hmm..\nChecked now, and it's still slower. So I don't see an alternative to\nmaking rev_info.commits a prio_queue.\n\nRené\n\n"},{"id":"522178","messageId":"1404fe4a-9b7f-4a7f-905c-e36b2ca45858@web.de","threadId":"63797","inReplyTo":"xmqqtt3b93ls.fsf@gitster.g","subject":"Re: [PATCH 1/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-07-17T08:22:31Z","receivedAt":"2025-07-17T08:22:40Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"On 7/17/25 12:23 AM, Junio C Hamano wrote:\n> René Scharfe writes:\n> \n>> t/perf/p1501-rev-parse-oneline.sh | 55 +++++++++++++++++++++++++++++++\n>> create mode 100755 t/perf/p1501-rev-parse-oneline.sh\n> \n> This unfortunately calls for something like.\n> \n> Tonight's integration cycle I have this on top of your series\n> in 'seen'.\n> \n> Subject: [PATCH] fixup! commit: convert pop_most_recent_commit() to prio_queue\n> \n> t/meson.build | 1 +\n> 1 file changed, 1 insertion(+)\n> \n> diff --git a/t/meson.build b/t/meson.build\n> index d052fc3e23..b39f6d008d 100644\n> --- a/t/meson.build\n> +++ b/t/meson.build\n> @@ -1117,6 +1117,7 @@ benchmarks = [\n> 'perf/p1450-fsck.sh',\n> 'perf/p1451-fsck-skip-list.sh',\n> 'perf/p1500-graph-walks.sh',\n> + 'perf/p1501-rev-parse-oneline.sh',\n> 'perf/p2000-sparse-operations.sh',\n> 'perf/p3400-rebase.sh',\n> 'perf/p3404-rebase-interactive.sh',\n\nOh, OK, thanks. Will include it in v2.\n\nRené\n\n"},{"id":"522180","messageId":"4ed087c9-0229-4219-8cbd-55f9ee79ca35@web.de","threadId":"63797","inReplyTo":"298dd1d6-7756-4ecb-9202-d77491541253@web.de","subject":"Re: [PATCH 2/3] prio-queue: add prio_queue_replace()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-07-17T09:20:53Z","receivedAt":"2025-07-17T09:20:58Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"On 7/16/25 11:38 AM, René Scharfe wrote:\n> On 7/16/25 7:09 AM, Jeff King wrote:\n>> On Tue, Jul 15, 2025 at 04:51:22PM +0200, René Scharfe wrote:\n>>\n>>> Add a function to replace the top element of the queue that basically\n>>> does the same as prio_queue_get() followed by prio_queue_put(), but\n>>> without the work by prio_queue_get() to rebalance the heap. It can be\n>>> used to optimize loops that get one element and then immediately add\n>>> another one. That's common e.g., with commit history traversal, where\n>>> we get out a commit and then put in its parents.\n>>\n>> Hmm. But surely we still need to rebalance the heap after adding an\n>> element? And indeed, we still call the new sift_down_root() function.\n> \n> Yes.\n> \n>> But I guess we are getting away without the \"bubble up\" operation that\n>> put would do? So we are doing half as much work (but still big-O the\n>> same)?\n> \n> Yes.\n> \n> I thought about building this optimization into prio_queue_get(), but\n> that would require prio_queue_peek() and prio_queue_put() to be adjusted\n> as well and all prio_queue users would have to be either made aware of\n> the not-fully-heapified state, or prevented from accessing prio_queue\n> properties like .nr and .array.\n\nHere's what that would like like. .nr and .array elements are kept\nconsistent at all times, but the root item is not in heap order after a\nprio_queue_get(). That's good enough to enumerate all prio_queue items\nlike commit-reach.c::queue_has_nonstale() or\nnegotiator/skipping.c::push_parent() do.\n\nNot sure what other weird patterns people might come up with that\nrequire touching the innards of a prio_queue directly. I don't even\nunderstand why negotiator/skipping.c::push_parent() does a linear\nsearch for each parent -- isn't that expensive? Setting an object\nflag on prio_queue_put() and clearing it on prio_queue_get() or a\nusing a commit_slab seem to be better options from a very cursory\nglance.\n\nAnyway, here's what doing prio_queue_replace() automatically could look\nlike. I almost talked myself into using it now. Any objections, ideas\non how to make it safer or clearer, other thoughts?\n\nRené\n\n---\n prio-queue.c | 52 +++++++++++++++++++++++++++++++++++++++-------------\n prio-queue.h | 1 +\n 2 files changed, 40 insertions(+), 13 deletions(-)\n\ndiff --git a/prio-queue.c b/prio-queue.c\nindex ec33ac27db..265663e116 100644\n--- a/prio-queue.c\n+++ b/prio-queue.c\n@@ -34,12 +34,46 @@ void clear_prio_queue(struct prio_queue *queue)\n \tqueue->nr = 0;\n \tqueue->alloc = 0;\n \tqueue->insertion_ctr = 0;\n+\tqueue->sift_down_root_pending = false;\n+}\n+\n+static void sift_down_root(struct prio_queue *queue)\n+{\n+\tsize_t ix, child;\n+\n+\t/* Push down the one at the root */\n+\tfor (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {\n+\t\tchild = ix * 2 + 1; /* left */\n+\t\tif (child + 1 < queue->nr &&\n+\t\t compare(queue, child, child + 1) >= 0)\n+\t\t\tchild++; /* use right child */\n+\n+\t\tif (compare(queue, ix, child) <= 0)\n+\t\t\tbreak;\n+\n+\t\tswap(queue, child, ix);\n+\t}\n+\tqueue->sift_down_root_pending = false;\n }\n \n void prio_queue_put(struct prio_queue *queue, void *thing)\n {\n \tsize_t ix, parent;\n \n+\tif (queue->sift_down_root_pending) {\n+\t\t/*\n+\t\t * Restore the original heap size. The last item is\n+\t\t * still in the right place.\n+\t\t */\n+\t\tqueue->nr++;\n+\n+\t\t/* Now fill the hole at the root with the new item. */\n+\t\tqueue->array[0].ctr = queue->insertion_ctr++;\n+\t\tqueue->array[0].data = thing;\n+\t\tsift_down_root(queue);\n+\t\treturn;\n+\t}\n+\n \t/* Append at the end */\n \tALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);\n \tqueue->array[queue->nr].ctr = queue->insertion_ctr++;\n@@ -61,31 +95,21 @@ void prio_queue_put(struct prio_queue *queue, void *thing)\n void *prio_queue_get(struct prio_queue *queue)\n {\n \tvoid *result;\n-\tsize_t ix, child;\n \n \tif (!queue->nr)\n \t\treturn NULL;\n \tif (!queue->compare)\n \t\treturn queue->array[--queue->nr].data; /* LIFO */\n \n+\tif (queue->sift_down_root_pending)\n+\t\tsift_down_root(queue);\n \tresult = queue->array[0].data;\n \tif (!--queue->nr)\n \t\treturn result;\n \n \tqueue->array[0] = queue->array[queue->nr];\n \n-\t/* Push down the one at the root */\n-\tfor (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {\n-\t\tchild = ix * 2 + 1; /* left */\n-\t\tif (child + 1 < queue->nr &&\n-\t\t compare(queue, child, child + 1) >= 0)\n-\t\t\tchild++; /* use right child */\n-\n-\t\tif (compare(queue, ix, child) <= 0)\n-\t\t\tbreak;\n-\n-\t\tswap(queue, child, ix);\n-\t}\n+\tqueue->sift_down_root_pending = true;\n \treturn result;\n }\n \n@@ -95,5 +119,7 @@ void *prio_queue_peek(struct prio_queue *queue)\n \t\treturn NULL;\n \tif (!queue->compare)\n \t\treturn queue->array[queue->nr - 1].data;\n+\tif (queue->sift_down_root_pending)\n+\t\tsift_down_root(queue);\n \treturn queue->array[0].data;\n }\ndiff --git a/prio-queue.h b/prio-queue.h\nindex 38d032636d..6d8d268f41 100644\n--- a/prio-queue.h\n+++ b/prio-queue.h\n@@ -32,6 +32,7 @@ struct prio_queue {\n \tvoid *cb_data;\n \tsize_t alloc, nr;\n \tstruct prio_queue_entry *array;\n+\tbool sift_down_root_pending;\n };\n \n /*\n-- \n2.50.1\n\n"},{"id":"522272","messageId":"8ff40c56-368a-4347-aeae-2aca2cb6a5b2@web.de","threadId":"63797","inReplyTo":"bc079b3c-a472-4f5d-95ca-390f9de25196@web.de","subject":"[PATCH v2 0/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-07-18T09:09:04Z","receivedAt":"2025-07-18T09:09:13Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Use prio_queue to improve worst-case performance at the cost of slightly\nworse best-case performance. Then add and use prio_queue_replace() to\nrecover that loss.\n\nChanges since v2:\n- Mention that a prio_queue improves performance for merge-heavy\n histories in the commit message.\n- Add the new perf script to Meson build file.\n- Mention which kind of history we are aiming for and show its shape in\n a comment in the perf script.\n- Remove unnecessary quotes and use single quotes for the perf test\n code.\n- Rename the variable delete_pending to get_pending to align it with\n the concrete function prio_queue_get() instead of referring to the\n abstract concept of deletion, to improve readability.\n\n commit: convert pop_most_recent_commit() to prio_queue\n prio-queue: add prio_queue_replace()\n commit: use prio_queue_replace() in pop_most_recent_commit()\n\n commit.c | 14 ++++--\n commit.h | 8 ++--\n fetch-pack.c | 13 +++---\n object-name.c | 10 ++---\n prio-queue.c | 45 ++++++++++++++------\n prio-queue.h | 8 ++++\n t/meson.build | 1 +\n t/perf/p1501-rev-parse-oneline.sh | 71 +++++++++++++++++++++++++++++++\n t/unit-tests/u-prio-queue.c | 23 ++++++++++\n walker.c | 11 +++--\n 10 files changed, 170 insertions(+), 34 deletions(-)\n create mode 100755 t/perf/p1501-rev-parse-oneline.sh\n\nRange-diff against v1:\n1: d9c0d13801 ! 1: 5bff885d0f commit: convert pop_most_recent_commit() to prio_queue\n @@ Metadata\n ## Commit message ##\n commit: convert pop_most_recent_commit() to prio_queue\n \n - pop_most_recent_commit() calls commit_list_insert_by_date(), which and\n - is itself called in a loop, which can lead to quadratic complexity.\n - Replace the commit_list with a prio_queue to ensure logarithmic worst\n - case complexity and convert all three users.\n + pop_most_recent_commit() calls commit_list_insert_by_date() for parent\n + commits, which is itself called in a loop. This can lead to quadratic\n + complexity if there are many merges. Replace the commit_list with a\n + prio_queue to ensure logarithmic worst case complexity and convert all\n + three users.\n \n Add a performance test that exercises one of them using a pathological\n history that consists of 50% merges and 50% root commits to demonstrate\n @@ object-name.c: static enum get_oid_result get_oid_with_context_1(struct reposito\n \n \t\t\tfree_commit_list(list);\n \n + ## t/meson.build ##\n +@@ t/meson.build: benchmarks = [\n + 'perf/p1450-fsck.sh',\n + 'perf/p1451-fsck-skip-list.sh',\n + 'perf/p1500-graph-walks.sh',\n ++ 'perf/p1501-rev-parse-oneline.sh',\n + 'perf/p2000-sparse-operations.sh',\n + 'perf/p3400-rebase.sh',\n + 'perf/p3404-rebase-interactive.sh',\n +\n ## t/perf/p1501-rev-parse-oneline.sh (new) ##\n @@\n +#!/bin/sh\n @@ t/perf/p1501-rev-parse-oneline.sh (new)\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 @@ t/perf/p1501-rev-parse-oneline.sh (new)\n +\tsed -n -e \"s/^.* //p\" -e \"q\" needle\n +'\n +\n -+test_perf \"rev-parse ':/$(cat needle)'\" \"\n -+\tgit rev-parse ':/$(cat needle)' >actual\n -+\"\n ++test_perf \"rev-parse :/$(cat needle)\" '\n ++\tgit rev-parse :/$(cat needle) >actual\n ++'\n +\n +test_expect_success 'verify result' '\n +\ttest_cmp expect actual\n2: a4011d850c = 2: a2e57ca443 prio-queue: add prio_queue_replace()\n3: dc535e8b64 ! 3: 1cbea38524 commit: use prio_queue_replace() in pop_most_recent_commit()\n @@ commit.c: void commit_list_sort_by_date(struct commit_list **list)\n {\n -\tstruct commit *ret = prio_queue_get(queue);\n +\tstruct commit *ret = prio_queue_peek(queue);\n -+\tint delete_pending = 1;\n ++\tint get_pending = 1;\n \tstruct commit_list *parents = ret->parents;\n \n \twhile (parents) {\n @@ commit.c: void commit_list_sort_by_date(struct commit_list **list)\n \t\tif (!repo_parse_commit(the_repository, commit) && !(commit->object.flags & mark)) {\n \t\t\tcommit->object.flags |= mark;\n -\t\t\tprio_queue_put(queue, commit);\n -+\t\t\tif (delete_pending)\n ++\t\t\tif (get_pending)\n +\t\t\t\tprio_queue_replace(queue, commit);\n +\t\t\telse\n +\t\t\t\tprio_queue_put(queue, commit);\n -+\t\t\tdelete_pending = 0;\n ++\t\t\tget_pending = 0;\n \t\t}\n \t\tparents = parents->next;\n \t}\n -+\tif (delete_pending)\n ++\tif (get_pending)\n +\t\tprio_queue_get(queue);\n \treturn ret;\n }\n-- \n2.50.1\n"},{"id":"522273","messageId":"5d7c631a-ae94-4a59-b4ee-8161b5136d86@web.de","threadId":"63797","inReplyTo":"8ff40c56-368a-4347-aeae-2aca2cb6a5b2@web.de","subject":"[PATCH v2 1/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-07-18T09:39:06Z","receivedAt":"2025-07-18T09:39:15Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"pop_most_recent_commit() calls commit_list_insert_by_date() for parent\ncommits, which is itself called in a loop. This can lead to quadratic\ncomplexity if there are many merges. Replace the commit_list with a\nprio_queue to ensure logarithmic worst case complexity and convert all\nthree users.\n\nAdd a performance test that exercises one of them using a pathological\nhistory that consists of 50% merges and 50% root commits to demonstrate\nthe speedup:\n\nTest v2.50.1 HEAD\n----------------------------------------------------------------------\n1501.2: rev-parse ':/65535' 2.48(2.47+0.00) 0.20(0.19+0.00) -91.9%\n\nAlas, sane histories don't benefit from the conversion much, and\ntraversing Git's own history takes a 1% performance hit on my machine:\n\n $ hyperfine -w3 -L git ./git_2.50.1,./git '{git} rev-parse :/^Initial.revision'\n Benchmark 1: ./git_2.50.1 rev-parse :/^Initial.revision\n Time (mean ± σ): 1.071 s ± 0.004 s [User: 1.052 s, System: 0.017 s]\n Range (min … max): 1.067 s … 1.078 s 10 runs\n\n Benchmark 2: ./git rev-parse :/^Initial.revision\n Time (mean ± σ): 1.079 s ± 0.003 s [User: 1.060 s, System: 0.017 s]\n Range (min … max): 1.074 s … 1.083 s 10 runs\n\n Summary\n ./git_2.50.1 rev-parse :/^Initial.revision ran\n 1.01 ± 0.00 times faster than ./git rev-parse :/^Initial.revision\n\nSigned-off-by: René Scharfe \n---\n commit.c | 7 +--\n commit.h | 8 ++--\n fetch-pack.c | 13 +++---\n object-name.c | 10 ++---\n t/meson.build | 1 +\n t/perf/p1501-rev-parse-oneline.sh | 71 +++++++++++++++++++++++++++++++\n walker.c | 11 +++--\n 7 files changed, 100 insertions(+), 21 deletions(-)\n create mode 100755 t/perf/p1501-rev-parse-oneline.sh\n\ndiff --git a/commit.c b/commit.c\nindex 15115125c3..f4712ad9a7 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -31,6 +31,7 @@\n #include \"parse.h\"\n #include \"object-file.h\"\n #include \"object-file-convert.h\"\n+#include \"prio-queue.h\"\n \n static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **);\n \n@@ -739,17 +740,17 @@ void commit_list_sort_by_date(struct commit_list **list)\n \tcommit_list_sort(list, commit_list_compare_by_date);\n }\n \n-struct commit *pop_most_recent_commit(struct commit_list **list,\n+struct commit *pop_most_recent_commit(struct prio_queue *queue,\n \t\t\t\t unsigned int mark)\n {\n-\tstruct commit *ret = pop_commit(list);\n+\tstruct commit *ret = prio_queue_get(queue);\n \tstruct commit_list *parents = ret->parents;\n \n \twhile (parents) {\n \t\tstruct commit *commit = parents->item;\n \t\tif (!repo_parse_commit(the_repository, commit) && !(commit->object.flags & mark)) {\n \t\t\tcommit->object.flags |= mark;\n-\t\t\tcommit_list_insert_by_date(commit, list);\n+\t\t\tprio_queue_put(queue, commit);\n \t\t}\n \t\tparents = parents->next;\n \t}\ndiff --git a/commit.h b/commit.h\nindex 70c870dae4..9630c076d6 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -201,10 +201,10 @@ const char *repo_logmsg_reencode(struct repository *r,\n \n const char *skip_blank_lines(const char *msg);\n \n-/** Removes the first commit from a list sorted by date, and adds all\n- * of its parents.\n- **/\n-struct commit *pop_most_recent_commit(struct commit_list **list,\n+struct prio_queue;\n+\n+/* Removes the first commit from a prio_queue and adds its parents. */\n+struct commit *pop_most_recent_commit(struct prio_queue *queue,\n \t\t\t\t unsigned int mark);\n \n struct commit *pop_commit(struct commit_list **stack);\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 5e74235fc0..8ad5bf2931 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -34,6 +34,7 @@\n #include \"commit-graph.h\"\n #include \"sigchain.h\"\n #include \"mergesort.h\"\n+#include \"prio-queue.h\"\n \n static int transfer_unpack_limit = -1;\n static int fetch_unpack_limit = -1;\n@@ -601,7 +602,7 @@ static int find_common(struct fetch_negotiator *negotiator,\n \treturn count ? retval : 0;\n }\n \n-static struct commit_list *complete;\n+static struct prio_queue complete = { compare_commits_by_commit_date };\n \n static int mark_complete(const struct object_id *oid)\n {\n@@ -609,7 +610,7 @@ static int mark_complete(const struct object_id *oid)\n \n \tif (commit && !(commit->object.flags & COMPLETE)) {\n \t\tcommit->object.flags |= COMPLETE;\n-\t\tcommit_list_insert(commit, &complete);\n+\t\tprio_queue_put(&complete, commit);\n \t}\n \treturn 0;\n }\n@@ -626,9 +627,12 @@ static int mark_complete_oid(const char *refname UNUSED,\n static void mark_recent_complete_commits(struct fetch_pack_args *args,\n \t\t\t\t\t timestamp_t cutoff)\n {\n-\twhile (complete && cutoff <= complete->item->date) {\n+\twhile (complete.nr) {\n+\t\tstruct commit *item = prio_queue_peek(&complete);\n+\t\tif (item->date < cutoff)\n+\t\t\tbreak;\n \t\tprint_verbose(args, _(\"Marking %s as complete\"),\n-\t\t\t oid_to_hex(&complete->item->object.oid));\n+\t\t\t oid_to_hex(&item->object.oid));\n \t\tpop_most_recent_commit(&complete, COMPLETE);\n \t}\n }\n@@ -798,7 +802,6 @@ static void mark_complete_and_common_ref(struct fetch_negotiator *negotiator,\n \t\trefs_for_each_rawref(get_main_ref_store(the_repository),\n \t\t\t\t mark_complete_oid, NULL);\n \t\tfor_each_cached_alternate(NULL, mark_alternate_complete);\n-\t\tcommit_list_sort_by_date(&complete);\n \t\tif (cutoff)\n \t\t\tmark_recent_complete_commits(args, cutoff);\n \t}\ndiff --git a/object-name.c b/object-name.c\nindex ddafe7f9b1..41930609e3 100644\n--- a/object-name.c\n+++ b/object-name.c\n@@ -28,6 +28,7 @@\n #include \"commit-reach.h\"\n #include \"date.h\"\n #include \"object-file-convert.h\"\n+#include \"prio-queue.h\"\n \n static int get_oid_oneline(struct repository *r, const char *, struct object_id *,\n \t\t\t const struct commit_list *);\n@@ -1461,7 +1462,7 @@ static int get_oid_oneline(struct repository *r,\n \t\t\t const char *prefix, struct object_id *oid,\n \t\t\t const struct commit_list *list)\n {\n-\tstruct commit_list *copy = NULL, **copy_tail = ©\n+\tstruct prio_queue copy = { compare_commits_by_commit_date };\n \tconst struct commit_list *l;\n \tint found = 0;\n \tint negative = 0;\n@@ -1483,9 +1484,9 @@ static int get_oid_oneline(struct repository *r,\n \n \tfor (l = list; l; l = l->next) {\n \t\tl->item->object.flags |= ONELINE_SEEN;\n-\t\tcopy_tail = &commit_list_insert(l->item, copy_tail)->next;\n+\t\tprio_queue_put(©, l->item);\n \t}\n-\twhile (copy) {\n+\twhile (copy.nr) {\n \t\tconst char *p, *buf;\n \t\tstruct commit *commit;\n \t\tint matches;\n@@ -1507,7 +1508,7 @@ static int get_oid_oneline(struct repository *r,\n \tregfree(®ex);\n \tfor (l = list; l; l = l->next)\n \t\tclear_commit_marks(l->item, ONELINE_SEEN);\n-\tfree_commit_list(copy);\n+\tclear_prio_queue(©);\n \treturn found ? 0 : -1;\n }\n \n@@ -2061,7 +2062,6 @@ static enum get_oid_result get_oid_with_context_1(struct repository *repo,\n \t\t\tcb.list = &list;\n \t\t\trefs_for_each_ref(get_main_ref_store(repo), handle_one_ref, &cb);\n \t\t\trefs_head_ref(get_main_ref_store(repo), handle_one_ref, &cb);\n-\t\t\tcommit_list_sort_by_date(&list);\n \t\t\tret = get_oid_oneline(repo, name + 2, oid, list);\n \n \t\t\tfree_commit_list(list);\ndiff --git a/t/meson.build b/t/meson.build\nindex 1af289425d..660d780dcc 100644\n--- a/t/meson.build\n+++ b/t/meson.build\n@@ -1116,6 +1116,7 @@ benchmarks = [\n 'perf/p1450-fsck.sh',\n 'perf/p1451-fsck-skip-list.sh',\n 'perf/p1500-graph-walks.sh',\n+ 'perf/p1501-rev-parse-oneline.sh',\n 'perf/p2000-sparse-operations.sh',\n 'perf/p3400-rebase.sh',\n 'perf/p3404-rebase-interactive.sh',\ndiff --git a/t/perf/p1501-rev-parse-oneline.sh b/t/perf/p1501-rev-parse-oneline.sh\nnew file mode 100755\nindex 0000000000..538fa9c404\n--- /dev/null\n+++ b/t/perf/p1501-rev-parse-oneline.sh\n@@ -0,0 +1,71 @@\n+#!/bin/sh\n+\n+test_description='Test :/ object name notation'\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 1234567890 +0000\" &&\n+\t\techo \"data < 1234567890 +0000\" &&\n+\t\techo \"data <commits &&\n+\tsed -n -e \"s/ .*$//p\" -e \"q\" expect &&\n+\tsed -n -e \"s/^.* //p\" -e \"q\" needle\n+'\n+\n+test_perf \"rev-parse :/$(cat needle)\" '\n+\tgit rev-parse :/$(cat needle) >actual\n+'\n+\n+test_expect_success 'verify result' '\n+\ttest_cmp expect actual\n+'\n+\n+test_done\ndiff --git a/walker.c b/walker.c\nindex d131af04c7..8073754517 100644\n--- a/walker.c\n+++ b/walker.c\n@@ -14,6 +14,7 @@\n #include \"blob.h\"\n #include \"refs.h\"\n #include \"progress.h\"\n+#include \"prio-queue.h\"\n \n static struct object_id current_commit_oid;\n \n@@ -78,7 +79,7 @@ static int process_tree(struct walker *walker, struct tree *tree)\n #define SEEN\t\t(1U << 1)\n #define TO_SCAN\t\t(1U << 2)\n \n-static struct commit_list *complete = NULL;\n+static struct prio_queue complete = { compare_commits_by_commit_date };\n \n static int process_commit(struct walker *walker, struct commit *commit)\n {\n@@ -87,7 +88,10 @@ static int process_commit(struct walker *walker, struct commit *commit)\n \tif (repo_parse_commit(the_repository, commit))\n \t\treturn -1;\n \n-\twhile (complete && complete->item->date >= commit->date) {\n+\twhile (complete.nr) {\n+\t\tstruct commit *item = prio_queue_peek(&complete);\n+\t\tif (item->date < commit->date)\n+\t\t\tbreak;\n \t\tpop_most_recent_commit(&complete, COMPLETE);\n \t}\n \n@@ -233,7 +237,7 @@ static int mark_complete(const char *path UNUSED,\n \n \tif (commit) {\n \t\tcommit->object.flags |= COMPLETE;\n-\t\tcommit_list_insert(commit, &complete);\n+\t\tprio_queue_put(&complete, commit);\n \t}\n \treturn 0;\n }\n@@ -302,7 +306,6 @@ int walker_fetch(struct walker *walker, int targets, char **target,\n \tif (!walker->get_recover) {\n \t\trefs_for_each_ref(get_main_ref_store(the_repository),\n \t\t\t\t mark_complete, NULL);\n-\t\tcommit_list_sort_by_date(&complete);\n \t}\n \n \tfor (i = 0; i < targets; i++) {\n-- \n2.50.1\n"},{"id":"522274","messageId":"494e9686-e014-45f8-86d2-8dfcd6630f46@web.de","threadId":"63797","inReplyTo":"8ff40c56-368a-4347-aeae-2aca2cb6a5b2@web.de","subject":"[PATCH v2 3/3] commit: use prio_queue_replace() in pop_most_recent_commit(),MIME-Version: 1.0","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-07-18T09:39:11Z","receivedAt":"2025-07-18T09:39:16Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Optimize pop_most_recent_commit() by adding the first parent using the\nmore efficient prio_queue_peek() and prio_queue_replace() instead of\nprio_queue_get() and prio_queue_put().\n\nOn my machine this neutralizes the performance hit it took in Git's own\nrepository when we converted it to prio_queue two patches ago (git_pq):\n\n $ hyperfine -w3 -L git ./git_2.50.1,./git_pq,./git '{git} rev-parse :/^Initial.revision'\n Benchmark 1: ./git_2.50.1 rev-parse :/^Initial.revision\n Time (mean ± σ): 1.073 s ± 0.003 s [User: 1.053 s, System: 0.019 s]\n Range (min … max): 1.069 s … 1.078 s 10 runs\n\n Benchmark 2: ./git_pq rev-parse :/^Initial.revision\n Time (mean ± σ): 1.077 s ± 0.002 s [User: 1.057 s, System: 0.018 s]\n Range (min … max): 1.072 s … 1.079 s 10 runs\n\n Benchmark 3: ./git rev-parse :/^Initial.revision\n Time (mean ± σ): 1.069 s ± 0.003 s [User: 1.049 s, System: 0.018 s]\n Range (min … max): 1.065 s … 1.074 s 10 runs\n\n Summary\n ./git rev-parse :/^Initial.revision ran\n 1.00 ± 0.00 times faster than ./git_2.50.1 rev-parse :/^Initial.revision\n 1.01 ± 0.00 times faster than ./git_pq rev-parse :/^Initial.revision\n\nSigned-off-by: René Scharfe \n---\n commit.c | 11 +++++++++--\n 1 file changed, 9 insertions(+), 2 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex f4712ad9a7..ea84c8e7f6 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -743,17 +743,24 @@ void commit_list_sort_by_date(struct commit_list **list)\n struct commit *pop_most_recent_commit(struct prio_queue *queue,\n \t\t\t\t unsigned int mark)\n {\n-\tstruct commit *ret = prio_queue_get(queue);\n+\tstruct commit *ret = prio_queue_peek(queue);\n+\tint get_pending = 1;\n \tstruct commit_list *parents = ret->parents;\n \n \twhile (parents) {\n \t\tstruct commit *commit = parents->item;\n \t\tif (!repo_parse_commit(the_repository, commit) && !(commit->object.flags & mark)) {\n \t\t\tcommit->object.flags |= mark;\n-\t\t\tprio_queue_put(queue, commit);\n+\t\t\tif (get_pending)\n+\t\t\t\tprio_queue_replace(queue, commit);\n+\t\t\telse\n+\t\t\t\tprio_queue_put(queue, commit);\n+\t\t\tget_pending = 0;\n \t\t}\n \t\tparents = parents->next;\n \t}\n+\tif (get_pending)\n+\t\tprio_queue_get(queue);\n \treturn ret;\n }\n \n-- \n2.50.1\n"},{"id":"522275","messageId":"67346fb7-36eb-4682-ade1-4baee8c026e3@web.de","threadId":"63797","inReplyTo":"8ff40c56-368a-4347-aeae-2aca2cb6a5b2@web.de","subject":"[PATCH v2 2/3] prio-queue: add prio_queue_replace()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-07-18T09:39:14Z","receivedAt":"2025-07-18T09:39:19Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Add a function to replace the top element of the queue that basically\ndoes the same as prio_queue_get() followed by prio_queue_put(), but\nwithout the work by prio_queue_get() to rebalance the heap. It can be\nused to optimize loops that get one element and then immediately add\nanother one. That's common e.g., with commit history traversal, where\nwe get out a commit and then put in its parents.\n\nSigned-off-by: René Scharfe \n---\n prio-queue.c | 45 ++++++++++++++++++++++++++-----------\n prio-queue.h | 8 +++++++\n t/unit-tests/u-prio-queue.c | 23 +++++++++++++++++++\n 3 files changed, 63 insertions(+), 13 deletions(-)\n\ndiff --git a/prio-queue.c b/prio-queue.c\nindex ec33ac27db..9748528ce6 100644\n--- a/prio-queue.c\n+++ b/prio-queue.c\n@@ -58,22 +58,10 @@ void prio_queue_put(struct prio_queue *queue, void *thing)\n \t}\n }\n \n-void *prio_queue_get(struct prio_queue *queue)\n+static void sift_down_root(struct prio_queue *queue)\n {\n-\tvoid *result;\n \tsize_t ix, child;\n \n-\tif (!queue->nr)\n-\t\treturn NULL;\n-\tif (!queue->compare)\n-\t\treturn queue->array[--queue->nr].data; /* LIFO */\n-\n-\tresult = queue->array[0].data;\n-\tif (!--queue->nr)\n-\t\treturn result;\n-\n-\tqueue->array[0] = queue->array[queue->nr];\n-\n \t/* Push down the one at the root */\n \tfor (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {\n \t\tchild = ix * 2 + 1; /* left */\n@@ -86,6 +74,23 @@ void *prio_queue_get(struct prio_queue *queue)\n \n \t\tswap(queue, child, ix);\n \t}\n+}\n+\n+void *prio_queue_get(struct prio_queue *queue)\n+{\n+\tvoid *result;\n+\n+\tif (!queue->nr)\n+\t\treturn NULL;\n+\tif (!queue->compare)\n+\t\treturn queue->array[--queue->nr].data; /* LIFO */\n+\n+\tresult = queue->array[0].data;\n+\tif (!--queue->nr)\n+\t\treturn result;\n+\n+\tqueue->array[0] = queue->array[queue->nr];\n+\tsift_down_root(queue);\n \treturn result;\n }\n \n@@ -97,3 +102,17 @@ void *prio_queue_peek(struct prio_queue *queue)\n \t\treturn queue->array[queue->nr - 1].data;\n \treturn queue->array[0].data;\n }\n+\n+void prio_queue_replace(struct prio_queue *queue, void *thing)\n+{\n+\tif (!queue->nr) {\n+\t\tprio_queue_put(queue, thing);\n+\t} else if (!queue->compare) {\n+\t\tqueue->array[queue->nr - 1].ctr = queue->insertion_ctr++;\n+\t\tqueue->array[queue->nr - 1].data = thing;\n+\t} else {\n+\t\tqueue->array[0].ctr = queue->insertion_ctr++;\n+\t\tqueue->array[0].data = thing;\n+\t\tsift_down_root(queue);\n+\t}\n+}\ndiff --git a/prio-queue.h b/prio-queue.h\nindex 38d032636d..da7fad2f1f 100644\n--- a/prio-queue.h\n+++ b/prio-queue.h\n@@ -52,6 +52,14 @@ void *prio_queue_get(struct prio_queue *);\n */\n void *prio_queue_peek(struct prio_queue *);\n \n+/*\n+ * Replace the \"thing\" that compares the smallest with a new \"thing\",\n+ * like prio_queue_get()+prio_queue_put() would do, but in a more\n+ * efficient way. Does the same as prio_queue_put() if the queue is\n+ * empty.\n+ */\n+void prio_queue_replace(struct prio_queue *queue, void *thing);\n+\n void clear_prio_queue(struct prio_queue *);\n \n /* Reverse the LIFO elements */\ndiff --git a/t/unit-tests/u-prio-queue.c b/t/unit-tests/u-prio-queue.c\nindex 145e689c9c..63e58114ae 100644\n--- a/t/unit-tests/u-prio-queue.c\n+++ b/t/unit-tests/u-prio-queue.c\n@@ -13,6 +13,7 @@ static int intcmp(const void *va, const void *vb, void *data UNUSED)\n #define STACK\t -3\n #define GET\t -4\n #define REVERSE -5\n+#define REPLACE -6\n \n static int show(int *v)\n {\n@@ -51,6 +52,15 @@ static void test_prio_queue(int *input, size_t input_size,\n \t\tcase REVERSE:\n \t\t\tprio_queue_reverse(&pq);\n \t\t\tbreak;\n+\t\tcase REPLACE:\n+\t\t\tpeek = prio_queue_peek(&pq);\n+\t\t\tcl_assert(i + 1 < input_size);\n+\t\t\tcl_assert(input[i + 1] >= 0);\n+\t\t\tcl_assert(j < result_size);\n+\t\t\tcl_assert_equal_i(result[j], show(peek));\n+\t\t\tj++;\n+\t\t\tprio_queue_replace(&pq, &input[++i]);\n+\t\t\tbreak;\n \t\tdefault:\n \t\t\tprio_queue_put(&pq, &input[i]);\n \t\t\tbreak;\n@@ -81,6 +91,13 @@ void test_prio_queue__empty(void)\n \t\t ((int []){ 1, 2, MISSING, 1, 2, MISSING }));\n }\n \n+void test_prio_queue__replace(void)\n+{\n+\tTEST_INPUT(((int []){ REPLACE, 6, 2, 4, REPLACE, 5, 7, GET,\n+\t\t\t REPLACE, 1, DUMP }),\n+\t\t ((int []){ MISSING, 2, 4, 5, 1, 6, 7 }));\n+}\n+\n void test_prio_queue__stack(void)\n {\n \tTEST_INPUT(((int []){ STACK, 8, 1, 5, 4, 6, 2, 3, DUMP }),\n@@ -92,3 +109,9 @@ void test_prio_queue__reverse_stack(void)\n \tTEST_INPUT(((int []){ STACK, 1, 2, 3, 4, 5, 6, REVERSE, DUMP }),\n \t\t ((int []){ 1, 2, 3, 4, 5, 6 }));\n }\n+\n+void test_prio_queue__replace_stack(void)\n+{\n+\tTEST_INPUT(((int []){ STACK, 8, 1, 5, REPLACE, 4, 6, 2, 3, DUMP }),\n+\t\t ((int []){ 5, 3, 2, 6, 4, 1, 8 }));\n+}\n-- \n2.50.1\n"},{"id":"522307","messageId":"20250719064516.GC705356@coredump.intra.peff.net","threadId":"63797","inReplyTo":"5a25d830-0825-4b28-8763-2be342d2b6a3@web.de","subject":"Re: [PATCH 0/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-07-19T06:45:16Z","receivedAt":"2025-07-19T06:45:17Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 16, 2025 at 11:38:39AM +0200, René Scharfe wrote:\n\n> Yes, commit_list_insert_by_date() is stable, as it inserts commits after\n> ones with the same date. Items are popped from the top, so this ensures\n> FIFO behavior for commits with the same date.\n> \n> prio_queue ensures stability using an ID and favors lower ones, so it\n> provides the same order.\n> \n> We should add unit tests for that, no?\n\nProbably wouldn't hurt to do so, but I don't think doing so needs to\nhold up your series.\n\n-Peff\n"},{"id":"522308","messageId":"20250719065558.GD705356@coredump.intra.peff.net","threadId":"63797","inReplyTo":"b0950e32-b4fa-4aff-8b5c-58c734b880b2@web.de","subject":"Re: [PATCH 1/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-07-19T06:55:58Z","receivedAt":"2025-07-19T06:56:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 16, 2025 at 11:39:49AM +0200, René Scharfe wrote:\n\n> On 7/16/25 7:05 AM, Jeff King wrote:\n> > On Tue, Jul 15, 2025 at 04:51:07PM +0200, René Scharfe wrote:\n> > \n> >> pop_most_recent_commit() calls commit_list_insert_by_date(), which and\n> >> is itself called in a loop, which can lead to quadratic complexity.\n> >> Replace the commit_list with a prio_queue to ensure logarithmic worst\n> >> case complexity and convert all three users.\n> > \n> > I guess I'm cc'd because of my frequent complains about the quadratic\n> > nature of our commit lists? :)\n> \n> And because you introduced prio_queue.\n\nI think that was Junio, but I think I can be counted as a cheerleader\nfor the topic. :)\n\n> > Mostly I asked because I had to look at pop_most_recent_commit() to see\n> > what operation would be made faster here. Looks like it's mostly \":/\",\n> > but maybe also fetch's mark_recent_complete_commits()? I guess we might\n> > hit that if you have a huge number of refs?\n> \n> The :/ handling was the easiest to test for me. fetch_pack() and\n> walker_fetch() require some server side to set up, which seems not worth\n> it just to demonstrate quadratic behavior. Having thousands of refs\n> would make the list long enough to notice, as would having lots of\n> merges.\n\nOK, that makes sense. Just making sure I understand the benefits.\n\n> My general idea is to get rid of commit_list_insert_by_date() eventually\n> to avoid quadratic complexity.\n\nYeah, it's certainly at the root of many such problems we've seen over\nthe years.\n\n> > I actually have a series turning rev_info.commits into a prio_queue\n> > which I need to polish up (mostly just writing commit messages; I've\n> > been running with it for almost 2 years without trouble). Ironically it\n> > does not touch this spot, as these commit lists are formed on their own.\n> \n> That is not a coincidence. I had a look at that series and tried to\n> reach its goals while keeping rev_info.commits a commit_list. Why?\n> Mostly being vaguely uncomfortable with prio_queue' memory overhead,\n> lack of type safety and dual use as a stack. I still used it, but only\n> as local variable, not in the central struct rev_info.\n\nHmm, I would have thought prio_queue had less memory overhead. You're\nspending one pointer per entry in a packed array, versus list nodes. But\nit's true that it doesn't shrink as items are removed (though that is\nsomething we _could_ implement).\n\nThe dual use as a stack actually came in handy for my series, IIRC.\nThere are spots which use a commit_list but care about a specific order,\nand my list/prio_queue conversion helpers use that to create a non-heap\nprio_queue that just returns the items in the original order (it's\nactually FIFO, but we can get that by reversing).\n\nI dunno. That's kind of horrible when I say it out loud, but it did make\nthings work. I'm surprised that your attempt ended up with a performance\nhit when mine did not. Mine tried not to be clever, and even leaves in\nplace a few spots where we convert between the two representations to\nsatisfy various interfaces (with the goal that we'd probably eventually\nswitch to prio_queue everywhere).\n\n-Peff\n"},{"id":"522309","messageId":"20250719065732.GE705356@coredump.intra.peff.net","threadId":"63797","inReplyTo":"20250719065558.GD705356@coredump.intra.peff.net","subject":"Re: [PATCH 1/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-07-19T06:57:32Z","receivedAt":"2025-07-19T06:57:43Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Jul 19, 2025 at 02:55:58AM -0400, Jeff King wrote:\n\n> > That is not a coincidence. I had a look at that series and tried to\n> > reach its goals while keeping rev_info.commits a commit_list. Why?\n> > Mostly being vaguely uncomfortable with prio_queue' memory overhead,\n> > lack of type safety and dual use as a stack. I still used it, but only\n> > as local variable, not in the central struct rev_info.\n> \n> Hmm, I would have thought prio_queue had less memory overhead. You're\n> spending one pointer per entry in a packed array, versus list nodes. But\n> it's true that it doesn't shrink as items are removed (though that is\n> something we _could_ implement).\n> \n> The dual use as a stack actually came in handy for my series, IIRC.\n> There are spots which use a commit_list but care about a specific order,\n> and my list/prio_queue conversion helpers use that to create a non-heap\n> prio_queue that just returns the items in the original order (it's\n> actually FIFO, but we can get that by reversing).\n> \n> I dunno. That's kind of horrible when I say it out loud, but it did make\n> things work. I'm surprised that your attempt ended up with a performance\n> hit when mine did not. Mine tried not to be clever, and even leaves in\n> place a few spots where we convert between the two representations to\n> satisfy various interfaces (with the goal that we'd probably eventually\n> switch to prio_queue everywhere).\n\nOh, re-reading what you wrote again: you left rev_info.commits as a\nlist, so presumably you were paying more conversion overhead as you\nwalked (whereas I think in mine the prio_queue becomes the data\nstructure for the hot path during traversal).\n\n-Peff\n"},{"id":"522310","messageId":"20250719070229.GF705356@coredump.intra.peff.net","threadId":"63797","inReplyTo":"4ed087c9-0229-4219-8cbd-55f9ee79ca35@web.de","subject":"Re: [PATCH 2/3] prio-queue: add prio_queue_replace()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-07-19T07:02:29Z","receivedAt":"2025-07-19T07:02:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jul 17, 2025 at 11:20:53AM +0200, René Scharfe wrote:\n\n> > I thought about building this optimization into prio_queue_get(), but\n> > that would require prio_queue_peek() and prio_queue_put() to be adjusted\n> > as well and all prio_queue users would have to be either made aware of\n> > the not-fully-heapified state, or prevented from accessing prio_queue\n> > properties like .nr and .array.\n> \n> Here's what that would like like. .nr and .array elements are kept\n> consistent at all times, but the root item is not in heap order after a\n> prio_queue_get(). That's good enough to enumerate all prio_queue items\n> like commit-reach.c::queue_has_nonstale() or\n> negotiator/skipping.c::push_parent() do.\n\nHmm, I agree that _probably_ we'd be fine as long as .nr and .array were\nalways consistent. It does make me feel a bit dirty to violate the heap\nproperty in a way that callers can see. I guess the argument in favor of\nit would be:\n\n - if you are directly walking over all elements, then almost all\n ordering is out the window. Yes, the root item is supposed to be the\n min, but in a heap the rest of the elements won't be sorted.\n\n - if you really want things in order from a heap, you'll be calling\n the get() or peek() accessors. And that gives us an opportunity to\n lazily put things in order.\n\nI guess one alternative would be to make the array private and require\nsome kind of foreach accessor. True struct-field privacy in C sucks.\nYou have to hide behind a pointer, so there's runtime cost, plus\niteration requires a clunky callback rather than a loop. I guess we\ncould call it \"array_\" or something, and provide a foreach macro.\n\nI dunno. I'm on the fence.\n\n-Peff\n"},{"id":"522311","messageId":"20250719070427.GG705356@coredump.intra.peff.net","threadId":"63797","inReplyTo":"8ff40c56-368a-4347-aeae-2aca2cb6a5b2@web.de","subject":"Re: [PATCH v2 0/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-07-19T07:04:27Z","receivedAt":"2025-07-19T07:04:28Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jul 18, 2025 at 11:09:04AM +0200, René Scharfe wrote:\n\n> Use prio_queue to improve worst-case performance at the cost of slightly\n> worse best-case performance. Then add and use prio_queue_replace() to\n> recover that loss.\n> \n> Changes since v2:\n> [...]\n\nThanks for fleshing out the test script. This version looks good to me.\n\n-Peff\n"},{"id":"522313","messageId":"37f34e15-f44f-4b8a-b684-bda27a977775@web.de","threadId":"63797","inReplyTo":"20250719065558.GD705356@coredump.intra.peff.net","subject":"Re: [PATCH 1/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-07-19T11:15:28Z","receivedAt":"2025-07-19T11:15:35Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"On 7/19/25 8:55 AM, Jeff King wrote:\n> On Wed, Jul 16, 2025 at 11:39:49AM +0200, René Scharfe wrote:\n> \n>> On 7/16/25 7:05 AM, Jeff King wrote:\n>>> On Tue, Jul 15, 2025 at 04:51:07PM +0200, René Scharfe wrote:\n>>>\n>>>> pop_most_recent_commit() calls commit_list_insert_by_date(), which and\n>>>> is itself called in a loop, which can lead to quadratic complexity.\n>>>> Replace the commit_list with a prio_queue to ensure logarithmic worst\n>>>> case complexity and convert all three users.\n>>>\n>>> I guess I'm cc'd because of my frequent complains about the quadratic\n>>> nature of our commit lists? :)\n>>\n>> And because you introduced prio_queue.\n> \n> I think that was Junio, but I think I can be counted as a cheerleader\n> for the topic. :)\n\nAh, sorry. You did make it stable, though, which allows using it for\nbackward-compatible history traversal.\n>>> I actually have a series turning rev_info.commits into a prio_queue\n>>> which I need to polish up (mostly just writing commit messages; I've\n>>> been running with it for almost 2 years without trouble). Ironically it\n>>> does not touch this spot, as these commit lists are formed on their own.\n>>\n>> That is not a coincidence. I had a look at that series and tried to\n>> reach its goals while keeping rev_info.commits a commit_list. Why?\n>> Mostly being vaguely uncomfortable with prio_queue' memory overhead,\n>> lack of type safety and dual use as a stack. I still used it, but only\n>> as local variable, not in the central struct rev_info.\n> \n> Hmm, I would have thought prio_queue had less memory overhead. You're\n> spending one pointer per entry in a packed array, versus list nodes. But\n> it's true that it doesn't shrink as items are removed (though that is\n> something we _could_ implement).\n\nIf we just count the net data then a commit_list item has two pointers\nand a prio_queue_entry has a pointer and an ID for stability. That's a\ntie. ALLOC_GROW overallocates by ca. 50%, so that's 25% more on\naverage for the prio_queue. No idea what overhead malloc() needs per\nallocation, but I guess it's enough to tilt the scale back against\ncommit_lists.\n\nHowever, a prio_queue without a comparison function acts as a FIFO\nstack, but needs double the amount of memory than a pointer array\nwithout the stability ID would, for the same behavior.\n\nI don't think lack of shrinking causes much of an issue. I did stumble\nover at least one place where using a prio_queue in FIFO mode made the\ncode slightly but measurably slower than using a commit_list, though,\nwhich could be rectified by using a raw array of pointers.\n\nRené\n\n"},{"id":"522327","messageId":"20250720000359.GA743449@coredump.intra.peff.net","threadId":"63797","inReplyTo":"37f34e15-f44f-4b8a-b684-bda27a977775@web.de","subject":"Re: [PATCH 1/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-07-20T00:03:59Z","receivedAt":"2025-07-20T00:04:07Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Jul 19, 2025 at 01:15:28PM +0200, René Scharfe wrote:\n\n> > Hmm, I would have thought prio_queue had less memory overhead. You're\n> > spending one pointer per entry in a packed array, versus list nodes. But\n> > it's true that it doesn't shrink as items are removed (though that is\n> > something we _could_ implement).\n> \n> If we just count the net data then a commit_list item has two pointers\n> and a prio_queue_entry has a pointer and an ID for stability. That's a\n> tie. ALLOC_GROW overallocates by ca. 50%, so that's 25% more on\n> average for the prio_queue. No idea what overhead malloc() needs per\n> allocation, but I guess it's enough to tilt the scale back against\n> commit_lists.\n\nOh right, I totally forgot about the extra counter.\n\n-Peff\n"},{"id":"522333","messageId":"xmqqseirzmdw.fsf@gitster.g","threadId":"63797","inReplyTo":"20250720000359.GA743449@coredump.intra.peff.net","subject":"Re: [PATCH 1/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-07-20T01:22:51Z","receivedAt":"2025-07-20T01:22:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Sat, Jul 19, 2025 at 01:15:28PM +0200, René Scharfe wrote:\n>\n>> > Hmm, I would have thought prio_queue had less memory overhead. You're\n>> > spending one pointer per entry in a packed array, versus list nodes. But\n>> > it's true that it doesn't shrink as items are removed (though that is\n>> > something we _could_ implement).\n>> \n>> If we just count the net data then a commit_list item has two pointers\n>> and a prio_queue_entry has a pointer and an ID for stability. That's a\n>> tie. ALLOC_GROW overallocates by ca. 50%, so that's 25% more on\n>> average for the prio_queue. No idea what overhead malloc() needs per\n>> allocation, but I guess it's enough to tilt the scale back against\n>> commit_lists.\n>\n> Oh right, I totally forgot about the extra counter.\n\nDon't feel bad. I forgot about it, too, when I gave my \"is it\nstable?\" comment to René's patch. ;-)\n"},{"id":"522349","messageId":"148541F5-DC9F-4A3A-B1B1-0FED8AA5A101@gmail.com","threadId":"63797","inReplyTo":"5d7c631a-ae94-4a59-b4ee-8161b5136d86@web.de","subject":"Re: [PATCH v2 1/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"Lidong Yan","fromEmail":"yldhome2d2@gmail.com","sentAt":"2025-07-21T14:02:01Z","receivedAt":"2025-07-21T14:02:17Z","isPatch":true,"sender":{"key":"yldhome2d2@gmail.com","avatar":"https://avatars.githubusercontent.com/u/77328395?v=4"},"body":"René Scharfe writes:\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\nI feel that the reason there's no significant performance improvement is probably\nbecause mostly we are using the priority queue to sort O(siblings) nodes.\nFor example, in this case, the most time-consuming operation is when the priority\nqueue or commit list contains 4 and 5, and we then need to insert 6 and 7.\n\nAssuming the maximum number of siblings is W and the number of nodes is N,\nthe time complexity with a commit list is O(W² × N), while using a priority queue\ngives O(W log W × N). Perhaps in many projects, W isn't particularly large,\nwhich results in the performance improvement not being very significant.\n\n- Lidong"},{"id":"522393","messageId":"aH8vKQa7z313w1RG@szeder.dev","threadId":"63797","inReplyTo":"8ff40c56-368a-4347-aeae-2aca2cb6a5b2@web.de","subject":"Re: [PATCH v2 0/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2025-07-22T06:26:49Z","receivedAt":"2025-07-22T06:27:13Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Fri, Jul 18, 2025 at 11:09:04AM +0200, René Scharfe wrote:\n> Use prio_queue to improve worst-case performance at the cost of slightly\n> worse best-case performance. Then add and use prio_queue_replace() to\n> recover that loss.\n> \n> Changes since v2:\n> - Mention that a prio_queue improves performance for merge-heavy\n> histories in the commit message.\n> - Add the new perf script to Meson build file.\n> - Mention which kind of history we are aiming for and show its shape in\n> a comment in the perf script.\n> - Remove unnecessary quotes and use single quotes for the perf test\n> code.\n> - Rename the variable delete_pending to get_pending to align it with\n> the concrete function prio_queue_get() instead of referring to the\n> abstract concept of deletion, to improve readability.\n> \n> commit: convert pop_most_recent_commit() to prio_queue\n> prio-queue: add prio_queue_replace()\n> commit: use prio_queue_replace() in pop_most_recent_commit()\n\nThe patches in this series were picked up in the wrong order:\n\n $ git log --topo-order --reverse --oneline -3 e436bc94f3\n 36554bf51a commit: convert pop_most_recent_commit() to prio_queue\n 304f06e0c0 commit: use prio_queue_replace() in pop_most_recent_commit(),MIME-Version: 1.0\n e436bc94f3 prio-queue: add prio_queue_replace()\n\nNote that the order of the second and third patches is reversed.\n\nSince the second patch/third commit introduces a new function used by\nthe third patch/second commit, this leads to build failure of\n304f06e0c0:\n\n CC commit.o\n commit.c: In function ‘pop_most_recent_commit’:\n commit.c:754:33: error: implicit declaration of function ‘prio_queue_replace’; did you mean ‘prio_queue_reverse’? [-Werror=implicit-function-declaration]\n 754 | prio_queue_replace(queue, commit);\n | ^~~~~~~~~~~~~~~~~~\n | prio_queue_reverse\n cc1: all warnings being treated as errors\n make: *** [Makefile:2821: commit.o] Error 1\n\n(And there's that MIME-Version thing at the end of 304f06e0c0's subject\nline as well.)\n\n"},{"id":"522444","messageId":"xmqqikjkuwqi.fsf@gitster.g","threadId":"63797","inReplyTo":"aH8vKQa7z313w1RG@szeder.dev","subject":"Re: [PATCH v2 0/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-07-22T14:27:17Z","receivedAt":"2025-07-22T14:27:19Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"SZEDER Gábor writes:\n\n> $ git log --topo-order --reverse --oneline -3 e436bc94f3\n> 36554bf51a commit: convert pop_most_recent_commit() to prio_queue\n> 304f06e0c0 commit: use prio_queue_replace() in pop_most_recent_commit(),MIME-Version: 1.0\n> e436bc94f3 prio-queue: add prio_queue_replace()\n\nFunny. Thanks for spotting.\n"},{"id":"523331","messageId":"c5d91cec-3fec-422e-86d4-78767d95f208@web.de","threadId":"63797","inReplyTo":"148541F5-DC9F-4A3A-B1B1-0FED8AA5A101@gmail.com","subject":"Re: [PATCH v2 1/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-08-03T09:54:26Z","receivedAt":"2025-08-03T09:54:36Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"On 7/21/25 4:02 PM, Lidong Yan wrote:\n> René Scharfe writes:\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> \n> I feel that the reason there's no significant performance improvement is probably\n> because mostly we are using the priority queue to sort O(siblings) nodes.\n> For example, in this case, the most time-consuming operation is when the priority\n> queue or commit list contains 4 and 5, and we then need to insert 6 and 7.\n> \n> Assuming the maximum number of siblings is W and the number of nodes is N,\n> the time complexity with a commit list is O(W² × N), while using a priority queue\n> gives O(W log W × N). Perhaps in many projects, W isn't particularly large,\n> which results in the performance improvement not being very significant.\n\nKinda. While traversing the history we take a commit from to the\ncommit_list or prio_queue and put back its parents. For single-parent\ncommits this sequence keeps the number of stored items the same. Merges\nincrease that number.\n\nWe add and retrieve each commit in the (relevant part of) history. That\ntakes O(N) and O(1) for the sorted list, and O(log N) and O(log N) for\nthe prio_queue, where N is the length of the list.\n\nSo the best-case history is a string of single-parent commits, keeping\nonly a single item on the list/queue throughout. That requires no\nsorting or heaping, making the additions and retrievals O(1). The\noverall complexity is then O(N) for both variants, N being the number\nof commits in the history.\n\nWorst-case history might be a single merge of all commits -- a\ncentipede or myriapod? With all commits on the sorted list we get a\ncomplexity of O(N²) for the traversal, and O(N log N) with a prio_queue.\n\nRené\n\n"},{"id":"523332","messageId":"0d3ddfcc-485e-45cb-28e6-62108e6d5a4d@gmx.de","threadId":"63797","inReplyTo":"494e9686-e014-45f8-86d2-8dfcd6630f46@web.de","subject":"Re: [PATCH v2 3/3] commit: use prio_queue_replace() in pop_most_recent_commit(),MIME-Version: 1.0","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2025-08-03T11:12:16Z","receivedAt":"2025-08-03T11:12:27Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi René,\n\nOn Fri, 18 Jul 2025, René Scharfe wrote:\n\n> Optimize pop_most_recent_commit() by adding the first parent using the\n> more efficient prio_queue_peek() and prio_queue_replace() instead of\n> prio_queue_get() and prio_queue_put().\n> \n> [... clipped ...]\n\nI noticed that v2 of this patch not only made it into `next`, but it also\nintroduced a commit subject suffix (likely unintended?):\n\n [PATCH v2 3/3] commit: use prio_queue_replace() in pop_most_recent_commit(),MIME-Version: 1.0\n\nMaybe that is something you want to look into?\n\nCiao,\nJohannes\n"},{"id":"523333","messageId":"90d4a2c7-70a1-4bf2-85e4-9821b55cdde7@web.de","threadId":"63797","inReplyTo":"0d3ddfcc-485e-45cb-28e6-62108e6d5a4d@gmx.de","subject":"Re: [PATCH v2 3/3] commit: use prio_queue_replace() in pop_most_recent_commit(),MIME-Version: 1.0","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-08-03T11:33:28Z","receivedAt":"2025-08-03T11:33:43Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"On 8/3/25 1:12 PM, Johannes Schindelin wrote:\n> Hi René,\n> \n> On Fri, 18 Jul 2025, René Scharfe wrote:\n> \n>> Optimize pop_most_recent_commit() by adding the first parent using the\n>> more efficient prio_queue_peek() and prio_queue_replace() instead of\n>> prio_queue_get() and prio_queue_put().\n>>\n>> [... clipped ...]\n> \n> I noticed that v2 of this patch not only made it into `next`, but it also\n> introduced a commit subject suffix (likely unintended?):\n> \n> [PATCH v2 3/3] commit: use prio_queue_replace() in pop_most_recent_commit(),MIME-Version: 1.0\n> \n> Maybe that is something you want to look into?\n\nMy bad, copy+paste error. A fixed version made it into master in the\nmeantime. Sorry about that, and thanks a lot for correcting it, Junio!\n\nRené\n\n"},{"id":"523352","messageId":"xmqqtt2oe4gi.fsf@gitster.g","threadId":"63797","inReplyTo":"c5d91cec-3fec-422e-86d4-78767d95f208@web.de","subject":"Re: [PATCH v2 1/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-08-03T16:48:45Z","receivedAt":"2025-08-03T16:48:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> We add and retrieve each commit in the (relevant part of) history. That\n> takes O(N) and O(1) for the sorted list, and O(log N) and O(log N) for\n> the prio_queue, where N is the length of the list.\n>\n> So the best-case history is a string of single-parent commits, keeping\n> only a single item on the list/queue throughout. That requires no\n> sorting or heaping, making the additions and retrievals O(1). The\n> overall complexity is then O(N) for both variants, N being the number\n> of commits in the history.\n>\n> Worst-case history might be a single merge of all commits -- a\n> centipede or myriapod? With all commits on the sorted list we get a\n> complexity of O(N²) for the traversal, and O(N log N) with a prio_queue.\n\nIn other words, for a typical two-parent merge, we peek the current\none, \"replace\" it with its first parent and then do the usual \"put\nand sift it down into place\" for the second one. \n\nI am wondering if there is a more optimization opportunity if we\nallowed \"put more than one, and then sift all of them down into\nplace\". In other words, if I told the machinery:\n\n I am doing this put. I promise I won't do get until I say \"now\n I'll start doing get's, so you are free to delay your internal\n state maintenance and do so immediately before my next 'get'\".\n\nand did such put's a few times before I do a 'get', would there be a\nway to teach the machinery to take advantage of the promise?\n\nIn any case, it is very much welcome to speed up \"describe\" with a\nbetter data structure and algorithm. Will queue.\n\nThanks.\n\n\n"},{"id":"523479","messageId":"a35aae22-da05-4098-88d0-f8dcb50a9a0f@web.de","threadId":"63797","inReplyTo":"xmqqtt2oe4gi.fsf@gitster.g","subject":"Re: [PATCH v2 1/3] commit: convert pop_most_recent_commit() to prio_queue","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-08-04T19:56:27Z","receivedAt":"2025-08-04T19:56:36Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"On 8/3/25 6:48 PM, Junio C Hamano wrote:\n> René Scharfe writes:\n> \n>> We add and retrieve each commit in the (relevant part of) history. That\n>> takes O(N) and O(1) for the sorted list, and O(log N) and O(log N) for\n>> the prio_queue, where N is the length of the list.\n>>\n>> So the best-case history is a string of single-parent commits, keeping\n>> only a single item on the list/queue throughout. That requires no\n>> sorting or heaping, making the additions and retrievals O(1). The\n>> overall complexity is then O(N) for both variants, N being the number\n>> of commits in the history.\n>>\n>> Worst-case history might be a single merge of all commits -- a\n>> centipede or myriapod? With all commits on the sorted list we get a\n>> complexity of O(N²) for the traversal, and O(N log N) with a prio_queue.\n> \n> In other words, for a typical two-parent merge, we peek the current\n> one, \"replace\" it with its first parent and then do the usual \"put\n> and sift it down into place\" for the second one. \n> \n> I am wondering if there is a more optimization opportunity if we\n> allowed \"put more than one, and then sift all of them down into\n> place\". In other words, if I told the machinery:\n> \n> I am doing this put. I promise I won't do get until I say \"now\n> I'll start doing get's, so you are free to delay your internal\n> state maintenance and do so immediately before my next 'get'\".\n> \n> and did such put's a few times before I do a 'get', would there be a\n> way to teach the machinery to take advantage of the promise?\n\nWell, we could reestablish the heap at a cost of O(N), which only pays\noff if it's less than the O(P log N) needed for regular puts of P\nparents, with N being the number of queue elements. This starts to\nlose once queues become too long -- just when an optimization would be\nmost welcome. So it seems impractical.\n\nWe could replace our binary heap with an algorithm that has O(1)\ninserts, like a pairing heap, though.\n\nRené\n\n"}]}