Kristofer Karlsson [off-list ref] writes:

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.

Nice.

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?

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