From: Jeff King Date: Fri, 15 May 2026 04:16:41 GMT Subject: Re: [PATCH] revision: use priority queue in limit_list() Message-ID: <20260515041641.GA81292@coredump.intra.peff.net> In-Reply-To: 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