On Monday, September 22nd, 2025 at 2:48 AM, David Brown via Gcc
<[email protected]> wrote:
>
>
> On 22/09/2025 08:29, Yair Lenga via Gcc wrote:
>
> > Hi,
> >
> > I've inherited an old code base of "C" code, which was maintained by
> > relatively inexperience team. One of the common pattern that I've seen was:
> >
> > for (int i=0 ; i < strlen(s) ; i++) { ... }
> >
> > Which has O(n^2) performance, given O(n) performance on s. Acceptable on
> > strings up to 400-500 characters, but painful when large strings - 4k.
> >
> > My question: Is there a path to add new performance-related diagnostics for
> > those cases, in general, any function with expected O(n) in the
> > condition/step of a loop (for ; while ; do ... while) should trigger this
> > warning. The most common pattern that I've seen - I believe other pattern
> > also exists - with strchr, strstr, ...
> >
> > Ideally, this will come with an annotation that can be placed on function
> > to say "I'm expensive, should not be called in a tight loop"
> >
> > [[GNU:expensive]] const int count_something(const char *x) ;
> >
> > which will result in a performance warning on
> > for (int i=0 ; i<count_something(s) ; i++)
> >
> > Looking for feedback, and suggestion on how to get something like that
> > implement - is this something that will be useful ?
> >
> > Yair
>
>
> gcc (and most C libraries used with gcc) already has a solution for
> making code such as your original pattern efficient. "strlen" is marked
> with the attribute "pure", which tells gcc that the function has no
> side-effects and it can therefore in many cases move the call to
> strlen() outside the loop :
>
> https://godbolt.org/z/1r6sj3dnf
It can only do this if it can prove that str is not modified in the
loop. As soon as you call a function the compiler doesn't know about
this optimization unfortunately is no longer valid.
I wish this wasn't the case, but alas.
https://godbolt.org/z/Khqh3PTxn
>
>
> I can understand that you feel it is poor practice to have the strlen
> call inside the loop - not every compiler can optimise as well as gcc -
> but I don't think it is easy to specify a warning such as you describe.
> How should it distinguish between a tight loop that calls your
> "expensive" function, and one that calls another function that happens
> to contain the "expensive" function?
>
> It would certainly make sense in a coding standard to say that the
> limits in a for-loop should be calculated before the loop, but I suspect
> it would be very difficult to have good automatic tests on that.
>
I don't think it would be too difficult to implement this, you just
walk the expression looking for calls to functions that are tagged with
the proposed attribute. Granted you will have 'false positives' for
cases that can be optimized, but that isn't necessarily a bad thing
since it can be a problem in debug builds. Whether this would be useful
for more than just loop conditions, I'm not sure.
Adding annotations for big O time/space complexity is an idea I've
discussed with others in the past in the context of general language
design. I reckon it could be useful for more things than just this.
Perhaps one attribute for size and one attribute for time complexity
would be a good idea.
Of course, I'm not so sure the maintainers of glibc and libstdc++ will
be happy about adding yet another annotation to standard library
functions. I think it's most important we hear from them.
Alex
