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 15, 2026, 07:47 UTC
Message-ID
<CAL71e4Mfq3SCO7vnTbFCxpzH9txWPTencV-vq-aQ=wJ7dPMV2g@mail.gmail.com>
In-Reply-To
<20260515041641.GA81292@coredump.intra.peff.net>
Thanks for the reviews!

**Junio C Hamano**: Good question about A..B. Since 1b4d8827 (revision: use generation for A..B --topo-order queries, 2019-05-21), a plain `A..B` with commit-graph avoids limit_list() entirely via init_topo_walk(). The commands I listed are those that still force `revs->limited = 1` even with a commit-graph.

As you suggested, I ran benchmarks without commit-graph. On the same 2.3M-commit repo with `core.commitGraph=false`:

    git rev-list --left-right --count HEAD~100...HEAD (3,751 sym-diff)
    baseline (no commit-graph):  67.0s
    patched  (no commit-graph):  43.1s   (1.6x speedup)
    baseline (with commit-graph): 21.2s
    patched  (with commit-graph):  8.5s   (2.5x speedup)

The gain is smaller without commit-graph because more time goes to parsing commits from pack, but it's still a meaningful improvement.

**Derrick Stolee**: Unfortunately git.git's mostly-linear history doesn't trigger the quadratic behavior (the queue stays narrow). Even with 5,584 commits in the symmetric diff, `--left-right --count` finishes in ~0.4s on git.git for both baseline and patched. A 50-pair interleaved run shows no statistically significant difference:

    git rev-list --left-right --count v2.47.1...v2.54.0 (git.git, 5,584 commits)
    50 interleaved paired runs:
    baseline: mean 393ms, stdev 13ms, median 392ms
    patched:  mean 396ms, stdev 14ms, median 393ms
    paired t-test: +2.9ms, t=1.16, p>0.05 (not significant)

There may be a tiny constant-factor overhead (~1%) from the heap's bookkeeping on narrow queues (sift-up/sift-down vs simple pointer splice), but it's well within noise and dwarfed by the 2.5-3x win on wide queues. The improvement is specific to merge-heavy DAGs where the active frontier (queue width) grows large.

I also measured `--ancestry-path`, which hits the same limit_list() bottleneck. 74% of CPU was in commit_list_insert_by_date():

    git log --oneline --ancestry-path HEAD~100..HEAD (monorepo, 100 results)
    baseline: 16.5s
    patched:   3.8s   (4.3x speedup)

You're right that `git log --graph` without commit-graph also goes through limit_list(). I can add that to the description.

Regarding the O(N·w) analysis in the cover letter vs commit message: I'll move the key points into the commit message in v2.

The existing t/perf tests don't cover this path. p0001 doesn't use --left-right and p6010 is merge-base specific. I could add a perf test, though it would need a merge-heavy test repo to show the difference. Would a synthetic one (like p6010 does) be useful?

**Jeff King**
Confirmed: unsorted_input is only set alongside no_walk, and
limit_list() is called after the no_walk early return.
So the incoming list is always date-sorted when limit_list() runs.

That said, even if unsorted input did reach this code, the prio_queue maintains its sorted invariant on every prio_queue_put(), so the output order would still be correct; the heap sorts by commit date regardless of insertion order.

Your patch to convert revs.commits to a prio_queue sounds like a natural next step; this change would indeed slot right in (the initial drain-and-fill loop would just disappear).

On Fri, 15 May 2026 at 06:16, Jeff King <peff@peff.net> wrote:
Show 47 quoted lines
>
> On Thu, May 14, 2026 at 04:51:31PM +0000, Kristofer Karlsson via GitGitGadget wrote:
>
> > @@ -1451,6 +1447,7 @@ static int limit_list(struct rev_info *revs)
> >       struct commit_list *newlist = NULL;
> >       struct commit_list **p = &newlist;
> >       struct commit *interesting_cache = NULL;
> > +     struct prio_queue queue = { .compare = compare_commits_by_commit_date };
> >
> >       if (revs->ancestry_path_implicit_bottoms) {
> >               collect_bottom_commits(original_list,
> > @@ -1461,6 +1458,11 @@ static int limit_list(struct rev_info *revs)
> >
> >       while (original_list) {
> >               struct commit *commit = pop_commit(&original_list);
> > +             prio_queue_put(&queue, commit);
> > +     }
> > +
> > +     while (queue.nr) {
> > +             struct commit *commit = prio_queue_get(&queue);
>
> Here we push the whole starting list into the prio-queue, which will let
> us pull the commits out in date order. But is the incoming list always
> in date order?
>
> If revs->unsorted_input, then we don't sort the initial list. So we'd
> now see the commits in a different order, and put them onto newlist in
> that different order.
>
> I _think_ it may not matter because we don't call limit_list() when
> revs->no_walk is set, and we only have revs->unsorted_input when no_walk
> is also set. If that wasn't true, it would get weird when limit_list()
> calls process_parents(), which uses commit_list_insert_by_date().
>
>
> I was on the lookout for this issue particularly because I have another
> patch which converts revs.commits to a prio_queue totally. And I
> remember running into issues (and the solution is that sometimes the
> prio_queue has a NULL comparator and acts like a LIFO queue). But if my
> analysis is right above, we can ignore that for now. And if we
> eventually move to revs.commits as a prio_queue, then it will just slot
> in nicely here (we can drop the queue generation step and just use it
> directly).
>
> The rest of the patch looks as I'd expect from what my other patch does.
>
> -Peff
Previous: Jeff KingNext: Derrick Stolee
Message 6 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.