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

From: René Scharfe <l.s.r@web.de>
Date: Jul 19, 2025, 11:15 UTC
Message-ID: <37f34e15-f44f-4b8a-b684-bda27a977775@web.de>
In-Reply-To: <20250719065558.GD705356@coredump.intra.peff.net>

On 7/19/25 8:55 AM, Jeff King wrote:

Show 17 quoted lines

> On Wed, Jul 16, 2025 at 11:39:49AM +0200, René Scharfe wrote:
> 
>> On 7/16/25 7:05 AM, Jeff King wrote:
>>> On Tue, Jul 15, 2025 at 04:51:07PM +0200, René Scharfe wrote:
>>>
>>>> pop_most_recent_commit() calls commit_list_insert_by_date(), which and
>>>> is itself called in a loop, which can lead to quadratic complexity.
>>>> Replace the commit_list with a prio_queue to ensure logarithmic worst
>>>> case complexity and convert all three users.
>>>
>>> I guess I'm cc'd because of my frequent complains about the quadratic
>>> nature of our commit lists? :)
>>
>> And because you introduced prio_queue.
> 
> I think that was Junio, but I think I can be counted as a cheerleader
> for the topic. :)

Ah, sorry. You did make it stable, though, which allows using it for backward-compatible history traversal.

Show 15 quoted lines

>>> I actually have a series turning rev_info.commits into a prio_queue
>>> which I need to polish up (mostly just writing commit messages; I've
>>> been running with it for almost 2 years without trouble). Ironically it
>>> does not touch this spot, as these commit lists are formed on their own.
>>
>> That is not a coincidence.  I had a look at that series and tried to
>> reach its goals while keeping rev_info.commits a commit_list.  Why?
>> Mostly being vaguely uncomfortable with prio_queue' memory overhead,
>> lack of type safety and dual use as a stack.  I still used it, but only
>> as local variable, not in the central struct rev_info.
> 
> Hmm, I would have thought prio_queue had less memory overhead. You're
> spending one pointer per entry in a packed array, versus list nodes. But
> it's true that it doesn't shrink as items are removed (though that is
> something we _could_ implement).

If we just count the net data then a commit_list item has two pointers and a prio_queue_entry has a pointer and an ID for stability. That's a tie. ALLOC_GROW overallocates by ca. 50%, so that's 25% more on average for the prio_queue. No idea what overhead malloc() needs per allocation, but I guess it's enough to tilt the scale back against commit_lists.

However, a prio_queue without a comparison function acts as a FIFO stack, but needs double the amount of memory than a pointer array without the stability ID would, for the same behavior.

I don't think lack of shrinking causes much of an issue. I did stumble over at least one place where using a prio_queue in FIFO mode made the code slightly but measurably slower than using a commit_list, though, which could be rectified by using a raw array of pointers.

René