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

[Jeff King <peff@peff.net>]

On Sat, Jul 19, 2025 at 02:55:58AM -0400, Jeff King wrote:

> > 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).
> 
> The dual use as a stack actually came in handy for my series, IIRC.
> There are spots which use a commit_list but care about a specific order,
> and my list/prio_queue conversion helpers use that to create a non-heap
> prio_queue that just returns the items in the original order (it's
> actually FIFO, but we can get that by reversing).
> 
> I dunno. That's kind of horrible when I say it out loud, but it did make
> things work. I'm surprised that your attempt ended up with a performance
> hit when mine did not. Mine tried not to be clever, and even leaves in
> place a few spots where we convert between the two representations to
> satisfy various interfaces (with the goal that we'd probably eventually
> switch to prio_queue everywhere).

Oh, re-reading what you wrote again: you left rev_info.commits as a
list, so presumably you were paying more conversion overhead as you
walked (whereas I think in mine the prio_queue becomes the data
structure for the hot path during traversal).

-Peff