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

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

From
Kristofer Karlsson <krka@spotify.com>
Date
May 26, 2026, 06:57 UTC
Message-ID
<CAL71e4OFniTMgG2Sj3LDMdfdZzYh-J71maNcWaobEHri9ox43g@mail.gmail.com>
In-Reply-To
<xmqqzf1ncded.fsf@gitster.g>
On Tue, 26 May 2026 at 00:50, Junio C Hamano <gitster@pobox.com> wrote:
Show 6 quoted lines
> OK.  I guess an obvious alternative design would be to have an
> associated hashtable for deduping, or tweak prio_queue_get() so
> that it notices duplicated entry just before it returns (i.e.,
> peek and discard until queue->array[0].data is different from
> what you are going to return).  Both would not beat the cheap cost
> of using a single bit per object, I guess ;-)

Yes, I think a hashtable or hashset would work here too. I realize that I have done a lot of local experimentation with alternative approaches but I forgot to mention the ones I discarded for various reasons - but that would be useful information for you to have too. Let me rectify that here.

oidset instead of enqueued flag: Works fine, but is ~15-20% slower end-to-end. Both are O(1) but the overhead is quite significant compared to a flag.

Peek and discard: the problem here is that the commits are not necessarily ordered. We can have a sequence of A,B,A if we are unlucky. What I did try however was an alternative to this - just change the fast-exit heuristic to overshoot until comparison returns > 0 - i.e. consume some extra commits in the queue. This works and in my example data we typically would only need to walk ~16 extra commits with this heuristic, so it's not bad at all. But the extra comparisons we need to run on each iteration make it ~15-20% slower.

Another thing I tried was simply tracking the minimum generation seen and terminate as soon as we have gone past it. This is fast and simple and does not require deduping, but it only works if we have a commit graph and generation numbers.

The advantage of the approach with deduping via the ENQUEUED flag and then just tracking the most recently enqueued commit is that it works independently of ordering guarantees. All it needs to work is the fact that we can prove that we have reached a point where queue no longer has any non-stale commits at all.

Summary:
  Approach        Dedup         Works w/o commit-graph?  Speed
  ENQUEUED flag   yes (1 bit)   yes                      fastest
  Hashtable       yes           yes                      15-20% slower
  Peek-discard    -             -                        broken
  Cmp overshoot   no            yes                      15-20% slower
  Gen overshoot   no            no                       same as ENQUEUED
Previous: Junio C HamanoNext: Kristofer Karlsson via GitGitGadget
Message 25 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.