{"thread":{"id":"63896","subject":"[PATCH 1/2] describe: use prio_queue","startedAt":"2025-08-03T11:38:31Z","lastAt":"2025-08-03T11:49:13Z","messageCount":2,"participants":["René Scharfe"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"523334","messageId":"81c7deee-75e9-471a-84f3-8604c0860ee3@web.de","threadId":"63896","inReplyTo":null,"subject":"[PATCH 1/2] describe: use prio_queue","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-08-03T11:38:29Z","receivedAt":"2025-08-03T11:38:31Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Replace the use a list-based priority queue whose order is maintained by\ncommit_list_insert_by_date() with a prio_queue.  This avoids quadratic\nworst-case complexity.  And in the somewhat contrived example of\ndescribing the 4751 commits from v2.41.0 to v2.47.0 in one go (to get a\nsizable chunk of describe work with minimal ref loading overhead) it's\nsignificantly faster:\n\nBenchmark 1: ./git_2.50.1 describe $(git rev-list v2.41.0..v2.47.0)\n  Time (mean ± σ):      1.558 s ±  0.002 s    [User: 1.492 s, System: 0.051 s]\n  Range (min … max):    1.557 s …  1.562 s    10 runs\n\nBenchmark 2: ./git describe $(git rev-list v2.41.0..v2.47.0)\n  Time (mean ± σ):      1.209 s ±  0.006 s    [User: 1.143 s, System: 0.051 s]\n  Range (min … max):    1.201 s …  1.219 s    10 runs\n\nSummary\n  ./git describe $(git rev-list v2.41.0..v2.47.0) ran\n    1.29 ± 0.01 times faster than ./git_2.50.1 describe $(git rev-list v2.41.0..v2.47.0)\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n builtin/describe.c | 51 ++++++++++++++++++++++++----------------------\n 1 file changed, 27 insertions(+), 24 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex fbf305d762..80722ae0c0 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -23,6 +23,7 @@\n #include \"list-objects.h\"\n #include \"commit-slab.h\"\n #include \"wildmatch.h\"\n+#include \"prio-queue.h\"\n \n #define MAX_TAGS\t(FLAG_BITS - 1)\n #define DEFAULT_CANDIDATES 10\n@@ -249,24 +250,26 @@ static int compare_pt(const void *a_, const void *b_)\n \treturn 0;\n }\n \n-static unsigned long finish_depth_computation(\n-\tstruct commit_list **list,\n-\tstruct possible_tag *best)\n+static bool all_have_flag(const struct prio_queue *queue, unsigned flag)\n+{\n+\tfor (size_t i = 0; i < queue->nr; i++) {\n+\t\tstruct commit *commit = queue->array[i].data;\n+\t\tif (!(commit->object.flags & flag))\n+\t\t\treturn false;\n+\t}\n+\treturn true;\n+}\n+\n+static unsigned long finish_depth_computation(struct prio_queue *queue,\n+\t\t\t\t\t      struct possible_tag *best)\n {\n \tunsigned long seen_commits = 0;\n-\twhile (*list) {\n-\t\tstruct commit *c = pop_commit(list);\n+\twhile (queue->nr) {\n+\t\tstruct commit *c = prio_queue_get(queue);\n \t\tstruct commit_list *parents = c->parents;\n \t\tseen_commits++;\n \t\tif (c->object.flags & best->flag_within) {\n-\t\t\tstruct commit_list *a = *list;\n-\t\t\twhile (a) {\n-\t\t\t\tstruct commit *i = a->item;\n-\t\t\t\tif (!(i->object.flags & best->flag_within))\n-\t\t\t\t\tbreak;\n-\t\t\t\ta = a->next;\n-\t\t\t}\n-\t\t\tif (!a)\n+\t\t\tif (all_have_flag(queue, best->flag_within))\n \t\t\t\tbreak;\n \t\t} else\n \t\t\tbest->depth++;\n@@ -274,7 +277,7 @@ static unsigned long finish_depth_computation(\n \t\t\tstruct commit *p = parents->item;\n \t\t\trepo_parse_commit(the_repository, p);\n \t\t\tif (!(p->object.flags & SEEN))\n-\t\t\t\tcommit_list_insert_by_date(p, list);\n+\t\t\t\tprio_queue_put(queue, p);\n \t\t\tp->object.flags |= c->object.flags;\n \t\t\tparents = parents->next;\n \t\t}\n@@ -316,7 +319,7 @@ static void append_suffix(int depth, const struct object_id *oid, struct strbuf\n static void describe_commit(struct object_id *oid, struct strbuf *dst)\n {\n \tstruct commit *cmit, *gave_up_on = NULL;\n-\tstruct commit_list *list;\n+\tstruct prio_queue queue = { compare_commits_by_commit_date };\n \tstruct commit_name *n;\n \tstruct possible_tag all_matches[MAX_TAGS];\n \tunsigned int match_cnt = 0, annotated_cnt = 0, cur_match;\n@@ -359,11 +362,10 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \t\thave_util = 1;\n \t}\n \n-\tlist = NULL;\n \tcmit->object.flags = SEEN;\n-\tcommit_list_insert(cmit, &list);\n-\twhile (list) {\n-\t\tstruct commit *c = pop_commit(&list);\n+\tprio_queue_put(&queue, cmit);\n+\twhile (queue.nr) {\n+\t\tstruct commit *c = prio_queue_get(&queue);\n \t\tstruct commit_list *parents = c->parents;\n \t\tstruct commit_name **slot;\n \n@@ -397,7 +399,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \t\t\t\tt->depth++;\n \t\t}\n \t\t/* Stop if last remaining path already covered by best candidate(s) */\n-\t\tif (annotated_cnt && !list) {\n+\t\tif (annotated_cnt && !queue.nr) {\n \t\t\tint best_depth = INT_MAX;\n \t\t\tunsigned best_within = 0;\n \t\t\tfor (cur_match = 0; cur_match < match_cnt; cur_match++) {\n@@ -420,7 +422,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \t\t\tstruct commit *p = parents->item;\n \t\t\trepo_parse_commit(the_repository, p);\n \t\t\tif (!(p->object.flags & SEEN))\n-\t\t\t\tcommit_list_insert_by_date(p, &list);\n+\t\t\t\tprio_queue_put(&queue, p);\n \t\t\tp->object.flags |= c->object.flags;\n \t\t\tparents = parents->next;\n \n@@ -435,6 +437,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \t\t\tstrbuf_add_unique_abbrev(dst, cmit_oid, abbrev);\n \t\t\tif (suffix)\n \t\t\t\tstrbuf_addstr(dst, suffix);\n+\t\t\tclear_prio_queue(&queue);\n \t\t\treturn;\n \t\t}\n \t\tif (unannotated_cnt)\n@@ -450,11 +453,11 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \tQSORT(all_matches, match_cnt, compare_pt);\n \n \tif (gave_up_on) {\n-\t\tcommit_list_insert_by_date(gave_up_on, &list);\n+\t\tprio_queue_put(&queue, gave_up_on);\n \t\tseen_commits--;\n \t}\n-\tseen_commits += finish_depth_computation(&list, &all_matches[0]);\n-\tfree_commit_list(list);\n+\tseen_commits += finish_depth_computation(&queue, &all_matches[0]);\n+\tclear_prio_queue(&queue);\n \n \tif (debug) {\n \t\tstatic int label_width = -1;\n-- \n2.50.1\n"},{"id":"523335","messageId":"36d5b59a-a99a-4a6f-b637-dfb0b760660f@web.de","threadId":"63896","inReplyTo":"81c7deee-75e9-471a-84f3-8604c0860ee3@web.de","subject":"[PATCH 2/2] describe: use prio_queue_replace()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-08-03T11:49:11Z","receivedAt":"2025-08-03T11:49:13Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Optimize the sequence get+put to peek+replace to avoid one unnecessary\nheap rebalance.\n\nDo that by tracking partial get operations in a prio_queue wrapper,\nstruct lazy_queue, and using wrapper functions that turn get into peek\nand put into replace as needed.  This is simpler than tracking the\nstate explicitly in the calling code.\n\nWe get a nice speedup on top of the previous patch's conversion to\nprio_queue:\n\nBenchmark 1: ./git_2.50.1 describe $(git rev-list v2.41.0..v2.47.0)\n  Time (mean ± σ):      1.559 s ±  0.002 s    [User: 1.493 s, System: 0.051 s]\n  Range (min … max):    1.556 s …  1.563 s    10 runs\n\nBenchmark 2: ./git_describe_pq describe $(git rev-list v2.41.0..v2.47.0)\n  Time (mean ± σ):      1.204 s ±  0.001 s    [User: 1.138 s, System: 0.051 s]\n  Range (min … max):    1.202 s …  1.205 s    10 runs\n\nBenchmark 3: ./git describe $(git rev-list v2.41.0..v2.47.0)\n  Time (mean ± σ):     850.9 ms ±   1.6 ms    [User: 786.6 ms, System: 49.8 ms]\n  Range (min … max):   849.1 ms … 854.1 ms    10 runs\n\nSummary\n  ./git describe $(git rev-list v2.41.0..v2.47.0) ran\n    1.41 ± 0.00 times faster than ./git_describe_pq describe $(git rev-list v2.41.0..v2.47.0)\n    1.83 ± 0.00 times faster than ./git_2.50.1 describe $(git rev-list v2.41.0..v2.47.0)\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\nA more convincing showcase for that optimization than a79e3519d6\n(commit: use prio_queue_replace() in pop_most_recent_commit(),\n2025-07-18).\n\n builtin/describe.c | 68 +++++++++++++++++++++++++++++++++++-----------\n 1 file changed, 52 insertions(+), 16 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 80722ae0c0..c18e4b3e4b 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -250,22 +250,58 @@ static int compare_pt(const void *a_, const void *b_)\n \treturn 0;\n }\n \n-static bool all_have_flag(const struct prio_queue *queue, unsigned flag)\n+struct lazy_queue {\n+\tstruct prio_queue queue;\n+\tbool get_pending;\n+};\n+\n+#define LAZY_QUEUE_INIT { { compare_commits_by_commit_date }, false }\n+\n+static void *lazy_queue_get(struct lazy_queue *queue)\n+{\n+\tif (queue->get_pending)\n+\t\tprio_queue_get(&queue->queue);\n+\telse\n+\t\tqueue->get_pending = true;\n+\treturn prio_queue_peek(&queue->queue);\n+}\n+\n+static void lazy_queue_put(struct lazy_queue *queue, void *thing)\n+{\n+\tif (queue->get_pending)\n+\t\tprio_queue_replace(&queue->queue, thing);\n+\telse\n+\t\tprio_queue_put(&queue->queue, thing);\n+\tqueue->get_pending = false;\n+}\n+\n+static bool lazy_queue_empty(const struct lazy_queue *queue)\n+{\n+\treturn queue->queue.nr == (queue->get_pending ? 1 : 0);\n+}\n+\n+static void lazy_queue_clear(struct lazy_queue *queue)\n+{\n+\tclear_prio_queue(&queue->queue);\n+\tqueue->get_pending = false;\n+}\n+\n+static bool all_have_flag(const struct lazy_queue *queue, unsigned flag)\n {\n-\tfor (size_t i = 0; i < queue->nr; i++) {\n-\t\tstruct commit *commit = queue->array[i].data;\n+\tfor (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) {\n+\t\tstruct commit *commit = queue->queue.array[i].data;\n \t\tif (!(commit->object.flags & flag))\n \t\t\treturn false;\n \t}\n \treturn true;\n }\n \n-static unsigned long finish_depth_computation(struct prio_queue *queue,\n+static unsigned long finish_depth_computation(struct lazy_queue *queue,\n \t\t\t\t\t      struct possible_tag *best)\n {\n \tunsigned long seen_commits = 0;\n-\twhile (queue->nr) {\n-\t\tstruct commit *c = prio_queue_get(queue);\n+\twhile (!lazy_queue_empty(queue)) {\n+\t\tstruct commit *c = lazy_queue_get(queue);\n \t\tstruct commit_list *parents = c->parents;\n \t\tseen_commits++;\n \t\tif (c->object.flags & best->flag_within) {\n@@ -277,7 +313,7 @@ static unsigned long finish_depth_computation(struct prio_queue *queue,\n \t\t\tstruct commit *p = parents->item;\n \t\t\trepo_parse_commit(the_repository, p);\n \t\t\tif (!(p->object.flags & SEEN))\n-\t\t\t\tprio_queue_put(queue, p);\n+\t\t\t\tlazy_queue_put(queue, p);\n \t\t\tp->object.flags |= c->object.flags;\n \t\t\tparents = parents->next;\n \t\t}\n@@ -319,7 +355,7 @@ static void append_suffix(int depth, const struct object_id *oid, struct strbuf\n static void describe_commit(struct object_id *oid, struct strbuf *dst)\n {\n \tstruct commit *cmit, *gave_up_on = NULL;\n-\tstruct prio_queue queue = { compare_commits_by_commit_date };\n+\tstruct lazy_queue queue = LAZY_QUEUE_INIT;\n \tstruct commit_name *n;\n \tstruct possible_tag all_matches[MAX_TAGS];\n \tunsigned int match_cnt = 0, annotated_cnt = 0, cur_match;\n@@ -363,9 +399,9 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \t}\n \n \tcmit->object.flags = SEEN;\n-\tprio_queue_put(&queue, cmit);\n-\twhile (queue.nr) {\n-\t\tstruct commit *c = prio_queue_get(&queue);\n+\tlazy_queue_put(&queue, cmit);\n+\twhile (!lazy_queue_empty(&queue)) {\n+\t\tstruct commit *c = lazy_queue_get(&queue);\n \t\tstruct commit_list *parents = c->parents;\n \t\tstruct commit_name **slot;\n \n@@ -399,7 +435,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \t\t\t\tt->depth++;\n \t\t}\n \t\t/* Stop if last remaining path already covered by best candidate(s) */\n-\t\tif (annotated_cnt && !queue.nr) {\n+\t\tif (annotated_cnt && lazy_queue_empty(&queue)) {\n \t\t\tint best_depth = INT_MAX;\n \t\t\tunsigned best_within = 0;\n \t\t\tfor (cur_match = 0; cur_match < match_cnt; cur_match++) {\n@@ -422,7 +458,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \t\t\tstruct commit *p = parents->item;\n \t\t\trepo_parse_commit(the_repository, p);\n \t\t\tif (!(p->object.flags & SEEN))\n-\t\t\t\tprio_queue_put(&queue, p);\n+\t\t\t\tlazy_queue_put(&queue, p);\n \t\t\tp->object.flags |= c->object.flags;\n \t\t\tparents = parents->next;\n \n@@ -437,7 +473,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \t\t\tstrbuf_add_unique_abbrev(dst, cmit_oid, abbrev);\n \t\t\tif (suffix)\n \t\t\t\tstrbuf_addstr(dst, suffix);\n-\t\t\tclear_prio_queue(&queue);\n+\t\t\tlazy_queue_clear(&queue);\n \t\t\treturn;\n \t\t}\n \t\tif (unannotated_cnt)\n@@ -453,11 +489,11 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \tQSORT(all_matches, match_cnt, compare_pt);\n \n \tif (gave_up_on) {\n-\t\tprio_queue_put(&queue, gave_up_on);\n+\t\tlazy_queue_put(&queue, gave_up_on);\n \t\tseen_commits--;\n \t}\n \tseen_commits += finish_depth_computation(&queue, &all_matches[0]);\n-\tclear_prio_queue(&queue);\n+\tlazy_queue_clear(&queue);\n \n \tif (debug) {\n \t\tstatic int label_width = -1;\n-- \n2.50.1\n"}]}