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

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

[Kristofer Karlsson via GitGitGadget]

From: Kristofer Karlsson <krka@spotify.com>

limit_list() maintains a date-sorted work queue of commits using a
linked list with commit_list_insert_by_date() for insertion.  Each
insertion walks the list to find the right position — O(n) per insert.
In repositories with merge-heavy histories, the symmetric difference
can contain thousands of commits, making this O(n) insertion the
dominant cost.

Replace the sorted linked list with a prio_queue (binary heap).  This
gives O(log n) insertion and O(log n) extraction instead of O(n)
insertion and O(1) extraction, which is a net win when the queue is
large.

The still_interesting() and everybody_uninteresting() helpers are
updated to scan the prio_queue's contiguous array instead of walking a
linked list.  process_parents() already accepts both a commit_list and
a prio_queue parameter, so the change in limit_list() simply switches
which one is passed.

Benchmark: git rev-list --left-right --count HEAD~N...HEAD
Repository: 2.3M commits, merge-heavy DAG (monorepo)
Best of 5 runs, times in seconds:

  commits in
  symmetric diff   baseline   patched    speedup
  --------------   --------   -------    -------
            10       0.01      0.01       1.0x
            50       0.01      0.01       1.0x
          3751      21.23      8.49       2.5x
          4524      21.70      8.29       2.6x
         10130      20.10      6.65       3.0x

No change for small traversals; 2.5-3.0x faster when the queue grows
to thousands of commits.

Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
    revision: use priority queue in limit_list()
    
    This patch speeds up limit_list() by 2.5–3x on large, merge-heavy
    repositories by replacing a sorted linked list with a priority queue.
    
    The sorted linked list used as a work queue in limit_list() has O(n)
    insertion cost per commit, where n is the current queue length (the
    "width" of the active walk frontier). In merge-heavy DAGs this frontier
    grows wide — profiling on a 2.3M-commit monorepo showed 59% of total CPU
    time in commit_list_insert_by_date(). Total cost is O(N·w) where N is
    commits walked and w is peak queue width; in merge-heavy histories w
    scales with N, approaching O(N²).
    
    Switching to a prio_queue (binary heap) reduces insertion cost to O(log
    w), bringing total cost to O(N·log w). The practical result on the same
    repository:
    
    commits in
    symmetric diff   before     after      speedup
    --------------   --------   -------    -------
            3751      21.2s      8.5s       2.5x
            4524      21.7s      8.3s       2.6x
           10130      20.1s      6.6s       3.0x
    
    
    This affects any command that triggers limit_list() — i.e., when
    revs->limited is set — including --left-right, --cherry-mark,
    --cherry-pick, --ancestry-path, bisect, and rebase's fork-point
    computation. The practical trigger is git status --ahead-behind on a
    branch that has diverged from upstream in a merge-heavy repository.
    
    The change is minimal (+21/−17 lines, single file) because
    process_parents() already accepts both a commit_list and a prio_queue
    parameter — limit_list() just switches which one it passes.

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2114%2Fspkrka%2Flimit-list-prio-queue-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2114/spkrka/limit-list-prio-queue-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/2114

 revision.c | 38 +++++++++++++++++++++-----------------
 1 file changed, 21 insertions(+), 17 deletions(-)

diff --git a/revision.c b/revision.c
index 599b3a66c3..2b1b3bb10e 100644
--- a/revision.c
+++ b/revision.c
@@ -473,10 +473,10 @@ static struct commit *handle_commit(struct rev_info *revs,
 	die("%s is unknown object", name);
 }
 
