Jeff King <peff@xxxxxxxx> writes: > On Tue, Jul 15, 2025 at 05:07:38PM -0700, Junio C Hamano wrote: > >> René Scharfe <l.s.r@xxxxxx> 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.
