From: Jeff King <peff@peff•net>
To: Kristofer Karlsson via GitGitGadget <gitgitgadget@gmail•com>
Cc: git@vger•kernel.org, Kristofer Karlsson <krka@spotify•com>
Subject: Re: [PATCH 3/3] commit-reach: optimize queue scan in ahead_behind
Date: Mon, 25 May 2026 03:11:50 -0400 [thread overview]
Message-ID: <20260525071150.GC2737798@coredump.intra.peff.net> (raw)
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
next prev parent reply other threads:[~2026-05-25 7:11 UTC|newest]
Thread overview: 26+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-05-24 17:42 [PATCH 0/3] commit-reach: replace queue_has_nonstale with a counter Kristofer Karlsson via GitGitGadget
2026-05-24 17:42 ` [PATCH 1/3] commit-reach: deduplicate queue entries in paint_down_to_common Kristofer Karlsson via GitGitGadget
2026-05-24 23:40 ` Junio C Hamano
2026-05-25 1:43 ` Derrick Stolee
2026-05-25 6:50 ` Kristofer Karlsson
2026-05-25 7:17 ` Junio C Hamano
2026-05-25 7:53 ` Kristofer Karlsson
2026-05-25 10:02 ` Jeff King
2026-05-25 7:01 ` Jeff King
2026-05-25 7:15 ` Jeff King
2026-05-24 17:42 ` [PATCH 2/3] commit-reach: optimize queue scan " Kristofer Karlsson via GitGitGadget
2026-05-25 1:59 ` Derrick Stolee
2026-05-25 8:54 ` Kristofer Karlsson
2026-05-24 17:42 ` [PATCH 3/3] commit-reach: optimize queue scan in ahead_behind Kristofer Karlsson via GitGitGadget
2026-05-25 7:11 ` Jeff King [this message]
2026-05-25 6:47 ` [PATCH 0/3] commit-reach: replace queue_has_nonstale with a counter Jeff King
2026-05-25 7:59 ` Kristofer Karlsson
2026-05-25 8:38 ` Junio C Hamano
2026-05-25 9:55 ` Jeff King
2026-05-25 10:47 ` Kristofer Karlsson
2026-05-25 14:28 ` [PATCH v2 0/3] commit-reach: replace queue_has_nonstale() scan with O(1) tracking Kristofer Karlsson via GitGitGadget
2026-05-25 14:28 ` [PATCH v2 1/3] object.h: fix stale entries in object flag allocation table Kristofer Karlsson via GitGitGadget
2026-05-25 14:28 ` [PATCH v2 2/3] commit-reach: deduplicate queue entries in paint_down_to_common Kristofer Karlsson via GitGitGadget
2026-05-25 22:50 ` Junio C Hamano
2026-05-26 6:57 ` Kristofer Karlsson
2026-05-25 14:28 ` [PATCH v2 3/3] commit-reach: replace queue_has_nonstale() scan with O(1) tracking Kristofer Karlsson via GitGitGadget
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20260525071150.GC2737798@coredump.intra.peff.net \
--to=peff@peff$(echo .)net \
--cc=git@vger$(echo .)kernel.org \
--cc=gitgitgadget@gmail$(echo .)com \
--cc=krka@spotify$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox