Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min
From: René Scharfe <hidden>
Date: 2026-06-02 16:36:56
Subsystem:
the rest · Maintainer:
Linus Torvalds
On 6/1/26 10:17 AM, Kristofer Karlsson via GitGitGadget wrote:
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)
* 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; }; /*