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

From: René Scharfe <l.s.r@web.de>
Date: Jul 16, 2025, 09:38 UTC
Message-ID: <298dd1d6-7756-4ecb-9202-d77491541253@web.de>
In-Reply-To: <20250716050933.GC1396022@coredump.intra.peff.net>

On 7/16/25 7:09 AM, Jeff King wrote:

Show 11 quoted lines

> 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é