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