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

[PATCH v3 2/2] prio-queue: use cascade for unfused gets

From
Kristofer Karlsson via GitGitGadget <gitgitgadget@gmail.com>
Date
Jul 8, 2026, 17:49 UTC
Message-ID
<89a22c6a7532afa530f1c04ee27177e141dd360c.1783532989.git.gitgitgadget@gmail.com>
In-Reply-To
<pull.2132.v3.git.1783532989.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>

When flush_get() removes the root without an immediate replacement, use a cascade-then-sift-up strategy instead of sift-down.

Standard sift-down places the last element at the root and sifts it down. This needs two comparisons per level (pick the smaller child, then compare against the element), even though the displaced element almost always ends up near the bottom where it came from.

cascade_down() instead moves the vacancy down by promoting the smaller child at each level (one comparison per level), leaving the vacancy at a leaf. The last element is then placed at the vacancy and sift_up() floats it to its correct position, which is typically very little work since it already belongs near the bottom.

This is the well-known "bottom-up" variant of sift-down [1].
[1] https://en.wikipedia.org/wiki/Heapsort#Bottom-up_heapsort
Helped-by: Rene Scharfe <l.s.r@web.de>
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
 prio-queue.c | 22 ++++++++++++++++++++--
 1 file changed, 20 insertions(+), 2 deletions(-)
diff --git a/prio-queue.c b/prio-queue.c
index 926fc04e85..230d6f5e33 100644
--- a/prio-queue.c
+++ b/prio-queue.c
@@ -66,13 +66,31 @@ static void sift_down_root(struct prio_queue *queue)
 	}
 }
 
+/* Cascade vacancy toward a leaf, promoting the smaller child at each level */
+static size_t cascade_down(struct prio_queue *queue)
+{
+	size_t ix, child;
+
+	for (ix = 0; (child = ix * 2 + 1) < queue->nr_; ix = child) {
+		if (child + 1 < queue->nr_ &&
+		    compare(queue, child, child + 1) >= 0)
+			child++;
+		queue->array[ix] = queue->array[child];
+	}
+	return ix;
+}
+
 static inline void flush_get(struct prio_queue *queue)
 {
+	size_t ix;
+
 	if (!queue->get_pending)
 		return;
 	queue->get_pending = 0;
-	queue->array[0] = queue->array[--queue->nr_];
-	sift_down_root(queue);
+	--queue->nr_;
+	ix = cascade_down(queue);
+	queue->array[ix] = queue->array[queue->nr_];
+	sift_up(queue, ix);
 }
 
 void prio_queue_put(struct prio_queue *queue, void *thing)
-- 
gitgitgadget
Previous: Kristofer Karlsson via GitGitGadgetNext: René Scharfe
Message 20 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.