From: Kristofer Karlsson Date: Fri, 15 May 2026 07:47:31 GMT Subject: Re: [PATCH] revision: use priority queue in limit_list() Message-ID: 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 wrote: > > 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