From: Jeff King Date: Tue, 19 May 2026 21:56:27 GMT Subject: Re: [PATCH] revision: use priority queue in limit_list() Message-ID: <20260519215627.GB2278669@coredump.intra.peff.net> In-Reply-To: On Tue, May 19, 2026 at 11:33:19AM +0200, Kristofer Karlsson wrote: > 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. Yeah, I think that is an accurate summary. What I worry about with your approach is any code that looks at or modifies the commit list during the traversal. It has to know whether to use the queue or the list. > 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... */ I looked at the patch you linked for this. I'm undecided on whether this makes things simpler (because the if/else-cascade is in one spot) or more confusing (because now the details are all hidden behind a layer of abstraction). > 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). It would be easy-ish to further convert limit_list() to store newlist as a queue, and then transfer ownership of its fields into revs->commits (i.e., a struct assignment). One possible complication is that we do pass "newlist" into a few sub-functions, like cherry_pick_list(). Looking at that function, it iterates over the list, but it's not clear to me if the order matters. Certainly not in the first loop, but later we do some flag assignments. I _think_ they're all independent, but I'm not sure. Obviously we can iterate over the prio_queue in date order with a series of get() calls, but that is roughly equivalent to building a list (and we have to rebuild the queue after, too). Of course that is already happening in limit_to_ancestry(), which builds the reverse-order list. So I dunno. Moving to the dual-structure state feels messy and error-prone to me, but it does perhaps let us move a little more incrementally. -Peff