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
Jeff King <peff@peff.net>
Date
May 25, 2026, 09:55 UTC
Message-ID
<20260525095506.GA3868724@coredump.intra.peff.net>
In-Reply-To
<CAL71e4MOH2iPve19dKixLHSgpC3ZAZz59zLWEWRoxW1a7vhMwg@mail.gmail.com>
On Mon, May 25, 2026 at 09:59:59AM +0200, Kristofer Karlsson wrote:
Show 15 quoted lines
> 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: Junio C HamanoNext: Kristofer Karlsson
Message 19 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.