Re: [PATCH] revision: use priority queue in limit_list()
- From
Jeff King <peff@peff.net>
- Date
- May 19, 2026, 00:54 UTC
- Message-ID
- <20260519005429.GD1612961@coredump.intra.peff.net>
- In-Reply-To
- <CAL71e4MxhcZqxPVEe38Shuqt7h5dxLDGi66hN2cFXnmg-POKWA@mail.gmail.com>
On Sun, May 17, 2026 at 05:26:06PM +0200, Kristofer Karlsson wrote:
Show 10 quoted lines
> 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