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@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). 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é
