git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min

From
René Scharfe <l.s.r@web.de>
Date
Jun 7, 2026, 07:30 UTC
Message-ID
<1aa5b755-0f74-46d5-bd6e-a9cb7f3fbb12@web.de>
In-Reply-To
<CAL71e4PV-1aDvn1JnweMa3OR1xxB75fWjzJOBvM54KOWqC0stw@mail.gmail.com>
On 6/5/26 10:39 PM, Kristofer Karlsson wrote:
Show 29 quoted lines
> I did some more benchmarking to understand how these approaches
> interact, with four variants based on origin/next on my large monorepo:
> 
>   1. base: next as-is
>   2. cascade: base + sift_up_rebalance from this patch (v2)
>   3. lazy-fold: base + lazy get fusion folded into prio_queue
>   4. cascade+lazy: both combined
> 
> Note that alt 3 is not yet shared with the mailing list so it's hard for you
> to reason about it, though it's quite straightforward. I will submit a new
> patch for that one soon, not necessarily with the primary goal to merge it,
> but rather show how it is implemented.
> 
>   merge-base --all master master~1000:
>     base            4.27s
>     cascade         4.07s  (1.05x)
>     lazy-fold       4.12s  (1.03x)
>     cascade+lazy    4.01s  (1.06x)
> 
>   rev-list --count master~1000..master:
>     base            3.60s
>     cascade         3.35s  (1.08x)
>     lazy-fold       3.37s  (1.07x)
>     cascade+lazy    3.30s  (1.09x)
> 
> So both optimizations are valuable both on their own, and when combined,
> which I think helps to reason about it. This cascading sift seems to have a
> larger effect, but folding lazy_queue into prio_queue also speeds up other
> use cases and simplifies the code a bit.

Right. I was wondering, though: Why is sift-down so much faster than cascade in the describe benchmark from 30598ccc4d (describe: use oidset in finish_depth_computation(), 2025-09-02)?

I think I mostly understand it now: cascade is better in prio_queue_get() because the sift-down item is from the bottom and will likely end up back at the bottom, just of a different branch of the heap. Thus a sift-down costs 3 compares times the number of levels, while a cascade costs just 2 compares times the number of levels and there is likely little to no need to sift it back up.

For prio_queue_replace() we sift down a random item, though; we don't know where it will end up. If it belongs at the very top then sift-down just needs 3 compares, while cascade needs 2 compares times the number of levels to bring the hole down and the same to bring the item up.

Below is a diff on top of your second cascade patch to use sift-down only for the root and cascade otherwise. It comes remarkably close to the performance of a full sift-down. I don't know how to find the optimal number of levels to try sift-down before switching to cascade for a given random item, though.

So I guess we keep the full sift-down for prio_queue_replace(), knowing that sometimes we have a lot of items that end up at or close to the root of the heap.

Benchmark 1: ./git_main describe $(git rev-list v2.41.0..v2.47.0)
  Time (mean ± σ):     602.4 ms ±   1.2 ms    [User: 539.2 ms, System: 47.7 ms]
  Range (min … max):   600.5 ms … 604.7 ms    10 runs
Benchmark 2: ./git_cascade1 describe $(git rev-list v2.41.0..v2.47.0)
  Time (mean ± σ):     993.9 ms ±   1.7 ms    [User: 930.2 ms, System: 48.2 ms]
  Range (min … max):   991.1 ms … 996.6 ms    10 runs
Benchmark 3: ./git_cascade2 describe $(git rev-list v2.41.0..v2.47.0)
  Time (mean ± σ):     602.4 ms ±   1.7 ms    [User: 539.1 ms, System: 47.6 ms]
  Range (min … max):   599.9 ms … 606.2 ms    10 runs
Benchmark 4: ./git describe $(git rev-list v2.41.0..v2.47.0)
  Time (mean ± σ):     625.4 ms ±   1.7 ms    [User: 561.8 ms, System: 48.0 ms]
  Range (min … max):   623.4 ms … 627.9 ms    10 runs
Summary
  ./git_main describe $(git rev-list v2.41.0..v2.47.0) ran
    1.00 ± 0.00 times faster than ./git_cascade2 describe $(git rev-list v2.41.0..v2.47.0)
    1.04 ± 0.00 times faster than ./git describe $(git rev-list v2.41.0..v2.47.0)
    1.65 ± 0.00 times faster than ./git_cascade1 describe $(git rev-list v2.41.0..v2.47.0)

