commit-reach: replace queue_has_nonstale with a counter

paint_down_to_common() and ahead_behind() terminate when every commit in their priority queue is STALE. The current check, queue_has_nonstale(), does an O(n) linear scan of the queue on every iteration, costing O(n*m) total where n is the queue size and m is the number of commits processed. This series replaces that scan with an O(1) counter.

Performance measurements with git merge-base --all and git for-each-ref --format='%(ahead-behind:...)':

git.git (merge-base)
Baseline Dedup Dedup+Ctr
seen..next, 33 merge bases: 157ms 165ms 143ms

seen..master, 1 base:                      47ms     40ms     44ms
master..next, 1 base:                      62ms     60ms     63ms

(seen=fe056fe1, next=c82f1880, master=6a4418c3)

Large monorepo, 2.4M commits (merge-base)
Baseline Dedup+Ctr

component import, wide frontier (1):      8083ms           3778ms
component import, wide frontier (2):      5664ms           4207ms
component import, wide frontier (3):      4558ms           1796ms

Large monorepo, 2.4M commits (ahead-behind)
Baseline Dedup+Ctr

component import, wide frontier (1):      8216ms           4145ms
component import, wide frontier (2):      6107ms           4528ms
component import, wide frontier (3):      4725ms           1999ms

Linear history (merge-base), no regression:

master vs HEAD~10000:                     4410ms           4180ms
master vs HEAD~50000:                     4412ms           4494ms

The improvement depends on how wide the frontier gets during the walk. Component imports in the monorepo create wide frontiers where the queue grows large, making the O(n) scan expensive -- up to 2.5x speedup for merge-base and 2.4x for ahead-behind. Linear history and simple merges show no regression.

With a very narrow frontier the counter approach adds a small constant overhead per iteration (maintaining the counter and the ENQUEUED flag) compared to the old scan which would return almost immediately. Both are O(1) and cheap in that scenario, so it should not matter in practice -- the benchmark numbers above confirm this.

Kristofer Karlsson (3):
commit-reach: deduplicate queue entries in paint_down_to_common
commit-reach: optimize queue scan in paint_down_to_common
commit-reach: optimize queue scan in ahead_behind

 commit-reach.c | 58 ++++++++++++++++++++++++++++++++++++--------------
 object.h       |  2 +-
 2 files changed, 43 insertions(+), 17 deletions(-)

base-commit: 6a4418c36d6bad69a599044b3cf49dcbd049cb45
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2124%2Fspkrka%2Fqueue-has-nonstale-v3-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2124/spkrka/queue-has-nonstale-v3-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/2124

gitgitgadget

From: Kristofer Karlsson <[email protected]>

paint_down_to_common() can enqueue the same commit multiple times when it is reached through different parents with different flag combinations. Add an ENQUEUED flag to track whether a commit is currently in the priority queue, and skip it if already present.

This change is performance-neutral on its own: the O(n) queue_has_nonstale() scan still dominates the per-iteration cost. However, the deduplication guarantee (each commit appears in the queue at most once) is a prerequisite for the next commit, which replaces that scan with an O(1) nonstale counter.

---
 commit-reach.c | 19 +++++++++++++++----
 object.h       |  2 +-
 2 files changed, 16 insertions(+), 5 deletions(-)

index d3a9b3ed6f..c16d4b061c 100644
@@ -17,8 +17,9 @@
 #define PARENT2		(1u<<17)
 #define STALE		(1u<<18)
 #define RESULT		(1u<<19)
+#define ENQUEUED	(1u<<20)
 
-static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);
+static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT | ENQUEUED);
 
 static int compare_commits_by_gen(const void *_a, const void *_b)
 {

@@ -39,6 +40,14 @@ static int compare_commits_by_gen(const void *_a, const void *_b)
 	return 0;
 }
 
+static void maybe_enqueue(struct prio_queue *queue, struct commit *c)
+{
+	if (c->object.flags & ENQUEUED)
+		return;
+	c->object.flags |= ENQUEUED;
+	prio_queue_put(queue, c);
+}
+
 static int queue_has_nonstale(struct prio_queue *queue)
 {
 	for (size_t i = 0; i < queue->nr; i++) {

@@ -70,11 +79,11 @@ static int paint_down_to_common(struct repository *r,
 		commit_list_append(one, result);
 		return 0;
 	}
-	prio_queue_put(&queue, one);
+	maybe_enqueue(&queue, one);
 
 	for (i = 0; i < n; i++) {
 		twos[i]->object.flags |= PARENT2;
-		prio_queue_put(&queue, twos[i]);
+		maybe_enqueue(&queue, twos[i]);
 	}
 
 	while (queue_has_nonstale(&queue)) {

@@ -83,6 +92,8 @@ static int paint_down_to_common(struct repository *r,
 		int flags;
 		timestamp_t generation = commit_graph_generation(commit);
 
+		commit->object.flags &= ~ENQUEUED;
+
 		if (min_generation && generation > last_gen)
 			BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
 			    generation, last_gen,

@@ -124,7 +135,7 @@ static int paint_down_to_common(struct repository *r,
 					     oid_to_hex(&p->object.oid));
 			}
 			p->object.flags |= flags;
-			prio_queue_put(&queue, p);
+			maybe_enqueue(&queue, p);
 		}
 	}
 

index d814647ebe..05cbf728e9 100644
@@ -74,7 +74,7 @@ void object_array_init(struct object_array *array);
  * bundle.c:                                        16
  * http-push.c:                          11-----14
  * commit-graph.c:                                15
- * commit-reach.c:                                  16-----19
+ * commit-reach.c:                                  16-------20
  * builtin/last-modified.c:                         1617
  * sha1-name.c:                                              20
  * list-objects-filter.c:                                      21

gitgitgadget

From: Kristofer Karlsson <[email protected]>

paint_down_to_common() terminates when every commit remaining in its priority queue is STALE. This was checked by queue_has_nonstale(), which performed an O(n) linear scan of the entire queue on every iteration, resulting in O(n*m) total overhead where n is the queue size and m is the number of commits processed.

Replace this with an O(1) nonstale_count that tracks the number of non-stale commits currently in the queue. The counter is incremented by maybe_enqueue() and decremented on dequeue and by mark_stale() when a commit transitions to STALE while still in the queue. Since each commit appears at most once (guaranteed by the ENQUEUED flag from the previous commit), the counter is exact.

ahead_behind() also uses queue_has_nonstale() and will be converted in the next commit.

---
 commit-reach.c | 28 +++++++++++++++++++++++-----
 1 file changed, 23 insertions(+), 5 deletions(-)

index c16d4b061c..356ff52d08 100644
@@ -40,12 +40,25 @@ static int compare_commits_by_gen(const void *_a, const void *_b)
 	return 0;
 }
 
-static void maybe_enqueue(struct prio_queue *queue, struct commit *c)
+static void maybe_enqueue(struct prio_queue *queue, struct commit *c,
+			  int *nonstale_count)
 {
 	if (c->object.flags & ENQUEUED)
 		return;
 	c->object.flags |= ENQUEUED;
 	prio_queue_put(queue, c);
+	if (!(c->object.flags & STALE))
+		(*nonstale_count)++;
+}
+
+static void mark_stale(struct commit *c, unsigned queued_flag,
+		       int *nonstale_count)
+{
+	if (!(c->object.flags & STALE)) {
+		if (c->object.flags & queued_flag)
+			(*nonstale_count)--;
+		c->object.flags |= STALE;
+	}
 }
 
 static int queue_has_nonstale(struct prio_queue *queue)

