From: Kristofer Karlsson Date: Mon, 25 May 2026 10:47:32 GMT Subject: Re: [PATCH 0/3] commit-reach: replace queue_has_nonstale with a counter Message-ID: In-Reply-To: <20260525095506.GA3868724@coredump.intra.peff.net> 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 wrote: > > 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