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

Jeff King [off-list ref] writes:

On Sat, Jul 19, 2025 at 01:15:28PM +0200, René Scharfe wrote:

quoted

quoted

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.

Oh right, I totally forgot about the extra counter.

Don't feel bad.  I forgot about it, too, when I gave my "is it
stable?" comment to René's patch.  ;-)