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
