git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH] revision: use priority queue in limit_list()

From
Jeff King <peff@peff.net>
Date
May 19, 2026, 21:56 UTC
Message-ID
<20260519215627.GB2278669@coredump.intra.peff.net>
In-Reply-To
<CAL71e4O6UcnqmxDgqyGqvgvfruSzeoz6Wj5muXiwEp_8y2wAcg@mail.gmail.com>
On Tue, May 19, 2026 at 11:33:19AM +0200, Kristofer Karlsson wrote:
Show 13 quoted lines
> 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.

Show 15 quoted lines
> 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).

Show 15 quoted lines
> 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
Previous: Kristofer Karlsson
Message 12 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.