From: Junio C Hamano Date: Mon, 25 May 2026 08:38:21 GMT Subject: Re: [PATCH 0/3] commit-reach: replace queue_has_nonstale with a counter Message-ID: In-Reply-To: Kristofer Karlsson 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.