git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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
Previous: Junio C HamanoNext: Kristofer Karlsson
Message 10 of 12 in “revision: use priority queue in limit_list()”
  1. revision: use priority queue in limit_list()Kristofer Karlsson via GitGitGadget, May 14, 2026
  2. Junio C HamanoMay 14, 2026
  3. Derrick StoleeMay 14, 2026
  4. René ScharfeMay 17, 2026
  5. Jeff KingMay 15, 2026
  6. Kristofer KarlssonMay 15, 2026
  7. Derrick StoleeMay 15, 2026
  8. Kristofer KarlssonMay 17, 2026
  9. Junio C HamanoMay 17, 2026
  10. Jeff KingMay 19, 2026
  11. Kristofer KarlssonMay 19, 2026
  12. Jeff KingMay 19, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.