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

Re: [PATCH 3/3] commit-reach: optimize queue scan in ahead_behind

From
Jeff King <peff@peff.net>
Date
May 25, 2026, 07:11 UTC
Message-ID
<20260525071150.GC2737798@coredump.intra.peff.net>
In-Reply-To
<711a0e2235103489f17ff867439e007abd0e4291.1779644541.git.gitgitgadget@gmail.com>
On Sun, May 24, 2026 at 05:42:20PM +0000, Kristofer Karlsson via GitGitGadget wrote:
> ahead_behind() already deduplicates queue entries using the PARENT2
> flag (via insert_no_dup), so the counter is maintained through
> insert_no_dup() and mark_stale() using PARENT2 as the queued_flag.

That makes sense, but it does raise one question: since we do not clear the PARENT2 flag upon popping, is it possible to consider a commit a second time, after it has been popped?

I suspect the answer is "yes", if you have commits with out-of-order dates (so we visit X, which has PARENT2 set, and then later visit its descendant, and try to add X again as a parent).

I guess your counter does not make anything worse, though, because the same PARENT2 flag that prevents us from incrementing the counter also prevents us from actually adding it to the queue again.

And I think the current code is OK because we do not care about de-duping the queue, but about not double-counting commits in the global space. So PARENT2 effectively acts as a "seen" flag here.

-Peff
Previous: Kristofer Karlsson via GitGitGadgetNext: Jeff King
Message 15 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.