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
