From: "René Scharfe" <l.s.r@web•de>
To: Kristofer Karlsson via GitGitGadget <gitgitgadget@gmail•com>,
git@vger•kernel.org
Cc: Kristofer Karlsson <krka@spotify•com>
Subject: Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min
Date: Tue, 2 Jun 2026 18:36:48 +0200 [thread overview]
Message-ID: <90270818-c52b-4611-8da2-6cee20628fc2@web.de> (raw)
In-Reply-To: <pull.2132.v2.git.1780301856444.gitgitgadget@gmail.com>
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;
};
/*
next prev parent reply other threads:[~2026-06-02 16:36 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-05-31 17:57 [PATCH] prio-queue: use cascade-down sift for faster extract-min Kristofer Karlsson via GitGitGadget
2026-06-01 0:09 ` Junio C Hamano
2026-06-01 6:16 ` Junio C Hamano
2026-06-01 6:21 ` Kristofer Karlsson
2026-06-01 8:17 ` [PATCH v2] prio-queue: use cascade-down " Kristofer Karlsson via GitGitGadget
2026-06-02 16:36 ` René Scharfe [this message]
2026-06-02 22:40 ` Kristofer Karlsson
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=90270818-c52b-4611-8da2-6cee20628fc2@web.de \
--to=l.s.r@web$(echo .)de \
--cc=git@vger$(echo .)kernel.org \
--cc=gitgitgadget@gmail$(echo .)com \
--cc=krka@spotify$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox