From: René Scharfe <l.s.r@web.de>
Date: Wed, 16 Jul 2025 09:38:39 GMT
Subject: Re: [PATCH 0/3] commit: convert pop_most_recent_commit() to prio_queue
Message-ID: <5a25d830-0825-4b28-8763-2be342d2b6a3@web.de>
In-Reply-To: <20250716051533.GD1396022@coredump.intra.peff.net>

On 7/16/25 7:15 AM, Jeff King wrote:
> 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. ;)
Yes, commit_list_insert_by_date() is stable, as it inserts commits after
ones with the same date.  Items are popped from the top, so this ensures
FIFO behavior for commits with the same date.

prio_queue ensures stability using an ID and favors lower ones, so it
provides the same order.

We should add unit tests for that, no?

René