patchbranch: avoid slow strvec Coccinelle matching
11 messages between Jul 24, 2026 and Sep 4, 2026, from tnyman@openai.com, Jeff King, Harald Nordgren, Junio C Hamano, Taylor Blau, Emmanuel Ugwu.
Plain Markdown or JSON for tools and agents. Diffs are folded; open one to read it.
From: Ted Nyman <tnyman@openai.com>
The --delete-merged implementation declares a loop index at function scope and reuses it to walk its strvec of upstreams and its list of candidate branches. Coccinelle 1.1.1 spends hours matching this against the separate_loop_index rule in tools/coccinelle/strvec.cocci, causing the static-analysis job on 'seen' to reach its six-hour timeout.
Declare each index in its for loop instead. This avoids the expensive separate-index rule, limits each index to the loop that uses it, and leaves the branch deletion behavior unchanged.
Signed-off-by: Ted Nyman <tnyman@openai.com>
---
This applies on top of hn/branch-delete-merged and addresses the long
static-analysis runs on 'seen'. Coccinelle 1.1.1 spends hours matching
the existing separate_loop_index rule against delete_merged_branches().
Declare each loop index in its for statement instead of sharing an index declared at function scope. This avoids the pathological matching without changing branch behavior.
The CI failure reproduces locally with Coccinelle 1.1.1: applying strvec.cocci to the original builtin/branch.c still times out with "spatch --timeout 120". With this change, the same check completes in 0.06 seconds.
The full coccicheck run completes in 47 seconds, and all 190 tests in t3200-branch.sh pass with a fresh DEVELOPER=1 build.
builtin/branch.c | 5 ++---
1 file changed, 2 insertions(+), 3 deletions(-)
Show changes to builtin/branch.c +2 −3
diff --git a/builtin/branch.c b/builtin/branch.c
index 42f2221547..2415a275ea 100644
--- a/builtin/branch.c
+++ b/builtin/branch.c
@@ -797,10 +797,9 @@ static int delete_merged_branches(const struct strvec *upstreams,
struct strbuf key = STRBUF_INIT;
struct hashmap_iter iter;
struct strmap_entry *entry;
- size_t i;
int ret = 0;
- for (i = 0; i < upstreams->nr; i++)
+ for (size_t i = 0; i < upstreams->nr; i++)
if (ref_filter_forked_add(&filter, upstreams->v[i]) < 0)
die(_("'%s' is not a valid branch or pattern"),
upstreams->v[i]);
@@ -809,7 +808,7 @@ static int delete_merged_branches(const struct strvec *upstreams,
filter.name_patterns = argv;
filter_refs(&candidates, &filter, filter.kind);
- for (i = 0; i < (size_t)candidates.nr; i++) {
+ for (size_t i = 0; i < (size_t)candidates.nr; i++) {
const char *branch_refname = candidates.items[i]->refname;
const char *branch_name;
struct branch *branch;
--
2.54.0.8.g047e0526de
Re: [PATCH] branch: avoid slow strvec Coccinelle matching
On Fri, Jul 24, 2026 at 02:11:53AM -0700, tnyman@openai.com wrote:
Show 5 quoted lines
> The --delete-merged implementation declares a loop index at function
> scope and reuses it to walk its strvec of upstreams and its list of
> candidate branches. Coccinelle 1.1.1 spends hours matching this against
> the separate_loop_index rule in tools/coccinelle/strvec.cocci, causing
> the static-analysis job on 'seen' to reach its six-hour timeout.
Yuck. So this is really a coccinelle problem. It looks like it has been fixed (or at least improved) in recent versions. I can reproduce the slowness locally on 1.2.0 (I couldn't get 1.1.1 to build), but 1.3.0 is fast. Bisection turns up 58619b8fe (break up envs for e1 & e2, 2024-08-18), which says:
Since 362937b2a84840e68ae021171df10c7a4cc6fbef, e1 ... e2 has the
quantifiers for the free variables of e1 around the whole thing, to ensure
that the when code on the ... refers to the same variables as e1. This can
make the semantic patch very slow, as illustrated by kmerr.cocci in
scripts/coccinelle/null/kmerr.cocci in the Linux kernel. The slowness
comes from environments based on multipl metavariable bindings getting very
large. To reduce (but not solve) the problem, for the first & where the left side
has multiple results, consider these results individually when working on
the right side, and then union the results. This may lead to some loss of
sharing. Maybe it is not advantageous when the ... contains when any and
does not contain any explicit when clause containing the variables of e1.The static-analysis CI job uses the ubuntu-22.04 image, for no reason that I can really discern. It looks like coccinelle 1.3.0 is in ubuntu 25.10, according to:
https://packages.ubuntu.com/km/questing/coccinelle
Why don't we just use the more recent version instead of trying to work around it? That would fix this problem and prevent future ones. Looking at the code in question:
Show 16 quoted lines
> diff --git a/builtin/branch.c b/builtin/branch.c
> index 42f2221547..2415a275ea 100644
> --- a/builtin/branch.c
> +++ b/builtin/branch.c
> @@ -797,10 +797,9 @@ static int delete_merged_branches(const struct strvec *upstreams,
> struct strbuf key = STRBUF_INIT;
> struct hashmap_iter iter;
> struct strmap_entry *entry;
> - size_t i;
> int ret = 0;
>
> - for (i = 0; i < upstreams->nr; i++)
> + for (size_t i = 0; i < upstreams->nr; i++)
> if (ref_filter_forked_add(&filter, upstreams->v[i]) < 0)
> die(_("'%s' is not a valid branch or pattern"),
> upstreams->v[i]);...there is nothing suspicious or wrong about it. It seems likely that somebody else may end up writing something similar and triggering the same problem.
That said, moving the iterator into the loop declaration is perhaps nicer anyway, because it avoids two unrelated uses of the same variable. Notably:
Show 9 quoted lines
> @@ -809,7 +808,7 @@ static int delete_merged_branches(const struct strvec *upstreams,
> filter.name_patterns = argv;
> filter_refs(&candidates, &filter, filter.kind);
>
> - for (i = 0; i < (size_t)candidates.nr; i++) {
> + for (size_t i = 0; i < (size_t)candidates.nr; i++) {
> const char *branch_refname = candidates.items[i]->refname;
> const char *branch_name;
> struct branch *branch;This hunk is not using a strvec at all. Because it uses the same variable, if we did not change this loop, then we'd still have to declare "i" at the top of the function and the other loop would introduce a shadowed variable. That's not wrong, but it is confusing.
However, if we are going to have our own variable here, perhaps it should use the correct type? candidate.nr is an int, so probably this should also be an int, and then the gross cast can go away.
-Peff
Re: [PATCH] branch: avoid slow strvec Coccinelle matching
Thanks for the report, Ted! CI had been timing out on this branch, but I chalked it up to one of the many CI failures we had in the last few months. CI is now generally stable again for some days, and with your fix it's also green on this branch specifically.
Good point, Jeff, probably it can be 'int i' in the 'candidates.nr', case to avoid a cast. I'll push it to GitHub to verify that the CI passes there as well, but I'll wait with submitting until others have finished reviewing, to not overload inboxes after already pushing out one version today.
Harald
Re: [PATCH] branch: avoid slow strvec Coccinelle matching
tnyman@openai.com writes:
Show 12 quoted lines
> From: Ted Nyman <tnyman@openai.com>
>
> The --delete-merged implementation declares a loop index at function
> scope and reuses it to walk its strvec of upstreams and its list of
> candidate branches. Coccinelle 1.1.1 spends hours matching this against
> the separate_loop_index rule in tools/coccinelle/strvec.cocci, causing
> the static-analysis job on 'seen' to reach its six-hour timeout.
> ...
> The CI failure reproduces locally with Coccinelle 1.1.1: applying
> strvec.cocci to the original builtin/branch.c still times out with
> "spatch --timeout 120". With this change, the same check completes in
> 0.06 seconds.
Impressive. Nicely analyzed.
Even though this is very much like bending the code only to appease the checker, the resulting code is arguably better in this particular case, so I do not feel as bad as I have on other occasions when we had to work around deficiencies in our tools [*].
I see Harald already took this in the latest update. Thanks for working well together.
[*]
* Here, I do not blame Coccinelle alone. The performance bug is
caused by a combination of Coccinelle and the 'strvec' check that
makes it so inefficient. I wonder if there are ways to make the
checks in 'strvec.cocci' more efficient?
Show 25 quoted lines
> diff --git a/builtin/branch.c b/builtin/branch.c
> index 42f2221547..2415a275ea 100644
> --- a/builtin/branch.c
> +++ b/builtin/branch.c
> @@ -797,10 +797,9 @@ static int delete_merged_branches(const struct strvec *upstreams,
> struct strbuf key = STRBUF_INIT;
> struct hashmap_iter iter;
> struct strmap_entry *entry;
> - size_t i;
> int ret = 0;
>
> - for (i = 0; i < upstreams->nr; i++)
> + for (size_t i = 0; i < upstreams->nr; i++)
> if (ref_filter_forked_add(&filter, upstreams->v[i]) < 0)
> die(_("'%s' is not a valid branch or pattern"),
> upstreams->v[i]);
> @@ -809,7 +808,7 @@ static int delete_merged_branches(const struct strvec *upstreams,
> filter.name_patterns = argv;
> filter_refs(&candidates, &filter, filter.kind);
>
> - for (i = 0; i < (size_t)candidates.nr; i++) {
> + for (size_t i = 0; i < (size_t)candidates.nr; i++) {
> const char *branch_refname = candidates.items[i]->refname;
> const char *branch_name;
> struct branch *branch;Re: [PATCH] branch: avoid slow strvec Coccinelle matching
Jeff King <peff@peff.net> writes:
Show 30 quoted lines
> The static-analysis CI job uses the ubuntu-22.04 image, for no reason
> that I can really discern. It looks like coccinelle 1.3.0 is in ubuntu
> 25.10, according to:
>
> https://packages.ubuntu.com/km/questing/coccinelle
>
> Why don't we just use the more recent version instead of trying to work
> around it? That would fix this problem and prevent future ones. Looking
> at the code in question:
>
>> diff --git a/builtin/branch.c b/builtin/branch.c
>> index 42f2221547..2415a275ea 100644
>> --- a/builtin/branch.c
>> +++ b/builtin/branch.c
>> @@ -797,10 +797,9 @@ static int delete_merged_branches(const struct strvec *upstreams,
>> struct strbuf key = STRBUF_INIT;
>> struct hashmap_iter iter;
>> struct strmap_entry *entry;
>> - size_t i;
>> int ret = 0;
>>
>> - for (i = 0; i < upstreams->nr; i++)
>> + for (size_t i = 0; i < upstreams->nr; i++)
>> if (ref_filter_forked_add(&filter, upstreams->v[i]) < 0)
>> die(_("'%s' is not a valid branch or pattern"),
>> upstreams->v[i]);
>
> ...there is nothing suspicious or wrong about it. It seems likely that
> somebody else may end up writing something similar and triggering the
> same problem.> That said, moving the iterator into the loop declaration is perhaps
> nicer anyway, because it avoids two unrelated uses of the same variable.
Show 20 quoted lines
> Notably:
>
>> @@ -809,7 +808,7 @@ static int delete_merged_branches(const struct strvec *upstreams,
>> filter.name_patterns = argv;
>> filter_refs(&candidates, &filter, filter.kind);
>>
>> - for (i = 0; i < (size_t)candidates.nr; i++) {
>> + for (size_t i = 0; i < (size_t)candidates.nr; i++) {
>> const char *branch_refname = candidates.items[i]->refname;
>> const char *branch_name;
>> struct branch *branch;
>
> This hunk is not using a strvec at all. Because it uses the same
> variable, if we did not change this loop, then we'd still have to
> declare "i" at the top of the function and the other loop would
> introduce a shadowed variable. That's not wrong, but it is confusing.
>
> However, if we are going to have our own variable here, perhaps it
> should use the correct type? candidate.nr is an int, so probably this
> should also be an int, and then the gross cast can go away.Ah, very good eyes. It is a disease to try appeasing -Wsign-compare without thinking, instead of questioning the value of the warning first, and in this case there is no reason to try forcing the use of size_t, even with the unnecessary casting.
Re: [PATCH] branch: avoid slow strvec Coccinelle matching
Junio C Hamano <gitster@pobox.com> writes:
Show 25 quoted lines
>> Notably:
>>
>>> @@ -809,7 +808,7 @@ static int delete_merged_branches(const struct strvec *upstreams,
>>> filter.name_patterns = argv;
>>> filter_refs(&candidates, &filter, filter.kind);
>>>
>>> - for (i = 0; i < (size_t)candidates.nr; i++) {
>>> + for (size_t i = 0; i < (size_t)candidates.nr; i++) {
>>> const char *branch_refname = candidates.items[i]->refname;
>>> const char *branch_name;
>>> struct branch *branch;
>>
>> This hunk is not using a strvec at all. Because it uses the same
>> variable, if we did not change this loop, then we'd still have to
>> declare "i" at the top of the function and the other loop would
>> introduce a shadowed variable. That's not wrong, but it is confusing.
>>
>> However, if we are going to have our own variable here, perhaps it
>> should use the correct type? candidate.nr is an int, so probably this
>> should also be an int, and then the gross cast can go away.
>
> Ah, very good eyes. It is a disease to try appeasing -Wsign-compare
> without thinking, instead of questioning the value of the warning
> first, and in this case there is no reason to try forcing the use of
> size_t, even with the unnecessary casting.Having said that, another fix might be to standardize the way we count the number of things in an array and update 'ref-filter.h' to use size_t in 'struct ref_array' as well.
It is not as though 2 billion refs are too few to satisfy our needs, and in general, the platform-natural int should be used to count things unless there is a compelling reason to deviate from that norm. However, "somehow we ended up counting many things in size_t, so it is better to count everything using the same type" could serve as "the compelling reason" to make such a change.
Re: [PATCH] branch: avoid slow strvec Coccinelle matching
Junio C Hamano <gitster@pobox.com> writes:
Show 15 quoted lines
>> Ah, very good eyes. It is a disease to try appeasing -Wsign-compare
>> without thinking, instead of questioning the value of the warning
>> first, and in this case there is no reason to try forcing the use of
>> size_t, even with the unnecessary casting.
>
> Having said that, another fix might be to standardize the way we
> count the number of things in an array and update 'ref-filter.h' to
> use size_t in 'struct ref_array' as well.
>
> It is not as though 2 billion refs are too few to satisfy our
> needs, and in general, the platform-natural int should be used to
> count things unless there is a compelling reason to deviate from
> that norm. However, "somehow we ended up counting many things in
> size_t, so it is better to count everything using the same type"
> could serve as "the compelling reason" to make such a change.
Let's not allow too much latitude to ourselves, as that would only confuse us.
Here is what I recommend that we do. In the short term, i.e., within the context of the topic in question, let's use 'int' to match the type used to count the members of an array embedded in 'struct ref_array'.
But let's leave a '#leftoverbits' note here in the mailing list archive to remind us to revisit the idea of consistently using 'size_t' to count things when things are quiet. This is not the time to needlessly disrupt the 'hn/branch-delete-merged' topic, I think.
Re: [PATCH] branch: avoid slow strvec Coccinelle matching
On Fri, Jul 24, 2026 at 08:27:06AM -0700, Junio C Hamano wrote:
Show 21 quoted lines
> tnyman@openai.com writes:
>
> > From: Ted Nyman <tnyman@openai.com>
> >
> > The --delete-merged implementation declares a loop index at function
> > scope and reuses it to walk its strvec of upstreams and its list of
> > candidate branches. Coccinelle 1.1.1 spends hours matching this against
> > the separate_loop_index rule in tools/coccinelle/strvec.cocci, causing
> > the static-analysis job on 'seen' to reach its six-hour timeout.
> > ...
> > The CI failure reproduces locally with Coccinelle 1.1.1: applying
> > strvec.cocci to the original builtin/branch.c still times out with
> > "spatch --timeout 120". With this change, the same check completes in
> > 0.06 seconds.
>
> Impressive. Nicely analyzed.
>
> Even though this is very much like bending the code only to appease
> the checker, the resulting code is arguably better in this
> particular case, so I do not feel as bad as I have on other
> occasions when we had to work around deficiencies in our tools [*].
Agreed. I don't think we should ever bend over backwards to appease a static analysis tool, *especially* when it results in worse looking code. But this case is a strict improvement, and just so happens to address the Coccinelle issue. ;-)
> I see Harald already took this in the latest update. Thanks for
> working well together.
Yup. Thanks, both.
Thanks, Taylor
Re: [PATCH] branch: avoid slow strvec Coccinelle matching
On Fri, Jul 24, 2026 at 09:26:04AM -0700, Junio C Hamano wrote:
Show 8 quoted lines
> > Ah, very good eyes. It is a disease to try appeasing -Wsign-compare
> > without thinking, instead of questioning the value of the warning
> > first, and in this case there is no reason to try forcing the use of
> > size_t, even with the unnecessary casting.
>
> Having said that, another fix might be to standardize the way we
> count the number of things in an array and update 'ref-filter.h' to
> use size_t in 'struct ref_array' as well.
Yes, I had the same thought.
I am generally in favor of using size_t for anything that counts allocations. I'd also be fine with (and maybe even prefer) a type that is a signed integer of the same magnitude as size_t, because loops, etc, are often easier to reason about when "0 - 1" is actually less than 0, and doesn't wrap. But we would need to define our own custom type for that, since ssize_t isn't portable enough.
Show 6 quoted lines
> It is not as though 2 billion refs are too few to satisfy our
> needs, and in general, the platform-natural int should be used to
> count things unless there is a compelling reason to deviate from
> that norm. However, "somehow we ended up counting many things in
> size_t, so it is better to count everything using the same type"
> could serve as "the compelling reason" to make such a change.
Yeah, I think that consistency is nice.
My personal reason (and this is mostly re-hashing previous discussions) is avoiding integer overflow attacks by making it impractical to allocate sufficient memory.
If you had a repository with 3 billion refs, then I think right now "git for-each-ref" would wrap and start using negative values. I _suspect_ it would be caught when ALLOC_GROW() converts that negative into to a size_t (yielding an impractical allocation), but I don't think it's practical to try. I started feeding 2^31 refs into "update-ref --stdin" and it was around 64GB of heap after only 160 million or so.
But in general, if the counters are all size_t or similar magnitude, then any geometric growth pattern is going to require allocating some significant portion of the whole address space before we hit the integer overflow condition (and presumably such an allocation would fail).
-Peff
Re: [PATCH] branch: avoid slow strvec Coccinelle matching
On Fri, Jul 24, 2026 at 10:33:05AM -0700, Junio C Hamano wrote:
Show 10 quoted lines
> Here is what I recommend that we do. In the short term, i.e.,
> within the context of the topic in question, let's use 'int' to
> match the type used to count the members of an array embedded in
> 'struct ref_array'.
>
> But let's leave a '#leftoverbits' note here in the mailing list
> archive to remind us to revisit the idea of consistently using
> 'size_t' to count things when things are quiet. This is not the
> time to needlessly disrupt the 'hn/branch-delete-merged' topic, I
> think.
Yep, agreed on all points.
-Peff
Re: [PATCH] branch: avoid slow strvec Coccinelle matching
Hi Junio, Jeff,
I'm Emmanuel Ugwu, new to the project and looking to get involved. I noticed this #leftoverbits from <https://github.com/pabloosabaterr/WhatToGit/blob/main/leftoverbits.md>. I have gone through the thread, the desired fix is to fix the inconsistencies in type by choosing/using a wide-enough type to avoid overflow (size_t) right?
Is now a reasonable time to start looking into this, or would you rather it wait until 'hn/branch-delete-merged' has settled?
Thanks, Emmanuel Ugwu
On Sun, Jul 26, 2026 at 8:41 AM Jeff King <peff@peff.net> wrote:
Show 18 quoted lines
>
> On Fri, Jul 24, 2026 at 10:33:05AM -0700, Junio C Hamano wrote:
>
> > Here is what I recommend that we do. In the short term, i.e.,
> > within the context of the topic in question, let's use 'int' to
> > match the type used to count the members of an array embedded in
> > 'struct ref_array'.
> >
> > But let's leave a '#leftoverbits' note here in the mailing list
> > archive to remind us to revisit the idea of consistently using
> > 'size_t' to count things when things are quiet. This is not the
> > time to needlessly disrupt the 'hn/branch-delete-merged' topic, I
> > think.
>
> Yep, agreed on all points.
>
> -Peff
>