{"thread":{"id":"65720","subject":"[PATCH] prio-queue: use cascade-down sift for faster extract-min","startedAt":"2026-05-31T17:57:19Z","lastAt":"2026-07-10T17:41:10Z","messageCount":24,"participants":["Kristofer Karlsson via GitGitGadget","Junio C Hamano","Kristofer Karlsson","René Scharfe"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"544318","messageId":"pull.2132.git.1780250236304.gitgitgadget@gmail.com","threadId":"65720","inReplyTo":null,"subject":"[PATCH] prio-queue: use cascade-down sift for faster extract-min","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-31T17:57:15Z","receivedAt":"2026-05-31T17:57:19Z","isPatch":true,"body":"From: Kristofer Karlsson \n\nReplace the standard sift-down in prio_queue_get() with a\ncascade-down approach.\n\nThe standard approach places the last array element at the root,\nthen sifts it down. At each level this requires two comparisons\n(left vs right child, then element vs winner) and, when the\nelement is larger, a swap (three 16-byte copies).\n\nThe cascade approach instead promotes the smaller child into the\nvacant root slot at each level — one comparison and one copy.\nThe vacancy sinks to a leaf, where the last array element is\nplaced and sifted up if needed — typically zero levels since the\nlast array element tends to be large.\n\nIn the common case, work per extract drops from 2d comparisons\n+ 3d copies to d comparisons + d copies: roughly half the\ncomparisons and a third of the data movement. The sift-up phase\ncan add work when the last element is smaller than ancestors of\nthe leaf vacancy, but this is rare in practice.\n\nSimplify prio_queue_replace() to a plain get+put sequence. This\nis semantically equivalent: the old implementation wrote to slot 0\nand sifted down, which has the same observable effect as removing\nthe root and inserting a new element. No caller observes queue\nstate between the two operations. The previous implementation\nshared sift_down_root() with get, but the cascade approach no\nlonger accommodates that cleanly since sift_down_root() now\nexpects the element to reinsert at queue->array[queue->nr], left\nthere by prio_queue_get() after decrementing nr. This is fine in\npractice: replace is only called from pop_most_recent_commit()\n(fetch-pack, object-name, walker) and show-branch — none of\nwhich appear in any hot path.\n\nA synthetic benchmark (10 rounds of 10M put+get cycles, ascending\ninteger keys, CPU-pinned, median of 3 runs, same compiler and\nMakefile flags) shows consistent improvement across all queue\nsizes, with no regressions:\n\n queue width baseline cascade speedup\n ------------------------------------------------\n 10 4.32s 3.97s 1.09x\n 100 7.95s 6.49s 1.23x\n 1,000 11.30s 9.66s 1.17x\n 10,000 16.34s 14.15s 1.16x\n 100,000 21.43s 18.66s 1.15x\n\nWith descending keys (worst case — the last element always sinks\nto a leaf in both approaches) the cascade still wins slightly\n(1-4%) by replacing swaps with copies, and never regresses.\n\nIn end-to-end git commands the improvement is modest because\nsift_down_root is only ~8% of total runtime. Profiling\nrev-list --count on a 2.5M-commit monorepo shows sift_down_root\ndropping from 8.2% to 0.4% of total runtime. The improvement\nscales with DAG width: wider DAGs produce larger priority queues,\namplifying the per-level savings. In small or narrow repos the\nqueues stay shallow and the effect is negligible.\n\nSigned-off-by: Kristofer Karlsson \n---\n prio-queue: use cascade-down sift for faster extract-min\n \n Hi, I am not sure this is just noise or not but I thought it at least\n was interesting.\n \n I looked into the internals of prio_queue and found it was technically\n doing too much work and could be simplified/optimized. I found I could\n optimize it by ~20% for the common case (adding commits that would\n typically end up far back in the queue) but only ~1% for the reverse\n case (adding things to the front of the prio queue). The average speedup\n is somewhere in between I suppose. That said, this is not really the\n bottleneck so the overall boost seems to be around ~3-4% improvement for\n repos with wide DAGs.\n \n I would normally classify this as not urgent or important, but I think\n the advantage is that the change is very small and simple and it already\n has good unit tests (t/unit-tests/u-prio-queue.c).\n \n With that said, here are the details:\n \n The prio_queue_get impl is based on removing the root entry, then moving\n the very last element into the root slot, then sifting it down into the\n right place. This uses both comparisons between sibling elements in the\n heap as well as comparisons between the element to add and one of the\n siblings. Then it uses swap operations to move things correctly.\n \n This patch instead promotes the smaller child upward at each level,\n leaving a vacancy that sinks to a leaf, then places the removed element\n there with a short sift-up to keep the heap balanced.\n \n We can analytically compare this - for a sift-distance of d we can\n reason about the number of operations to execute.\n \n Before: 2d comparisons + 3d copies\n After: d comparisons + d copies\n \n \n After changing sift_down in this way, the replace operation can't simply\n depend on it anymore, so I reimplemented it as a sequence of get + put.\n This is technically correct but maybe not as efficient. However, I am\n not sure that it matters, since I couldn't see any usage of the replace\n operation in any hot path.\n \n Performance: Profiling git rev-list --count on a 2.5M-commit monorepo\n shows sift_down_root dropping from 8.2% to 0.4% of total runtime,\n effectively eliminated as significant overhead.\n \n Synthetic benchmark 10 rounds of 10M put+get cycles, CPU-pinned, median\n of 3 runs, same compiler and Makefile flags.\n \n Ascending keys (git's typical pattern -- parents have lower priority\n than children):\n \n queue width baseline patched speedup\n 10 4.32s 3.97s 1.09x\n 100 7.95s 6.49s 1.23x\n 1,000 11.30s 9.66s 1.17x\n 10,000 16.34s 14.15s 1.16x\n 100,000 21.43s 18.66s 1.15x\n \n \n Descending keys (worst case — last element always sinks to leaf in both\n approaches):\n \n queue width baseline patched speedup\n 10 4.84s 4.78s 1.01x\n 100 9.43s 9.20s 1.03x\n 1,000 15.28s 14.71s 1.04x\n 10,000 23.61s 23.49s 1.01x\n 100,000 29.16s 28.22s 1.03x\n \n \n No regressions in any scenario.\n \n End-to-end benchmarks\n \n All benchmarks use a benchmark setup of 1 warmup run followed by 10\n timed runs. Each configuration is built from the same source tree and\n tested on the same repo in alternating order.\n \n linux kernel (1.4M commits) — range v5.0..v6.0 (311K commits):\n \n Command baseline patched speedup\n rev-list --count v5.0..v6.0 455ms 440ms 1.04x\n \n \n I also ran it on git.git but did not see any performance diff at all,\n due to the size and narrow DAG.\n \n The improvement scales with DAG width: wider DAGs produce larger\n priority queues, amplifying the per-level savings. In small or narrow\n repositories the priority queues stay shallow and the sift-down cost is\n already negligible, so the change is not noticeable.\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2132%2Fspkrka%2Fcascade-sift-down-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2132/spkrka/cascade-sift-down-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/2132\n\n prio-queue.c | 22 ++++++++++++----------\n 1 file changed, 12 insertions(+), 10 deletions(-)\n\ndiff --git a/prio-queue.c b/prio-queue.c\nindex 9748528ce6..18005c43c4 100644\n--- a/prio-queue.c\n+++ b/prio-queue.c\n@@ -62,17 +62,21 @@ 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+\tfor (ix = 0; (child = ix * 2 + 1) < queue->nr; ix = child) {\n \t\tif (child + 1 < queue->nr &&\n \t\t compare(queue, child, child + 1) >= 0)\n \t\t\tchild++; /* use right child */\n+\t\tqueue->array[ix] = queue->array[child];\n+\t}\n \n-\t\tif (compare(queue, ix, child) <= 0)\n+\t/* Place queue->array[queue->nr] (left by caller) and sift up. */\n+\tqueue->array[ix] = queue->array[queue->nr];\n+\twhile (ix) {\n+\t\tsize_t parent = (ix - 1) / 2;\n+\t\tif (compare(queue, parent, ix) <= 0)\n \t\t\tbreak;\n-\n-\t\tswap(queue, child, ix);\n+\t\tswap(queue, parent, ix);\n+\t\tix = parent;\n \t}\n }\n \n@@ -89,7 +93,6 @@ void *prio_queue_get(struct prio_queue *queue)\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@@ -111,8 +114,7 @@ void prio_queue_replace(struct prio_queue *queue, void *thing)\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\tprio_queue_get(queue);\n+\t\tprio_queue_put(queue, thing);\n \t}\n }\n\nbase-commit: c69baaf57ba26cf117c2b6793802877f19738b0d\n-- \ngitgitgadget\n"},{"id":"544335","messageId":"xmqqqzmrazpi.fsf@gitster.g","threadId":"65720","inReplyTo":"pull.2132.git.1780250236304.gitgitgadget@gmail.com","subject":"Re: [PATCH] prio-queue: use cascade-down sift for faster extract-min","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-06-01T00:09:29Z","receivedAt":"2026-06-01T00:09:32Z","isPatch":true,"body":"\"Kristofer Karlsson via GitGitGadget\" \nwrites:\n\nI'll add René the recipients, as _replace() was added by him as\noptimization, so \"this new one is functionally equivalent to the\noriginal\" somewhat misses the point, even though we may all agree\nthat the change is a very good one overall in the end when we look\nat the entire picture.\n\n> From: Kristofer Karlsson \n>\n> Replace the standard sift-down in prio_queue_get() with a\n> cascade-down approach.\n>\n> The standard approach places the last array element at the root,\n> then sifts it down. At each level this requires two comparisons\n> (left vs right child, then element vs winner) and, when the\n> element is larger, a swap (three 16-byte copies).\n>\n> The cascade approach instead promotes the smaller child into the\n> vacant root slot at each level — one comparison and one copy.\n> The vacancy sinks to a leaf, where the last array element is\n> placed and sifted up if needed — typically zero levels since the\n> last array element tends to be large.\n>\n> In the common case, work per extract drops from 2d comparisons\n> + 3d copies to d comparisons + d copies: roughly half the\n> comparisons and a third of the data movement. The sift-up phase\n> can add work when the last element is smaller than ancestors of\n> the leaf vacancy, but this is rare in practice.\n>\n> Simplify prio_queue_replace() to a plain get+put sequence. This\n> is semantically equivalent: the old implementation wrote to slot 0\n> and sifted down, which has the same observable effect as removing\n> the root and inserting a new element. No caller observes queue\n> state between the two operations. The previous implementation\n> shared sift_down_root() with get, but the cascade approach no\n> longer accommodates that cleanly since sift_down_root() now\n> expects the element to reinsert at queue->array[queue->nr], left\n> there by prio_queue_get() after decrementing nr. This is fine in\n> practice: replace is only called from pop_most_recent_commit()\n> (fetch-pack, object-name, walker) and show-branch — none of\n> which appear in any hot path.\n>\n> A synthetic benchmark (10 rounds of 10M put+get cycles, ascending\n> integer keys, CPU-pinned, median of 3 runs, same compiler and\n> Makefile flags) shows consistent improvement across all queue\n> sizes, with no regressions:\n>\n> queue width baseline cascade speedup\n> ------------------------------------------------\n> 10 4.32s 3.97s 1.09x\n> 100 7.95s 6.49s 1.23x\n> 1,000 11.30s 9.66s 1.17x\n> 10,000 16.34s 14.15s 1.16x\n> 100,000 21.43s 18.66s 1.15x\n>\n> With descending keys (worst case — the last element always sinks\n> to a leaf in both approaches) the cascade still wins slightly\n> (1-4%) by replacing swaps with copies, and never regresses.\n>\n> In end-to-end git commands the improvement is modest because\n> sift_down_root is only ~8% of total runtime. Profiling\n> rev-list --count on a 2.5M-commit monorepo shows sift_down_root\n> dropping from 8.2% to 0.4% of total runtime. The improvement\n> scales with DAG width: wider DAGs produce larger priority queues,\n> amplifying the per-level savings. In small or narrow repos the\n> queues stay shallow and the effect is negligible.\n>\n> Signed-off-by: Kristofer Karlsson \n> ---\n> prio-queue: use cascade-down sift for faster extract-min\n> \n> Hi, I am not sure this is just noise or not but I thought it at least\n> was interesting.\n> \n> I looked into the internals of prio_queue and found it was technically\n> doing too much work and could be simplified/optimized. I found I could\n> optimize it by ~20% for the common case (adding commits that would\n> typically end up far back in the queue) but only ~1% for the reverse\n> case (adding things to the front of the prio queue). The average speedup\n> is somewhere in between I suppose. That said, this is not really the\n> bottleneck so the overall boost seems to be around ~3-4% improvement for\n> repos with wide DAGs.\n> \n> I would normally classify this as not urgent or important, but I think\n> the advantage is that the change is very small and simple and it already\n> has good unit tests (t/unit-tests/u-prio-queue.c).\n> \n> With that said, here are the details:\n> \n> The prio_queue_get impl is based on removing the root entry, then moving\n> the very last element into the root slot, then sifting it down into the\n> right place. This uses both comparisons between sibling elements in the\n> heap as well as comparisons between the element to add and one of the\n> siblings. Then it uses swap operations to move things correctly.\n> \n> This patch instead promotes the smaller child upward at each level,\n> leaving a vacancy that sinks to a leaf, then places the removed element\n> there with a short sift-up to keep the heap balanced.\n> \n> We can analytically compare this - for a sift-distance of d we can\n> reason about the number of operations to execute.\n> \n> Before: 2d comparisons + 3d copies\n> After: d comparisons + d copies\n> \n> \n> After changing sift_down in this way, the replace operation can't simply\n> depend on it anymore, so I reimplemented it as a sequence of get + put.\n> This is technically correct but maybe not as efficient. However, I am\n> not sure that it matters, since I couldn't see any usage of the replace\n> operation in any hot path.\n> \n> Performance: Profiling git rev-list --count on a 2.5M-commit monorepo\n> shows sift_down_root dropping from 8.2% to 0.4% of total runtime,\n> effectively eliminated as significant overhead.\n> \n> Synthetic benchmark 10 rounds of 10M put+get cycles, CPU-pinned, median\n> of 3 runs, same compiler and Makefile flags.\n> \n> Ascending keys (git's typical pattern -- parents have lower priority\n> than children):\n> \n> queue width baseline patched speedup\n> 10 4.32s 3.97s 1.09x\n> 100 7.95s 6.49s 1.23x\n> 1,000 11.30s 9.66s 1.17x\n> 10,000 16.34s 14.15s 1.16x\n> 100,000 21.43s 18.66s 1.15x\n> \n> \n> Descending keys (worst case — last element always sinks to leaf in both\n> approaches):\n> \n> queue width baseline patched speedup\n> 10 4.84s 4.78s 1.01x\n> 100 9.43s 9.20s 1.03x\n> 1,000 15.28s 14.71s 1.04x\n> 10,000 23.61s 23.49s 1.01x\n> 100,000 29.16s 28.22s 1.03x\n> \n> \n> No regressions in any scenario.\n> \n> End-to-end benchmarks\n> \n> All benchmarks use a benchmark setup of 1 warmup run followed by 10\n> timed runs. Each configuration is built from the same source tree and\n> tested on the same repo in alternating order.\n> \n> linux kernel (1.4M commits) — range v5.0..v6.0 (311K commits):\n> \n> Command baseline patched speedup\n> rev-list --count v5.0..v6.0 455ms 440ms 1.04x\n> \n> \n> I also ran it on git.git but did not see any performance diff at all,\n> due to the size and narrow DAG.\n> \n> The improvement scales with DAG width: wider DAGs produce larger\n> priority queues, amplifying the per-level savings. In small or narrow\n> repositories the priority queues stay shallow and the sift-down cost is\n> already negligible, so the change is not noticeable.\n>\n> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2132%2Fspkrka%2Fcascade-sift-down-v1\n> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2132/spkrka/cascade-sift-down-v1\n> Pull-Request: https://github.com/gitgitgadget/git/pull/2132\n>\n> prio-queue.c | 22 ++++++++++++----------\n> 1 file changed, 12 insertions(+), 10 deletions(-)\n>\n> diff --git a/prio-queue.c b/prio-queue.c\n> index 9748528ce6..18005c43c4 100644\n> --- a/prio-queue.c\n> +++ b/prio-queue.c\n> @@ -62,17 +62,21 @@ 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> +\tfor (ix = 0; (child = ix * 2 + 1) < queue->nr; ix = child) {\n> \t\tif (child + 1 < queue->nr &&\n> \t\t compare(queue, child, child + 1) >= 0)\n> \t\t\tchild++; /* use right child */\n> +\t\tqueue->array[ix] = queue->array[child];\n> +\t}\n> \n> -\t\tif (compare(queue, ix, child) <= 0)\n> +\t/* Place queue->array[queue->nr] (left by caller) and sift up. */\n> +\tqueue->array[ix] = queue->array[queue->nr];\n> +\twhile (ix) {\n> +\t\tsize_t parent = (ix - 1) / 2;\n> +\t\tif (compare(queue, parent, ix) <= 0)\n> \t\t\tbreak;\n> -\n> -\t\tswap(queue, child, ix);\n> +\t\tswap(queue, parent, ix);\n> +\t\tix = parent;\n> \t}\n> }\n> \n> @@ -89,7 +93,6 @@ void *prio_queue_get(struct prio_queue *queue)\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> @@ -111,8 +114,7 @@ void prio_queue_replace(struct prio_queue *queue, void *thing)\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\tprio_queue_get(queue);\n> +\t\tprio_queue_put(queue, thing);\n> \t}\n> }\n>\n> base-commit: c69baaf57ba26cf117c2b6793802877f19738b0d\n"},{"id":"544345","messageId":"xmqq5x42aipu.fsf@gitster.g","threadId":"65720","inReplyTo":"pull.2132.git.1780250236304.gitgitgadget@gmail.com","subject":"Re: [PATCH] prio-queue: use cascade-down sift for faster extract-min","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-06-01T06:16:29Z","receivedAt":"2026-06-01T06:16:31Z","isPatch":true,"body":"\"Kristofer Karlsson via GitGitGadget\" \nwrites:\n\n> diff --git a/prio-queue.c b/prio-queue.c\n> index 9748528ce6..18005c43c4 100644\n> --- a/prio-queue.c\n> +++ b/prio-queue.c\n> @@ -62,17 +62,21 @@ 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> +\tfor (ix = 0; (child = ix * 2 + 1) < queue->nr; ix = child) {\n> \t\tif (child + 1 < queue->nr &&\n> \t\t compare(queue, child, child + 1) >= 0)\n> \t\t\tchild++; /* use right child */\n> +\t\tqueue->array[ix] = queue->array[child];\n> +\t}\n> \n> -\t\tif (compare(queue, ix, child) <= 0)\n> +\t/* Place queue->array[queue->nr] (left by caller) and sift up. */\n> +\tqueue->array[ix] = queue->array[queue->nr];\n\nHere we always sift/bubble up the last element.\n\nI am wondering if it makes sense to teach sift_down_root to take an\nextra argument, \"struct prio_queue_entry entry\" (passed by value)\nand sift/bubble it up, not always queue->array[queue->nr], and ...\n\n> +\twhile (ix) {\n> +\t\tsize_t parent = (ix - 1) / 2;\n> +\t\tif (compare(queue, parent, ix) <= 0)\n> \t\t\tbreak;\n> -\n> -\t\tswap(queue, child, ix);\n> +\t\tswap(queue, parent, ix);\n> +\t\tix = parent;\n> \t}\n> }\n> \n> @@ -89,7 +93,6 @@ void *prio_queue_get(struct prio_queue *queue)\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> @@ -111,8 +114,7 @@ void prio_queue_replace(struct prio_queue *queue, void *thing)\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\tprio_queue_get(queue);\n> +\t\tprio_queue_put(queue, thing);\n\n... update this part in the else clause to do something like\n\n\t\tstruct prio_queue_entry entry;\n\t\tentry.ctr = queue->insertion_ctr++;\n\t\tentry.data = thing;\n\t\tsift_down_root(queue, entry);\n\nto retain the optimization? It would perform a single cascade-down\nsift, followed by a single sift-up, so it would save a comparison, a\ncopy, and a swap in the worset case compared to the get+put sequence?\n\nOf course, the original sift_down_root() caller (i.e. prio_queue_get())\nneeds to pass queue->array[queue->nr] as the second parameter to match.\n\n> \t}\n> }\n>\n> base-commit: c69baaf57ba26cf117c2b6793802877f19738b0d\n"},{"id":"544346","messageId":"CAL71e4PjZz-BLpRzXd9MXnoWzHHGHzTYyGw0xM9ntg+iRATN2Q@mail.gmail.com","threadId":"65720","inReplyTo":"xmqq5x42aipu.fsf@gitster.g","subject":"Re: [PATCH] prio-queue: use cascade-down sift for faster extract-min","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-06-01T06:21:57Z","receivedAt":"2026-06-01T06:22:09Z","isPatch":true,"body":"Thanks for the quick and very valid feedback! I already started\ninvestigating - I think I was too quick (and wrong) when I reasoned\nabout the replace operation.I will rework it a bit and come back with\na patch version 2 soon that ensures that neither get and replace have\nregressed in any way.\n\n- Kristofer\n\nOn Mon, 1 Jun 2026 at 08:16, Junio C Hamano wrote:\n>\n> \"Kristofer Karlsson via GitGitGadget\" \n> writes:\n>\n> > diff --git a/prio-queue.c b/prio-queue.c\n> > index 9748528ce6..18005c43c4 100644\n> > --- a/prio-queue.c\n> > +++ b/prio-queue.c\n> > @@ -62,17 +62,21 @@ static void sift_down_root(struct prio_queue *queue)\n> > {\n> > size_t ix, child;\n> >\n> > - /* Push down the one at the root */\n> > - for (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {\n> > - child = ix * 2 + 1; /* left */\n> > + for (ix = 0; (child = ix * 2 + 1) < queue->nr; ix = child) {\n> > if (child + 1 < queue->nr &&\n> > compare(queue, child, child + 1) >= 0)\n> > child++; /* use right child */\n> > + queue->array[ix] = queue->array[child];\n> > + }\n> >\n> > - if (compare(queue, ix, child) <= 0)\n> > + /* Place queue->array[queue->nr] (left by caller) and sift up. */\n> > + queue->array[ix] = queue->array[queue->nr];\n>\n> Here we always sift/bubble up the last element.\n>\n> I am wondering if it makes sense to teach sift_down_root to take an\n> extra argument, \"struct prio_queue_entry entry\" (passed by value)\n> and sift/bubble it up, not always queue->array[queue->nr], and ...\n>\n> > + while (ix) {\n> > + size_t parent = (ix - 1) / 2;\n> > + if (compare(queue, parent, ix) <= 0)\n> > break;\n> > -\n> > - swap(queue, child, ix);\n> > + swap(queue, parent, ix);\n> > + ix = parent;\n> > }\n> > }\n> >\n> > @@ -89,7 +93,6 @@ void *prio_queue_get(struct prio_queue *queue)\n> > if (!--queue->nr)\n> > return result;\n> >\n> > - queue->array[0] = queue->array[queue->nr];\n> > sift_down_root(queue);\n> > return result;\n> > }\n> > @@ -111,8 +114,7 @@ void prio_queue_replace(struct prio_queue *queue, void *thing)\n> > queue->array[queue->nr - 1].ctr = queue->insertion_ctr++;\n> > queue->array[queue->nr - 1].data = thing;\n> > } else {\n> > - queue->array[0].ctr = queue->insertion_ctr++;\n> > - queue->array[0].data = thing;\n> > - sift_down_root(queue);\n> > + prio_queue_get(queue);\n> > + prio_queue_put(queue, thing);\n>\n> ... update this part in the else clause to do something like\n>\n> struct prio_queue_entry entry;\n> entry.ctr = queue->insertion_ctr++;\n> entry.data = thing;\n> sift_down_root(queue, entry);\n>\n> to retain the optimization? It would perform a single cascade-down\n> sift, followed by a single sift-up, so it would save a comparison, a\n> copy, and a swap in the worset case compared to the get+put sequence?\n>\n> Of course, the original sift_down_root() caller (i.e. prio_queue_get())\n> needs to pass queue->array[queue->nr] as the second parameter to match.\n>\n> > }\n> > }\n> >\n> > base-commit: c69baaf57ba26cf117c2b6793802877f19738b0d\n"},{"id":"544354","messageId":"pull.2132.v2.git.1780301856444.gitgitgadget@gmail.com","threadId":"65720","inReplyTo":"pull.2132.git.1780250236304.gitgitgadget@gmail.com","subject":"[PATCH v2] prio-queue: use cascade-down for faster extract-min","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-06-01T08:17:35Z","receivedAt":"2026-06-01T08:17:38Z","isPatch":true,"body":"From: Kristofer Karlsson \n\nAdd sift_up_rebalance(), an alternative to sift_down_root() that\nhalves the number of comparisons per extract-min.\n\nThe standard extract places the last array element at the root and\nsifts it down. At each level this requires two comparisons (left\nvs right child, then element vs winner) and a swap.\n\nsift_up_rebalance() instead promotes the smaller child into the\nroot slot at each level — one comparison and one copy — until the\nvacancy reaches a leaf. The last array element is placed at the\nvacancy and sifted up to restore heap order. In practice the\nsift-up rarely moves more than a level or two because the last\narray element tends to be large.\n\nWork per extract drops from 2d comparisons + d swaps to\nd comparisons + d copies + a short sift-up.\n\nprio_queue_get() now calls sift_up_rebalance() instead of placing\nthe last element at root and calling sift_down_root().\n\nsift_down_root() and prio_queue_replace() are left unchanged.\n\nSynthetic benchmark (10 rounds of 10M put+get cycles, CPU-pinned,\nsame compiler and Makefile flags):\n\nAscending keys (git's typical pattern — parents have lower\npriority than children):\n\n queue width baseline patched speedup\n 10 4.39s 3.91s 1.12x\n 100 9.10s 6.61s 1.38x\n 1,000 11.84s 9.25s 1.28x\n 10,000 17.50s 13.92s 1.26x\n 100,000 23.97s 20.19s 1.19x\n\nDescending keys (worst case — last element always sinks to leaf):\n\n queue width baseline patched speedup\n 10 4.94s 4.95s 1.00x\n 100 9.75s 9.42s 1.03x\n 1,000 15.01s 15.29s 0.98x\n 10,000 24.79s 23.88s 1.04x\n 100,000 29.69s 28.24s 1.05x\n\nRandom keys:\n\n queue width baseline patched speedup\n 10 5.05s 4.99s 1.01x\n 100 9.90s 9.50s 1.04x\n 1,000 15.35s 14.77s 1.04x\n 10,000 25.35s 24.21s 1.05x\n 100,000 65.71s 63.38s 1.04x\n\nNo regressions in any scenario.\n\nEnd-to-end benchmark on the linux kernel repo (1.4M commits,\nrange v5.0..v6.0, 311K commits, 20 interleaved runs, 1 warmup):\n\n Command baseline patched speedup\n rev-list --count v5.0..v6.0 484ms 474ms 1.02x\n\nThe improvement scales with DAG width: wider DAGs produce larger\npriority queues, amplifying the per-level savings. In small or\nnarrow repositories the queues stay shallow and the sift-down\ncost is already negligible.\n\nSigned-off-by: Kristofer Karlsson \n---\n prio-queue: use cascade-down sift for faster extract-min\n \n This is a small optimization to prio_queue_get() that reduces the number\n of comparisons per extract-min from 2d to d (where d is the sift\n distance).\n \n The standard extract places the last array element at the root and sifts\n it down, comparing against both children at each level. The new\n sift_up_rebalance() instead promotes the smaller child at each level\n (one comparison and one copy) leaving a vacancy that sinks to a leaf.\n The last element is placed there and sifted up, which in practice rarely\n moves more than a level or two.\n \n The improvement shows clearly in synthetic benchmarks (up to 1.38x for\n ascending keys at queue width 100) but is modest end-to-end since\n sift_down_root is only a fraction of total runtime. On the linux kernel\n repo, rev-list --count v5.0..v6.0 improves by ~2%. The effect scales\n with DAG width.\n \n Changes since v1:\n \n * Kept sift_down_root() and prio_queue_replace() completely unchanged,\n preserving René's optimization that avoids the get+put overhead for\n replace. The cascade approach now only applies to prio_queue_get().\n \n * Extracted the new logic into a separate sift_up_rebalance() function\n rather than inlining it in prio_queue_get().\n \n * Updated benchmark numbers for ascending, descending and random\n insertion ordering. No regressions in any scenario.\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2132%2Fspkrka%2Fcascade-sift-down-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2132/spkrka/cascade-sift-down-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/2132\n\nRange-diff vs v1:\n\n 1: 9ca2fab4dc ! 1: 6051d44e59 prio-queue: use cascade-down sift for faster extract-min\n @@ Metadata\n Author: Kristofer Karlsson \n \n ## Commit message ##\n - prio-queue: use cascade-down sift for faster extract-min\n -\n - Replace the standard sift-down in prio_queue_get() with a\n - cascade-down approach.\n -\n - The standard approach places the last array element at the root,\n - then sifts it down. At each level this requires two comparisons\n - (left vs right child, then element vs winner) and, when the\n - element is larger, a swap (three 16-byte copies).\n -\n - The cascade approach instead promotes the smaller child into the\n - vacant root slot at each level — one comparison and one copy.\n - The vacancy sinks to a leaf, where the last array element is\n - placed and sifted up if needed — typically zero levels since the\n - last array element tends to be large.\n -\n - In the common case, work per extract drops from 2d comparisons\n - + 3d copies to d comparisons + d copies: roughly half the\n - comparisons and a third of the data movement. The sift-up phase\n - can add work when the last element is smaller than ancestors of\n - the leaf vacancy, but this is rare in practice.\n -\n - Simplify prio_queue_replace() to a plain get+put sequence. This\n - is semantically equivalent: the old implementation wrote to slot 0\n - and sifted down, which has the same observable effect as removing\n - the root and inserting a new element. No caller observes queue\n - state between the two operations. The previous implementation\n - shared sift_down_root() with get, but the cascade approach no\n - longer accommodates that cleanly since sift_down_root() now\n - expects the element to reinsert at queue->array[queue->nr], left\n - there by prio_queue_get() after decrementing nr. This is fine in\n - practice: replace is only called from pop_most_recent_commit()\n - (fetch-pack, object-name, walker) and show-branch — none of\n - which appear in any hot path.\n -\n - A synthetic benchmark (10 rounds of 10M put+get cycles, ascending\n - integer keys, CPU-pinned, median of 3 runs, same compiler and\n - Makefile flags) shows consistent improvement across all queue\n - sizes, with no regressions:\n -\n - queue width baseline cascade speedup\n - ------------------------------------------------\n - 10 4.32s 3.97s 1.09x\n - 100 7.95s 6.49s 1.23x\n - 1,000 11.30s 9.66s 1.17x\n - 10,000 16.34s 14.15s 1.16x\n - 100,000 21.43s 18.66s 1.15x\n -\n - With descending keys (worst case — the last element always sinks\n - to a leaf in both approaches) the cascade still wins slightly\n - (1-4%) by replacing swaps with copies, and never regresses.\n -\n - In end-to-end git commands the improvement is modest because\n - sift_down_root is only ~8% of total runtime. Profiling\n - rev-list --count on a 2.5M-commit monorepo shows sift_down_root\n - dropping from 8.2% to 0.4% of total runtime. The improvement\n - scales with DAG width: wider DAGs produce larger priority queues,\n - amplifying the per-level savings. In small or narrow repos the\n - queues stay shallow and the effect is negligible.\n + prio-queue: use cascade-down for faster extract-min\n +\n + Add sift_up_rebalance(), an alternative to sift_down_root() that\n + halves the number of comparisons per extract-min.\n +\n + The standard extract places the last array element at the root and\n + sifts it down. At each level this requires two comparisons (left\n + vs right child, then element vs winner) and a swap.\n +\n + sift_up_rebalance() instead promotes the smaller child into the\n + root slot at each level — one comparison and one copy — until the\n + vacancy reaches a leaf. The last array element is placed at the\n + vacancy and sifted up to restore heap order. In practice the\n + sift-up rarely moves more than a level or two because the last\n + array element tends to be large.\n +\n + Work per extract drops from 2d comparisons + d swaps to\n + d comparisons + d copies + a short sift-up.\n +\n + prio_queue_get() now calls sift_up_rebalance() instead of placing\n + the last element at root and calling sift_down_root().\n +\n + sift_down_root() and prio_queue_replace() are left unchanged.\n +\n + Synthetic benchmark (10 rounds of 10M put+get cycles, CPU-pinned,\n + same compiler and Makefile flags):\n +\n + Ascending keys (git's typical pattern — parents have lower\n + priority than children):\n +\n + queue width baseline patched speedup\n + 10 4.39s 3.91s 1.12x\n + 100 9.10s 6.61s 1.38x\n + 1,000 11.84s 9.25s 1.28x\n + 10,000 17.50s 13.92s 1.26x\n + 100,000 23.97s 20.19s 1.19x\n +\n + Descending keys (worst case — last element always sinks to leaf):\n +\n + queue width baseline patched speedup\n + 10 4.94s 4.95s 1.00x\n + 100 9.75s 9.42s 1.03x\n + 1,000 15.01s 15.29s 0.98x\n + 10,000 24.79s 23.88s 1.04x\n + 100,000 29.69s 28.24s 1.05x\n +\n + Random keys:\n +\n + queue width baseline patched speedup\n + 10 5.05s 4.99s 1.01x\n + 100 9.90s 9.50s 1.04x\n + 1,000 15.35s 14.77s 1.04x\n + 10,000 25.35s 24.21s 1.05x\n + 100,000 65.71s 63.38s 1.04x\n +\n + No regressions in any scenario.\n +\n + End-to-end benchmark on the linux kernel repo (1.4M commits,\n + range v5.0..v6.0, 311K commits, 20 interleaved runs, 1 warmup):\n +\n + Command baseline patched speedup\n + rev-list --count v5.0..v6.0 484ms 474ms 1.02x\n +\n + The improvement scales with DAG width: wider DAGs produce larger\n + priority queues, amplifying the per-level savings. In small or\n + narrow repositories the queues stay shallow and the sift-down\n + cost is already negligible.\n \n Signed-off-by: Kristofer Karlsson \n \n ## prio-queue.c ##\n @@ prio-queue.c: static void sift_down_root(struct prio_queue *queue)\n - {\n - \tsize_t ix, child;\n + \t}\n + }\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 ++static void sift_up_rebalance(struct prio_queue *queue)\n ++{\n ++\tsize_t ix, child;\n ++\n ++\t/* Cascade: promote smaller child at each level. */\n +\tfor (ix = 0; (child = ix * 2 + 1) < queue->nr; ix = child) {\n - \t\tif (child + 1 < queue->nr &&\n - \t\t compare(queue, child, child + 1) >= 0)\n - \t\t\tchild++; /* use right child */\n ++\t\tif (child + 1 < queue->nr &&\n ++\t\t compare(queue, child, child + 1) >= 0)\n ++\t\t\tchild++;\n +\t\tqueue->array[ix] = queue->array[child];\n +\t}\n - \n --\t\tif (compare(queue, ix, child) <= 0)\n -+\t/* Place queue->array[queue->nr] (left by caller) and sift up. */\n ++\n ++\t/* Place the last element at the vacancy and sift up. */\n +\tqueue->array[ix] = queue->array[queue->nr];\n +\twhile (ix) {\n +\t\tsize_t parent = (ix - 1) / 2;\n +\t\tif (compare(queue, parent, ix) <= 0)\n - \t\t\tbreak;\n --\n --\t\tswap(queue, child, ix);\n ++\t\t\tbreak;\n +\t\tswap(queue, parent, ix);\n +\t\tix = parent;\n - \t}\n - }\n - \n ++\t}\n ++}\n ++\n + void *prio_queue_get(struct prio_queue *queue)\n + {\n + \tvoid *result;\n @@ prio-queue.c: void *prio_queue_get(struct prio_queue *queue)\n \tif (!--queue->nr)\n \t\treturn result;\n \n -\tqueue->array[0] = queue->array[queue->nr];\n - \tsift_down_root(queue);\n +-\tsift_down_root(queue);\n ++\tsift_up_rebalance(queue);\n \treturn result;\n }\n -@@ prio-queue.c: void prio_queue_replace(struct prio_queue *queue, void *thing)\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\tprio_queue_get(queue);\n -+\t\tprio_queue_put(queue, thing);\n - \t}\n - }\n + \n\n\n prio-queue.c | 26 ++++++++++++++++++++++++--\n 1 file changed, 24 insertions(+), 2 deletions(-)\n\ndiff --git a/prio-queue.c b/prio-queue.c\nindex 9748528ce6..66d445b078 100644\n--- a/prio-queue.c\n+++ b/prio-queue.c\n@@ -76,6 +76,29 @@ static void sift_down_root(struct prio_queue *queue)\n \t}\n }\n \n+static void sift_up_rebalance(struct prio_queue *queue)\n+{\n+\tsize_t ix, child;\n+\n+\t/* Cascade: promote smaller child at each level. */\n+\tfor (ix = 0; (child = ix * 2 + 1) < queue->nr; ix = child) {\n+\t\tif (child + 1 < queue->nr &&\n+\t\t compare(queue, child, child + 1) >= 0)\n+\t\t\tchild++;\n+\t\tqueue->array[ix] = queue->array[child];\n+\t}\n+\n+\t/* Place the last element at the vacancy and sift up. */\n+\tqueue->array[ix] = queue->array[queue->nr];\n+\twhile (ix) {\n+\t\tsize_t parent = (ix - 1) / 2;\n+\t\tif (compare(queue, parent, ix) <= 0)\n+\t\t\tbreak;\n+\t\tswap(queue, parent, ix);\n+\t\tix = parent;\n+\t}\n+}\n+\n void *prio_queue_get(struct prio_queue *queue)\n {\n \tvoid *result;\n@@ -89,8 +112,7 @@ void *prio_queue_get(struct prio_queue *queue)\n \tif (!--queue->nr)\n \t\treturn result;\n \n-\tqueue->array[0] = queue->array[queue->nr];\n-\tsift_down_root(queue);\n+\tsift_up_rebalance(queue);\n \treturn result;\n }\n \n\nbase-commit: 1666c1265231b0bc5f613fbbf3f0a9896cdef76e\n-- \ngitgitgadget\n"},{"id":"544535","messageId":"90270818-c52b-4611-8da2-6cee20628fc2@web.de","threadId":"65720","inReplyTo":"pull.2132.v2.git.1780301856444.gitgitgadget@gmail.com","subject":"Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-06-02T16:36:48Z","receivedAt":"2026-06-02T16:36:56Z","isPatch":true,"body":"On 6/1/26 10:17 AM, Kristofer Karlsson via GitGitGadget wrote:\n> \n> Changes since v1:\n> \n> * Kept sift_down_root() and prio_queue_replace() completely unchanged,\n> preserving René's optimization that avoids the get+put overhead for\n> replace. The cascade approach now only applies to prio_queue_get().\n\nThe prospect of no longer needing prio_queue_replace() had me excited in\nround 1. The benchmarks from commits that added its callers [1][2][3]\ndid show performance regressions with your patch 1 plus changes to\nrevert prio_queue_peek()+prio_queue_replace() to prio_queue_get()+\nprio_queue_put(), but for two of them low enough to be in the noise.\n'git describe $(git rev-list v2.41.0..v2.47.0)' took a 50%+ hit, though.\n\n[1] a79e3519d6 (commit: use prio_queue_replace() in pop_most_recent_commit(), 2025-07-18)\n[2] 08bb69d70f (describe: use prio_queue_replace(), 2025-08-03)\n[3] abf05d856f (show-branch: use prio_queue, 2025-12-26)\n\n> * Extracted the new logic into a separate sift_up_rebalance() function\n> rather than inlining it in prio_queue_get().\n> \n> * Updated benchmark numbers for ascending, descending and random\n> insertion ordering. No regressions in any scenario.\n\nI don't see any regression for the benchmarks mentioned above with\npatch 2 alone, unsurprisingly. The describe command still takes that\n50%+ performance hit after reverting [2] on top.\n\nWould you be interested in benchmarking the following patch for making\nprio_queue_replace() unnecessary by doing its optimization\nautomatically? I get a 1% performance hit for the describe command\nthat I can't explain. And it leaves the heap unbalanced after a\nprio_queue_get(), which complicates things, so I found it lacking.\nBut I wonder how it stacks up against your cascade approach for your\nuse case and if there's anything to salvage.\n\nRené\n\n\n---\n prio-queue.c | 60 +++++++++++++++++++++++++++++++++++++++++-------------------\n prio-queue.h | 1 +\n 2 files changed, 42 insertions(+), 19 deletions(-)\n\ndiff --git a/prio-queue.c b/prio-queue.c\nindex 9748528ce6..ba6b460a46 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@@ -58,24 +92,6 @@ void prio_queue_put(struct prio_queue *queue, void *thing)\n \t}\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-}\n-\n void *prio_queue_get(struct prio_queue *queue)\n {\n \tvoid *result;\n@@ -85,12 +101,14 @@ void *prio_queue_get(struct prio_queue *queue)\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-\tsift_down_root(queue);\n+\tqueue->sift_down_root_pending = true;\n \treturn result;\n }\n \n@@ -100,6 +118,8 @@ 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 }\n \n@@ -111,6 +131,8 @@ void prio_queue_replace(struct prio_queue *queue, void *thing)\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\tif (queue->sift_down_root_pending)\n+\t\t\tsift_down_root(queue);\n \t\tqueue->array[0].ctr = queue->insertion_ctr++;\n \t\tqueue->array[0].data = thing;\n \t\tsift_down_root(queue);\ndiff --git a/prio-queue.h b/prio-queue.h\nindex da7fad2f1f..5977fba438 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\n"},{"id":"544561","messageId":"CAL71e4Ob-B5MJ5DPY+_tzpj6nyrbQ5WutxED2T93SWJV6kJGPA@mail.gmail.com","threadId":"65720","inReplyTo":"90270818-c52b-4611-8da2-6cee20628fc2@web.de","subject":"Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-06-02T22:40:55Z","receivedAt":"2026-06-02T22:41:07Z","isPatch":true,"body":"On Tue, 2 Jun 2026 at 18:37, René Scharfe wrote:\n>\n> Would you be interested in benchmarking the following patch for making\n> prio_queue_replace() unnecessary by doing its optimization\n> automatically? I get a 1% performance hit for the describe command\n> that I can't explain. And it leaves the heap unbalanced after a\n> prio_queue_get(), which complicates things, so I found it lacking.\n> But I wonder how it stacks up against your cascade approach for your\n> use case and if there's anything to salvage.\n>\n> René\n\nThank you for the detailed feedback and the patch! It was very\nhelpful to have a concrete alternative to compare against.\n\nI spent some time benchmarking the different approaches on a\nlarge monorepo with a wide DAG.\n\nAll measurements include the nonstale O(1) tracking from my other\nseries as a common base, since that dominates the merge-base path.\n\nThe approaches I compared:\n\n 1. cascade-only: the sift_up_rebalance from this patch (v2)\n 2. rene-lazy: your deferred sift_down_root patch\n 3. cascade+lazy: cascade for unfused gets, lazy fusion for\n get+put pairs\n\nResults (10 runs, 1 warmup, CPU pinned to performance):\n\n merge-base --all master master~1000 (~4s workload):\n\n cascade-only 4.18s (median)\n rene-lazy 4.25s\n cascade+lazy 4.24s\n\n rev-list --count master~1000..master (~3.8s workload):\n\n cascade-only 3.86s\n rene-lazy 3.75s\n cascade+lazy 3.74s\n\nThe lazy approaches show a small win on rev-list (~3%) where get+put\npairs are common in limit_list. On merge-base --all, everything is\nwithin noise, the prio_queue is a small fraction of total runtime\nthere. Combining cascade with lazy fusion didn't produce additional\ngains beyond what each gives individually.\n\nLooking at your patch, I think the deferred sift-down logic is\nessentially the same optimization as the lazy_queue wrapper you\nwrote for describe.c - both defer the work from get and fuse it\nwith a following put. So I'd be hesitant to add a second form of\nthat deferral directly into prio_queue when lazy_queue already\n\"owns\" that responsibility as a wrapper.\n\nThat said, I think it would make sense to fold lazy_queue entirely\ninto prio_queue. It's an optimization that never hurts as far as I can\ntell, and it would simplify several callers. pop_most_recent_commit\nand show-branch both independently re-implement the same\npeek+replace pattern that lazy_queue formalizes. Making it automatic\nin prio_queue would clean up all of them.\n\nI have a local branch exploring that direction. Maybe it makes more\nsense to do the lazy_queue fold first, and then see if the cascade\nchange is still worth adding on top?\n\nEither way, I think the two directions are complementary - cascade\nreduces comparisons per sift, while lazy fusion can eliminate full\nrebalance cycles.\n\nI'm on a company offsite now so I may be slow to answer, but I will\ndefinitely resume this when I get back home.\n\n- Kristofer\n"},{"id":"544824","messageId":"CAL71e4PV-1aDvn1JnweMa3OR1xxB75fWjzJOBvM54KOWqC0stw@mail.gmail.com","threadId":"65720","inReplyTo":"CAL71e4Ob-B5MJ5DPY+_tzpj6nyrbQ5WutxED2T93SWJV6kJGPA@mail.gmail.com","subject":"Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-06-05T20:39:32Z","receivedAt":"2026-06-05T20:39:45Z","isPatch":true,"body":"I did some more benchmarking to understand how these approaches\ninteract, with four variants based on origin/next on my large monorepo:\n\n 1. base: next as-is\n 2. cascade: base + sift_up_rebalance from this patch (v2)\n 3. lazy-fold: base + lazy get fusion folded into prio_queue\n 4. cascade+lazy: both combined\n\nNote that alt 3 is not yet shared with the mailing list so it's hard for you\nto reason about it, though it's quite straightforward. I will submit a new\npatch for that one soon, not necessarily with the primary goal to merge it,\nbut rather show how it is implemented.\n\n merge-base --all master master~1000:\n base 4.27s\n cascade 4.07s (1.05x)\n lazy-fold 4.12s (1.03x)\n cascade+lazy 4.01s (1.06x)\n\n rev-list --count master~1000..master:\n base 3.60s\n cascade 3.35s (1.08x)\n lazy-fold 3.37s (1.07x)\n cascade+lazy 3.30s (1.09x)\n\nSo both optimizations are valuable both on their own, and when combined,\nwhich I think helps to reason about it. This cascading sift seems to have a\nlarger effect, but folding lazy_queue into prio_queue also speeds up other\nuse cases and simplifies the code a bit.\n\nBased on this, my (very subjective) approach would be:\n\n1. Land this cascade patch first since it's a pure algorithmic improvement,\n2. Follow up with a separate patch that folds lazy_queue into\n prio_queue. Will post it separately soon, as I mentioned.\n\n- Kristofer\n"},{"id":"544839","messageId":"1aa5b755-0f74-46d5-bd6e-a9cb7f3fbb12@web.de","threadId":"65720","inReplyTo":"CAL71e4PV-1aDvn1JnweMa3OR1xxB75fWjzJOBvM54KOWqC0stw@mail.gmail.com","subject":"Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-06-07T07:30:39Z","receivedAt":"2026-06-07T07:30:47Z","isPatch":true,"body":"On 6/5/26 10:39 PM, Kristofer Karlsson wrote:\n> I did some more benchmarking to understand how these approaches\n> interact, with four variants based on origin/next on my large monorepo:\n> \n> 1. base: next as-is\n> 2. cascade: base + sift_up_rebalance from this patch (v2)\n> 3. lazy-fold: base + lazy get fusion folded into prio_queue\n> 4. cascade+lazy: both combined\n> \n> Note that alt 3 is not yet shared with the mailing list so it's hard for you\n> to reason about it, though it's quite straightforward. I will submit a new\n> patch for that one soon, not necessarily with the primary goal to merge it,\n> but rather show how it is implemented.\n> \n> merge-base --all master master~1000:\n> base 4.27s\n> cascade 4.07s (1.05x)\n> lazy-fold 4.12s (1.03x)\n> cascade+lazy 4.01s (1.06x)\n> \n> rev-list --count master~1000..master:\n> base 3.60s\n> cascade 3.35s (1.08x)\n> lazy-fold 3.37s (1.07x)\n> cascade+lazy 3.30s (1.09x)\n> \n> So both optimizations are valuable both on their own, and when combined,\n> which I think helps to reason about it. This cascading sift seems to have a\n> larger effect, but folding lazy_queue into prio_queue also speeds up other\n> use cases and simplifies the code a bit.\nRight. I was wondering, though: Why is sift-down so much faster than\ncascade in the describe benchmark from 30598ccc4d (describe: use oidset\nin finish_depth_computation(), 2025-09-02)?\n\nI think I mostly understand it now: cascade is better in prio_queue_get()\nbecause the sift-down item is from the bottom and will likely end up back\nat the bottom, just of a different branch of the heap. Thus a sift-down\ncosts 3 compares times the number of levels, while a cascade costs just\n2 compares times the number of levels and there is likely little to no\nneed to sift it back up.\n\nFor prio_queue_replace() we sift down a random item, though; we don't\nknow where it will end up. If it belongs at the very top then sift-down\njust needs 3 compares, while cascade needs 2 compares times the number\nof levels to bring the hole down and the same to bring the item up.\n\nBelow is a diff on top of your second cascade patch to use sift-down\nonly for the root and cascade otherwise. It comes remarkably close to\nthe performance of a full sift-down. I don't know how to find the\noptimal number of levels to try sift-down before switching to cascade\nfor a given random item, though.\n\nSo I guess we keep the full sift-down for prio_queue_replace(), knowing\nthat sometimes we have a lot of items that end up at or close to the\nroot of the heap.\n\nBenchmark 1: ./git_main describe $(git rev-list v2.41.0..v2.47.0)\n Time (mean ± σ): 602.4 ms ± 1.2 ms [User: 539.2 ms, System: 47.7 ms]\n Range (min … max): 600.5 ms … 604.7 ms 10 runs\n\nBenchmark 2: ./git_cascade1 describe $(git rev-list v2.41.0..v2.47.0)\n Time (mean ± σ): 993.9 ms ± 1.7 ms [User: 930.2 ms, System: 48.2 ms]\n Range (min … max): 991.1 ms … 996.6 ms 10 runs\n\nBenchmark 3: ./git_cascade2 describe $(git rev-list v2.41.0..v2.47.0)\n Time (mean ± σ): 602.4 ms ± 1.7 ms [User: 539.1 ms, System: 47.6 ms]\n Range (min … max): 599.9 ms … 606.2 ms 10 runs\n\nBenchmark 4: ./git describe $(git rev-list v2.41.0..v2.47.0)\n Time (mean ± σ): 625.4 ms ± 1.7 ms [User: 561.8 ms, System: 48.0 ms]\n Range (min … max): 623.4 ms … 627.9 ms 10 runs\n\nSummary\n ./git_main describe $(git rev-list v2.41.0..v2.47.0) ran\n 1.00 ± 0.00 times faster than ./git_cascade2 describe $(git rev-list v2.41.0..v2.47.0)\n 1.04 ± 0.00 times faster than ./git describe $(git rev-list v2.41.0..v2.47.0)\n 1.65 ± 0.00 times faster than ./git_cascade1 describe $(git rev-list v2.41.0..v2.47.0)\n\ngit_main and git_cascade2 (your v2): sift-down\ngit_cascade1 (your v1): cascade\ngit (your v2 and the patch below): sift-down for root then cascade\n\nRené\n\n\ndiff --git a/prio-queue.c b/prio-queue.c\nindex 66d445b078..4d7debc2ba 100644\n--- a/prio-queue.c\n+++ b/prio-queue.c\n@@ -58,30 +58,12 @@ void prio_queue_put(struct prio_queue *queue, void *thing)\n \t}\n }\n \n-static void sift_down_root(struct prio_queue *queue)\n+static void sift_up_rebalance(struct prio_queue *queue, size_t ix)\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-}\n-\n-static void sift_up_rebalance(struct prio_queue *queue)\n-{\n-\tsize_t ix, child;\n+\tsize_t child;\n \n \t/* Cascade: promote smaller child at each level. */\n-\tfor (ix = 0; (child = ix * 2 + 1) < queue->nr; ix = child) {\n+\tfor (; (child = ix * 2 + 1) < queue->nr; ix = child) {\n \t\tif (child + 1 < queue->nr &&\n \t\t compare(queue, child, child + 1) >= 0)\n \t\t\tchild++;\n@@ -112,7 +94,7 @@ void *prio_queue_get(struct prio_queue *queue)\n \tif (!--queue->nr)\n \t\treturn result;\n \n-\tsift_up_rebalance(queue);\n+\tsift_up_rebalance(queue, 0);\n \treturn result;\n }\n \n@@ -132,9 +114,20 @@ void prio_queue_replace(struct prio_queue *queue, void *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 if (queue->nr < 3) {\n+\t\tprio_queue_get(queue);\n+\t\tprio_queue_put(queue, thing);\n \t} else {\n-\t\tqueue->array[0].ctr = queue->insertion_ctr++;\n+\t\tsize_t child = compare(queue, 1, 2) <= 0 ? 1 : 2;\n+\t\tqueue->array[0].ctr = queue->insertion_ctr;\n \t\tqueue->array[0].data = thing;\n-\t\tsift_down_root(queue);\n+\t\tif (compare(queue, 0, child) <= 0) {\n+\t\t\tqueue->insertion_ctr++;\n+\t\t} else {\n+\t\t\tqueue->array[0] = queue->array[child];\n+\t\t\tqueue->nr--;\n+\t\t\tsift_up_rebalance(queue, child);\n+\t\t\tprio_queue_put(queue, thing);\n+\t\t}\n \t}\n }\n\n"},{"id":"544845","messageId":"CAL71e4MYNiScZjTwkApjDAjRh2LM0_SP59h5HCTywV-Pua03tw@mail.gmail.com","threadId":"65720","inReplyTo":"1aa5b755-0f74-46d5-bd6e-a9cb7f3fbb12@web.de","subject":"Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-06-07T12:07:21Z","receivedAt":"2026-06-07T12:07:33Z","isPatch":true,"body":"On Sat, 7 Jun 2026 at 09:30, Rene Scharfe wrote:\n>\n> Right. I was wondering, though: Why is sift-down so much faster than\n> cascade in the describe benchmark from 30598ccc4d (describe: use oidset\n> in finish_depth_computation(), 2025-09-02)?\n>\n> I think I mostly understand it now: cascade is better in prio_queue_get()\n> because the sift-down item is from the bottom and will likely end up back\n> at the bottom, just of a different branch of the heap. Thus a sift-down\n> costs 3 compares times the number of levels, while a cascade costs just\n> 2 compares times the number of levels and there is likely little to no\n> need to sift it back up.\n>\n> For prio_queue_replace() we sift down a random item, though; we don't\n> know where it will end up. If it belongs at the very top then sift-down\n> just needs 3 compares, while cascade needs 2 compares times the number\n> of levels to bring the hole down and the same to bring the item up.\n\nYes, I think that reasoning is correct. It depends on where the item\nwill land.\n\nFor get() the last array element came from the bottom of the heap\nand will almost certainly end up back near the bottom, so\ncascade's blind descent is a good default.\n\nFor replace() the new element is arbitrary -- in describe's pattern\nit often belongs near the root, so sift-down's early exit after\n2-3 compares dominates.\n\nYour benchmark confirms this: v2 (cascade only in get) matches the\nbaseline exactly for describe, while the hybrid is 4% slower.\n\n> So I guess we keep the full sift-down for prio_queue_replace(), knowing\n> that sometimes we have a lot of items that end up at or close to the\n> root of the heap.\n\nAgreed. And with the lazy-fold series (v3 just sent), replace() is\nremoved as a public API entirely. But the same principle applies to\nthe fused replace path inside prio_queue_put(): when get_pending is\nset and a put arrives, we write the new element at the root and\nsift it down -- that path should keep sift-down for the same reason\nyour analysis shows.\n\nIf (that's a big if) both my patches eventually land,\nthe split would be:\n - unfused get-flush (in get() and peek()): use cascade\n - fused replace (in put()): keep sift-down\n\nWhich is exactly the split your analysis predicts is optimal.\n\nNow I am thinking it would be easier to reason about this if the other\npatch lands first, since the cascade change becomes simpler to evaluate\nwhen replace is already gone and only the unfused paths remain.\n\n- Kristofer\n"},{"id":"544909","messageId":"xmqq4ijd1c0e.fsf@gitster.g","threadId":"65720","inReplyTo":"1aa5b755-0f74-46d5-bd6e-a9cb7f3fbb12@web.de","subject":"Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-06-08T11:56:33Z","receivedAt":"2026-06-08T11:56:35Z","isPatch":true,"body":"René Scharfe writes:\n\n> I think I mostly understand it now: cascade is better in prio_queue_get()\n> because the sift-down item is from the bottom and will likely end up back\n> at the bottom, just of a different branch of the heap. Thus a sift-down\n> costs 3 compares times the number of levels, while a cascade costs just\n> 2 compares times the number of levels and there is likely little to no\n> need to sift it back up.\n>\n> For prio_queue_replace() we sift down a random item, though; we don't\n> know where it will end up. If it belongs at the very top then sift-down\n> just needs 3 compares, while cascade needs 2 compares times the number\n> of levels to bring the hole down and the same to bring the item up.\n\nAn excellent observation, showing clear and analytic mind. This is\none of the reasons why I love reading review messages from you (and\nalso explanation in the proposed commit log messages in your\npatches).\n\nThanks.\n"},{"id":"546715","messageId":"xmqqv7b1t5d0.fsf@gitster.g","threadId":"65720","inReplyTo":"CAL71e4MYNiScZjTwkApjDAjRh2LM0_SP59h5HCTywV-Pua03tw@mail.gmail.com","subject":"Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-06-29T21:16:11Z","receivedAt":"2026-06-29T21:16:13Z","isPatch":true,"body":"Kristofer Karlsson writes:\n\n> Now I am thinking it would be easier to reason about this if the other\n> patch lands first, since the cascade change becomes simpler to evaluate\n> when replace is already gone and only the unfused paths remain.\n\nSorry, I should have noticed this message and responded earlier.\nLet's make sure that the \"other patch\" is ready then and merge it\ndown.\n\nSince June 8th, nothing seemed to have happened to the thread for\nthe \"other patch\".\n\n https://lore.kernel.org/git/pull.2140.v4.git.1780945851.gitgitgadget@gmail.com/\n\nIs everybody happy with these two patches?\n\nThanks.\n"},{"id":"547272","messageId":"CAL71e4NZYdpw5cvi6ARn1req8xaRGGg9X4xhZKp6S9Dz4K23aQ@mail.gmail.com","threadId":"65720","inReplyTo":"1aa5b755-0f74-46d5-bd6e-a9cb7f3fbb12@web.de","subject":"Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-07-06T21:52:34Z","receivedAt":"2026-07-06T21:52:49Z","isPatch":true,"body":"On Sun, 7 Jun 2026 at 09:30, René Scharfe wrote:\n>\n> So I guess we keep the full sift-down for prio_queue_replace(), knowing\n> that sometimes we have a lot of items that end up at or close to the\n> root of the heap.\n\nThe lazy-fold series (kk/prio-queue-get-put-fusion) is in next now.\nI rebased this cascade patch on top of it to check if it's still\nuseful.\n\nWith lazy-fold in place the regression scenario you identified\nis resolved. The only remaining change is in flush_get(),\nwhere unfused gets now cascade instead of sifting down:\n\n - queue->array[0] = queue->array[--queue->nr_];\n - sift_down_root(queue);\n + --queue->nr_;\n + sift_up_rebalance(queue);\n\nplus the ~20-line sift_up_rebalance() implementation.\n\nI benchmarked this on the linux kernel repo and on a large\nmerge-heavy repo.\n\nThe results are consistent: a real but small 1-2% end-to-end\nimprovement across commands. A prio-queue microbenchmark\nwould likely show a larger difference, but the queue\nis only a fraction of the total work in any real git operation.\n\nThe lazy-fold optimization cannibalized some of the value here,\nso cascade only helps the remaining unfused gets. As you observed,\ncascade is better there, but there are fewer of them now that there\nis more fusing happening.\n\nI am on the fence about whether 1-2% end-to-end justifies adding\nanother sift function. If you (René and Junio) think the benefit\nis too small for the code cost, I am happy to drop this patch.\nOtherwise I can submit a small reroll on top of\nkk/prio-queue-get-put-fusion (or rather next, in practice).\n\nThanks,\nKristofer\n"},{"id":"547481","messageId":"57bb0e9e-221d-4234-b5bc-a87610e8263c@web.de","threadId":"65720","inReplyTo":"CAL71e4NZYdpw5cvi6ARn1req8xaRGGg9X4xhZKp6S9Dz4K23aQ@mail.gmail.com","subject":"Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-07-08T10:43:52Z","receivedAt":"2026-07-08T10:44:04Z","isPatch":true,"body":"On 7/6/26 11:52 PM, Kristofer Karlsson wrote:\n> On Sun, 7 Jun 2026 at 09:30, René Scharfe wrote:\n>>\n>> So I guess we keep the full sift-down for prio_queue_replace(), knowing\n>> that sometimes we have a lot of items that end up at or close to the\n>> root of the heap.\n> \n> The lazy-fold series (kk/prio-queue-get-put-fusion) is in next now.\n> I rebased this cascade patch on top of it to check if it's still\n> useful.\n> \n> With lazy-fold in place the regression scenario you identified\n> is resolved. The only remaining change is in flush_get(),\n> where unfused gets now cascade instead of sifting down:\n> \n> - queue->array[0] = queue->array[--queue->nr_];\n> - sift_down_root(queue);\n> + --queue->nr_;\n> + sift_up_rebalance(queue);\n> \n> plus the ~20-line sift_up_rebalance() implementation.\n> \n> I benchmarked this on the linux kernel repo and on a large\n> merge-heavy repo.\n> \n> The results are consistent: a real but small 1-2% end-to-end\n> improvement across commands. A prio-queue microbenchmark\n> would likely show a larger difference, but the queue\n> is only a fraction of the total work in any real git operation.\n> \n> The lazy-fold optimization cannibalized some of the value here,\n> so cascade only helps the remaining unfused gets. As you observed,\n> cascade is better there, but there are fewer of them now that there\n> is more fusing happening.\n> \n> I am on the fence about whether 1-2% end-to-end justifies adding\n> another sift function. If you (René and Junio) think the benefit\n> is too small for the code cost, I am happy to drop this patch.\n> Otherwise I can submit a small reroll on top of\n> kk/prio-queue-get-put-fusion (or rather next, in practice).\n\ntl;dr: Yes, please, but I'm biased.\n\nThe text size of prio-queue.o on Apple silicon increases from 1351 to\n1563 bytes for me, 212 bytes or 16% more. OK.\n\nIt makes intuitive sense to find the new position of the last item by\nsearching from the bottom up instead of from the top down. Timings\nconfirm it. Are there pathologic cases that perform worse, though? I\ndon't see how to construct one. It would require an unbalanced heap,\nwhere the bottom items from one branch would rise high in other\nbranches. Is this even possible?\n\nFor a full drain (only _get(), no _put()) of up to 12 items the answer\nis no, at least. Cascade never needs more comparisons for any\npermutation; test code below. Here are the aggregate numbers:\n\n next cascade\n n min max mean min max mean\n 2 0 0 0.0 0 0 0.0\n 3 1 1 1.0 1 1 1.0\n 4 3 3 3.0 3 3 3.0\n 5 5 6 5.8 5 6 5.6\n 6 7 10 8.7 7 9 8.0\n 7 10 14 12.0 9 12 10.9\n 8 14 18 16.3 12 16 13.9\n 9 18 23 20.9 15 20 17.4\n 10 22 29 25.5 18 24 20.7\n 11 26 35 30.5 21 28 24.4\n 12 30 41 35.5 24 33 27.9\n\nsift_up_rebalance() is a combination of sift_down_root() with an empty\nroot and the bubble-up operation from prio_queue_put(). The latter can\neasily be factored out into a sift-up function, reducing code\nduplication.\n\nExtending sift_down_root() to deal with an empty root would be easy as\nwell, but also a bit tricky to avoid pointless checks for each caller.\nNot sure it's worth it. Like this perhaps?\n\nstatic inline size_t sift_down_root(struct prio_queue *queue, bool empty)\n{\n size_t ix, child;\n\n /* Push down the one at the root */\n for (ix = 0; ix * 2 + 1 < queue->nr_; ix = child) {\n child = ix * 2 + 1; /* left */\n if (child + 1 < queue->nr_ &&\n compare(queue, child, child + 1) >= 0)\n child++; /* use right child */\n\n if (empty)\n queue->array[ix] = queue->array[child];\n else if (compare(queue, ix, child) <= 0)\n break;\n else\n swap(queue, child, ix);\n }\n return ix;\n}\n\nAnyway, my point is that it's not \"adding another sift function\", but\nremixing existing ones, which I only count as half. :)\n\nI'd very much like to see this go in because it seems to be strictly\nfaster, makes intuitive sense and adds only little code. I didn't\nfind this method used anywhere else, which is a warning sign, but I\ncan't find any catch.\n\nRené\n\n\n $ for n in $(seq 2 2)\n do\n t/helper/test-tool prio-queue permute get $n |\n awk -v n=$n -v max=0 '\n {sum+=$2}\n max < $2 {max=$2}\n !min || min > $2 {min=$2}\n END {printf \"%2d %3d %3d %5.1f \\n\", n, min, max, sum/NR}\n '\n done\n\n---\n Makefile | 1 +\n t/helper/test-prio-queue.c | 91 ++++++++++++++++++++++++++++++++++++++++++++++\n t/helper/test-tool.c | 1 +\n t/helper/test-tool.h | 1 +\n 4 files changed, 94 insertions(+)\n\ndiff --git a/Makefile b/Makefile\nindex 1f3f099f5c5..ba7d293cf5f 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -843,6 +843,7 @@ TEST_BUILTINS_OBJS += test-partial-clone.o\n TEST_BUILTINS_OBJS += test-path-utils.o\n TEST_BUILTINS_OBJS += test-path-walk.o\n TEST_BUILTINS_OBJS += test-pcre2-config.o\n+TEST_BUILTINS_OBJS += test-prio-queue.o\n TEST_BUILTINS_OBJS += test-pkt-line.o\n TEST_BUILTINS_OBJS += test-proc-receive.o\n TEST_BUILTINS_OBJS += test-progress.o\ndiff --git a/t/helper/test-prio-queue.c b/t/helper/test-prio-queue.c\nnew file mode 100644\nindex 00000000000..c175021b12b\n--- /dev/null\n+++ b/t/helper/test-prio-queue.c\n@@ -0,0 +1,91 @@\n+#include \"test-tool.h\"\n+#include \"prio-queue.h\"\n+\n+/* Generate all permutations using Heap's algorithm. */\n+static int permute_ints(size_t n, void (*fn)(int *, size_t))\n+{\n+\tint *arr;\n+\tsize_t *c;\n+\n+\tALLOC_ARRAY(arr, n);\n+\tfor (size_t i = 0; i < n; i++)\n+\t\tarr[i] = i + 1;\n+\tCALLOC_ARRAY(c, n);\n+\n+\tfn(arr, n);\n+\tfor (size_t i = 1; i < n; i++) {\n+\t\tif (c[i] < i) {\n+\t\t\tSWAP(arr[i & 1 ? c[i] : 0], arr[i]);\n+\t\t\tfn(arr, n);\n+\t\t\tc[i]++;\n+\t\t\ti = 0;\n+\t\t} else {\n+\t\t\tc[i] = 0;\n+\t\t}\n+\t}\n+\n+\tfree(arr);\n+\tfree(c);\n+\n+\treturn 0;\n+}\n+\n+static uintmax_t nr_of_compares;\n+\n+static int compare_ints(const void *a_, const void *b_, void *cb_data UNUSED)\n+{\n+\tconst int *a = a_;\n+\tconst int *b = b_;\n+\tnr_of_compares++;\n+\treturn *a - *b;\n+}\n+\n+static void report(const char *name, const int *arr, size_t n)\n+{\n+\tprintf(\"%s %\"PRIuMAX\" for\", name, nr_of_compares);\n+\tfor (size_t i = 0; i < n; i++)\n+\t\tprintf(\" %d\", arr[i]);\n+\tputchar('\\n');\n+}\n+\n+static void get_permutation(int *arr, size_t n)\n+{\n+\tstatic struct prio_queue queue = { compare_ints };\n+\n+\tfor (size_t i = 0; i < n; i++)\n+\t\tprio_queue_put(&queue, &arr[i]);\n+\n+\tnr_of_compares = 0;\n+\tfor (size_t i = 0; i < n; i++)\n+\t\tprio_queue_get(&queue);\n+\n+\treport(\"get\", arr, n);\n+}\n+\n+static void put_permutation(int *arr, size_t n)\n+{\n+\tstruct prio_queue queue = { compare_ints };\n+\n+\tnr_of_compares = 0;\n+\tfor (size_t i = 0; i < n; i++)\n+\t\tprio_queue_put(&queue, &arr[i]);\n+\n+\treport(\"put\", arr, n);\n+\n+\tclear_prio_queue(&queue);\n+}\n+\n+int cmd__prio_queue(int argc, const char **argv)\n+{\n+\tif (argc == 4 && !strcmp(argv[1], \"permute\")) {\n+\t\tsize_t n = strtoul(argv[3], NULL, 10);\n+\t\tif (!strcmp(argv[2], \"get\"))\n+\t\t\treturn permute_ints(n, get_permutation);\n+\t\tif (!strcmp(argv[2], \"put\"))\n+\t\t\treturn permute_ints(n, put_permutation);\n+\t}\n+\n+\tfprintf(stderr, \"usage: test-tool prio-queue permute get \\n\");\n+\tfprintf(stderr, \" or: test-tool prio-queue permute put \\n\");\n+\treturn 129;\n+}\ndiff --git a/t/helper/test-tool.c b/t/helper/test-tool.c\nindex b71a22b43bb..69352f541f4 100644\n--- a/t/helper/test-tool.c\n+++ b/t/helper/test-tool.c\n@@ -57,6 +57,7 @@ static struct test_cmd cmds[] = {\n \t{ \"path-walk\", cmd__path_walk },\n \t{ \"pcre2-config\", cmd__pcre2_config },\n \t{ \"pkt-line\", cmd__pkt_line },\n+\t{ \"prio-queue\", cmd__prio_queue },\n \t{ \"proc-receive\", cmd__proc_receive },\n \t{ \"progress\", cmd__progress },\n \t{ \"reach\", cmd__reach },\ndiff --git a/t/helper/test-tool.h b/t/helper/test-tool.h\nindex f2885b33d58..ab0d3e01d1e 100644\n--- a/t/helper/test-tool.h\n+++ b/t/helper/test-tool.h\n@@ -50,6 +50,7 @@ int cmd__path_utils(int argc, const char **argv);\n int cmd__path_walk(int argc, const char **argv);\n int cmd__pcre2_config(int argc, const char **argv);\n int cmd__pkt_line(int argc, const char **argv);\n+int cmd__prio_queue(int argc, const char **argv);\n int cmd__proc_receive(int argc, const char **argv);\n int cmd__progress(int argc, const char **argv);\n int cmd__reach(int argc, const char **argv);\n\n"},{"id":"547482","messageId":"CAL71e4NiSSRgxO_L7vb5=ohnchOCvuhEZwMc0Ls+Xu-Q+YytDg@mail.gmail.com","threadId":"65720","inReplyTo":"57bb0e9e-221d-4234-b5bc-a87610e8263c@web.de","subject":"Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-07-08T10:59:56Z","receivedAt":"2026-07-08T11:00:09Z","isPatch":true,"body":"On Wed, 8 Jul 2026 at 12:44, René Scharfe wrote:\n>\n> tl;dr: Yes, please, but I'm biased.\n>\n> The text size of prio-queue.o on Apple silicon increases from 1351 to\n> 1563 bytes for me, 212 bytes or 16% more. OK.\n>\n> It makes intuitive sense to find the new position of the last item by\n> searching from the bottom up instead of from the top down. Timings\n> confirm it. Are there pathologic cases that perform worse, though? I\n> don't see how to construct one. It would require an unbalanced heap,\n> where the bottom items from one branch would rise high in other\n> branches. Is this even possible?\n\nAgreed, I also struggle to come up with such a case. Perhaps\ntheoretically possible to construct, but would not invalidate\nthe general heuristic?\n\n> For a full drain (only _get(), no _put()) of up to 12 items the answer\n> is no, at least. Cascade never needs more comparisons for any\n> permutation; test code below. Here are the aggregate numbers:\n>\n> next cascade\n> n min max mean min max mean\n> 2 0 0 0.0 0 0 0.0\n> 3 1 1 1.0 1 1 1.0\n> 4 3 3 3.0 3 3 3.0\n> 5 5 6 5.8 5 6 5.6\n> 6 7 10 8.7 7 9 8.0\n> 7 10 14 12.0 9 12 10.9\n> 8 14 18 16.3 12 16 13.9\n> 9 18 23 20.9 15 20 17.4\n> 10 22 29 25.5 18 24 20.7\n> 11 26 35 30.5 21 28 24.4\n> 12 30 41 35.5 24 33 27.9\n\nI am sincerely grateful that you took the time to analyze it\nto this level of detail. Very nice analysis and data!\n\n> sift_up_rebalance() is a combination of sift_down_root() with an empty\n> root and the bubble-up operation from prio_queue_put(). The latter can\n> easily be factored out into a sift-up function, reducing code\n> duplication.\n\nGood point! I am not sure how messy this gets in practice, but I\nwill see if I can implement this split for the next patch.\n\n> Extending sift_down_root() to deal with an empty root would be easy as\n> well, but also a bit tricky to avoid pointless checks for each caller.\n> Not sure it's worth it. Like this perhaps?\n>\n> static inline size_t sift_down_root(struct prio_queue *queue, bool empty)\n> {\n> size_t ix, child;\n>\n> /* Push down the one at the root */\n> for (ix = 0; ix * 2 + 1 < queue->nr_; ix = child) {\n> child = ix * 2 + 1; /* left */\n> if (child + 1 < queue->nr_ &&\n> compare(queue, child, child + 1) >= 0)\n> child++; /* use right child */\n>\n> if (empty)\n> queue->array[ix] = queue->array[child];\n> else if (compare(queue, ix, child) <= 0)\n> break;\n> else\n> swap(queue, child, ix);\n> }\n> return ix;\n> }\n\nYes, something like that would work, but I agree -- ideally we\ncould have something that's even nicer and avoids the boolean flag\nfor split behavior.\n\n> Anyway, my point is that it's not \"adding another sift function\", but\n> remixing existing ones, which I only count as half. :)\n>\n> I'd very much like to see this go in because it seems to be strictly\n> faster, makes intuitive sense and adds only little code. I didn't\n> find this method used anywhere else, which is a warning sign, but I\n> can't find any catch.\n\nThanks, I think that is enough motivation for me to at least attempt\nanother version and then it will be easier to reason about dropping\nor keeping.\n\nI am not sure why it's a warning sign to have no other usages,\nespecially when it's a file local static function. I guess it could\nbe inlined instead (though I would not prefer that).\n\nThanks for the very thorough and insightful review,\nKristofer\n"},{"id":"547485","messageId":"15fa1b16-b911-47b1-a843-400e320d7e4f@web.de","threadId":"65720","inReplyTo":"CAL71e4NiSSRgxO_L7vb5=ohnchOCvuhEZwMc0Ls+Xu-Q+YytDg@mail.gmail.com","subject":"Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-07-08T11:55:35Z","receivedAt":"2026-07-08T11:55:37Z","isPatch":true,"body":"On 7/8/26 12:59 PM, Kristofer Karlsson wrote:\n> On Wed, 8 Jul 2026 at 12:44, René Scharfe wrote:\n>>\n>> I didn't\n>> find this method used anywhere else, which is a warning sign, but I\n>> can't find any catch.\n> \n> I am not sure why it's a warning sign to have no other usages,\n> especially when it's a file local static function.\nI meant that I didn't find this optimization in other priority queue\nimplementations or papers, but admittedly I didn't do an exhaustive\nsearch. Given it's benefits I would have expected to find prior art\non it pretty easily, though.\n\nRené\n\n"},{"id":"547489","messageId":"CAL71e4NKcCBs-UjF3ZxOGrTbT_TUAumZV_G2PAfyf4JgzCm+Cg@mail.gmail.com","threadId":"65720","inReplyTo":"15fa1b16-b911-47b1-a843-400e320d7e4f@web.de","subject":"Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-07-08T12:44:06Z","receivedAt":"2026-07-08T12:44:18Z","isPatch":true,"body":"On Wed, 8 Jul 2026 at 13:55, René Scharfe wrote:\n>\n> I meant that I didn't find this optimization in other priority queue\n> implementations or papers, but admittedly I didn't do an exhaustive\n> search. Given it's benefits I would have expected to find prior art\n> on it pretty easily, though.\n\nAha! Got it, I misunderstood you first.\nIt's actually described here[1]:\n> Bottom-up heapsort conceptually replaces the root with a value of −∞\n> and sifts it down using only one comparison per level\n> (since no child can possibly be less than −∞)\n> until the leaves are reached,\n> then replaces the −∞ with the correct value and sifts it up\n> (again, using one comparison per level) until the correct position\n> is found.\n\nIt's for heapsort, not an interactive heap, but the algorithm\nstill matches.\n\nAlso, your idea to split out sift up/down into helper functions did\nwork, and was quite clean - will share patch shortly once I have\ncleaned up the commits and benchmark data.\n\nThanks again,\nKristofer\n\n[1] https://en.wikipedia.org/wiki/Heapsort#Bottom-up_heapsort\n"},{"id":"547518","messageId":"pull.2132.v3.git.1783532989.gitgitgadget@gmail.com","threadId":"65720","inReplyTo":"pull.2132.v2.git.1780301856444.gitgitgadget@gmail.com","subject":"[PATCH v3 0/2] prio-queue: use bottom-up sift for extract-min","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-07-08T17:49:46Z","receivedAt":"2026-07-08T17:49:51Z","isPatch":true,"body":"This tweaks the prio_queue implementation to use a bottom-up approach\nsifting for get [1].\n\nIn practice, the performance boost is small, but measurable for reasonably\nlarge prio_queue:s (thousands of elements, not millions) but it should never\nincrease the work.\n\nMinor note on v3: After the most recent discussion I am not 100% sure how to\nreason about the value of this change - both the value gain and code cost\nseem small, but since there was some interest and research done by René I\nwanted to complete this v3 anyway so it can be properly discussed (though\nstill maybe ultimately closed).\n\nHere's how it works:\n\nInstead of placing the last element at the root and sifting it down with two\ncomparisons per level, cascade the vacancy down by promoting the smaller\nchild (one comparison per level), then place the last element at the vacancy\nand sift it up. Since the displaced element is likely to belong near the\nbottom of the heap, sift_up() typically does very little work.\n\nsift_down_root() is kept as-is for the fused replace path in\nprio_queue_put(), where the new element is arbitrary and may belong near the\nroot -- Rene's testing showed that cascade regresses on git-describe for\nthis reason.\n\nBenchmarks (rev-list --all --count) on public repos confirm no regression on\ngit.git and linux.git. On a large example repo with thousands of active\nbranches the cascade yields a measurable (~2%) end-to-end improvement; the\ngain is modest because the lazy-fold optimization (now in next) already\nfuses most get+put pairs, leaving only the remaining unfused gets to benefit\nfrom cascade.\n\nRené's exhaustive analysis [2] of all permutations up to n=12 confirms that\ncascade never requires more comparisons than standard sift-down for a full\ndrain.\n\nNote: sift_up() currently uses swap, matching the existing code style. It\ncould be further optimized to use copy (hold the element in a temp, shift\nparents down, write once), but that would require changing compare() to\naccept element values instead of array indices. Left for a potential\nfollow-up.\n\nChanges since v2:\n\n * Rebased on kk/prio-queue-get-put-fusion (now in next).\n\n * Split into two commits - refactoring and then introducing cascade_down.\n\nChanges since v1:\n\n * Kept sift_down_root() and prio_queue_replace() completely unchanged,\n preserving René's optimization that avoids the get+put overhead for\n replace. The cascade approach now only applies to prio_queue_get().\n\n * Extracted the new logic into a separate sift_up_rebalance() function\n rather than inlining it in prio_queue_get().\n\n * Updated benchmark numbers for ascending, descending and random insertion\n ordering. No regressions in any scenario.\n\n[1] https://en.wikipedia.org/wiki/Heapsort#Bottom-up_heapsort [2]\nhttps://lore.kernel.org/git/pull.2132.git.1780250236304.gitgitgadget@gmail.com/T/#m114df6e1c2845acbbc64d875ed7dc1d7d9193ed5\n\nKristofer Karlsson (2):\n prio-queue: extract sift_up() from prio_queue_put()\n prio-queue: use cascade for unfused gets\n\n prio-queue.c | 43 ++++++++++++++++++++++++++++++++-----------\n 1 file changed, 32 insertions(+), 11 deletions(-)\n\n\nbase-commit: 00534a21ce949ef80a5b8b9d7fc20b7d381038e9\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2132%2Fspkrka%2Fcascade-sift-down-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2132/spkrka/cascade-sift-down-v3\nPull-Request: https://github.com/gitgitgadget/git/pull/2132\n\nRange-diff vs v2:\n\n -: ---------- > 1: ec6a448563 prio-queue: extract sift_up() from prio_queue_put()\n 1: 6051d44e59 ! 2: 89a22c6a75 prio-queue: use cascade-down for faster extract-min\n @@ Metadata\n Author: Kristofer Karlsson \n \n ## Commit message ##\n - prio-queue: use cascade-down for faster extract-min\n + prio-queue: use cascade for unfused gets\n \n - Add sift_up_rebalance(), an alternative to sift_down_root() that\n - halves the number of comparisons per extract-min.\n + When flush_get() removes the root without an immediate replacement,\n + use a cascade-then-sift-up strategy instead of sift-down.\n \n - The standard extract places the last array element at the root and\n - sifts it down. At each level this requires two comparisons (left\n - vs right child, then element vs winner) and a swap.\n + Standard sift-down places the last element at the root and sifts it\n + down. This needs two comparisons per level (pick the smaller child,\n + then compare against the element), even though the displaced element\n + almost always ends up near the bottom where it came from.\n \n - sift_up_rebalance() instead promotes the smaller child into the\n - root slot at each level — one comparison and one copy — until the\n - vacancy reaches a leaf. The last array element is placed at the\n - vacancy and sifted up to restore heap order. In practice the\n - sift-up rarely moves more than a level or two because the last\n - array element tends to be large.\n + cascade_down() instead moves the vacancy down by promoting the\n + smaller child at each level (one comparison per level), leaving the\n + vacancy at a leaf. The last element is then placed at the vacancy\n + and sift_up() floats it to its correct position, which is typically\n + very little work since it already belongs near the bottom.\n \n - Work per extract drops from 2d comparisons + d swaps to\n - d comparisons + d copies + a short sift-up.\n + This is the well-known \"bottom-up\" variant of sift-down [1].\n \n - prio_queue_get() now calls sift_up_rebalance() instead of placing\n - the last element at root and calling sift_down_root().\n -\n - sift_down_root() and prio_queue_replace() are left unchanged.\n -\n - Synthetic benchmark (10 rounds of 10M put+get cycles, CPU-pinned,\n - same compiler and Makefile flags):\n -\n - Ascending keys (git's typical pattern — parents have lower\n - priority than children):\n -\n - queue width baseline patched speedup\n - 10 4.39s 3.91s 1.12x\n - 100 9.10s 6.61s 1.38x\n - 1,000 11.84s 9.25s 1.28x\n - 10,000 17.50s 13.92s 1.26x\n - 100,000 23.97s 20.19s 1.19x\n -\n - Descending keys (worst case — last element always sinks to leaf):\n -\n - queue width baseline patched speedup\n - 10 4.94s 4.95s 1.00x\n - 100 9.75s 9.42s 1.03x\n - 1,000 15.01s 15.29s 0.98x\n - 10,000 24.79s 23.88s 1.04x\n - 100,000 29.69s 28.24s 1.05x\n -\n - Random keys:\n -\n - queue width baseline patched speedup\n - 10 5.05s 4.99s 1.01x\n - 100 9.90s 9.50s 1.04x\n - 1,000 15.35s 14.77s 1.04x\n - 10,000 25.35s 24.21s 1.05x\n - 100,000 65.71s 63.38s 1.04x\n -\n - No regressions in any scenario.\n -\n - End-to-end benchmark on the linux kernel repo (1.4M commits,\n - range v5.0..v6.0, 311K commits, 20 interleaved runs, 1 warmup):\n -\n - Command baseline patched speedup\n - rev-list --count v5.0..v6.0 484ms 474ms 1.02x\n -\n - The improvement scales with DAG width: wider DAGs produce larger\n - priority queues, amplifying the per-level savings. In small or\n - narrow repositories the queues stay shallow and the sift-down\n - cost is already negligible.\n + [1] https://en.wikipedia.org/wiki/Heapsort#Bottom-up_heapsort\n \n + Helped-by: Rene Scharfe \n Signed-off-by: Kristofer Karlsson \n \n ## prio-queue.c ##\n @@ prio-queue.c: static void sift_down_root(struct prio_queue *queue)\n \t}\n }\n \n -+static void sift_up_rebalance(struct prio_queue *queue)\n ++/* Cascade vacancy toward a leaf, promoting the smaller child at each level */\n ++static size_t cascade_down(struct prio_queue *queue)\n +{\n +\tsize_t ix, child;\n +\n -+\t/* Cascade: promote smaller child at each level. */\n -+\tfor (ix = 0; (child = ix * 2 + 1) < queue->nr; ix = child) {\n -+\t\tif (child + 1 < queue->nr &&\n ++\tfor (ix = 0; (child = ix * 2 + 1) < queue->nr_; ix = child) {\n ++\t\tif (child + 1 < queue->nr_ &&\n +\t\t compare(queue, child, child + 1) >= 0)\n +\t\t\tchild++;\n +\t\tqueue->array[ix] = queue->array[child];\n +\t}\n -+\n -+\t/* Place the last element at the vacancy and sift up. */\n -+\tqueue->array[ix] = queue->array[queue->nr];\n -+\twhile (ix) {\n -+\t\tsize_t parent = (ix - 1) / 2;\n -+\t\tif (compare(queue, parent, ix) <= 0)\n -+\t\t\tbreak;\n -+\t\tswap(queue, parent, ix);\n -+\t\tix = parent;\n -+\t}\n ++\treturn ix;\n +}\n +\n - void *prio_queue_get(struct prio_queue *queue)\n + static inline void flush_get(struct prio_queue *queue)\n {\n - \tvoid *result;\n -@@ prio-queue.c: void *prio_queue_get(struct prio_queue *queue)\n - \tif (!--queue->nr)\n - \t\treturn result;\n - \n --\tqueue->array[0] = queue->array[queue->nr];\n ++\tsize_t ix;\n ++\n + \tif (!queue->get_pending)\n + \t\treturn;\n + \tqueue->get_pending = 0;\n +-\tqueue->array[0] = queue->array[--queue->nr_];\n -\tsift_down_root(queue);\n -+\tsift_up_rebalance(queue);\n - \treturn result;\n ++\t--queue->nr_;\n ++\tix = cascade_down(queue);\n ++\tqueue->array[ix] = queue->array[queue->nr_];\n ++\tsift_up(queue, ix);\n }\n \n + void prio_queue_put(struct prio_queue *queue, void *thing)\n\n-- \ngitgitgadget\n"},{"id":"547519","messageId":"ec6a448563ad57a40dd7d964ea4b2f9bb3dafb7c.1783532989.git.gitgitgadget@gmail.com","threadId":"65720","inReplyTo":"pull.2132.v3.git.1783532989.gitgitgadget@gmail.com","subject":"[PATCH v3 1/2] prio-queue: extract sift_up() from prio_queue_put()","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-07-08T17:49:47Z","receivedAt":"2026-07-08T17:49:52Z","isPatch":true,"body":"From: Kristofer Karlsson \n\nFactor out the bubble-up loop from prio_queue_put() into a\nstandalone sift_up() function. This is a pure refactor with\nno behavior change, preparing for reuse in a subsequent commit.\n\nSuggested-by: Rene Scharfe \nSigned-off-by: Kristofer Karlsson \n---\n prio-queue.c | 21 ++++++++++++---------\n 1 file changed, 12 insertions(+), 9 deletions(-)\n\ndiff --git a/prio-queue.c b/prio-queue.c\nindex 199775d5af..926fc04e85 100644\n--- a/prio-queue.c\n+++ b/prio-queue.c\n@@ -37,6 +37,17 @@ void clear_prio_queue(struct prio_queue *queue)\n \tqueue->get_pending = 0;\n }\n \n+static void sift_up(struct prio_queue *queue, size_t ix)\n+{\n+\twhile (ix) {\n+\t\tsize_t parent = (ix - 1) / 2;\n+\t\tif (compare(queue, parent, ix) <= 0)\n+\t\t\tbreak;\n+\t\tswap(queue, parent, ix);\n+\t\tix = parent;\n+\t}\n+}\n+\n static void sift_down_root(struct prio_queue *queue)\n {\n \tsize_t ix, child;\n@@ -66,8 +77,6 @@ static inline void flush_get(struct prio_queue *queue)\n \n void prio_queue_put(struct prio_queue *queue, void *thing)\n {\n-\tsize_t ix, parent;\n-\n \tif (queue->get_pending) {\n \t\tqueue->get_pending = 0;\n \t\tqueue->array[0].ctr = queue->insertion_ctr++;\n@@ -85,13 +94,7 @@ void prio_queue_put(struct prio_queue *queue, void *thing)\n \t\treturn; /* LIFO */\n \n \t/* Bubble up the new one */\n-\tfor (ix = queue->nr_ - 1; ix; ix = parent) {\n-\t\tparent = (ix - 1) / 2;\n-\t\tif (compare(queue, parent, ix) <= 0)\n-\t\t\tbreak;\n-\n-\t\tswap(queue, parent, ix);\n-\t}\n+\tsift_up(queue, queue->nr_ - 1);\n }\n \n void *prio_queue_get(struct prio_queue *queue)\n-- \ngitgitgadget\n\n"},{"id":"547520","messageId":"89a22c6a7532afa530f1c04ee27177e141dd360c.1783532989.git.gitgitgadget@gmail.com","threadId":"65720","inReplyTo":"pull.2132.v3.git.1783532989.gitgitgadget@gmail.com","subject":"[PATCH v3 2/2] prio-queue: use cascade for unfused gets","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-07-08T17:49:48Z","receivedAt":"2026-07-08T17:49:53Z","isPatch":true,"body":"From: Kristofer Karlsson \n\nWhen flush_get() removes the root without an immediate replacement,\nuse a cascade-then-sift-up strategy instead of sift-down.\n\nStandard sift-down places the last element at the root and sifts it\ndown. This needs two comparisons per level (pick the smaller child,\nthen compare against the element), even though the displaced element\nalmost always ends up near the bottom where it came from.\n\ncascade_down() instead moves the vacancy down by promoting the\nsmaller child at each level (one comparison per level), leaving the\nvacancy at a leaf. The last element is then placed at the vacancy\nand sift_up() floats it to its correct position, which is typically\nvery little work since it already belongs near the bottom.\n\nThis is the well-known \"bottom-up\" variant of sift-down [1].\n\n[1] https://en.wikipedia.org/wiki/Heapsort#Bottom-up_heapsort\n\nHelped-by: Rene Scharfe \nSigned-off-by: Kristofer Karlsson \n---\n prio-queue.c | 22 ++++++++++++++++++++--\n 1 file changed, 20 insertions(+), 2 deletions(-)\n\ndiff --git a/prio-queue.c b/prio-queue.c\nindex 926fc04e85..230d6f5e33 100644\n--- a/prio-queue.c\n+++ b/prio-queue.c\n@@ -66,13 +66,31 @@ static void sift_down_root(struct prio_queue *queue)\n \t}\n }\n \n+/* Cascade vacancy toward a leaf, promoting the smaller child at each level */\n+static size_t cascade_down(struct prio_queue *queue)\n+{\n+\tsize_t ix, child;\n+\n+\tfor (ix = 0; (child = ix * 2 + 1) < queue->nr_; ix = child) {\n+\t\tif (child + 1 < queue->nr_ &&\n+\t\t compare(queue, child, child + 1) >= 0)\n+\t\t\tchild++;\n+\t\tqueue->array[ix] = queue->array[child];\n+\t}\n+\treturn ix;\n+}\n+\n static inline void flush_get(struct prio_queue *queue)\n {\n+\tsize_t ix;\n+\n \tif (!queue->get_pending)\n \t\treturn;\n \tqueue->get_pending = 0;\n-\tqueue->array[0] = queue->array[--queue->nr_];\n-\tsift_down_root(queue);\n+\t--queue->nr_;\n+\tix = cascade_down(queue);\n+\tqueue->array[ix] = queue->array[queue->nr_];\n+\tsift_up(queue, ix);\n }\n \n void prio_queue_put(struct prio_queue *queue, void *thing)\n-- \ngitgitgadget\n"},{"id":"547751","messageId":"10fad562-90b8-4feb-b7ab-d61015872127@web.de","threadId":"65720","inReplyTo":"89a22c6a7532afa530f1c04ee27177e141dd360c.1783532989.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v3 2/2] prio-queue: use cascade for unfused gets","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-07-10T16:37:21Z","receivedAt":"2026-07-10T16:37:29Z","isPatch":true,"body":"On 7/8/26 7:49 PM, Kristofer Karlsson via GitGitGadget wrote:\n> From: Kristofer Karlsson \n> \n> When flush_get() removes the root without an immediate replacement,\n> use a cascade-then-sift-up strategy instead of sift-down.\n> \n> Standard sift-down places the last element at the root and sifts it\n> down. This needs two comparisons per level (pick the smaller child,\n> then compare against the element), even though the displaced element\n> almost always ends up near the bottom where it came from.\n> \n> cascade_down() instead moves the vacancy down by promoting the\n> smaller child at each level (one comparison per level), leaving the\n> vacancy at a leaf. The last element is then placed at the vacancy\n> and sift_up() floats it to its correct position, which is typically\n> very little work since it already belongs near the bottom.\n> \n> This is the well-known \"bottom-up\" variant of sift-down [1].\n> \n> [1] https://en.wikipedia.org/wiki/Heapsort#Bottom-up_heapsort\n\nOn an Apple M1 I get a 1% slowdown for bulk describe on Git's repo:\n\nBenchmark 1: ./git_next describe $(git rev-list v2.41.0..v2.47.0)\n Time (mean ± σ): 939.5 ms ± 3.6 ms [User: 576.8 ms, System: 65.0 ms]\n Range (min … max): 935.0 ms … 946.2 ms 10 runs\n\nBenchmark 2: ./git describe $(git rev-list v2.41.0..v2.47.0)\n Time (mean ± σ): 945.5 ms ± 3.3 ms [User: 581.6 ms, System: 67.5 ms]\n Range (min … max): 940.1 ms … 950.5 ms 10 runs\n\nSummary\n ./git_next describe $(git rev-list v2.41.0..v2.47.0) ran\n 1.01 ± 0.01 times faster than ./git describe $(git rev-list v2.41.0..v2.47.0)\n\n... and on Linux's repo:\n\nBenchmark 1: ./git_next -C ../linux describe $(git -C ../linux rev-list v4.0..v4.1)\n Time (mean ± σ): 4.880 s ± 0.014 s [User: 3.914 s, System: 0.252 s]\n Range (min … max): 4.864 s … 4.905 s 10 runs\n\nBenchmark 2: ./git -C ../linux describe $(git -C ../linux rev-list v4.0..v4.1)\n Time (mean ± σ): 4.917 s ± 0.011 s [User: 3.948 s, System: 0.254 s]\n Range (min … max): 4.902 s … 4.938 s 10 runs\n\nSummary\n ./git_next -C ../linux describe $(git -C ../linux rev-list v4.0..v4.1) ran\n 1.01 ± 0.00 times faster than ./git -C ../linux describe $(git -C ../linux rev-list v4.0..v4.1)\n\nI see a 1% slowdown on an Apple M5 as well in both cases. I can't\nreproduce it on a Ryzen laptop, but that's too noisy to measure 1%\nchanges anyway.\n\nChecked the total number of prio_queue comparisons with the crude patch\nbelow, and as expected they go down, from 70386235 to 60682175 for Git\nand from 473983445 to 439809087 for Linux. So there's less work to do,\nstill user time goes up -- no idea why.\n\nAlso this -- what's up with the system time here:\n\nBenchmark 1: ./git_next rev-list --all --count\n Time (mean ± σ): 115.2 ms ± 0.8 ms [User: 95.6 ms, System: 17.7 ms]\n Range (min … max): 113.0 ms … 117.1 ms 24 runs\n\nBenchmark 2: ./git rev-list --all --count\n Time (mean ± σ): 116.5 ms ± 0.8 ms [User: 95.4 ms, System: 19.0 ms]\n Range (min … max): 115.1 ms … 118.6 ms 24 runs\n\nSummary\n ./git_next rev-list --all --count ran\n 1.01 ± 0.01 times faster than ./git rev-list --all --count\n\nBut:\n\nBenchmark 1: ./git_next -C ../linux rev-list --all --count\n Time (mean ± σ): 937.6 ms ± 2.2 ms [User: 887.2 ms, System: 45.5 ms]\n Range (min … max): 933.2 ms … 939.9 ms 10 runs\n\nBenchmark 2: ./git -C ../linux rev-list --all --count\n Time (mean ± σ): 937.3 ms ± 1.7 ms [User: 887.8 ms, System: 45.0 ms]\n Range (min … max): 934.6 ms … 940.3 ms 10 runs\n\nSummary\n ./git -C ../linux rev-list --all --count ran\n 1.00 ± 0.00 times faster than ./git_next -C ../linux rev-list --all --count\n\n:-?\n\n> Helped-by: Rene Scharfe \n> Signed-off-by: Kristofer Karlsson \n> ---\n> prio-queue.c | 22 ++++++++++++++++++++--\n> 1 file changed, 20 insertions(+), 2 deletions(-)\n> \n> diff --git a/prio-queue.c b/prio-queue.c\n> index 926fc04e85..230d6f5e33 100644\n> --- a/prio-queue.c\n> +++ b/prio-queue.c\n> @@ -66,13 +66,31 @@ static void sift_down_root(struct prio_queue *queue)\n> \t}\n> }\n> \n> +/* Cascade vacancy toward a leaf, promoting the smaller child at each level */\n> +static size_t cascade_down(struct prio_queue *queue)\n> +{\n> +\tsize_t ix, child;\n> +\n> +\tfor (ix = 0; (child = ix * 2 + 1) < queue->nr_; ix = child) {\n> +\t\tif (child + 1 < queue->nr_ &&\n> +\t\t compare(queue, child, child + 1) >= 0)\n> +\t\t\tchild++;\n> +\t\tqueue->array[ix] = queue->array[child];\n> +\t}\n> +\treturn ix;\n> +}\n> +\n> static inline void flush_get(struct prio_queue *queue)\n> {\n> +\tsize_t ix;\n> +\n> \tif (!queue->get_pending)\n> \t\treturn;\n> \tqueue->get_pending = 0;\n> -\tqueue->array[0] = queue->array[--queue->nr_];\n> -\tsift_down_root(queue);\n> +\t--queue->nr_;\n> +\tix = cascade_down(queue);\n> +\tqueue->array[ix] = queue->array[queue->nr_];\n> +\tsift_up(queue, ix);\n> }\n> \n> void prio_queue_put(struct prio_queue *queue, void *thing)\n\nThe patch looks fine, though. It introduces struct assignments, but\nthey should be OK. Tried replacing them with swap() instead (which\ndoes a useless extra write), but that didn't change the performance\n(still 1% slowdown). Odd.\n\nRené\n\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex c0abc931a59..4a6ad976d30 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -791,5 +791,6 @@ int cmd_describe(int argc,\n \t\twhile (argc-- > 0)\n \t\t\tdescribe(*argv++, argc == 0);\n \t}\n+\tprint_compares();\n \treturn 0;\n }\ndiff --git a/prio-queue.c b/prio-queue.c\nindex 199775d5afd..b0189bf80e6 100644\n--- a/prio-queue.c\n+++ b/prio-queue.c\n@@ -1,6 +1,13 @@\n #include \"git-compat-util.h\"\n #include \"prio-queue.h\"\n \n+static uintmax_t compares;\n+\n+void print_compares(void)\n+{\n+\tfprintf(stderr, \"compares: %lu\\n\", compares);\n+}\n+\n static inline int compare(struct prio_queue *queue, size_t i, size_t j)\n {\n \tint cmp = queue->compare(queue->array[i].data, queue->array[j].data,\n@@ -8,6 +15,7 @@ static inline int compare(struct prio_queue *queue, size_t i, size_t j)\n \tif (!cmp)\n \t\tcmp = (queue->array[i].ctr > queue->array[j].ctr) -\n \t\t (queue->array[i].ctr < queue->array[j].ctr);\n+\tcompares++;\n \treturn cmp;\n }\n \ndiff --git a/prio-queue.h b/prio-queue.h\nindex 570b48e6485..e4cc0c4fb83 100644\n--- a/prio-queue.h\n+++ b/prio-queue.h\n@@ -68,4 +68,6 @@ void clear_prio_queue(struct prio_queue *);\n /* Reverse the LIFO elements */\n void prio_queue_reverse(struct prio_queue *);\n \n+void print_compares(void);\n+\n #endif /* PRIO_QUEUE_H */\n\n"},{"id":"547754","messageId":"dfab9ff4-fbfa-4ea2-bea3-09c1d1b1cc18@web.de","threadId":"65720","inReplyTo":"pull.2132.v3.git.1783532989.gitgitgadget@gmail.com","subject":"Re: [PATCH v3 0/2] prio-queue: use bottom-up sift for extract-min","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-07-10T16:37:22Z","receivedAt":"2026-07-10T16:37:31Z","isPatch":true,"body":"On 7/8/26 7:49 PM, Kristofer Karlsson via GitGitGadget wrote:\n> Note: sift_up() currently uses swap, matching the existing code style. It\n> could be further optimized to use copy (hold the element in a temp, shift\n> parents down, write once), but that would require changing compare() to\n> accept element values instead of array indices. Left for a potential\n> follow-up.\n\nSame for sift_down_root(), I guess? It could almost halve the number of\nwrites, right? I wonder how much of that benefit will be eaten by\ncaching.\n\nRené\n\n"},{"id":"547781","messageId":"CAL71e4PRVYfUWc-c+6XHTwtADqrbub9ykbo+rPyramDhJw=Rfg@mail.gmail.com","threadId":"65720","inReplyTo":"10fad562-90b8-4feb-b7ab-d61015872127@web.de","subject":"Re: [PATCH v3 2/2] prio-queue: use cascade for unfused gets","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-07-10T17:28:43Z","receivedAt":"2026-07-10T17:29:00Z","isPatch":true,"body":"On Fri, 10 Jul 2026 at 18:37, René Scharfe wrote:\n>\n> I see a 1% slowdown on an Apple M5 as well in both cases. I can't\n> reproduce it on a Ryzen laptop, but that's too noisy to measure 1%\n> changes anyway.\n>\n> Checked the total number of prio_queue comparisons with the crude patch\n> below, and as expected they go down, from 70386235 to 60682175 for Git\n> and from 473983445 to 439809087 for Linux. So there's less work to do,\n> still user time goes up -- no idea why.\n[snip]\n> The patch looks fine, though. It introduces struct assignments, but\n> they should be OK. Tried replacing them with swap() instead (which\n> does a useless extra write), but that didn't change the performance\n> (still 1% slowdown). Odd.\n\nFirst of all, thanks again for the very comprehensive\ninvestigation on your own hardware!\n\nI don't have any Apple machine to test on but I reran your\nexact operation on my machine\n(Lenovo Thinkpad Intel(R) Core(TM) Ultra 7 155U)\nand just saw noise.\n\nAs you say, this feels _logically_ better since it's fewer\ncompares but perhaps this boils down to the cost difference\nbetween executing CPU operations versus memory\naccess and the CPU cache?\n\nMy random guess:\ncascade_down() has fewer operations and compares\nbut needs to visit all levels of the heap,\nwhile sift_down_root perhaps stops slightly earlier,\nso the memory region right before the end\ngets fewer visits and reduces pressure on\nthe cache.\n\nI have no idea if my guess is correct,\nit's maybe more subtle than that, but\nI think ultimately this points to the fact\nthat while the change is a theoretical\nimprovement, the real world hardware\ntradeoffs make it a non-obvious change.\n\nI think this means we should simply drop the change\nand move on -- it produced bigger gains\nbefore making the lazy prio_queue the default,\nbut now it seems like it is pure noise, unless\nthe comparator function grows more expensive\nin the future.\n\nThanks,\nKristofer\n"},{"id":"547786","messageId":"CAL71e4PvOdH9-aER35f=OAEurNzM-coYr64A7GPckZ9AYctMtw@mail.gmail.com","threadId":"65720","inReplyTo":"dfab9ff4-fbfa-4ea2-bea3-09c1d1b1cc18@web.de","subject":"Re: [PATCH v3 0/2] prio-queue: use bottom-up sift for extract-min","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-07-10T17:40:57Z","receivedAt":"2026-07-10T17:41:10Z","isPatch":true,"body":"On Fri, 10 Jul 2026 at 18:37, René Scharfe wrote:\n>\n> On 7/8/26 7:49 PM, Kristofer Karlsson via GitGitGadget wrote:\n> > Note: sift_up() currently uses swap, matching the existing code style. It\n> > could be further optimized to use copy (hold the element in a temp, shift\n> > parents down, write once), but that would require changing compare() to\n> > accept element values instead of array indices. Left for a potential\n> > follow-up.\n>\n> Same for sift_down_root(), I guess? It could almost halve the number of\n> writes, right? I wonder how much of that benefit will be eaten by\n> caching.\n\nHm yes indeed, I stopped looking past sift_up() when I realized I should\nnot expand the scope of the change. But I think the CPU cache\neffectively makes the swap almost as cheap in practice.\n\n- Kristofer\n"}]}