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

From: Kristofer Karlsson <krka@spotify.com>

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.

Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
 commit-reach.c | 19 +++++++++++++++----
 object.h       |  2 +-
 2 files changed, 16 insertions(+), 5 deletions(-)

From: Kristofer Karlsson <krka@spotify.com>

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.

Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
 commit-reach.c | 28 +++++++++++++++++++++++-----
 1 file changed, 23 insertions(+), 5 deletions(-)

From: Kristofer Karlsson <krka@spotify.com>

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.

Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
 commit-reach.c | 27 ++++++++++++---------------
 1 file changed, 12 insertions(+), 15 deletions(-)

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

Not directly the fault of this series, but we'd need to audit and update this table of bit assignment to match more recent reality.

For example, there no longer exists sha1-name.c but the table claims that bit 20 is in use for its own purpose, and it being stale makes it harder to audit and ensure that this new use would not crash with these existing uses (note. there are other uses of bit 20 in other subsystems).

FWIW, object-name.c, which was formerly known as sha1-name.c, uses the bit 20 as ONELINE_SEEN bit, which is used to turn textual object names like :/string (i.e., commit with that string in its message) into raw object name, and bit 20 is cleared from all the objects involved in the search before the helper function returns. Presumably, once commit-reach.c starts queueing commits and reuses this bit for its own purpose, we will never try to parse a textual commit object name to clobber what we thought is ENQUEUED bit, breaking the code introduced here, so we are probably safe against its use.

I didn't check all other uses of bit 20, though.

On 5/24/26 7:40 PM, Junio C Hamano wrote:

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

On 5/24/26 1:42 PM, Kristofer Karlsson via GitGitGadget wrote:

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.

These two methods have some concerns on my end:

1. We need to store the nonstale count somewhere other than the
    priority queue, even though it's necessarily representing a
    subset of the commits within the queue.

2. mark_stale() needs a queued_flag. (I need to check to see if
    this is indeed changing in multiple callers or should always
    be ENQUEUED).

My preference would be to create a new struct that contains a prio_queue as a member _and_ a nonstale_count. It could initialize with compare_commits_by_gen_then_commit_date by default.

The important thing is that consumers of such a "stale-tracking" queue would not be setting the STALE or ENQUEUED bits themselves, but instead the queue would be responsible for that.

This could allow us to simplify callers by always assuming we can "add" an element to the queue and the queue will use its ENQUEUED bit to prevent duplicates from reaching its internal prio_queue.

Such a data structure could be private to commit-reach.c for now, since all the methods that would use it seem to be colocated there.

This is a big ask, but I'm interested to see if such an approach would simplify things here.

Here's a potential breakdown of how to build such a thing in "small" patches:

1. Create the data structure and update paint_down_to_common and
    ahead_behind to use that structure, but still use the existing
    prio_queue methods on its internal member.

2. Add the ENQUEUED bit and methods on the new struct that add
    that bit as it adds commits to the inner prio_queue. It would
    also ignore commits that already have that bit. (Should it
    also remove the bit as commits are removed from the queue?)

3. Now add the nonstale_count (or stale count?) to the struct and
    have it control the STALE bit modifications, with increasing
    the stale count when ENQUEUED is live, and decreasing the stale
    count as such a STALE object is dequeued.

I like the idea of this being encapsulated within the struct and its helper methods. But the proof will be in the implementation.

Thanks, -Stolee

On Sun, May 24, 2026 at 05:42:17PM +0000, Kristofer Karlsson via GitGitGadget wrote:

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:

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

On Mon, 25 May 2026 at 03:43, Derrick Stolee <stolee@gmail.com> wrote:

On Sun, May 24, 2026 at 05:42:18PM +0000, Kristofer Karlsson via GitGitGadget wrote:

OK, so we mark each commit with ENQUEUED when we queue it, and then...

...clear that when we pop it. But the loop may terminate early before popping everything, and we get to this cleanup code at the end:

	clear_prio_queue(&queue);

When we drop all of those queue elements, they'll all be left with the ENQUEUED flag set. Should we clear those?

The ahead_behind() variant doesn't have the same problem, because it uses PARENT2 to check for queueing, and then does:

	/* STALE is used here, PARENT2 is used by insert_no_dup(). */
	repo_clear_commit_marks(r, PARENT2 | STALE);

So it's cleaning up both flags, whereas paint_down_to_common() is already leaving the STALE flag set. I'm not sure how much that matters (or if it is even an intentional thing communicated to the caller). But now we'd be adding ENQUEUED.

-Peff

On Sun, May 24, 2026 at 05:42:20PM +0000, Kristofer Karlsson via GitGitGadget wrote:

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

On Mon, May 25, 2026 at 03:01:14AM -0400, Jeff King wrote:

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

Kristofer Karlsson <krka@spotify.com> writes:

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

On Mon, 25 May 2026 at 09:17, Junio C Hamano <gitster@pobox.com> wrote:

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

On Mon, 25 May 2026 at 08:47, Jeff King <peff@peff.net> wrote:

Kristofer Karlsson <krka@spotify.com> writes:

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

On Mon, 25 May 2026 at 03:59, Derrick Stolee <stolee@gmail.com> wrote:

On Mon, May 25, 2026 at 09:59:59AM +0200, Kristofer Karlsson wrote:

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

On Mon, May 25, 2026 at 09:53:09AM +0200, Kristofer Karlsson wrote:

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/20250826055210.GA1031277@coredump.intra.peff.net/

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

On Mon, 25 May 2026 at 11:55, Jeff King <peff@peff.net> wrote:

From: Kristofer Karlsson <krka@spotify.com>

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)

Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
 object.h | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

From: Kristofer Karlsson <krka@spotify.com>

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.

Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
 commit-reach.c | 27 ++++++++++++++++++++++-----
 object.h       |  2 +-
 2 files changed, 23 insertions(+), 6 deletions(-)

From: Kristofer Karlsson <krka@spotify.com>

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

Suggested-by: Jeff King <peff@peff.net>
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
 commit-reach.c | 96 ++++++++++++++++++++++++++++++++++----------------
 1 file changed, 65 insertions(+), 31 deletions(-)

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 <krka@spotify.com>
      
     @@ 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 <krka@spotify.com>
      
       ## 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 <peff@peff.net>
          Signed-off-by: Kristofer Karlsson <krka@spotify.com>
      
       ## 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 {

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

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.

On Tue, 26 May 2026 at 00:50, Junio C Hamano <gitster@pobox.com> wrote:

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