{"thread":{"id":"64682","subject":"[PATCH] show-branch: use prio_queue","startedAt":"2025-12-26T07:49:46Z","lastAt":"2025-12-29T20:02:06Z","messageCount":3,"participants":["René Scharfe","Derrick Stolee"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"532750","messageId":"70ed751e-fc3c-4cb4-a4fd-26094a9f622e@web.de","threadId":"64682","inReplyTo":null,"subject":"[PATCH] show-branch: use prio_queue","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-12-26T07:44:28Z","receivedAt":"2025-12-26T07:49:46Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Building a list using commit_list_insert_by_date() has quadratic worst\ncase complexity.  Avoid it by using prio_queue.\n\nUse prio_queue_peek()+prio_queue_replace() instead of prio_queue_get()+\nprio_queue_put() if possible, as the former only rebalance the\nprio_queue heap once instead of twice.\n\nIn sane repositories this won't make much of a difference because the\nnumber of items in the list or queue won't be very high:\n\nBenchmark 1: ./git_v2.52.0 show-branch origin/main origin/next origin/seen origin/todo\n  Time (mean ± σ):     538.2 ms ±   0.8 ms    [User: 527.6 ms, System: 9.6 ms]\n  Range (min … max):   537.0 ms … 539.2 ms    10 runs\n\nBenchmark 2: ./git show-branch origin/main origin/next origin/seen origin/todo\n  Time (mean ± σ):     530.6 ms ±   0.4 ms    [User: 519.8 ms, System: 9.8 ms]\n  Range (min … max):   530.1 ms … 531.3 ms    10 runs\n\nSummary\n  ./git show-branch origin/main origin/next origin/seen origin/todo ran\n    1.01 ± 0.00 times faster than ./git_v2.52.0 show-branch origin/main origin/next origin/seen origin/todo\n\nThat number is not limited, though, and in pathological cases like the\none in p6010 we see a sizable improvement:\n\nTest                      v2.52.0           HEAD\n------------------------------------------------------------------\n6010.4: git show-branch   2.19(2.19+0.00)   0.03(0.02+0.00) -98.6%\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n builtin/show-branch.c      | 34 +++++++++++++++++++++-------------\n t/perf/p6010-merge-base.sh |  8 ++++++--\n 2 files changed, 27 insertions(+), 15 deletions(-)\n\ndiff --git a/builtin/show-branch.c b/builtin/show-branch.c\nindex 10475a6b5e..f3ebc1d4ea 100644\n--- a/builtin/show-branch.c\n+++ b/builtin/show-branch.c\n@@ -18,6 +18,7 @@\n #include \"commit-slab.h\"\n #include \"date.h\"\n #include \"wildmatch.h\"\n+#include \"prio-queue.h\"\n \n static const char*const show_branch_usage[] = {\n     N_(\"git show-branch [-a | --all] [-r | --remotes] [--topo-order | --date-order]\\n\"\n@@ -59,11 +60,10 @@ static const char *get_color_reset_code(void)\n \treturn \"\";\n }\n \n-static struct commit *interesting(struct commit_list *list)\n+static struct commit *interesting(struct prio_queue *queue)\n {\n-\twhile (list) {\n-\t\tstruct commit *commit = list->item;\n-\t\tlist = list->next;\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 & UNINTERESTING)\n \t\t\tcontinue;\n \t\treturn commit;\n@@ -222,17 +222,18 @@ static int mark_seen(struct commit *commit, struct commit_list **seen_p)\n \treturn 0;\n }\n \n-static void join_revs(struct commit_list **list_p,\n+static void join_revs(struct prio_queue *queue,\n \t\t      struct commit_list **seen_p,\n \t\t      int num_rev, int extra)\n {\n \tint all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);\n \tint all_revs = all_mask & ~((1u << REV_SHIFT) - 1);\n \n-\twhile (*list_p) {\n+\twhile (queue->nr) {\n \t\tstruct commit_list *parents;\n-\t\tint still_interesting = !!interesting(*list_p);\n-\t\tstruct commit *commit = pop_commit(list_p);\n+\t\tint still_interesting = !!interesting(queue);\n+\t\tstruct commit *commit = prio_queue_peek(queue);\n+\t\tbool get_pending = true;\n \t\tint flags = commit->object.flags & all_mask;\n \n \t\tif (!still_interesting && extra <= 0)\n@@ -253,8 +254,14 @@ static void join_revs(struct commit_list **list_p,\n \t\t\tif (mark_seen(p, seen_p) && !still_interesting)\n \t\t\t\textra--;\n \t\t\tp->object.flags |= flags;\n-\t\t\tcommit_list_insert_by_date(p, list_p);\n+\t\t\tif (get_pending)\n+\t\t\t\tprio_queue_replace(queue, p);\n+\t\t\telse\n+\t\t\t\tprio_queue_put(queue, p);\n+\t\t\tget_pending = false;\n \t\t}\n+\t\tif (get_pending)\n+\t\t\tprio_queue_get(queue);\n \t}\n \n \t/*\n@@ -639,7 +646,8 @@ int cmd_show_branch(int ac,\n {\n \tstruct commit *rev[MAX_REVS], *commit;\n \tchar *reflog_msg[MAX_REVS] = {0};\n-\tstruct commit_list *list = NULL, *seen = NULL;\n+\tstruct commit_list *seen = NULL;\n+\tstruct prio_queue queue = { compare_commits_by_commit_date };\n \tunsigned int rev_mask[MAX_REVS];\n \tint num_rev, i, extra = 0;\n \tint all_heads = 0, all_remotes = 0;\n@@ -883,14 +891,14 @@ int cmd_show_branch(int ac,\n \t\t */\n \t\tcommit->object.flags |= flag;\n \t\tif (commit->object.flags == flag)\n-\t\t\tcommit_list_insert_by_date(commit, &list);\n+\t\t\tprio_queue_put(&queue, commit);\n \t\trev[num_rev] = commit;\n \t}\n \tfor (i = 0; i < num_rev; i++)\n \t\trev_mask[i] = rev[i]->object.flags;\n \n \tif (0 <= extra)\n-\t\tjoin_revs(&list, &seen, num_rev, extra);\n+\t\tjoin_revs(&queue, &seen, num_rev, extra);\n \n \tcommit_list_sort_by_date(&seen);\n \n@@ -1001,7 +1009,7 @@ int cmd_show_branch(int ac,\n \tfor (size_t i = 0; i < ARRAY_SIZE(reflog_msg); i++)\n \t\tfree(reflog_msg[i]);\n \tfree_commit_list(seen);\n-\tfree_commit_list(list);\n+\tclear_prio_queue(&queue);\n \tfree(args_copy);\n \tfree(head);\n \treturn ret;\ndiff --git a/t/perf/p6010-merge-base.sh b/t/perf/p6010-merge-base.sh\nindex 54f52fa23e..08212dd037 100755\n--- a/t/perf/p6010-merge-base.sh\n+++ b/t/perf/p6010-merge-base.sh\n@@ -83,9 +83,9 @@ build_history2 () {\n test_expect_success 'setup' '\n \tmax_level=15 &&\n \tbuild_history $max_level | git fast-import --export-marks=marks &&\n-\tgit tag one &&\n+\tgit branch one &&\n \tbuild_history2 $max_level | git fast-import --import-marks=marks --force &&\n-\tgit tag two &&\n+\tgit branch two &&\n \tgit gc &&\n \tgit log --format=%H --no-merges >expect\n '\n@@ -98,4 +98,8 @@ test_expect_success 'verify result' '\n \ttest_cmp expect actual\n '\n \n+test_perf 'git show-branch' '\n+\tgit show-branch one two\n+'\n+\n test_done\n-- \n2.52.0\n"},{"id":"532810","messageId":"01d09293-4b60-4a47-9350-73b1ff796c9a@gmail.com","threadId":"64682","inReplyTo":"70ed751e-fc3c-4cb4-a4fd-26094a9f622e@web.de","subject":"Re: [PATCH] show-branch: use prio_queue","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2025-12-29T18:09:07Z","receivedAt":"2025-12-29T18:09:09Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 12/26/2025 2:44 AM, René Scharfe wrote:\n> Building a list using commit_list_insert_by_date() has quadratic worst\n> case complexity.  Avoid it by using prio_queue.\n\nExcellent idea.\n\n> That number is not limited, though, and in pathological cases like the\n> one in p6010 we see a sizable improvement:\n> \n> Test                      v2.52.0           HEAD\n> ------------------------------------------------------------------\n> 6010.4: git show-branch   2.19(2.19+0.00)   0.03(0.02+0.00) -98.6%\n\nI love to see improvements like this, even if the construction is\nunlikely to exist in reality. I do think it's likely to be valuable\nfor some large repos with many parallel branches.\n\nIndeed, I tested this patch against a monorepo with lots of merges\nwith hyperfine, getting this output:\n\nBenchmark 1: old\n  Time (mean ± σ):      3.303 s ±  0.146 s    [User: 0.058 s, System: 0.069 s]\n  Range (min … max):    3.162 s …  3.631 s    10 runs\n\nBenchmark 2: new\n  Time (mean ± σ):     141.7 ms ±   3.2 ms    [User: 30.5 ms, System: 93.1 ms]\n  Range (min … max):   137.5 ms … 149.4 ms    19 runs\n\nSummary\n  new ran\n   23.31 ± 1.15 times faster than old\n\n> -static struct commit *interesting(struct commit_list *list)\n> +static struct commit *interesting(struct prio_queue *queue)\n>  {\n> -\twhile (list) {\n> -\t\tstruct commit *commit = list->item;\n> -\t\tlist = list->next;\n> +\tfor (size_t i = 0; i < queue->nr; i++) {\n> +\t\tstruct commit *commit = queue->array[i].data;\n...\n> -static void join_revs(struct commit_list **list_p,\n> +static void join_revs(struct prio_queue *queue,\n>  \t\t      struct commit_list **seen_p,\n>  \t\t      int num_rev, int extra)\n>  {\n>  \tint all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);\n>  \tint all_revs = all_mask & ~((1u << REV_SHIFT) - 1);\n>  \n> -\twhile (*list_p) {\n> +\twhile (queue->nr) {\n>  \t\tstruct commit_list *parents;\n> -\t\tint still_interesting = !!interesting(*list_p);\n> -\t\tstruct commit *commit = pop_commit(list_p);\n> +\t\tint still_interesting = !!interesting(queue);\n> +\t\tstruct commit *commit = prio_queue_peek(queue);\n\nMost of the changes are obvious replacements.\n\n> +\t\tbool get_pending = true;\n\nBut this is a new variable. Let's see how it's used.\n)\n> @@ -253,8 +254,14 @@ static void join_revs(struct commit_list **list_p,\n>  \t\t\tif (mark_seen(p, seen_p) && !still_interesting)\n>  \t\t\t\textra--;\n>  \t\t\tp->object.flags |= flags;\n> -\t\t\tcommit_list_insert_by_date(p, list_p);\n> +\t\t\tif (get_pending)\n> +\t\t\t\tprio_queue_replace(queue, p);\n> +\t\t\telse\n> +\t\t\t\tprio_queue_put(queue, p);\n> +\t\t\tget_pending = false;\n>  \t\t}\n> +\t\tif (get_pending)\n> +\t\t\tprio_queue_get(queue);\n\nWhat's missing from this context is the loop iterating over\nthe commit's parents. Here's the full context here:\n\n\twhile (queue->nr) {\n\t\tstruct commit_list *parents;\n\t\tint still_interesting = !!interesting(queue);\n\t\tstruct commit *commit = prio_queue_peek(queue);\n\t\tbool get_pending = true;\n\t\tint flags = commit->object.flags & all_mask;\n\n\t\tif (!still_interesting && extra <= 0)\n\t\t\tbreak;\n\n\t\tmark_seen(commit, seen_p);\n\t\tif ((flags & all_revs) == all_revs)\n\t\t\tflags |= UNINTERESTING;\n\t\tparents = commit->parents;\n\n\t\twhile (parents) {\n\t\t\tstruct commit *p = parents->item;\n\t\t\tint this_flag = p->object.flags;\n\t\t\tparents = parents->next;\n\t\t\tif ((this_flag & flags) == flags)\n\t\t\t\tcontinue;\n\t\t\trepo_parse_commit(the_repository, p);\n\t\t\tif (mark_seen(p, seen_p) && !still_interesting)\n\t\t\t\textra--;\n\t\t\tp->object.flags |= flags;\n\t\t\tif (get_pending)\n\t\t\t\tprio_queue_replace(queue, p);\n\t\t\telse\n\t\t\t\tprio_queue_put(queue, p);\n\t\t\tget_pending = false;\n\t\t}\n\t\tif (get_pending)\n\t\t\tprio_queue_get(queue);\n\t}\n\nThe important thing here is that we are _peeking_ at the\ncurrent commit and then doing the following:\n\n 1. Replace the current top of the queue with the first parent.\n 2. Insert any later parents into the queue as new elements.\n 3. If no parents exist, then remove the current top.\n\nThis replacement of the first parent is like a removal and a put,\nbut avoids a double-sift. That's a small optimization, but likely\nworth the complexity you're using here.\n\n> @@ -639,7 +646,8 @@ int cmd_show_branch(int ac,\n>  {\n>  \tstruct commit *rev[MAX_REVS], *commit;\n>  \tchar *reflog_msg[MAX_REVS] = {0};\n> -\tstruct commit_list *list = NULL, *seen = NULL;\n> +\tstruct commit_list *seen = NULL;\n> +\tstruct prio_queue queue = { compare_commits_by_commit_date };\n\nThis confirms that the queue sorts by date instead of acting like\na stack (if there was no sort specified).\n\n> -\t\t\tcommit_list_insert_by_date(commit, &list);\n> +\t\t\tprio_queue_put(&queue, commit);\n...\n> -\t\tjoin_revs(&list, &seen, num_rev, extra);\n> +\t\tjoin_revs(&queue, &seen, num_rev, extra);\n...\n> -\tfree_commit_list(list);\n> +\tclear_prio_queue(&queue);\n\nMore standard replacements. Good.\n\n> diff --git a/t/perf/p6010-merge-base.sh b/t/perf/p6010-merge-base.sh\n> index 54f52fa23e..08212dd037 100755\n> --- a/t/perf/p6010-merge-base.sh\n> +++ b/t/perf/p6010-merge-base.sh\n> @@ -83,9 +83,9 @@ build_history2 () {\n>  test_expect_success 'setup' '\n>  \tmax_level=15 &&\n>  \tbuild_history $max_level | git fast-import --export-marks=marks &&\n> -\tgit tag one &&\n> +\tgit branch one &&\n>  \tbuild_history2 $max_level | git fast-import --import-marks=marks --force &&\n> -\tgit tag two &&\n> +\tgit branch two &&\n\nThese replacements of tags with branches does not impede any\nother tests that use 'one' or 'two', but is necessary for the\nfunctionality of 'git show-branch'. OK.\n\n> +test_perf 'git show-branch' '\n> +\tgit show-branch one two\n> +'\n\nThanks for expanding the performance tests.\n\nThis patch LGTM.\n\n-Stolee\n\n"},{"id":"532814","messageId":"c30ebbab-e303-4301-971b-7ff619389597@web.de","threadId":"64682","inReplyTo":"01d09293-4b60-4a47-9350-73b1ff796c9a@gmail.com","subject":"Re: [PATCH] show-branch: use prio_queue","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-12-29T20:01:58Z","receivedAt":"2025-12-29T20:02:06Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"On 12/29/25 7:09 PM, Derrick Stolee wrote:\n> On 12/26/2025 2:44 AM, René Scharfe wrote:\n> \n>> That number is not limited, though, and in pathological cases like the\n>> one in p6010 we see a sizable improvement:\n>>\n>> Test                      v2.52.0           HEAD\n>> ------------------------------------------------------------------\n>> 6010.4: git show-branch   2.19(2.19+0.00)   0.03(0.02+0.00) -98.6%\n> \n> I love to see improvements like this, even if the construction is\n> unlikely to exist in reality. I do think it's likely to be valuable\n> for some large repos with many parallel branches.\n> \n> Indeed, I tested this patch against a monorepo with lots of merges\n> with hyperfine, getting this output:\n> \n> Benchmark 1: old\n>   Time (mean ± σ):      3.303 s ±  0.146 s    [User: 0.058 s, System: 0.069 s]\n>   Range (min … max):    3.162 s …  3.631 s    10 runs\n> \n> Benchmark 2: new\n>   Time (mean ± σ):     141.7 ms ±   3.2 ms    [User: 30.5 ms, System: 93.1 ms]\n>   Range (min … max):   137.5 ms … 149.4 ms    19 runs\n> \n> Summary\n>   new ran\n>    23.31 ± 1.15 times faster than old\nWoah, the perf test gets a speedup by factor 46 in a repository\npurpose-built to highlight this very difference, and here you get half\nof that in the wild!  Interesting to see that there are real commit\nhistories out there with such a taxing topology.\n\nAnd thanks for your review!\n\nRené\n\n"}]}