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

Re: [PATCH 1/3] commit-reach: deduplicate queue entries in paint_down_to_common

From
Jeff King <peff@peff.net>
Date
May 25, 2026, 10:02 UTC
Message-ID
<20260525100215.GB3868724@coredump.intra.peff.net>
In-Reply-To
<CAL71e4ODJeCJctKg=3o9PKD6Rw3_xHnrjc+zT_MYFc=CdNc59A@mail.gmail.com>
On Mon, May 25, 2026 at 09:53:09AM +0200, Kristofer Karlsson wrote:
> Good catch Jeff! I think it's possible that I missed the flag cleanup case
> here, but it's also possible that I got lucky and it worked anyway.

Well, you did add it to ALL_FLAGS, so it might have been your subconscious making you lucky. :)

Show 5 quoted lines
> That said, I think the observation in the other email thread/commit is key
> here. I will reply back in that one, but it seems like this can all be
> simplified using Jeff's idea with an amortized O(1) solution by caching a
> known non-stale entry in the queue, and thus becomes obsolete. I will post
> a new patchset when the discussion slows down.
Nifty, thanks.
> As for general flag management, I will spend some more time thinking about it.
> I don't fully trust static code analysis to work, but some cheap assertion
> based model might give a nice trade-off.

I think it would be really nice if we had per-operation flags kept outside of the structs completely. If you're a masochist, I fiddled around a bit with using a hash instead in this thread:

  https://lore.kernel.org/git/20250826055210.GA1031277@coredump.intra.peff.net/

It's sadly (but not surprisingly) quite slow. I do wonder how a slab would work there, but it would take a bit more surgery. We only allocate slab ids for commits, and we'd have to do so for all objects if we want to hold flags.

Probably a dead-end, but it would be neat if all of these flag allocation worries just went away.

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