Subject: Re: [PATCH 2/3] prio-queue: add prio_queue_replace()

From: René Scharfe <[email-masked]>
Date: Wed, 16 Jul 2025 11:38:44 +0200

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.  Adding a new function seemed like the
simplest and safest way for now.

René