From: Jeff King Date: Tue, 19 May 2026 00:54:29 GMT Subject: Re: [PATCH] revision: use priority queue in limit_list() Message-ID: <20260519005429.GD1612961@coredump.intra.peff.net> In-Reply-To: On Sun, May 17, 2026 at 05:26:06PM +0200, Kristofer Karlsson wrote: > Another note - I think I managed to apply the same change to > get_revision_1 too - speeding up a monorepo "git rev-list HEAD" by > 3.3x so it seems like a reasonable thing to do. > This simplifies process_parents and also makes > commit_list_insert_by_date dead code. > > The only caveat is that get_revision_1 starts to get messier and the > rev_info struct needs both a prio_queue and a linked list of commits - > and then flushing everything > from the list into the prio_queue when executing get_revision_1. IMHO it is worth replacing rev_info's list with a prio_queue and letting that be the source of authority. You do have to be careful to cover cases where the list _isn't_ date-sorted, but prio_queue supports that with a NULL comparator. You do still have to convert between list and queue at a few spots, but I think in the long run many of those could be converted to use a queue. You can see my patches to do so at: https://github.com/peff/git jk/revs-commits-prio-queue I've been running with them locally for a few years. Mostly I hadn't gotten around to polishing them, and I think I had wanted to do some more perf testing. It sounds like you have a good candidate repo for showing off the improvement. ;) If you'd like to go in that direction, please feel free to pick out whatever is useful from what you find on that branch. > I don't want to pollute this patch with that change - should I start a > separate thread for it or just revisit this later? > (Perhaps I have too many optimization patches in flux already) Yes, it definitely makes sense to do that as a separate change. If you look at the patches I linked above, note that they'll get a bit simpler by rebasing on top of your limit_list() changes, since it does some of the same things. -Peff