Re: [PATCH 0/3] commit-reach: replace queue_has_nonstale with a counter

On Mon, May 25, 2026 at 09:59:59AM +0200, Kristofer Karlsson 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'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.

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.

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.

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