From: Derrick Stolee <derrickstolee@github.com>
To: Junio C Hamano <gitster@pobox.com>, Han Xin <hanxin.hx@bytedance.com>
Cc: git@vger.kernel.org, xingxin.xx@bytedance.com, jonathantanmy@google.com
Subject: Re: [PATCH v3 1/2] negotiator/default: avoid stack overflow
Date: Wed, 26 Apr 2023 13:30:21 -0400 [thread overview]
Message-ID: <49695ce0-b9f9-0fc7-ed16-093dc7f12b7e@github.com> (raw)
In-Reply-To: <xmqqedo6tvkj.fsf@gitster.g>
On 4/26/2023 1:14 PM, Junio C Hamano wrote:
> Han Xin <hanxin.hx@bytedance.com> writes:
>> + if ((commit->object.flags & SEEN) && !(commit->object.flags & POPPED))
>> + ns->non_common_revs--;
>
> Hmph, this is a bit unexpected to duplicate the non_common_revs
> counting logic here. In the original, this piece of code was there
> just after we decided to continue digging into the parents, and even
> if this patch changes the mechanism with which "digging into the
> parents" from recursion to priority queue, it is not obvious why we
> can keep doing the decrementing for the current commit we are
> looking at, instead of doing that for parents of the commit like
> this patch does. In other words, it is not clear why it needs to be
> changed while going from recursive to iterative.
>
> Is it because ancestors_only is not usable inside the loop in the
> iterative version? That is, if ancestors_only is not set, we do
> paint the initial commit as COMMON just as the parents we discover
> in the loop, but when ancestors_only is set, we need to skip painting
> the initial commit as COMMON, so the patch moves that logic?
>
> It may solve the issue of special casing the initial commit, but it
> feels backwards in that the resulting loop becomes harder to
> understand by making it necessary to process the initial commit
> outside the loop only halfway.
The "ancestors_only" parameter is about treating the initial commit
differently than the ancestors. Since we add the initial commit to
the priority queue, the only way to know we are dealing with an
ancestor and not the initial commit is to do the processing when
visiting a parent for the first time.
> It may make it easier to understand if we had another local
> variable, "struct commit *skip_commit", that is NULL by default but
> is set to the initial commit when ancestors_only is set,
This is an interesting idea and could reduce the duplicated logic
for nw->common_revs.
> and do the
> painting with COMMON and counting of non_common_revs all inside the
> loop for the current commit that is being processed (instead of the
> parents the loop discovered). I dunno. It would avoid duplicating
> the logic and implements the "ancestors_only, do not paint or count
> the initial commit" in a more readable and straight-forward way, no?
However, we need to do the painting with COMMON when visiting a
parent in order to avoid adding duplicate entries to the priority
queue (and potentially growing exponentially).
Since we need to examine and modify a parent before adding it to
the queue, it is natural to do other "we are visiting a commit"
logic in that same place.
It is unfortunate that the logic for nw->common_revs is duplicated,
but I think this is a cleaner approach than other considered
approaches.
Thanks,
-Stolee
next prev parent reply other threads:[~2023-04-26 17:30 UTC|newest]
Thread overview: 20+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-04-24 2:23 [PATCH v1] negotiator/default.c: avoid stack overflow Han Xin
2023-04-24 14:44 ` Derrick Stolee
2023-04-25 3:02 ` [External] " Han Xin
2023-04-25 13:34 ` Derrick Stolee
2023-04-26 4:05 ` [PATCH v2 0/2] negotiator/default: " Han Xin
2023-04-26 4:05 ` [PATCH v2 1/2] " Han Xin
2023-04-26 11:13 ` Derrick Stolee
2023-04-26 11:40 ` [External] " Han Xin
2023-04-26 4:05 ` [PATCH v2 2/2] negotiator/skipping: fix some problems in mark_common() Han Xin
2023-04-26 11:08 ` Derrick Stolee
2023-04-26 11:55 ` [External] " Han Xin
2023-04-26 13:15 ` [PATCH v2 0/2] negotiator/default: avoid stack overflow Han Xin
2023-04-26 13:15 ` [PATCH v3 1/2] " Han Xin
2023-04-26 17:14 ` Junio C Hamano
2023-04-26 17:30 ` Derrick Stolee [this message]
2023-04-26 17:38 ` Junio C Hamano
2023-04-26 13:15 ` [PATCH v3 2/2] negotiator/skipping: fix some problems in mark_common() Han Xin
2023-05-01 22:11 ` [PATCH v2 0/2] negotiator/default: avoid stack overflow Junio C Hamano
2023-05-02 1:49 ` Derrick Stolee
2023-05-02 15:51 ` Junio C Hamano
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=49695ce0-b9f9-0fc7-ed16-093dc7f12b7e@github.com \
--to=derrickstolee@github.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=hanxin.hx@bytedance.com \
--cc=jonathantanmy@google.com \
--cc=xingxin.xx@bytedance.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
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;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).