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
Kristofer Karlsson <krka@spotify.com>
Date
May 25, 2026, 07:53 UTC
Message-ID
<CAL71e4ODJeCJctKg=3o9PKD6Rw3_xHnrjc+zT_MYFc=CdNc59A@mail.gmail.com>
In-Reply-To
<xmqqse7gez5l.fsf@gitster.g>

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. 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.

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.

Thanks for all the feedback!
- Kristofer
On Mon, 25 May 2026 at 09:17, Junio C Hamano <gitster@pobox.com> wrote:
Show 18 quoted lines
>
> Kristofer Karlsson <krka@spotify.com> writes:
>
> > While doing the audit I noticed that reasoning about flag safety is
> > currently entirely manual. Would there be interest in something more
> > systematic (e.g. runtime registration/assertion, dynamic allocation or static
> > analysis of flag usage)? I have some local work on that already, but I was
> > not sure if this was something worth spending time on or not.
>
> If there weren't existing code that are so tied to their current
> uses of fixed flag bits and assumption that nobody else uses these
> bits outside their intended use, I'd love to have any of these.
> Uncolliding and unbounded number of usable bits per object that are
> *fast* to access would be good (and commit-slab was an attempt to
> introduce a framework that can be used as the basis for such a
> system).  Independent of that, if we can statically analyze the uses
> of these bits to prove that the same flag bits are never used at the
> same time for colliding purposes, that would really be valuable.
Previous: Junio C HamanoNext: Jeff King
Message 7 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.