-static int everybody_uninteresting(struct commit_list *orig,
+static int everybody_uninteresting(struct prio_queue *orig,
 				   struct commit **interesting_cache)
 {
-	struct commit_list *list = orig;
+	size_t i;
 
 	if (*interesting_cache) {
 		struct commit *commit = *interesting_cache;
@@ -484,9 +484,8 @@ static int everybody_uninteresting(struct commit_list *orig,
 			return 0;
 	}
 
-	while (list) {
-		struct commit *commit = list->item;
-		list = list->next;
+	for (i = 0; i < orig->nr; i++) {
+		struct commit *commit = orig->array[i].data;
 		if (commit->object.flags & UNINTERESTING)
 			continue;
 
@@ -1300,20 +1299,17 @@ static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)
 /* How many extra uninteresting commits we want to see.. */
 #define SLOP 5
 
-static int still_interesting(struct commit_list *src, timestamp_t date, int slop,
+static int still_interesting(struct prio_queue *src, timestamp_t date, int slop,
 			     struct commit **interesting_cache)
 {
 	/*
-	 * No source list at all? We're definitely done..
+	 * Since src is sorted by date, it is enough to peek at the
+	 * first entry to compare dates.  No entry at all means done.
 	 */
-	if (!src)
+	struct commit *commit = prio_queue_peek(src);
+	if (!commit)
 		return 0;
-
-	/*
-	 * Does the destination list contain entries with a date
-	 * before the source list? Definitely _not_ done.
-	 */
-	if (date <= src->item->date)
+	if (date <= commit->date)
 		return SLOP;
 
 	/*
@@ -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);
 		struct object *obj = &commit->object;
 
 		if (commit == interesting_cache)
@@ -1468,11 +1470,13 @@ static int limit_list(struct rev_info *revs)
 
 		if (revs->max_age != -1 && (commit->date < revs->max_age))
 			obj->flags |= UNINTERESTING;
-		if (process_parents(revs, commit, &original_list, NULL) < 0)
+		if (process_parents(revs, commit, NULL, &queue) < 0) {
+			clear_prio_queue(&queue);
 			return -1;
+		}
 		if (obj->flags & UNINTERESTING) {
 			mark_parents_uninteresting(revs, commit);
-			slop = still_interesting(original_list, date, slop, &interesting_cache);
+			slop = still_interesting(&queue, date, slop, &interesting_cache);
 			if (slop)
 				continue;
 			break;
@@ -1509,7 +1513,7 @@ static int limit_list(struct rev_info *revs)
 		}
 	}
 
-	commit_list_free(original_list);
+	clear_prio_queue(&queue);
 	revs->commits = newlist;
 	return 0;
 }

base-commit: 59ff4886a579f4bc91e976fe18590b9ae02c7a08
-- 
gitgitgadget

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

[Junio C Hamano]

"Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com>
writes:

> Benchmark: git rev-list --left-right --count HEAD~N...HEAD
> Repository: 2.3M commits, merge-heavy DAG (monorepo)
> Best of 5 runs, times in seconds:
>
>   commits in
>   symmetric diff   baseline   patched    speedup
>   --------------   --------   -------    -------
>             10       0.01      0.01       1.0x
>             50       0.01      0.01       1.0x
>           3751      21.23      8.49       2.5x
>           4524      21.70      8.29       2.6x
>          10130      20.10      6.65       3.0x
>
> No change for small traversals; 2.5-3.0x faster when the queue grows
> to thousands of commits.

Impressive.

> Signed-off-by: Kristofer Karlsson <krka@spotify.com>
> ---
>     revision: use priority queue in limit_list()
> ...
>     This affects any command that triggers limit_list() — i.e., when
>     revs->limited is set — including --left-right, --cherry-mark,
>     --cherry-pick, --ancestry-path, bisect, and rebase's fork-point
>     computation. The practical trigger is git status --ahead-behind on a
>     branch that has diverged from upstream in a merge-heavy repository.

I found this description a bit curious.  Notably missing from the
above list of revs->limited users is a bog standard A..B and it is
unclear the omission is because that case is not improved and if so
why.

I think a major reason of the omission of A..B from the above is,
despite my recollection that such a range (i.e., any presense of
UNINTERESTING commit) computation _always_ worked on a limited list,
these days we conditionally do not when we have commit graph and we
are showing in --topo-order (which is implicitly enabled when many
options other than --topo-order is in effect) since 1b4d8827
(revision: use generation for A..B --topo-order queries, 2019-05-21).

It might be interesting to extend your benchmark over the same
history with the same command line, perhaps with and without an
explicit "--topo-order" added, in a repository _without_
commit-graph enabled.

Thanks.

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

[Derrick Stolee]

On 5/14/2026 12:51 PM, Kristofer Karlsson via GitGitGadget wrote:
> From: Kristofer Karlsson <krka@spotify.com>
> 
> limit_list() maintains a date-sorted work queue of commits using a
> linked list with commit_list_insert_by_date() for insertion.  Each
> insertion walks the list to find the right position — O(n) per insert.
> In repositories with merge-heavy histories, the symmetric difference
> can contain thousands of commits, making this O(n) insertion the
> dominant cost.

Linear operations are bad, especially when multiplied by linear-ish
loops, causing quadratic behavior.

> Replace the sorted linked list with a prio_queue (binary heap).  This
> gives O(log n) insertion and O(log n) extraction instead of O(n)
> insertion and O(1) extraction, which is a net win when the queue is
> large.

Yes, much better.

> The still_interesting() and everybody_uninteresting() helpers are
> updated to scan the prio_queue's contiguous array instead of walking a
> linked list.  process_parents() already accepts both a commit_list and
> a prio_queue parameter, so the change in limit_list() simply switches
> which one is passed.
> 
> Benchmark: git rev-list --left-right --count HEAD~N...HEAD
> Repository: 2.3M commits, merge-heavy DAG (monorepo)
> Best of 5 runs, times in seconds:
> 
>   commits in
>   symmetric diff   baseline   patched    speedup
>   --------------   --------   -------    -------
>             10       0.01      0.01       1.0x
>             50       0.01      0.01       1.0x
>           3751      21.23      8.49       2.5x
>           4524      21.70      8.29       2.6x
>          10130      20.10      6.65       3.0x
> 
> No change for small traversals; 2.5-3.0x faster when the queue grows
> to thousands of commits.

This is good. Is there any chance that you could demonstrate this with
any commits in the Git repo? It does have some interesting behavior,
especially around point releases that are independent from the 'master'
branch and thus could have lopsided symmetric differences using well-
established tag names.

>     Switching to a prio_queue (binary heap) reduces insertion cost to O(log
>     w), bringing total cost to O(N·log w). The practical result on the same
>     repository:
>     
>     commits in
>     symmetric diff   before     after      speedup
>     --------------   --------   -------    -------
>             3751      21.2s      8.5s       2.5x
>             4524      21.7s      8.3s       2.6x
>            10130      20.1s      6.6s       3.0x

Very nice! I notice that this data is in your cover letter, but
not the commit message. Is that intentional?

>     This affects any command that triggers limit_list() — i.e., when
>     revs->limited is set — including --left-right, --cherry-mark,
>     --cherry-pick, --ancestry-path, bisect, and rebase's fork-point
>     computation. The practical trigger is git status --ahead-behind on a
>     branch that has diverged from upstream in a merge-heavy repository.

This also impacts 'git log --graph' when there is no serialized
commit-graph file. We are still using limit_list() in that case.

>     The change is minimal (+21/−17 lines, single file) because
>     process_parents() already accepts both a commit_list and a prio_queue
>     parameter — limit_list() just switches which one it passes.

The key logic is turning the initial list into the starting
points for the priority queue and everything else is about
moving types around, it seems.

> @@ -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 };

Here, we are _not_ using generation numbers, which is correct
for this case because we are matching the date-based sorting
of the previous list.

>  	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);
>  		struct object *obj = &commit->object;
  
This is a fun reuse of lines to take the old "drain the
list as it is being mutated" loop and turn it into "fill
the priority queue" and "drain the priority queue as it
is being mutated"

This code change looks good. No new tests are needed, since
this is a performance-only change. Do any of the tests in
t/perf/ demonstrate this improvement?

Thanks,
-Stolee

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

[Jeff King]

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

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

[Kristofer Karlsson]

Thanks for the reviews!

**Junio C Hamano**:
Good question about A..B. Since 1b4d8827 (revision: use
generation for A..B --topo-order queries, 2019-05-21), a plain `A..B`
with commit-graph avoids limit_list() entirely via init_topo_walk().
The commands I listed are those that still force `revs->limited = 1`
even with a commit-graph.

As you suggested, I ran benchmarks without commit-graph. On the same
2.3M-commit repo with `core.commitGraph=false`:

    git rev-list --left-right --count HEAD~100...HEAD (3,751 sym-diff)

    baseline (no commit-graph):  67.0s
    patched  (no commit-graph):  43.1s   (1.6x speedup)

    baseline (with commit-graph): 21.2s
    patched  (with commit-graph):  8.5s   (2.5x speedup)

The gain is smaller without commit-graph because more time goes to
parsing commits from pack, but it's still a meaningful improvement.

**Derrick Stolee**:
Unfortunately git.git's mostly-linear history doesn't
trigger the quadratic behavior (the queue stays narrow). Even with
5,584 commits in the symmetric diff, `--left-right --count` finishes
in ~0.4s on git.git for both baseline and patched. A 50-pair
interleaved run shows no statistically significant difference:

    git rev-list --left-right --count v2.47.1...v2.54.0 (git.git, 5,584 commits)
    50 interleaved paired runs:

    baseline: mean 393ms, stdev 13ms, median 392ms
    patched:  mean 396ms, stdev 14ms, median 393ms
    paired t-test: +2.9ms, t=1.16, p>0.05 (not significant)

There may be a tiny constant-factor overhead (~1%) from the heap's
bookkeeping on narrow queues (sift-up/sift-down vs simple pointer
splice), but it's well within noise and dwarfed by the 2.5-3x win
on wide queues.
The improvement is specific to merge-heavy DAGs where the active
frontier (queue width) grows large.

I also measured `--ancestry-path`, which hits the same limit_list()
bottleneck. 74% of CPU was in commit_list_insert_by_date():

    git log --oneline --ancestry-path HEAD~100..HEAD (monorepo, 100 results)

    baseline: 16.5s
    patched:   3.8s   (4.3x speedup)

You're right that `git log --graph` without commit-graph also goes
through limit_list(). I can add that to the description.

Regarding the O(N·w) analysis in the cover letter vs commit message:
I'll move the key points into the commit message in v2.

The existing t/perf tests don't cover this path. p0001 doesn't
use --left-right and p6010 is merge-base specific. I could add a
perf test, though it would need a merge-heavy test repo to show the
difference. Would a synthetic one (like p6010 does) be useful?

**Jeff King**
Confirmed: unsorted_input is only set alongside no_walk, and
limit_list() is called after the no_walk early return.
So the incoming list is always date-sorted when limit_list() runs.

That said, even if unsorted input did reach this code, the prio_queue
maintains its sorted invariant on every prio_queue_put(), so the
output order would still be correct; the heap sorts by commit date
regardless of insertion order.

Your patch to convert revs.commits to a prio_queue sounds like a
natural next step; this change would indeed slot right in (the
initial drain-and-fill loop would just disappear).

On Fri, 15 May 2026 at 06:16, Jeff King <peff@peff.net> wrote:
>
> 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