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
Junio C Hamano <gitster@pobox.com>
Date
May 25, 2026, 08:38 UTC
Message-ID
<xmqqfr3fg9z6.fsf@gitster.g>
In-Reply-To
<CAL71e4MOH2iPve19dKixLHSgpC3ZAZz59zLWEWRoxW1a7vhMwg@mail.gmail.com>
Kristofer Karlsson <krka@spotify.com> writes:
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.
Nice.
Show 8 quoted lines
> 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.

Previous: Kristofer KarlssonNext: Jeff King
Message 18 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.