git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Kristofer Karlsson <krka@spotify.com>
Date
May 25, 2026, 10:47 UTC
Message-ID
<CAL71e4P0Ls9r0oAOeFoEUzD8Z+fBNKGAvLi-1zH+gb_nV=Ro7Q@mail.gmail.com>
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 <peff@peff.net> wrote:
Show 70 quoted lines
>
> 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
Previous: Jeff KingNext: Kristofer Karlsson via GitGitGadget
Message 20 of 26 in “commit-reach: replace queue_has_nonstale with a counter”
  1. 0/3 commit-reach: replace queue_has_nonstale with a counterKristofer Karlsson via GitGitGadget, May 24, 2026
  2. 1/3 commit-reach: deduplicate queue entries in paint_down_to_commonKristofer Karlsson via GitGitGadget, May 24, 2026
  3. Junio C HamanoMay 24, 2026
  4. Derrick StoleeMay 25, 2026
  5. Kristofer KarlssonMay 25, 2026
  6. Junio C HamanoMay 25, 2026
  7. Kristofer KarlssonMay 25, 2026
  8. Jeff KingMay 25, 2026
  9. Jeff KingMay 25, 2026
  10. Jeff KingMay 25, 2026
  11. 2/3 commit-reach: optimize queue scan in paint_down_to_commonKristofer Karlsson via GitGitGadget, May 24, 2026
  12. Derrick StoleeMay 25, 2026
  13. Kristofer KarlssonMay 25, 2026
  14. 3/3 commit-reach: optimize queue scan in ahead_behindKristofer Karlsson via GitGitGadget, May 24, 2026
  15. Jeff KingMay 25, 2026
  16. Jeff KingMay 25, 2026
  17. Kristofer KarlssonMay 25, 2026
  18. Junio C HamanoMay 25, 2026
  19. Jeff KingMay 25, 2026
  20. Kristofer KarlssonMay 25, 2026
  21. 0/3 commit-reach: replace queue_has_nonstale() scan with O(1) trackingKristofer Karlsson via GitGitGadget, May 25, 2026
  22. 1/3 object.h: fix stale entries in object flag allocation tableKristofer Karlsson via GitGitGadget, May 25, 2026
  23. 2/3 commit-reach: deduplicate queue entries in paint_down_to_commonKristofer Karlsson via GitGitGadget, May 25, 2026
  24. Junio C HamanoMay 25, 2026
  25. Kristofer KarlssonMay 26, 2026
  26. 3/3 commit-reach: replace queue_has_nonstale() scan with O(1) trackingKristofer Karlsson via GitGitGadget, May 25, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.