@@ -68,6 +81,7 @@ static int paint_down_to_common(struct repository *r,
 {
 	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
 	int i;
+	int nonstale_count = 0;
 	timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
 	struct commit_list **tail = result;
 

@@ -79,20 +93,22 @@ static int paint_down_to_common(struct repository *r,
 		commit_list_append(one, result);
 		return 0;
 	}
-	maybe_enqueue(&queue, one);
+	maybe_enqueue(&queue, one, &nonstale_count);
 
 	for (i = 0; i < n; i++) {
 		twos[i]->object.flags |= PARENT2;
-		maybe_enqueue(&queue, twos[i]);
+		maybe_enqueue(&queue, twos[i], &nonstale_count);
 	}
 
-	while (queue_has_nonstale(&queue)) {
+	while (nonstale_count > 0) {
 		struct commit *commit = prio_queue_get(&queue);
 		struct commit_list *parents;
 		int flags;
 		timestamp_t generation = commit_graph_generation(commit);
 
 		commit->object.flags &= ~ENQUEUED;
+		if (!(commit->object.flags & STALE))
+			nonstale_count--;
 
 		if (min_generation && generation > last_gen)
 			BUG("bad generation skip %"PRItime" > %"PRItime" at %s",

@@ -134,8 +150,10 @@ static int paint_down_to_common(struct repository *r,
 				return error(_("could not parse commit %s"),
 					     oid_to_hex(&p->object.oid));
 			}
+			if (flags & STALE)
+				mark_stale(p, ENQUEUED, &nonstale_count);
 			p->object.flags |= flags;
-			maybe_enqueue(&queue, p);
+			maybe_enqueue(&queue, p, &nonstale_count);
 		}
 	}
 

gitgitgadget

From: Kristofer Karlsson <[email protected]>

Apply the same nonstale_count optimization from the previous commit to ahead_behind(). This replaces the remaining caller of the O(n) queue_has_nonstale() scan with an O(1) counter check, allowing queue_has_nonstale() to be removed.

ahead_behind() already deduplicates queue entries using the PARENT2 flag (via insert_no_dup), so the counter is maintained through insert_no_dup() and mark_stale() using PARENT2 as the queued_flag.

---
 commit-reach.c | 27 ++++++++++++---------------
 1 file changed, 12 insertions(+), 15 deletions(-)

index 356ff52d08..41deb8fc78 100644
@@ -61,16 +61,6 @@ static void mark_stale(struct commit *c, unsigned queued_flag,
 	}
 }
 
-static int queue_has_nonstale(struct prio_queue *queue)
-{
-	for (size_t i = 0; i < queue->nr; i++) {
-		struct commit *commit = queue->array[i].data;
-		if (!(commit->object.flags & STALE))
-			return 1;
-	}
-	return 0;
-}
-
 /* all input commits in one and twos[] must have been parsed! */
 static int paint_down_to_common(struct repository *r,
 				struct commit *one, int n,

@@ -1051,12 +1041,15 @@ struct commit_list *get_reachable_subset(struct commit **from, size_t nr_from,
 define_commit_slab(bit_arrays, struct bitmap *);
 static struct bit_arrays bit_arrays;
 
-static void insert_no_dup(struct prio_queue *queue, struct commit *c)
+static void insert_no_dup(struct prio_queue *queue, struct commit *c,
+			  int *nonstale_count)
 {
 	if (c->object.flags & PARENT2)
 		return;
 	prio_queue_put(queue, c);
 	c->object.flags |= PARENT2;
+	if (!(c->object.flags & STALE))
+		(*nonstale_count)++;
 }
 
 static struct bitmap *get_bit_array(struct commit *c, int width)

@@ -1082,6 +1075,7 @@ void ahead_behind(struct repository *r,
 {
 	struct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date };
 	size_t width = DIV_ROUND_UP(commits_nr, BITS_IN_EWORD);
+	int nonstale_count = 0;
 
 	if (!commits_nr || !counts_nr)
 		return;

@@ -1100,14 +1094,17 @@ void ahead_behind(struct repository *r,
 		struct bitmap *bitmap = get_bit_array(c, width);
 
 		bitmap_set(bitmap, i);
-		insert_no_dup(&queue, c);
+		insert_no_dup(&queue, c, &nonstale_count);
 	}
 
-	while (queue_has_nonstale(&queue)) {
+	while (nonstale_count > 0) {
 		struct commit *c = prio_queue_get(&queue);
 		struct commit_list *p;
 		struct bitmap *bitmap_c = get_bit_array(c, width);
 
+		if (!(c->object.flags & STALE))
+			nonstale_count--;
+
 		for (size_t i = 0; i < counts_nr; i++) {
 			int reach_from_tip = !!bitmap_get(bitmap_c, counts[i].tip_index);
 			int reach_from_base = !!bitmap_get(bitmap_c, counts[i].base_index);

@@ -1136,9 +1133,9 @@ void ahead_behind(struct repository *r,
 			 * queue is STALE.
 			 */
 			if (bitmap_popcount(bitmap_p) == commits_nr)
-				p->item->object.flags |= STALE;
+				mark_stale(p->item, PARENT2, &nonstale_count);
 
-			insert_no_dup(&queue, p->item);
+			insert_no_dup(&queue, p->item, &nonstale_count);
 		}
 
 		free_bit_array(c);

gitgitgadget

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

It would be worth adding an update patch before this patch, that only makes these adjustments

This appears to me like the only interaction that _could_ have overlap with paint_down_to_common().

FLAG_LINK in builtin/index-pack.c and FLAG_OPEN in builtin/unpack-objects.c both seem to be completely independent from this use in commit-reach.c.

Thanks,
-Stolee

This idea has a lot of merit, but I'm a bit concerned about the organization of data. My ideas of how to improve things may also impact patch 1's use of ENQUEUED.

We faced a similar problem in limit_list() but solved it a bit differently (mostly because I was worried about keeping the counter up to date in all cases).

It's described in more detail in b6e8a3b540 (limit_list: avoid quadratic behavior from still_interesting, 2015-04-17), but the general idea is to just cache the interesting element we found, and invalidate the cache when it gets removed from the queue or gets marked UNINTERESTING.

The equivalent code for the STALE flag here is something like this:

index d3a9b3ed6f..d1621be89f 100644
@@ -39,12 +39,25 @@ static int compare_commits_by_gen(const void *_a, const void *_b)
 	return 0;
 }
 
-static int queue_has_nonstale(struct prio_queue *queue)
+static int queue_has_nonstale(struct prio_queue *queue,
+			      struct commit **nonstale_cache)
 {
+	if (*nonstale_cache) {
+		struct commit *commit = *nonstale_cache;
+		if (!(commit->object.flags & STALE))
+			return 1;
+	}
+
+	/*
+	 * This might also benefit from looking back-to-front, since
+	 * earlier commits are more likely to get popped sooner.
+	 */
 	for (size_t i = 0; i < queue->nr; i++) {
 		struct commit *commit = queue->array[i].data;
-		if (!(commit->object.flags & STALE))
+		if (!(commit->object.flags & STALE)) {
+			*nonstale_cache = commit;
 			return 1;
+		}
 	}
 	return 0;
 }

@@ -61,6 +74,7 @@ static int paint_down_to_common(struct repository *r,
 	int i;
 	timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
 	struct commit_list **tail = result;
+	struct commit *nonstale_cache = NULL;
 
 	if (!min_generation && !corrected_commit_dates_enabled(r))
 		queue.compare = compare_commits_by_commit_date;

@@ -77,12 +91,15 @@ static int paint_down_to_common(struct repository *r,
 		prio_queue_put(&queue, twos[i]);
 	}
 
-	while (queue_has_nonstale(&queue)) {
+	while (queue_has_nonstale(&queue, &nonstale_cache)) {
 		struct commit *commit = prio_queue_get(&queue);
 		struct commit_list *parents;
 		int flags;
 		timestamp_t generation = commit_graph_generation(commit);
 
+		if (nonstale_cache == commit)
+			nonstale_cache = NULL;
+
 		if (min_generation && generation > last_gen)
 			BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
 			    generation, last_gen,

@@ -1053,6 +1070,7 @@ void ahead_behind(struct repository *r,
 {
 	struct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date };
 	size_t width = DIV_ROUND_UP(commits_nr, BITS_IN_EWORD);
+	struct commit *nonstale_cache = NULL;
 
 	if (!commits_nr || !counts_nr)
 		return;

@@ -1074,11 +1092,14 @@ void ahead_behind(struct repository *r,
 		insert_no_dup(&queue, c);
 	}
 
-	while (queue_has_nonstale(&queue)) {
+	while (queue_has_nonstale(&queue, &nonstale_cache)) {
 		struct commit *c = prio_queue_get(&queue);
 		struct commit_list *p;
 		struct bitmap *bitmap_c = get_bit_array(c, width);
 
+		if (c == nonstale_cache)
+			nonstale_cache = NULL;
+
 		for (size_t i = 0; i < counts_nr; i++) {
 			int reach_from_tip = !!bitmap_get(bitmap_c, counts[i].tip_index);
 			int reach_from_base = !!bitmap_get(bitmap_c, counts[i].base_index);

I don't have a repo handy which reproduces the problem, so I can't see if it improves things. But if it's easy to do, can you report on the timing change with your monorepo?

I do think what I've shown here is a bit hacky (just like the limit_list() one), as we are relying on heuristics about the order in which items are taken from the queue. So even if it performs well, we may still prefer the counter version for being truly O(1). But having timing numbers would be useful for comparing the two approaches.

-Peff

I ran an audit of the flag allocation table and found three stale entries:

1. sha1-name.c was renamed to object-name.c.
2. builtin/show-branch.c uses bits 0 and 2-28, not 0-26.
3. negotiator/skipping.c is missing — it uses bits 2-5 like negotiator/default.c, with ADVERTISED on bit 3 instead of COMMON_REF.

I have a fixup commit ready - mini-preview below. I can submit it on top of this patchset or create a separate patch if you prefer that?

+ * negotiator/skipping.c: 2--5
- * sha1-name.c: 20
+ * object-name.c: 20
- * builtin/show-branch.c: 0-------------------------------------------26
+ * builtin/show-branch.c: 0-----------------------------------------------28

While doing the audit I noticed that reasoning about flag safety is currently entirely manual. Would there be interest in something more systematic (e.g. runtime registration/assertion, dynamic allocation or static analysis of flag usage)? I have some local work on that already, but I was not sure if this was something worth spending time on or not.

- Kristofer

That makes sense, but it does raise one question: since we do not clear the PARENT2 flag upon popping, is it possible to consider a commit a second time, after it has been popped?

I suspect the answer is "yes", if you have commits with out-of-order dates (so we visit X, which has PARENT2 set, and then later visit its descendant, and try to add X again as a parent).

I guess your counter does not make anything worse, though, because the same PARENT2 flag that prevents us from incrementing the counter also prevents us from actually adding it to the queue again.

And I think the current code is OK because we do not care about de-duping the queue, but about not double-counting commits in the global space. So PARENT2 effectively acts as a "seen" flag here.

-Peff

Ah, hmm. We do clear flags in the callers using clear_commit_marks(), which walks down parent pointers until nobody has a flag we care about (from all_flags). I'm not 100% sure that ENQUEUED flags will always be caught that way, but I think the reasoning is roughly: every thing we queue will either have PARENT1 or PARENT2 set, so we'll keep walking and clearing flags until we stop seeing those.

-Peff

If there weren't existing code that are so tied to their current uses of fixed flag bits and assumption that nobody else uses these bits outside their intended use, I'd love to have any of these. Uncolliding and unbounded number of usable bits per object that are *fast* to access would be good (and commit-slab was an attempt to introduce a framework that can be used as the basis for such a system). Independent of that, if we can statically analyze the uses of these bits to prove that the same flag bits are never used at the same time for colliding purposes, that would really be valuable.

Good catch Jeff! I think it's possible that I missed the flag cleanup case here, but it's also possible that I got lucky and it worked anyway. That said, I think the observation in the other email thread/commit is key here. I will reply back in that one, but it seems like this can all be simplified using Jeff's idea with an amortized O(1) solution by caching a known non-stale entry in the queue, and thus becomes obsolete. I will post a new patchset when the discussion slows down.

As for general flag management, I will spend some more time thinking about it. I don't fully trust static code analysis to work, but some cheap assertion based model might give a nice trade-off.

Thanks for all the feedback!
- Kristofer

That's an excellent approach! Much cleaner in general.

I benchmarked it against the counter on a monorepo with wide-frontier DAGs (2.4M commits, component import merges). Using merge-base --all to bypass the early-exit optimization from kk/paint-down-to-common-optim:

               Baseline    Cache   Counter
    import(A)    8079ms   3686ms    3723ms
    import(B)    5498ms   3993ms    4038ms
    import(C)    4350ms   1748ms    1766ms

The cache performs on par with the counter - within noise on all three cases. No new flags needed, much simpler diff.
The amortized O(1) is just as good as true O(1) in practice, and it avoids the ENQUEUED flag and counter bookkeeping entirely.

I went with back-to-front scanning as you suggested, and also clear the cache when the cached entry goes stale. Applied to both paint_down_to_common and ahead_behind.

I can rewrite the patchset with this approach and add you as co-author or suggested-by? Or I think I can wait for you to push it yourself. You did all the work here, and just didn't have enough data points to motivate it?

- Kristofer

Nice.

I can take from either of you two ;-). Thanks for working so well together, as always.

I have been thinking a bit about encapsulation too - the problem is twofold:
1. ENQUEUED is a tag on the commit object but it represents membership inside the queue and so we already have an implicit assumption that it only matches one queue (at a time).
2. The counter is touched on enqueue/dequeue BUT also when mutating objects - that last part is tricky to encapsulate as a part of the queue.

That said, I think if we go in the direction of Jeff's idea with an amortized O(1) staleness check, this becomes simpler - and we can perhaps do something to structure _that_ code instead. Something like this perhaps:

struct stale_prio_queue {
prio_queue pq;
commit *nonstale_cache;
}

and add the corresponding wrapper functions.

I think the encapsulation idea becomes even stronger with that approach than with the counter based approach.

- Kristofer

I'm not sure if it's technically amortized O(1), as I think in the worst case we are still quadratic. That would happen if we've cached some non-stale X, then pop it and put on some new commit Y. And then the next round we have no cache (X was popped), but have to walk the whole queue to find Y.

So I think it's more of a "heuristically O(1)" or something.

Out of curiosity, did you also time it front-to-back? What I wonder is if we might commonly hit that worst case for back-to-front when we're continually popping and inserting one new commit at the front of the queue. If there's a bunch of stale cruft in the back end of the queue, we'll walk over it repeatedly to find the new commit, and our cache will never (or seldom) remain valid. (I know it's a heap, not a real queue, but I think the far end of the array will still tend to represent stuff that is further away from being popped due to the heap property).

Whereas looking from front to back, we are likely to cache something that is going to be popped soon. But in that case we find it quickly, and the longer we search the more likely it is to hang around in the queue and remain valid.

I think this happens naturally when we call into queue_has_nonstale(). We only use the cached value if it's still non-stale. If it's gone stale then we either find a new commit, or if we can't then we return false (everything is stale). I guess the stale commit is left in the cache in the latter case, but it doesn't matter because the loop ends anyway (and even if it didn't, it is OK to repeatedly ignore the stale commit, as doing so is O(1) and we have nothing better to cache).

That said, it is probably only one line to explicitly set it to NULL in queue_has_nonstale(), so I am OK with that. ;)

If you're proposing to notice when we set the STALE flag on a commit which matches the cached value, I'd prefer to avoid that, just because it muddies up the code.

I think testing and writing the commit messages will be more work than the code. I am happy to live on in a trailer if you will do those other parts. ;)

-Peff

Well, you did add it to ALL_FLAGS, so it might have been your subconscious making you lucky. :)

Nifty, thanks.

I think it would be really nice if we had per-operation flags kept outside of the structs completely. If you're a masochist, I fiddled around a bit with using a hash instead in this thread:

https://lore.kernel.org/git/[email protected]/

It's sadly (but not surprisingly) quite slow. I do wonder how a slab would work there, but it would take a bit more surgery. We only allocate slab ids for commits, and we'd have to do so for all objects if we want to hold flags.

Probably a dead-end, but it would be neat if all of these flag allocation worries just went away.

-Peff

Good point, it may not truly be amortized O(1) — you can construct cases where all the interesting commits cluster at the front and the cache is repeatedly invalidated.

That said, I started thinking about what happens if we upgrade the cache on every enqueue, and I think there is a clean O(1) solution that eliminates scanning entirely.

The key observation: commits transition from non-stale to stale but never the other way. So if we track the lowest-priority non-stale commit in the queue and maintain it on every enqueue, we get a tight invariant:

struct nonstale_queue {
      struct prio_queue pq;
      struct commit *max_nonstale;
};

static void nonstale_queue_put(struct nonstale_queue *nsq,

                             struct commit *commit) {
        prio_queue_put(&nsq->pq, commit);
        if (commit->object.flags & STALE)
                return;
        if (!nsq->max_nonstale ||
            nsq->pq.compare(nsq->max_nonstale, commit,
                            nsq->pq.cb_data) < 0)
                nsq->max_nonstale = commit;
}

static struct commit *nonstale_queue_get(struct nonstale_queue *nsq)

{
      struct commit *commit = prio_queue_get(&nsq->pq);
      if (commit == nsq->max_nonstale) nsq->max_nonstale = NULL;
      return commit;
}

The loop condition becomes while (nsq.max_nonstale).

Why this works:

1. max_nonstale always points to the lowest-priority non-stale entry we have seen. Everything behind it in the priority order was stale at enqueue time, and stale is a one-way transition, so it stays stale.
2. When max_nonstale is popped, every remaining entry has lower priority and is therefore stale. The popped commit's parents get enqueued though, and if any are non-stale they restore max_nonstale via nonstale_queue_put().
3. If max_nonstale becomes stale between pops (e.g. painted from both sides), we don't notice immediately — the walk does a few extra iterations until it's popped. That's a small bounded cost.

This seems like the best of both worlds: O(1) like the counter approach but with the simplicity of the cache, and no new flags.

I have it implemented and tested it locally and the performance is identical to the cache version on the monorepo.

I can push an updated v2 patch with this approach later, unless something else pops up from the discussions (maybe I am wrong about all this!)

-- Kristofer

From: Kristofer Karlsson <[email protected]>

Update three stale entries found during an audit of the flag allocation table:

- sha1-name.c was renamed to object-name.c
- builtin/show-branch.c uses bits 0 and 2-28, not 0-26 (REV_SHIFT=2, MAX_REVS=FLAG_BITS-REV_SHIFT=27)
- negotiator/skipping.c uses bits 2-5 like negotiator/default.c (ADVERTISED on bit 3 instead of COMMON_REF)

---
 object.h | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

index d814647ebe..2b26de3044 100644
@@ -67,6 +67,7 @@ void object_array_init(struct object_array *array);
  * revision.h:               0---------10         15               23--------28
  * fetch-pack.c:             01    67
  * negotiator/default.c:       2--5
+ * negotiator/skipping.c:      2--5
  * walker.c:                 0-2
  * upload-pack.c:                4       11-----14  16-----19
  * builtin/blame.c:                        12-13

@@ -76,13 +77,13 @@ void object_array_init(struct object_array *array);
  * commit-graph.c:                                15
  * commit-reach.c:                                  16-----19
  * builtin/last-modified.c:                         1617
- * sha1-name.c:                                              20
+ * object-name.c:                                            20
  * list-objects-filter.c:                                      21
  * bloom.c:                                                    2122
  * builtin/fsck.c:           0--3
  * builtin/index-pack.c:                                     2021
  * reflog.c:                           10--12
- * builtin/show-branch.c:    0-------------------------------------------26
+ * builtin/show-branch.c:    0-----------------------------------------------28
  * builtin/unpack-objects.c:                                 2021
  * pack-bitmap.h:                                              2122
  */

gitgitgadget

From: Kristofer Karlsson <[email protected]>

paint_down_to_common() can enqueue the same commit multiple times when it is reached through different parents with different flag combinations. Add an ENQUEUED flag to track whether a commit is currently in the priority queue, and skip it if already present.

Introduce prio_queue_put_dedup() and prio_queue_get_dedup() wrappers that manage the ENQUEUED flag on enqueue and dequeue.

This change is performance-neutral on its own: the O(n) queue_has_nonstale() scan still dominates the per-iteration cost. However, the deduplication guarantee (each commit appears in the queue at most once) is a prerequisite for the next commit, which replaces that scan with O(1) tracking.

---
 commit-reach.c | 27 ++++++++++++++++++++++-----
 object.h       |  2 +-
 2 files changed, 23 insertions(+), 6 deletions(-)

index 5a52be90a6..85583ae359 100644
@@ -17,8 +17,9 @@
 #define PARENT2		(1u<<17)
 #define STALE		(1u<<18)
 #define RESULT		(1u<<19)
+#define ENQUEUED	(1u<<20)
 
-static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);
+static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT | ENQUEUED);
 
 static int compare_commits_by_gen(const void *_a, const void *_b)
 {

@@ -39,6 +40,22 @@ static int compare_commits_by_gen(const void *_a, const void *_b)
 	return 0;
 }
 
+static void prio_queue_put_dedup(struct prio_queue *queue, struct commit *c)
+{
+	if (c->object.flags & ENQUEUED)
+		return;
+	c->object.flags |= ENQUEUED;
+	prio_queue_put(queue, c);
+}
+
+static struct commit *prio_queue_get_dedup(struct prio_queue *queue)
+{
+	struct commit *commit = prio_queue_get(queue);
+	if (commit)
+		commit->object.flags &= ~ENQUEUED;
+	return commit;
+}
+
 static int queue_has_nonstale(struct prio_queue *queue)
 {
 	for (size_t i = 0; i < queue->nr; i++) {

@@ -70,15 +87,15 @@ static int paint_down_to_common(struct repository *r,
 		commit_list_append(one, result);
 		return 0;
 	}
-	prio_queue_put(&queue, one);
+	prio_queue_put_dedup(&queue, one);
 
 	for (i = 0; i < n; i++) {
 		twos[i]->object.flags |= PARENT2;
-		prio_queue_put(&queue, twos[i]);
+		prio_queue_put_dedup(&queue, twos[i]);
 	}
 
 	while (queue_has_nonstale(&queue)) {
-		struct commit *commit = prio_queue_get(&queue);
+		struct commit *commit = prio_queue_get_dedup(&queue);
 		struct commit_list *parents;
 		int flags;
 		timestamp_t generation = commit_graph_generation(commit);

@@ -132,7 +149,7 @@ static int paint_down_to_common(struct repository *r,
 					     oid_to_hex(&p->object.oid));
 			}
 			p->object.flags |= flags;
-			prio_queue_put(&queue, p);
+			prio_queue_put_dedup(&queue, p);
 		}
 	}
 

index 2b26de3044..8fb03ff90a 100644
@@ -75,7 +75,7 @@ void object_array_init(struct object_array *array);
  * bundle.c:                                        16
  * http-push.c:                          11-----14
  * commit-graph.c:                                15
- * commit-reach.c:                                  16-----19
+ * commit-reach.c:                                  16-------20
  * builtin/last-modified.c:                         1617
  * object-name.c:                                            20
  * list-objects-filter.c:                                      21

gitgitgadget

From: Kristofer Karlsson <[email protected]>

paint_down_to_common() and ahead_behind() call queue_has_nonstale() on every iteration to decide whether to continue the walk. queue_has_nonstale() performs a linear scan of the priority queue, making the overall walk O(n*m) where n is the number of commits walked and m is the queue size.

Introduce 'struct nonstale_queue', a thin wrapper around prio_queue that maintains a 'max_nonstale' pointer — the lowest-priority (oldest) non-stale commit seen so far. When this commit is popped, every remaining queue entry is known to be stale, so the walk can stop. This reduces the per-iteration termination check from O(m) to O(1).

Uses <= 0 (not < 0) when comparing priorities so that among distinct commits with equal priority (same generation and timestamp) the last-enqueued one is tracked. Since prio_queue breaks ties by insertion order, this ensures max_nonstale is always the last in its priority class to be popped, making pointer equality on pop sufficient for correctness.

The previous commit's ENQUEUED deduplication guarantees each commit appears at most once in the queue, which is required for the pointer equality check to be unambiguous.

On a large monorepo (3.7M commits), this yields ~2x end-to-end speedup for merge-base calculations on deep import branches. Profiling shows paint_down_to_common() drops from 50% to 4% of total runtime (~27x faster), with the remaining time in commit graph lookups and heap operations:

Before: 8536ms / 5757ms / 4743ms (three test cases)
After: 3956ms / 4383ms / 1927ms

---
 commit-reach.c | 96 ++++++++++++++++++++++++++++++++++----------------
 1 file changed, 65 insertions(+), 31 deletions(-)

index 85583ae359..b5328a804c 100644
@@ -40,32 +40,62 @@ static int compare_commits_by_gen(const void *_a, const void *_b)
 	return 0;
 }
 
-static void prio_queue_put_dedup(struct prio_queue *queue, struct commit *c)
+/*
+ * A prio_queue with O(1) termination check.  'max_nonstale' tracks
+ * the lowest-priority non-stale commit enqueued so far; once it is
+ * popped, every remaining entry is known to be STALE.
+ */
+struct nonstale_queue {
+	struct prio_queue pq;
+	struct commit *max_nonstale;
+};
+
+static void nonstale_queue_put(struct nonstale_queue *queue,
+			       struct commit *c)
+{
+	struct commit *old = queue->max_nonstale;
+
+	prio_queue_put(&queue->pq, c);
+	if (c->object.flags & STALE)
+		return;
+	if (!old || queue->pq.compare(old, c, queue->pq.cb_data) <= 0)
+		queue->max_nonstale = c;
+}
+
+static struct commit *nonstale_queue_get(struct nonstale_queue *queue)
+{
+	struct commit *commit = prio_queue_get(&queue->pq);
+
+	if (commit == queue->max_nonstale)
+		queue->max_nonstale = NULL;
+
+	return commit;
+}
+
+static void clear_nonstale_queue(struct nonstale_queue *queue)
+{
+	clear_prio_queue(&queue->pq);
+	queue->max_nonstale = NULL;
+}
+
+static void nonstale_queue_put_dedup(struct nonstale_queue *queue,
+				     struct commit *c)
 {
 	if (c->object.flags & ENQUEUED)
 		return;
 	c->object.flags |= ENQUEUED;
-	prio_queue_put(queue, c);
+	nonstale_queue_put(queue, c);
 }
 
-static struct commit *prio_queue_get_dedup(struct prio_queue *queue)
+static struct commit *nonstale_queue_get_dedup(struct nonstale_queue *queue)
 {
-	struct commit *commit = prio_queue_get(queue);
+	struct commit *commit = nonstale_queue_get(queue);
+
 	if (commit)
 		commit->object.flags &= ~ENQUEUED;
 	return commit;
 }
 
-static int queue_has_nonstale(struct prio_queue *queue)
-{
-	for (size_t i = 0; i < queue->nr; i++) {
-		struct commit *commit = queue->array[i].data;
-		if (!(commit->object.flags & STALE))
-			return 1;
-	}
-	return 0;
-}
-
 /* all input commits in one and twos[] must have been parsed! */
 static int paint_down_to_common(struct repository *r,
 				struct commit *one, int n,

@@ -74,28 +104,30 @@ static int paint_down_to_common(struct repository *r,
 				enum merge_base_flags mb_flags,
 				struct commit_list **result)
 {
-	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
+	struct nonstale_queue queue = {
+		{ compare_commits_by_gen_then_commit_date }
+	};
 	int i;
 	timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
 	struct commit_list **tail = result;
 
 	if (!min_generation && !corrected_commit_dates_enabled(r))
-		queue.compare = compare_commits_by_commit_date;
+		queue.pq.compare = compare_commits_by_commit_date;
 
 	one->object.flags |= PARENT1;
 	if (!n) {
 		commit_list_append(one, result);
 		return 0;
 	}
-	prio_queue_put_dedup(&queue, one);
+	nonstale_queue_put_dedup(&queue, one);
 
 	for (i = 0; i < n; i++) {
 		twos[i]->object.flags |= PARENT2;
-		prio_queue_put_dedup(&queue, twos[i]);
+		nonstale_queue_put_dedup(&queue, twos[i]);
 	}
 
-	while (queue_has_nonstale(&queue)) {
-		struct commit *commit = prio_queue_get_dedup(&queue);
+	while (queue.max_nonstale) {
+		struct commit *commit = nonstale_queue_get_dedup(&queue);
 		struct commit_list *parents;
 		int flags;
 		timestamp_t generation = commit_graph_generation(commit);

@@ -133,7 +165,7 @@ static int paint_down_to_common(struct repository *r,
 			if ((p->object.flags & flags) == flags)
 				continue;
 			if (repo_parse_commit(r, p)) {
-				clear_prio_queue(&queue);
+				clear_nonstale_queue(&queue);
 				commit_list_free(*result);
 				*result = NULL;
 				/*

@@ -149,11 +181,11 @@ static int paint_down_to_common(struct repository *r,
 					     oid_to_hex(&p->object.oid));
 			}
 			p->object.flags |= flags;
-			prio_queue_put_dedup(&queue, p);
+			nonstale_queue_put_dedup(&queue, p);
 		}
 	}
 
-	clear_prio_queue(&queue);
+	clear_nonstale_queue(&queue);
 	commit_list_sort_by_date(result);
 	return 0;
 }

@@ -1057,11 +1089,11 @@ struct commit_list *get_reachable_subset(struct commit **from, size_t nr_from,
 define_commit_slab(bit_arrays, struct bitmap *);
 static struct bit_arrays bit_arrays;
 
-static void insert_no_dup(struct prio_queue *queue, struct commit *c)
+static void insert_no_dup(struct nonstale_queue *queue, struct commit *c)
 {
 	if (c->object.flags & PARENT2)
 		return;
-	prio_queue_put(queue, c);
+	nonstale_queue_put(queue, c);
 	c->object.flags |= PARENT2;
 }
 

@@ -1086,7 +1118,9 @@ void ahead_behind(struct repository *r,
 		  struct commit **commits, size_t commits_nr,
 		  struct ahead_behind_count *counts, size_t counts_nr)
 {
-	struct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date };
+	struct nonstale_queue queue = {
+		{ .compare = compare_commits_by_gen_then_commit_date }
+	};
 	size_t width = DIV_ROUND_UP(commits_nr, BITS_IN_EWORD);
 
 	if (!commits_nr || !counts_nr)

@@ -1109,8 +1143,8 @@ void ahead_behind(struct repository *r,
 		insert_no_dup(&queue, c);
 	}
 
-	while (queue_has_nonstale(&queue)) {
-		struct commit *c = prio_queue_get(&queue);
+	while (queue.max_nonstale) {
+		struct commit *c = nonstale_queue_get(&queue);
 		struct commit_list *p;
 		struct bitmap *bitmap_c = get_bit_array(c, width);
 

@@ -1152,10 +1186,10 @@ void ahead_behind(struct repository *r,
 
 	/* STALE is used here, PARENT2 is used by insert_no_dup(). */
 	repo_clear_commit_marks(r, PARENT2 | STALE);
-	for (size_t i = 0; i < queue.nr; i++)
-		free_bit_array(queue.array[i].data);
+	for (size_t i = 0; i < queue.pq.nr; i++)
+		free_bit_array(queue.pq.array[i].data);
 	clear_bit_arrays(&bit_arrays);
-	clear_prio_queue(&queue);
+	clear_nonstale_queue(&queue);
 }
 
 struct commit_and_index {

gitgitgadget

This is v2 of the series to replace the O(n) queue_has_nonstale() scan with O(1) tracking.

Changes since v1:

* Replaced the nonstale counter with a max_nonstale pointer approach, as suggested by Jeff King. Instead of counting non-stale entries, we track the lowest-priority non-stale commit; when it is popped, all remaining entries must be stale.

* Restructured from 5 patches to 3:

1. object.h: fix stale entries in object flag allocation table
2. commit-reach: deduplicate queue entries in paint_down_to_common
3. commit-reach: replace queue_has_nonstale() scan with O(1) tracking

* Separated concerns: ENQUEUED dedup is a paint_down_to_common concern (commit 2), while nonstale_queue is a general wrapper usable by both paint_down_to_common and ahead_behind (commit 3). ahead_behind uses its own PARENT2-based dedup via insert_no_dup.

* The nonstale_queue struct is intentionally kept thin (no ENQUEUED handling). Dedup variants (nonstale_queue_put_dedup / nonstale_queue_get_dedup) are layered on top for paint_down_to_common.

Performance on a large monorepo (3.7M commits), merge-base --all on deep import branches:

Baseline Patched

component import, wide frontier (1):  8536ms           3956ms
component import, wide frontier (2):  5757ms           4383ms
component import, wide frontier (3):  4743ms           1927ms

Profiling shows paint_down_to_common() drops from 50% to 4% of total runtime (~27x faster). The remaining time is in commit graph lookups, heap operations, and object management — per-commit costs that are not addressed by this series.

Simple/linear cases show no regression (sub-15ms regardless).

Kristofer Karlsson (3):
object.h: fix stale entries in object flag allocation table
commit-reach: deduplicate queue entries in paint_down_to_common
commit-reach: replace queue_has_nonstale() scan with O(1) tracking

 commit-reach.c | 101 +++++++++++++++++++++++++++++++++++++------------
 object.h       |   7 ++--
 2 files changed, 80 insertions(+), 28 deletions(-)

base-commit: 56a4f3c3a221adf1df9b39da69b8a6890f803157
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2124%2Fspkrka%2Fqueue-has-nonstale-v3-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2124/spkrka/queue-has-nonstale-v3-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/2124

Range-diff vs v1:

 -:  ---------- > 1:  105f4646c2 object.h: fix stale entries in object flag allocation table
 1:  1d3751569b ! 2:  fc38c0f856 commit-reach: deduplicate queue entries in paint_down_to_common
     @@ Commit message
          combinations. Add an ENQUEUED flag to track whether a commit is
          currently in the priority queue, and skip it if already present.
      
     +    Introduce prio_queue_put_dedup() and prio_queue_get_dedup()
     +    wrappers that manage the ENQUEUED flag on enqueue and dequeue.
     +
          This change is performance-neutral on its own: the O(n)
          queue_has_nonstale() scan still dominates the per-iteration cost.
          However, the deduplication guarantee (each commit appears in the
          queue at most once) is a prerequisite for the next commit, which
     -    replaces that scan with an O(1) nonstale counter.
     +    replaces that scan with O(1) tracking.
      
          Signed-off-by: Kristofer Karlsson <[email protected]>
      
     @@ commit-reach.c: static int compare_commits_by_gen(const void *_a, const void *_b
       	return 0;
       }
       
     -+static void maybe_enqueue(struct prio_queue *queue, struct commit *c)
     ++static void prio_queue_put_dedup(struct prio_queue *queue, struct commit *c)
      +{
      +	if (c->object.flags & ENQUEUED)
      +		return;
      +	c->object.flags |= ENQUEUED;
      +	prio_queue_put(queue, c);
      +}
     ++
     ++static struct commit *prio_queue_get_dedup(struct prio_queue *queue)
     ++{
     ++	struct commit *commit = prio_queue_get(queue);
     ++	if (commit)
     ++		commit->object.flags &= ~ENQUEUED;
     ++	return commit;
     ++}
      +
       static int queue_has_nonstale(struct prio_queue *queue)
       {
     @@ commit-reach.c: static int paint_down_to_common(struct repository *r,
       		return 0;
       	}
      -	prio_queue_put(&queue, one);
     -+	maybe_enqueue(&queue, one);
     ++	prio_queue_put_dedup(&queue, one);
       
       	for (i = 0; i < n; i++) {
       		twos[i]->object.flags |= PARENT2;
      -		prio_queue_put(&queue, twos[i]);
     -+		maybe_enqueue(&queue, twos[i]);
     ++		prio_queue_put_dedup(&queue, twos[i]);
       	}
       
       	while (queue_has_nonstale(&queue)) {
     -@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
     +-		struct commit *commit = prio_queue_get(&queue);
     ++		struct commit *commit = prio_queue_get_dedup(&queue);
     + 		struct commit_list *parents;
       		int flags;
       		timestamp_t generation = commit_graph_generation(commit);
     - 
     -+		commit->object.flags &= ~ENQUEUED;
     -+
     - 		if (min_generation && generation > last_gen)
     - 			BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
     - 			    generation, last_gen,
      @@ commit-reach.c: static int paint_down_to_common(struct repository *r,
       					     oid_to_hex(&p->object.oid));
       			}
       			p->object.flags |= flags;
      -			prio_queue_put(&queue, p);
     -+			maybe_enqueue(&queue, p);
     ++			prio_queue_put_dedup(&queue, p);
       		}
       	}
       
     @@ object.h: void object_array_init(struct object_array *array);
      - * commit-reach.c:                                  16-----19
      + * commit-reach.c:                                  16-------20
        * builtin/last-modified.c:                         1617
     -  * sha1-name.c:                                              20
     +  * object-name.c:                                            20
        * list-objects-filter.c:                                      21
 2:  4742f5e634 < -:  ---------- commit-reach: optimize queue scan in paint_down_to_common
 3:  711a0e2235 ! 3:  03771eb34c commit-reach: optimize queue scan in ahead_behind

@@ Metadata
Author: Kristofer Karlsson <[email protected]>

## Commit message ##
- commit-reach: optimize queue scan in ahead_behind
+ commit-reach: replace queue_has_nonstale() scan with O(1) tracking

- Apply the same nonstale_count optimization from the previous commit
- to ahead_behind(). This replaces the remaining caller of the O(n)
- queue_has_nonstale() scan with an O(1) counter check, allowing
- queue_has_nonstale() to be removed.
+ paint_down_to_common() and ahead_behind() call queue_has_nonstale()
+ on every iteration to decide whether to continue the walk.
+ queue_has_nonstale() performs a linear scan of the priority queue,
+ making the overall walk O(n*m) where n is the number of commits
+ walked and m is the queue size.

- ahead_behind() already deduplicates queue entries using the PARENT2
- flag (via insert_no_dup), so the counter is maintained through
- insert_no_dup() and mark_stale() using PARENT2 as the queued_flag.
+ Introduce 'struct nonstale_queue', a thin wrapper around prio_queue
+ that maintains a 'max_nonstale' pointer — the lowest-priority
+ (oldest) non-stale commit seen so far. When this commit is popped,
+ every remaining queue entry is known to be stale, so the walk can
+ stop. This reduces the per-iteration termination check from O(m)
+ to O(1).

+ Uses <= 0 (not < 0) when comparing priorities so that among distinct
+ commits with equal priority (same generation and timestamp) the
+ last-enqueued one is tracked. Since prio_queue breaks ties by
+ insertion order, this ensures max_nonstale is always the last in its
+ priority class to be popped, making pointer equality on pop
+ sufficient for correctness.
+
+ The previous commit's ENQUEUED deduplication guarantees each commit
+ appears at most once in the queue, which is required for the pointer
+ equality check to be unambiguous.
+
+ On a large monorepo (3.7M commits), this yields ~2x end-to-end
+ speedup for merge-base calculations on deep import branches.
+ Profiling shows paint_down_to_common() drops from 50% to 4% of
+ total runtime (~27x faster), with the remaining time in commit
+ graph lookups and heap operations:
+
+ Before: 8536ms / 5757ms / 4743ms (three test cases)
+ After: 3956ms / 4383ms / 1927ms
+
+ Suggested-by: Jeff King <[email protected]>

## commit-reach.c ##
-@@ commit-reach.c: static void mark_stale(struct commit *c, unsigned queued_flag,
- }
+@@ commit-reach.c: static int compare_commits_by_gen(const void *_a, const void *_b)
+ return 0;
+ }
+
+-static void prio_queue_put_dedup(struct prio_queue *queue, struct commit *c) ++/*
++ * A prio_queue with O(1) termination check. 'max_nonstale' tracks ++ * the lowest-priority non-stale commit enqueued so far; once it is ++ * popped, every remaining entry is known to be STALE.
++ */
++struct nonstale_queue {
++ struct prio_queue pq;
++ struct commit *max_nonstale;
++};
++
++static void nonstale_queue_put(struct nonstale_queue *queue,
++ struct commit *c)
++{
++ struct commit *old = queue->max_nonstale;
++
++ prio_queue_put(&queue->pq, c);
++ if (c->object.flags & STALE)
++ return;
++ if (!old || queue->pq.compare(old, c, queue->pq.cb_data) <= 0)
++ queue->max_nonstale = c;
++}
++
++static struct commit *nonstale_queue_get(struct nonstale_queue *queue) ++{
++ struct commit *commit = prio_queue_get(&queue->pq);
++
++ if (commit == queue->max_nonstale)
++ queue->max_nonstale = NULL;
++
++ return commit;
++}
++
++static void clear_nonstale_queue(struct nonstale_queue *queue)
++{
++ clear_prio_queue(&queue->pq);
++ queue->max_nonstale = NULL;
++}
++
++static void nonstale_queue_put_dedup(struct nonstale_queue *queue,
++ struct commit *c)
+ {
+ if (c->object.flags & ENQUEUED)
+ return;
+ c->object.flags |= ENQUEUED;
+- prio_queue_put(queue, c);
++ nonstale_queue_put(queue, c);
+ }
+
+-static struct commit *prio_queue_get_dedup(struct prio_queue *queue) ++static struct commit *nonstale_queue_get_dedup(struct nonstale_queue *queue)
+ {
+- struct commit *commit = prio_queue_get(queue);
++ struct commit *commit = nonstale_queue_get(queue);
++
+ if (commit)
+ commit->object.flags &= ~ENQUEUED;
+ return commit;
}

-static int queue_has_nonstale(struct prio_queue *queue)
@@ commit-reach.c: static void mark_stale(struct commit *c, unsigned queued_flag,
/* all input commits in one and twos[] must have been parsed! */
static int paint_down_to_common(struct repository *r,
struct commit *one, int n,
+@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
+ enum merge_base_flags mb_flags,
+ struct commit_list **result)
+ {
+- struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
++ struct nonstale_queue queue = {
++ { compare_commits_by_gen_then_commit_date }
++ };
+ int i;
+ timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
+ struct commit_list **tail = result;
+
+ if (!min_generation && !corrected_commit_dates_enabled(r))
+- queue.compare = compare_commits_by_commit_date;
++ queue.pq.compare = compare_commits_by_commit_date;
+
+ one->object.flags |= PARENT1;
+ if (!n) {
+ commit_list_append(one, result);
+ return 0;
+ }
+- prio_queue_put_dedup(&queue, one);
++ nonstale_queue_put_dedup(&queue, one);
+
+ for (i = 0; i < n; i++) {
+ twos[i]->object.flags |= PARENT2;
+- prio_queue_put_dedup(&queue, twos[i]);
++ nonstale_queue_put_dedup(&queue, twos[i]);
+ }
+
+- while (queue_has_nonstale(&queue)) {
+- struct commit *commit = prio_queue_get_dedup(&queue);
++ while (queue.max_nonstale) {
++ struct commit *commit = nonstale_queue_get_dedup(&queue);
+ struct commit_list *parents;
+ int flags;
+ timestamp_t generation = commit_graph_generation(commit);
+@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
+ if ((p->object.flags & flags) == flags)
+ continue;
+ if (repo_parse_commit(r, p)) {
+- clear_prio_queue(&queue);
++ clear_nonstale_queue(&queue);
+ commit_list_free(*result);
+ *result = NULL;
+ /*
+@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
+ oid_to_hex(&p->object.oid));
+ }
+ p->object.flags |= flags;
+- prio_queue_put_dedup(&queue, p);
++ nonstale_queue_put_dedup(&queue, p);
+ }
+ }
+
+- clear_prio_queue(&queue);
++ clear_nonstale_queue(&queue);
+ commit_list_sort_by_date(result);
+ return 0;
+ }
@@ commit-reach.c: struct commit_list *get_reachable_subset(struct commit **from, size_t nr_from,
define_commit_slab(bit_arrays, struct bitmap *);
static struct bit_arrays bit_arrays;

-static void insert_no_dup(struct prio_queue *queue, struct commit *c)
-+static void insert_no_dup(struct prio_queue *queue, struct commit *c,
-+ int *nonstale_count)
++static void insert_no_dup(struct nonstale_queue *queue, struct commit *c)
{
if (c->object.flags & PARENT2)
return;
- prio_queue_put(queue, c);
+- prio_queue_put(queue, c);
++ nonstale_queue_put(queue, c);
c->object.flags |= PARENT2;
-+ if (!(c->object.flags & STALE))
-+ (*nonstale_count)++;
}

- static struct bitmap *get_bit_array(struct commit *c, int width) @@ commit-reach.c: void ahead_behind(struct repository *r,
+ struct commit **commits, size_t commits_nr,
+ struct ahead_behind_count *counts, size_t counts_nr)
{
- struct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date };
+- struct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date };
++ struct nonstale_queue queue = {
++ { .compare = compare_commits_by_gen_then_commit_date }
++ };
size_t width = DIV_ROUND_UP(commits_nr, BITS_IN_EWORD);
-+ int nonstale_count = 0;

if (!commits_nr || !counts_nr)
- return;
@@ commit-reach.c: void ahead_behind(struct repository *r,
- struct bitmap *bitmap = get_bit_array(c, width);
-
- bitmap_set(bitmap, i);
-- insert_no_dup(&queue, c);
-+ insert_no_dup(&queue, c, &nonstale_count);
+ insert_no_dup(&queue, c);
}

- while (queue_has_nonstale(&queue)) {
-+ while (nonstale_count > 0) {
- struct commit *c = prio_queue_get(&queue);
+- struct commit *c = prio_queue_get(&queue);
++ while (queue.max_nonstale) {
++ struct commit *c = nonstale_queue_get(&queue);
struct commit_list *p;
struct bitmap *bitmap_c = get_bit_array(c, width);

-+ if (!(c->object.flags & STALE))
-+ nonstale_count--;
-+
- for (size_t i = 0; i < counts_nr; i++) {
- int reach_from_tip = !!bitmap_get(bitmap_c, counts[i].tip_index);
- int reach_from_base = !!bitmap_get(bitmap_c, counts[i].base_index);
@@ commit-reach.c: void ahead_behind(struct repository *r,
- * queue is STALE.
- */
- if (bitmap_popcount(bitmap_p) == commits_nr)
-- p->item->object.flags |= STALE;
-+ mark_stale(p->item, PARENT2, &nonstale_count);

-- insert_no_dup(&queue, p->item);
-+ insert_no_dup(&queue, p->item, &nonstale_count);
- }
+ /* STALE is used here, PARENT2 is used by insert_no_dup(). */
+ repo_clear_commit_marks(r, PARENT2 | STALE);
+- for (size_t i = 0; i < queue.nr; i++)
+- free_bit_array(queue.array[i].data);
++ for (size_t i = 0; i < queue.pq.nr; i++)
++ free_bit_array(queue.pq.array[i].data);
+ clear_bit_arrays(&bit_arrays);
+- clear_prio_queue(&queue);
++ clear_nonstale_queue(&queue);
+ }

- free_bit_array(c);
+ struct commit_and_index {

gitgitgadget

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

OK. I guess an obvious alternative design would be to have an associated hashtable for deduping, or tweak prio_queue_get() so that it notices duplicated entry just before it returns (i.e., peek and discard until queue->array[0].data is different from what you are going to return). Both would not beat the cheap cost of using a single bit per object, I guess ;-)

Thanks for the clean-up in the previous step, by the way.

Yes, I think a hashtable or hashset would work here too. I realize that I have done a lot of local experimentation with alternative approaches but I forgot to mention the ones I discarded for various reasons - but that would be useful information for you to have too. Let me rectify that here.

oidset instead of enqueued flag: Works fine, but is ~15-20% slower end-to-end. Both are O(1) but the overhead is quite significant compared to a flag.

Peek and discard: the problem here is that the commits are not necessarily ordered. We can have a sequence of A,B,A if we are unlucky. What I did try however was an alternative to this - just change the fast-exit heuristic to overshoot until comparison returns > 0 - i.e. consume some extra commits in the queue. This works and in my example data we typically would only need to walk ~16 extra commits with this heuristic, so it's not bad at all. But the extra comparisons we need to run on each iteration make it ~15-20% slower.

Another thing I tried was simply tracking the minimum generation seen and terminate as soon as we have gone past it. This is fast and simple and does not require deduping, but it only works if we have a commit graph and generation numbers.

The advantage of the approach with deduping via the ENQUEUED flag and then just tracking the most recently enqueued commit is that it works independently of ordering guarantees. All it needs to work is the fact that we can prove that we have reached a point where queue no longer has any non-stale commits at all.

Summary:

  Approach        Dedup         Works w/o commit-graph?  Speed
  ENQUEUED flag   yes (1 bit)   yes                      fastest
  Hashtable       yes           yes                      15-20% slower
  Peek-discard    -             -                        broken
  Cmp overshoot   no            yes                      15-20% slower
  Gen overshoot   no            no                       same as ENQUEUED