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 2, 2026, 16:36 UTC
Message-ID
<90270818-c52b-4611-8da2-6cee20628fc2@web.de>
In-Reply-To
<pull.2132.v2.git.1780301856444.gitgitgadget@gmail.com>
On 6/1/26 10:17 AM, Kristofer Karlsson via GitGitGadget wrote:
Show 6 quoted lines
>     
>     Changes since v1:
>     
>      * Kept sift_down_root() and prio_queue_replace() completely unchanged,
>        preserving René's optimization that avoids the get+put overhead for
>        replace. The cascade approach now only applies to prio_queue_get().

The prospect of no longer needing prio_queue_replace() had me excited in round 1. The benchmarks from commits that added its callers [1][2][3] did show performance regressions with your patch 1 plus changes to revert prio_queue_peek()+prio_queue_replace() to prio_queue_get()+ prio_queue_put(), but for two of them low enough to be in the noise. 'git describe $(git rev-list v2.41.0..v2.47.0)' took a 50%+ hit, though.

[1] a79e3519d6 (commit: use prio_queue_replace() in pop_most_recent_commit(), 2025-07-18) [2] 08bb69d70f (describe: use prio_queue_replace(), 2025-08-03) [3] abf05d856f (show-branch: use prio_queue, 2025-12-26)

Show 5 quoted lines
>      * Extracted the new logic into a separate sift_up_rebalance() function
>        rather than inlining it in prio_queue_get().
>     
>      * Updated benchmark numbers for ascending, descending and random
>        insertion ordering. No regressions in any scenario.

I don't see any regression for the benchmarks mentioned above with patch 2 alone, unsurprisingly. The describe command still takes that 50%+ performance hit after reverting [2] on top.

Would you be interested in benchmarking the following patch for making prio_queue_replace() unnecessary by doing its optimization automatically? I get a 1% performance hit for the describe command that I can't explain. And it leaves the heap unbalanced after a prio_queue_get(), which complicates things, so I found it lacking. But I wonder how it stacks up against your cascade approach for your use case and if there's anything to salvage.

René
---
 prio-queue.c | 60 +++++++++++++++++++++++++++++++++++++++++-------------------
 prio-queue.h |  1 +
 2 files changed, 42 insertions(+), 19 deletions(-)
diff --git a/prio-queue.c b/prio-queue.c
index 9748528ce6..ba6b460a46 100644
--- a/prio-queue.c
+++ b/prio-queue.c
@@ -34,12 +34,46 @@ void clear_prio_queue(struct prio_queue *queue)
 	queue->nr = 0;
 	queue->alloc = 0;
 	queue->insertion_ctr = 0;
+	queue->sift_down_root_pending = false;
+}
+
+static void sift_down_root(struct prio_queue *queue)
+{
+	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);
+	}
+	queue->sift_down_root_pending = false;
 }
 
 void prio_queue_put(struct prio_queue *queue, void *thing)
 {
 	size_t ix, parent;
 
+	if (queue->sift_down_root_pending) {
+		/*
+		 * Restore the original heap size.  The last item is
+		 * still in the right place.
+		 */
+		queue->nr++;
+
+		/* Now fill the hole at the root with the new item. */
+		queue->array[0].ctr = queue->insertion_ctr++;
+		queue->array[0].data = thing;
+		sift_down_root(queue);
+		return;
+	}
+
 	/* Append at the end */
 	ALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);
 	queue->array[queue->nr].ctr = queue->insertion_ctr++;
@@ -58,24 +92,6 @@ void prio_queue_put(struct prio_queue *queue, void *thing)
 	}
 }
 
-static void sift_down_root(struct prio_queue *queue)
-{
-	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);
-	}
-}
-
 void *prio_queue_get(struct prio_queue *queue)
 {
 	void *result;
@@ -85,12 +101,14 @@ void *prio_queue_get(struct prio_queue *queue)
 	if (!queue->compare)
 		return queue->array[--queue->nr].data; /* LIFO */
 
+	if (queue->sift_down_root_pending)
+		sift_down_root(queue);
 	result = queue->array[0].data;
 	if (!--queue->nr)
 		return result;
 
 	queue->array[0] = queue->array[queue->nr];
-	sift_down_root(queue);
+	queue->sift_down_root_pending = true;
 	return result;
 }
 
@@ -100,6 +118,8 @@ void *prio_queue_peek(struct prio_queue *queue)
 		return NULL;
 	if (!queue->compare)
 		return queue->array[queue->nr - 1].data;
+	if (queue->sift_down_root_pending)
+		sift_down_root(queue);
 	return queue->array[0].data;
 }
 
@@ -111,6 +131,8 @@ void prio_queue_replace(struct prio_queue *queue, void *thing)
 		queue->array[queue->nr - 1].ctr = queue->insertion_ctr++;
 		queue->array[queue->nr - 1].data = thing;
 	} else {
+		if (queue->sift_down_root_pending)
+			sift_down_root(queue);
 		queue->array[0].ctr = queue->insertion_ctr++;
 		queue->array[0].data = thing;
 		sift_down_root(queue);
diff --git a/prio-queue.h b/prio-queue.h
index da7fad2f1f..5977fba438 100644
--- a/prio-queue.h
+++ b/prio-queue.h
@@ -32,6 +32,7 @@ struct prio_queue {
 	void *cb_data;
 	size_t alloc, nr;
 	struct prio_queue_entry *array;
+	bool sift_down_root_pending;
 };
 
 /*
Previous: Kristofer Karlsson via GitGitGadgetNext: Kristofer Karlsson
Message 6 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.