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

Re: [PATCH] revision: use priority queue in limit_list()

From
Kristofer Karlsson <krka@spotify.com>
Date
May 19, 2026, 09:33 UTC
Message-ID
<CAL71e4O6UcnqmxDgqyGqvgvfruSzeoz6Wj5muXiwEp_8y2wAcg@mail.gmail.com>
In-Reply-To
<20260519005429.GD1612961@coredump.intra.peff.net>
On Tue, 19 May 2026 at 02:54, Jeff King <peff@peff.net> wrote:
Show 44 quoted lines
>
> 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
I didn't know about your prior work on this -- very cool!

I took a look at your branch. Our approaches differ mainly in how broadly the prio_queue replaces the linked list. Here's a summary of the tradeoffs as I see them:

Your approach: replace commits entirely with struct prio_queue. Every access site is converted, and boundary cases (bisect, topo-sort, simplify_merges) convert queue->list->queue when they need list-based APIs.

My approach: keep the linked list for setup and add a separate commit_queue for the walk phase. External callers that read the list between prepare_revision_walk() and the walk are unchanged. The conversion happens once when the walk begins.

A quick size comparison:
  Your branch:  12 files changed, 167 insertions, 152 deletions
  My branch:     4 files changed, 138 insertions,  78 deletions

The main reason mine touches fewer files is that the list stays as a list during setup, so bisect.c, builtin/rev-list.c, line-log.c, and list-objects.c don't need changes.

On the walk side, my second and third commits refactor get_revision_1() to use a vtable ("walk_ops") that selects the right pop/expand strategy once and caches it:

    struct revision_walk_ops {
        void (*init)(struct rev_info *);
        struct commit *(*next)(struct rev_info *);
        int (*expand)(struct rev_info *, struct commit *);
    };
    static struct revision_walk_ops streaming_ops =
        { rev_info_commit_list_to_queue, next_streaming, expand_streaming };
    static struct revision_walk_ops limited_ops =
        { NULL, next_commit_list, NULL };
    /* ...reflog_ops, topo_ops, no_walk_ops... */

This replaces the nested if/else chain and makes each walk mode self-contained. The init function for streaming_ops drains the list into the queue; limited_ops just pops from the list directly.

The thing I'm less sure about is the prio_queue dual-mode usage in your branch -- using compare=NULL for FIFO mode. It works, but it means call sites need to reason about which mode the queue is in (heap vs array), and the queue<->list conversions at boundaries add up. In the two-field approach, the list is always a list and the queue is always a heap.

That said, your approach is clearly cleaner long-term if the remaining list consumers eventually migrate. And the single-field design avoids the "only one should be non-empty" invariant that mine relies on.

I benchmarked both approaches against a 2.4M-commit squash-merge- heavy monorepo (best of 3 runs each, commit-graph present):

  Benchmark                             mainline    kk      jk
  rev-list HEAD (streaming, full DAG)    21.8s     6.9s    6.9s
  --ancestry-path ~100K (limited)        21.8s     4.8s    5.0s
  rev-list --count HEAD~10000..HEAD      17.7s     3.7s    3.8s
  log --oneline -1000                     0.1s     0.1s    0.1s

Both give ~3-5x speedups over mainline. The streaming walk is identical. On limited walks kk is ~4% faster, which I think comes from avoiding the queue rebuild at the end of limit_list() -- jk's commit_list_to_queue() drains the result list back into the queue, while kk leaves the result as a linked list (which the limited walk then just pops from directly).

The perf profiles confirm this: compare_commits_by_commit_date is 11.3% in jk vs 8.0% in kk for the ancestry-path case, and sift_down_root is 7.3% vs 5.8%. The rest of the profile is identical.

I put up a draft PR with the two follow-up commits (on top of the limit_list change) so you can see the full picture if you're curious:

  https://github.com/gitgitgadget/git/pull/2118

I don't have a strong preference for which approach we end up with, since both will achieve the same performance. So it's mainly a question about which one is easier to maintain, where everyone else in this thread has more stake than I have :)

- Kristofer
Previous: Jeff KingNext: Jeff King
Message 11 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.