On Mon, 2025-09-22 at 10:41 +0000, waffl3x via Gcc wrote: > 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.
Perhaps an interprocedural analysis, looking for "expensive" calls and propagating that information through the call graph? We already have infrastructure for detecting loops. > 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. Interesting. Perhaps an interprocedural analysis that tries to calculate time complexity per function, based on the call graph and the nesting of call sites within loops? Sounds like a fun research project (but what is "n" at any given point?) Dave > > 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 >
