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 [off-list ref] wrote:

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

quoted

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

quoted

I went with back-to-front scanning as you suggested

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.

quoted

and also clear the cache when the cached entry goes stale.

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.

quoted

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?

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