From: Junio C Hamano <gitster@pobox.com>
Date: Wed, 16 Jul 2025 14:49:19 GMT
Subject: Re: [PATCH 0/3] commit: convert pop_most_recent_commit() to prio_queue
Message-ID: <xmqqldoodwcw.fsf@gitster.g>
In-Reply-To: <20250716051533.GD1396022@coredump.intra.peff.net>

Jeff King <peff@peff.net> writes:

> On Tue, Jul 15, 2025 at 05:07:38PM -0700, Junio C Hamano wrote:
>
>> René Scharfe <l.s.r@web.de> writes:
>> 
>> > Use prio_queue to improve worst-case performance at the cost of slightly
>> > worse best-case performance.  Then add and use prio_queue_replace() to
>> > recover that loss.
>> 
>> Would change in the tiebreaking behaviour (aka sort stability) also
>> a cost of this change, as this swaps use of sorted linearly linked
>> list with priority queue?
>
> The prio_queue uses insertion order as a tie-breaker for stability (with
> earlier entries coming first). For building the initial queue from the
> list, I think that is obviously fine (we feed them in sorted order,
> which the prio queue will retain).

OK, then everything looks great.  Thanks.