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

From: Jeff King <peff@peff.net>
Date: Jul 19, 2025, 06:55 UTC
Message-ID: <20250719065558.GD705356@coredump.intra.peff.net>
In-Reply-To: <b0950e32-b4fa-4aff-8b5c-58c734b880b2@web.de>

On Wed, Jul 16, 2025 at 11:39:49AM +0200, René Scharfe wrote:

Show 12 quoted lines

> 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. :)

Show 10 quoted lines

> > Mostly I asked because I had to look at pop_most_recent_commit() to see
> > what operation would be made faster here. Looks like it's mostly ":/",
> > but maybe also fetch's mark_recent_complete_commits()? I guess we might
> > hit that if you have a huge number of refs?
> 
> The :/ handling was the easiest to test for me.  fetch_pack() and
> walker_fetch() require some server side to set up, which seems not worth
> it just to demonstrate quadratic behavior.  Having thousands of refs
> would make the list long enough to notice, as would having lots of
> merges.

OK, that makes sense. Just making sure I understand the benefits.

> My general idea is to get rid of commit_list_insert_by_date() eventually
> to avoid quadratic complexity.

Yeah, it's certainly at the root of many such problems we've seen over the years.

Show 10 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).

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

-Peff