From: Kristofer Karlsson Date: Tue, 19 May 2026 09:33:19 GMT Subject: Re: [PATCH] revision: use priority queue in limit_list() Message-ID: In-Reply-To: <20260519005429.GD1612961@coredump.intra.peff.net> On Tue, 19 May 2026 at 02:54, Jeff King wrote: > > 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