revision: use priority queue in limit_list()

From: Kristofer Karlsson <[email protected]>

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.

---
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(-)

index 599b3a66c3..2b1b3bb10e 100644
@@ -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

"Kristofer Karlsson via GitGitGadget" <[email protected]>

Impressive.

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.

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

Yes, much better.

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.

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

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

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.

Couldn't find cases where the patch avoids quadratic runtimes, but nice speedups nonetheless:

Benchmark 1: ./git_main rev-list --bisect v2.0.1..v2.10.1
Time (mean ± σ): 108.2 ms ± 1.3 ms [User: 104.3 ms, System: 3.3 ms]
Range (min … max): 106.3 ms … 110.4 ms 27 runs

Benchmark 2: ./git rev-list --bisect v2.0.1..v2.10.1

  Time (mean ± σ):      93.4 ms ±   0.7 ms    [User: 89.3 ms, System: 3.3 ms]
  Range (min … max):    92.2 ms …  94.7 ms    31 runs

Summary
./git rev-list --bisect v2.0.1..v2.10.1 ran

    1.16 ± 0.02 times faster than ./git_main rev-list --bisect v2.0.1..v2.10.1

Benchmark 1: ./git_main rev-list --bisect v2.0.1..v2.20.1
Time (mean ± σ): 200.6 ms ± 1.8 ms [User: 196.1 ms, System: 3.7 ms]
Range (min … max): 197.3 ms … 203.2 ms 14 runs

Benchmark 2: ./git rev-list --bisect v2.0.1..v2.20.1
Time (mean ± σ): 160.1 ms ± 0.9 ms [User: 155.5 ms, System: 3.8 ms]
Range (min … max): 158.7 ms … 161.7 ms 18 runs

Summary
./git rev-list --bisect v2.0.1..v2.20.1 ran

    1.25 ± 0.01 times faster than ./git_main rev-list --bisect v2.0.1..v2.20.1

Benchmark 1: ./git_main rev-list --bisect v2.0.1..v2.30.1
Time (mean ± σ): 384.7 ms ± 2.1 ms [User: 379.8 ms, System: 4.0 ms]
Range (min … max): 382.5 ms … 390.0 ms 10 runs

Benchmark 2: ./git rev-list --bisect v2.0.1..v2.30.1
Time (mean ± σ): 300.6 ms ± 0.6 ms [User: 295.7 ms, System: 4.0 ms]
Range (min … max): 299.9 ms … 301.7 ms 10 runs

Summary
./git rev-list --bisect v2.0.1..v2.30.1 ran

    1.28 ± 0.01 times faster than ./git_main rev-list --bisect v2.0.1..v2.30.1

Benchmark 1: ./git_main rev-list --bisect v2.0.1..v2.40.1
Time (mean ± σ): 630.7 ms ± 4.2 ms [User: 625.5 ms, System: 4.4 ms]
Range (min … max): 625.0 ms … 637.4 ms 10 runs

Benchmark 2: ./git rev-list --bisect v2.0.1..v2.40.1
Time (mean ± σ): 496.9 ms ± 1.6 ms [User: 491.6 ms, System: 4.3 ms]
Range (min … max): 494.2 ms … 499.5 ms 10 runs

Summary
./git rev-list --bisect v2.0.1..v2.40.1 ran

    1.27 ± 0.01 times faster than ./git_main rev-list --bisect v2.0.1..v2.40.1

Benchmark 1: ./git_main rev-list --bisect v2.0.1..v2.50.1
Time (mean ± σ): 954.3 ms ± 7.9 ms [User: 948.3 ms, System: 5.1 ms]
Range (min … max): 943.0 ms … 965.6 ms 10 runs

Benchmark 2: ./git rev-list --bisect v2.0.1..v2.50.1
Time (mean ± σ): 754.8 ms ± 4.4 ms [User: 748.9 ms, System: 5.0 ms]
Range (min … max): 750.4 ms … 765.6 ms 10 runs

Summary
./git rev-list --bisect v2.0.1..v2.50.1 ran

    1.26 ± 0.01 times faster than ./git_main rev-list --bisect v2.0.1..v2.50.1

