Re: [PATCH 0/3] commit: convert pop_most_recent_commit() to prio_queue

> 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). For inserting while we walk the list,
> we'll produce the same results as long as the original code always
> inserted new entries after existing ones (in the case of a tie on commit
> date, that is).
> 
> And I think that is the case, since commit_list_insert_by_date() does
> this:
> 
>           while ((p = *pp) != NULL) {
>                   if (p->item->date < item->date) {
>                           break;
>                   }
>                   pp = &p->next;
>           }
>           return commit_list_insert(item, pp);
> 
> So we only insert once we have found an item in the list _after_ us,
> retaining the same order.
> 
> But hopefully somebody can double check my logic, as it is quite
> possible I got something reversed above. ;)