git_main and git_cascade2 (your v2): sift-down git_cascade1 (your v1): cascade git (your v2 and the patch below): sift-down for root then cascade

René
diff --git a/prio-queue.c b/prio-queue.c
index 66d445b078..4d7debc2ba 100644
--- a/prio-queue.c
+++ b/prio-queue.c
@@ -58,30 +58,12 @@ void prio_queue_put(struct prio_queue *queue, void *thing)
 	}
 }
 
-static void sift_down_root(struct prio_queue *queue)
+static void sift_up_rebalance(struct prio_queue *queue, size_t ix)
 {
-	size_t ix, child;
-
-	/* Push down the one at the root */
-	for (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {
-		child = ix * 2 + 1; /* left */
-		if (child + 1 < queue->nr &&
-		    compare(queue, child, child + 1) >= 0)
-			child++; /* use right child */
-
-		if (compare(queue, ix, child) <= 0)
-			break;
-
-		swap(queue, child, ix);
-	}
-}
-
-static void sift_up_rebalance(struct prio_queue *queue)
-{
-	size_t ix, child;
+	size_t child;
 
 	/* Cascade: promote smaller child at each level. */
-	for (ix = 0; (child = ix * 2 + 1) < queue->nr; ix = child) {
+	for (; (child = ix * 2 + 1) < queue->nr; ix = child) {
 		if (child + 1 < queue->nr &&
 		    compare(queue, child, child + 1) >= 0)
 			child++;
@@ -112,7 +94,7 @@ void *prio_queue_get(struct prio_queue *queue)
 	if (!--queue->nr)
 		return result;
 
-	sift_up_rebalance(queue);
+	sift_up_rebalance(queue, 0);
 	return result;
 }
 
@@ -132,9 +114,20 @@ void prio_queue_replace(struct prio_queue *queue, void *thing)
 	} else if (!queue->compare) {
 		queue->array[queue->nr - 1].ctr = queue->insertion_ctr++;
 		queue->array[queue->nr - 1].data = thing;
+	} else if (queue->nr < 3) {
+		prio_queue_get(queue);
+		prio_queue_put(queue, thing);
 	} else {
-		queue->array[0].ctr = queue->insertion_ctr++;
+		size_t child = compare(queue, 1, 2) <= 0 ? 1 : 2;
+		queue->array[0].ctr = queue->insertion_ctr;
 		queue->array[0].data = thing;
-		sift_down_root(queue);
+		if (compare(queue, 0, child) <= 0) {
+			queue->insertion_ctr++;
+		} else {
+			queue->array[0] = queue->array[child];
+			queue->nr--;
+			sift_up_rebalance(queue, child);
+			prio_queue_put(queue, thing);
+		}
 	}
 }
Previous: Kristofer KarlssonNext: Kristofer Karlsson
Message 9 of 24 in “prio-queue: use cascade-down sift for faster extract-min”
  1. prio-queue: use cascade-down sift for faster extract-minKristofer Karlsson via GitGitGadget, May 31, 2026
  2. Junio C HamanoJun 1, 2026
  3. Junio C HamanoJun 1, 2026
  4. Kristofer KarlssonJun 1, 2026
  5. prio-queue: use cascade-down for faster extract-minKristofer Karlsson via GitGitGadget, Jun 1, 2026
  6. René ScharfeJun 2, 2026
  7. Kristofer KarlssonJun 2, 2026
  8. Kristofer KarlssonJun 5, 2026
  9. René ScharfeJun 7, 2026
  10. Kristofer KarlssonJun 7, 2026
  11. Junio C HamanoJun 29, 2026
  12. Junio C HamanoJun 8, 2026
  13. Kristofer KarlssonJul 6, 2026
  14. René ScharfeJul 8, 2026
  15. Kristofer KarlssonJul 8, 2026
  16. René ScharfeJul 8, 2026
  17. Kristofer KarlssonJul 8, 2026
  18. 0/2 prio-queue: use bottom-up sift for extract-minKristofer Karlsson via GitGitGadget, Jul 8, 2026
  19. 1/2 prio-queue: extract sift_up() from prio_queue_put()Kristofer Karlsson via GitGitGadget, Jul 8, 2026
  20. 2/2 prio-queue: use cascade for unfused getsKristofer Karlsson via GitGitGadget, Jul 8, 2026
  21. René ScharfeJul 10, 2026
  22. Kristofer KarlssonJul 10, 2026
  23. René ScharfeJul 10, 2026
  24. Kristofer KarlssonJul 10, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.