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. ;)
-Peff
