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 15, 2026, 04:16 UTC
Message-ID
<20260515041641.GA81292@coredump.intra.peff.net>
In-Reply-To
<pull.2114.git.1778777491939.gitgitgadget@gmail.com>
On Thu, May 14, 2026 at 04:51:31PM +0000, Kristofer Karlsson via GitGitGadget wrote:
Show 17 quoted lines
> @@ -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
Previous: René ScharfeNext: Kristofer Karlsson
Message 5 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.