René

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).

Thanks for sharing these details! Consider my curiosity sated.

I'm usually interested in encoding ways to repeatedly exercise these performance gains and preventing regression in the future. However, you've demonstrated that not all repositories have a data shape that reveals the performance problem.

If you happen to find a publicly-available repository that shows this improvement, then documenting the performance benefits for that repo would be sufficient. I'm familiar with performance work that doesn't reveal its most important gains until working with private repositories at the proper scale, so don't sweat not having a public example.

I don't think it's worth constructing a synthetic repo to demonstrate this issue. I was hoping that it would be low- hanging fruit to cover this in the perf test suite, but that does not seem to be the case.

Thanks,
-Stolee

Another note - I think I managed to apply the same change to get_revision_1 too - speeding up a monorepo "git rev-list HEAD" by 3.3x so it seems like a reasonable thing to do.
This simplifies process_parents and also makes commit_list_insert_by_date dead code.

The only caveat is that get_revision_1 starts to get messier and the rev_info struct needs both a prio_queue and a linked list of commits - and then flushing everything
from the list into the prio_queue when executing get_revision_1.

I don't want to pollute this patch with that change - should I start a separate thread for it or just revisit this later?
(Perhaps I have too many optimization patches in flux already)

- Kristofer

Thanks for a great news. I agree that it is a good idea to find a good stopping point and make improvements step-wise, and the patch posted for limit_list() is probably such a good stopping point.

If we do not see further comments on the current patch, let's merge it to 'next', cook it for the standard 7 calendar days or so before merging it down to 'master'. Further optimizations can be made on top of the updated 'master' branch as new and separate topics.

IMHO it is worth replacing rev_info's list with a prio_queue and letting that be the source of authority. You do have to be careful to cover cases where the list _isn't_ date-sorted, but prio_queue supports that with a NULL comparator.

You do still have to convert between list and queue at a few spots, but I think in the long run many of those could be converted to use a queue.

You can see my patches to do so at:

https://github.com/peff/git jk/revs-commits-prio-queue

I've been running with them locally for a few years. Mostly I hadn't gotten around to polishing them, and I think I had wanted to do some more perf testing. It sounds like you have a good candidate repo for showing off the improvement. ;)

If you'd like to go in that direction, please feel free to pick out whatever is useful from what you find on that branch.

Yes, it definitely makes sense to do that as a separate change. If you look at the patches I linked above, note that they'll get a bit simpler by rebasing on top of your limit_list() changes, since it does some of the same things.

-Peff

I didn't know about your prior work on this -- very cool!

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.

A quick size comparison:

Your branch: 12 files changed, 167 insertions, 152 deletions
My branch: 4 files changed, 138 insertions, 78 deletions

The main reason mine touches fewer files is that the list stays as a list during setup, so bisect.c, builtin/rev-list.c, line-log.c, and list-objects.c don't need changes.

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... */

This replaces the nested if/else chain and makes each walk mode self-contained. The init function for streaming_ops drains the list into the queue; limited_ops just pops from the list directly.

The thing I'm less sure about is the prio_queue dual-mode usage in your branch -- using compare=NULL for FIFO mode. It works, but it means call sites need to reason about which mode the queue is in (heap vs array), and the queue<->list conversions at boundaries add up. In the two-field approach, the list is always a list and the queue is always a heap.

That said, your approach is clearly cleaner long-term if the remaining list consumers eventually migrate. And the single-field design avoids the "only one should be non-empty" invariant that mine relies on.

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).

The perf profiles confirm this: compare_commits_by_commit_date is 11.3% in jk vs 8.0% in kk for the ancestry-path case, and sift_down_root is 7.3% vs 5.8%. The rest of the profile is identical.

I put up a draft PR with the two follow-up commits (on top of the limit_list change) so you can see the full picture if you're curious:

https://github.com/gitgitgadget/git/pull/2118

I don't have a strong preference for which approach we end up with, since both will achieve the same performance. So it's mainly a question about which one is easier to maintain, where everyone else in this thread has more stake than I have :)

- Kristofer

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.

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).

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