From: "René Scharfe" <l.s.r@web•de>
To: Jeff King <peff@peff•net>
Cc: Git List <git@vger•kernel.org>
Subject: Re: [PATCH 2/3] prio-queue: add prio_queue_replace()
Date: Thu, 17 Jul 2025 11:20:53 +0200 [thread overview]
Message-ID: <4ed087c9-0229-4219-8cbd-55f9ee79ca35@web.de> (raw)
In-Reply-To: <298dd1d6-7756-4ecb-9202-d77491541253@web.de>
On 7/16/25 11:38 AM, René Scharfe wrote:
> On 7/16/25 7:09 AM, Jeff King wrote:
>> On Tue, Jul 15, 2025 at 04:51:22PM +0200, René Scharfe wrote:
>>
>>> Add a function to replace the top element of the queue that basically
>>> does the same as prio_queue_get() followed by prio_queue_put(), but
>>> without the work by prio_queue_get() to rebalance the heap. It can be
>>> used to optimize loops that get one element and then immediately add
>>> another one. That's common e.g., with commit history traversal, where
>>> we get out a commit and then put in its parents.
>>
>> Hmm. But surely we still need to rebalance the heap after adding an
>> element? And indeed, we still call the new sift_down_root() function.
>
> Yes.
>
>> But I guess we are getting away without the "bubble up" operation that
>> put would do? So we are doing half as much work (but still big-O the
>> same)?
>
> Yes.
>
> I thought about building this optimization into prio_queue_get(), but
> that would require prio_queue_peek() and prio_queue_put() to be adjusted
> as well and all prio_queue users would have to be either made aware of
> the not-fully-heapified state, or prevented from accessing prio_queue
> properties like .nr and .array.
Here's what that would like like. .nr and .array elements are kept
consistent at all times, but the root item is not in heap order after a
prio_queue_get(). That's good enough to enumerate all prio_queue items
like commit-reach.c::queue_has_nonstale() or
negotiator/skipping.c::push_parent() do.
Not sure what other weird patterns people might come up with that
require touching the innards of a prio_queue directly. I don't even
understand why negotiator/skipping.c::push_parent() does a linear
search for each parent -- isn't that expensive? Setting an object
flag on prio_queue_put() and clearing it on prio_queue_get() or a
using a commit_slab seem to be better options from a very cursory
glance.
Anyway, here's what doing prio_queue_replace() automatically could look
like. I almost talked myself into using it now. Any objections, ideas
on how to make it safer or clearer, other thoughts?
René
---
prio-queue.c | 52 +++++++++++++++++++++++++++++++++++++++-------------
prio-queue.h | 1 +
2 files changed, 40 insertions(+), 13 deletions(-)
diff --git a/prio-queue.c b/prio-queue.c
index ec33ac27db..265663e116 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++;
@@ -61,31 +95,21 @@ void prio_queue_put(struct prio_queue *queue, void *thing)
void *prio_queue_get(struct prio_queue *queue)
{
void *result;
- size_t ix, child;
if (!queue->nr)
return NULL;
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];
- /* 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 = true;
return result;
}
@@ -95,5 +119,7 @@ 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;
}
diff --git a/prio-queue.h b/prio-queue.h
index 38d032636d..6d8d268f41 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;
};
/*
--
2.50.1
next prev parent reply other threads:[~2025-07-17 9:20 UTC|newest]
Thread overview: 41+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-07-15 14:35 [PATCH 0/3] commit: convert pop_most_recent_commit() to prio_queue René Scharfe
2025-07-15 14:51 ` [PATCH 1/3] " René Scharfe
2025-07-15 19:23 ` Junio C Hamano
2025-07-15 20:47 ` Justin Tobler
2025-07-16 9:39 ` René Scharfe
2025-07-16 5:05 ` Jeff King
2025-07-16 9:39 ` René Scharfe
2025-07-17 8:22 ` René Scharfe
2025-07-19 6:55 ` Jeff King
2025-07-19 6:57 ` Jeff King
2025-07-19 11:15 ` René Scharfe
2025-07-20 0:03 ` Jeff King
2025-07-20 1:22 ` Junio C Hamano
2025-07-16 22:23 ` Junio C Hamano
2025-07-17 8:22 ` René Scharfe
2025-07-15 14:51 ` [PATCH 2/3] prio-queue: add prio_queue_replace() René Scharfe
2025-07-16 5:09 ` Jeff King
2025-07-16 9:38 ` René Scharfe
2025-07-17 9:20 ` René Scharfe [this message]
2025-07-19 7:02 ` Jeff King
2025-07-15 14:51 ` [PATCH 3/3] commit: use prio_queue_replace() in pop_most_recent_commit() René Scharfe
2025-07-15 20:43 ` Junio C Hamano
2025-07-16 9:38 ` René Scharfe
2025-07-16 0:07 ` [PATCH 0/3] commit: convert pop_most_recent_commit() to prio_queue Junio C Hamano
2025-07-16 5:15 ` Jeff King
2025-07-16 9:38 ` René Scharfe
2025-07-19 6:45 ` Jeff King
2025-07-16 14:49 ` Junio C Hamano
2025-07-18 9:09 ` [PATCH v2 " René Scharfe
2025-07-18 9:39 ` [PATCH v2 1/3] " René Scharfe
2025-07-21 14:02 ` Lidong Yan
2025-08-03 9:54 ` René Scharfe
2025-08-03 16:48 ` Junio C Hamano
2025-08-04 19:56 ` René Scharfe
2025-07-18 9:39 ` [PATCH v2 3/3] commit: use prio_queue_replace() in pop_most_recent_commit(),MIME-Version: 1.0 René Scharfe
2025-08-03 11:12 ` Johannes Schindelin
2025-08-03 11:33 ` René Scharfe
2025-07-18 9:39 ` [PATCH v2 2/3] prio-queue: add prio_queue_replace() René Scharfe
2025-07-19 7:04 ` [PATCH v2 0/3] commit: convert pop_most_recent_commit() to prio_queue Jeff King
2025-07-22 6:26 ` SZEDER Gábor
2025-07-22 14:27 ` Junio C Hamano
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=4ed087c9-0229-4219-8cbd-55f9ee79ca35@web.de \
--to=l.s.r@web$(echo .)de \
--cc=git@vger$(echo .)kernel.org \
--cc=peff@peff$(echo .)net \
/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