I'm not sure if the following code can cause redundant calculations, or is it compiler-specific?
for (int i = 0; i < strlen(ss); ++i)
{
// blabla
}
Will strlen()
be calculated every time when i
increases?
I'm not sure if the following code can cause redundant calculations, or is it compiler-specific?
for (int i = 0; i < strlen(ss); ++i)
{
// blabla
}
Will strlen()
be calculated every time when i
increases?
Yes, strlen()
will be evaluated on each iteration. It's possible that, under ideal circumstances, the optimiser might be able to deduce that the value won't change, but I personally wouldn't rely on that.
I'd do something like
for (int i = 0, n = strlen(ss); i < n; ++i)
or possibly
for (int i = 0; ss[i]; ++i)
as long as the string isn't going to change length during the iteration. If it might, then you'll need to either call strlen()
each time, or handle it through more complicated logic.
strlen
anyway.
strlen
is marked as __attribute__((pure))
allowing the compiler to elide multiple calls. GCC Attributes
Jul 6, 2012 at 15:42
Yes, every time you use the loop. Then it will every time calculate the length of the string. so use it like this:
char str[30];
for ( int i = 0; str[i] != '\0'; i++)
{
//Something;
}
In the above code str[i]
only verifies one particular character in the string at location i
each time the loop starts a cycle, thus it will take less memory and is more efficient.
See this Link for more information.
In the code below every time the loop runs strlen
will count the length of the whole string which is less efficient, takes more time and takes more memory.
char str[];
for ( int i = 0; i < strlen(str); i++)
{
//Something;
}
strlen
call, and if you're running that tight, you probably should be thinking about eliding a few other function calls as well...
int strlen(char *s) { int len = 0; while(s[len] != '\0') len++; return len; }
which is pretty much exactly what you are doing in the code in your answer. I'm not arguing that iterating over the string once rather than twice is more time-efficient, but I don't see one or the other using more or less memory. Or are you referring to the variable used to hold the string length?
A good compiler may not calculate it every time, but I don't think you can be sure, that every compiler does it.
In addition to that, the compiler has to know, that strlen(ss)
does not change. This is only true if ss
is not changed in for
loop.
For example, if you use a read-only function on ss
in for
loop but don't declare the ss
-parameter as const
, the compiler cannot even know that ss
is not changed in the loop and has to calculate strlen(ss)
in every iteration.
ss
not be changed in the for
loop; it must not be accessible from and changed by any function called in the loop (either because it is passed as an argument, or because it a global variable or a file-scope variable). Const-qualification may also be a factor, too.
Jul 6, 2012 at 15:25
restrict
is for in C99.
Jul 6, 2012 at 15:27
ss
in the for-loop, then even if its parameter is declared const char*
, the compiler still needs to recalculate the length unless either (a) it knows that ss
points to a const object, as opposed to just being a pointer-to-const, or (b) it can inline the function or otherwise see that it is read-only. Taking a const char*
parameter is not a promise not to modify the data pointed to, because it is valid to cast to char*
and modify provided that the object modified isn't const and isn't a string literal.
Jul 6, 2012 at 15:31
If ss
is of type const char *
and you're not casting away the const
ness within the loop the compiler might only call strlen
once, if optimizations are turned on. But this is certainly not behavior that can be counted upon.
You should save the strlen
result in a variable and use this variable in the loop. If you don't want to create an additional variable, depending on what you're doing, you may be ale to get away with reversing the loop to iterate backwards.
for( auto i = strlen(s); i > 0; --i ) {
// do whatever
// remember value of s[strlen(s)] is the terminating NULL character
}
strlen
at all. Just loop until you hit the end.
Jul 6, 2012 at 17:28
i > 0
? Should that not be i >= 0
here? Personally, I would also start at strlen(s) - 1
if iterating over the string backwards, then the terminating \0
needs no special consideration.
i >= 0
works only if you initialize to strlen(s) - 1
, but then if you have a string on zero length the initial value underflows
Jul 6, 2012 at 20:27
i > 0
expression on initial loop entry? If it doesn't, then you're right, the zero length case will definitely break the loop. If it does, you "simply" get a signed i
== -1 < 0 so no loop entry if the conditional is i >= 0
.
strlen
's return type is unsigned, so (strlen(s)-1) >= 0
evaluates to true for zero length strings.
Jul 6, 2012 at 20:34
Formally yes, strlen()
is expected to be called for every iteration.
Anyway I do not want to negate the possibility of the existance of some clever compiler optimisation, that will optimise away any successive call to strlen() after the first one.
The predicate code in it's entirety will be executed on every iteration of the for
loop. In order to memoize the result of the strlen(ss)
call the compiler would need to know that at least
strlen
was side effect freess
doesn't change for the duration of the loopThe compiler doesn't know either of these things and hence can't safely memoize the result of the first call
ss
into a size_t
or divide it up amongst several byte
values. My devious thread could then just write bytes into that address and the compiler would have know way of understanding that it related to ss
.
int a = 0; do_something(); printf("%d",a);
cannot be optimized, on the basis that do_something()
could do your uninitialized int thing, or could crawl back up the stack and modify a
deliberately. In point of fact, gcc 4.5 does optimize it to do_something(); printf("%d",0);
with -O3
Jul 6, 2012 at 16:09
Yes. strlen will be calculated everytime when i increases.
If you didn't change ss with in the loop means it won't affect logic otherwise it will affect.
It is safer to use following code.
int length = strlen(ss);
for ( int i = 0; i < length ; ++ i )
{
// blabla
}
Yes, the strlen(ss)
will calculate the length at each iteration. If you are increasing the ss
by some way and also increasing the i
; there would be infinite loop.
Yes, the strlen()
function is called every time the loop is evaluated.
If you want to improve the efficiency then always remember to save everything in local variables... It will take time but it's very useful ..
You can use code like below:
String str="ss";
int l = strlen(str);
for ( int i = 0; i < l ; i++ )
{
// blablabla
}
Not common nowadays but 20 years ago on 16 bit platforms, I'd recommend this:
for ( char* p = str; *p; p++ ) { /* ... */ }
Even if your compiler isn't very smart in optimization, the above code can result in good assembly code yet.
Yes. The test doesn't know that ss doesn't get changed inside the loop. If you know that it won't change then I would write:
int stringLength = strlen (ss);
for ( int i = 0; i < stringLength; ++ i )
{
// blabla
}
As of today (January 2018), and gcc 7.3 and clang 5.0, if you compile:
#include <string.h>
void bar(char c);
void foo(const char* __restrict__ ss)
{
for (int i = 0; i < strlen(ss); ++i)
{
bar(*ss);
}
}
So, we have:
ss
is a constant pointer.ss
is marked __restrict__
ss
(well, unless it violates the __restrict__
).and still, both compilers execute strlen()
every single iteration of that loop. Amazing.
This also means the allusions/wishful thinking of @Praetorian and @JaredPar doesn't pan out.
YES, in simple words.
And there is small no in rare condition in which compiler is wishing to, as an optimization step if it finds that there is no changes made in ss
at all. But in safe condition you should think it as YES. There are some situation like in multithreaded
and event driven program, it may get buggy if you consider it a NO.
Play safe as it is not going to improve the program complexity too much.
Yes.
strlen()
calculated everytime when i
increases and does not optimized.
Below code shows why the compiler should not optimize strlen()
.
for ( int i = 0; i < strlen(ss); ++i )
{
// Change ss string.
ss[i] = 'a'; // Compiler should not optimize strlen().
}
strlen
.
Jul 12, 2012 at 0:25
We can easily test it :
char nums[] = "0123456789";
size_t end;
int i;
for( i=0, end=strlen(nums); i<strlen(nums); i++ ) {
putchar( nums[i] );
num[--end] = 0;
}
Loop condition evaluates after each repetition, before restarting the loop .
Also be careful about the type you use to handle length of strings . it should be size_t
which has been defined as unsigned int
in stdio. comparing and casting it to int
might cause some serious vulnerability issue.
well, I noticed that someone is saying that it is optimized by default by any "clever" modern compiler. By the way look at results without optimization. I tried:
Minimal C code:
#include <stdio.h>
#include <string.h>
int main()
{
char *s="aaaa";
for (int i=0; i<strlen(s);i++)
printf ("a");
return 0;
}
My compiler: g++ (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3
Command for generation of assembly code: g++ -S -masm=intel test.cpp
Gotten assembly code at the output:
...
L3:
mov DWORD PTR [esp], 97
call putchar
add DWORD PTR [esp+40], 1
.L2:
THIS LOOP IS HERE
**<b>mov ebx, DWORD PTR [esp+40]
mov eax, DWORD PTR [esp+44]
mov DWORD PTR [esp+28], -1
mov edx, eax
mov eax, 0
mov ecx, DWORD PTR [esp+28]
mov edi, edx
repnz scasb</b>**
AS YOU CAN SEE it's done every time
mov eax, ecx
not eax
sub eax, 1
cmp ebx, eax
setb al
test al, al
jne .L3
mov eax, 0
.....
restrict
-qualified. While there are some cases where such optimization would be legitimate, the effort required to reliably identify such cases in the absence of restrict
would, by any reasonable measure, almost certainly exceed the benefit. If the string's address had a const restrict
qualifier, however, that would be sufficient in and of itself to justify the optimization without having to look at anything else.
Elaborating on Prætorian's answer I recommend the following:
for( auto i = strlen(s)-1; i > 0; --i ) {foo(s[i-1];}
auto
because you don't want to care about which type strlen returns. A C++11 compiler (e.g. gcc -std=c++0x
, not completely C++11 but auto types work) will do that for you.i = strlen(s)
becuase you want to compare to 0
(see below)i > 0
because comparison to 0 is (slightly) faster that comparison to any other number.disadvantage is that you have to use i-1
in order to access the string characters.
ss
inside the loop.ss
is never modified, it can hoist the computation out of the loop.