25

I have read that use of strlen is more expensive than such testing like this:

We have a string x 100 characters long.

I think that

for (int i = 0; i < strlen(x); i++)

is more expensive than this code:

for (int i = 0; x[i] != '\0'; i++)

Is it true? Maybe the second code will not work in some situation so is it better to use the first?

Will it be better with the below?

for (char *tempptr = x; *tempptr != '\0'; tempptr++)
Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138

8 Answers8

43
for (int i=0;i<strlen(x);i++)

This code is calling strlen(x) every iteration. So if x is length 100, strlen(x) will be called 100 times. This is very expensive. Also, strlen(x) is also iterating over x every time in the same way that your for loop does. This makes it O(n^2) complexity.

for (int i=0;x[i]!='\0';i++)

This code calls no functions, so will be much quicker than the previous example. Since it iterates through the loop only once, it is O(n) complexity.

MatthewD
  • 2,509
  • 2
  • 23
  • 27
  • Although there is nothing incorrect in the answer, again there is no point comparing the two versions as they are not two different versions of the same algorithm. They are just two sample codes doing different things – Gregory Pakosz Aug 02 '10 at 13:31
  • They both add 1 to `i` for each character in the string. Beyond that it's a bit hard to tell, since the code inside the loop hasn't been provided. – MatthewD Aug 02 '10 at 13:38
  • + 1 for pointing out that `strlen()` is being called each time the FOR-loop is executed, when it's returning the same value all the times. – apaderno Aug 02 '10 at 13:41
  • 1
    These methods may have a different result if the length of the string is changing during iteration, otherwise they are doing the same thing. – UncleBens Aug 02 '10 at 13:46
  • 8
    Most compilers (including gcc) are smart enough to cache the result of strlen, so performance will be pretty much the same for both loops. – Paul R Aug 02 '10 at 13:48
  • 3
    @Paul R: The second will still be faster, as strlen iterates once, then the OP iterates again in his loop, whereas in the second loop there is just one iteration. However, on the scale of things, it's a pretty micro optimization. – Puppy Aug 02 '10 at 21:37
  • 2
    @PaulR Are you sure that GCC would do that in all cases? It doesn't have any way of knowing what will happen when using multiple threads and a global string; another thread could modify the string while it's looping. Or maybe it doesn't do the optimization if you're using a global string. – sudo Jan 27 '14 at 22:04
  • Thumbs++ for showing me a new way to loop through C strings. – DeepDeadpool Nov 02 '15 at 19:49
  • 1
    @PaulR What about I change the string during the loop? strlen does not guarantee to be a const. – maplemaple Jul 09 '21 at 01:16
12

The first code checks length of x in every iteration of i and it takes O(n) to find the last 0, so it takes O(n^2), the second case is O(n)

Artyom
  • 31,019
  • 21
  • 127
  • 215
  • so people are happily voting up because O(n^2) > O(n) ? ;) – Gregory Pakosz Aug 02 '10 at 13:22
  • @Gregory Pakosz please they help me because i dont know well difference between them so why so angry ?i am happy because they help me not because of upvoting –  Aug 02 '10 at 13:25
  • I'm not angry, I'm helping you by making you realize your question is not a real question and therefore this isn't a "real answer" although there's nothing wrong at all in what @Artyom said – Gregory Pakosz Aug 02 '10 at 13:29
5

Yes your second may not work 100% percent of the time but it would be slighty quite. This is because when using strlen() you have to call the method each time. A better way would be like so

int strLength = strlen(x);
for (int i = 0; i < strLength; i++)

Hope this helps.

Ash Burlaczenko
  • 24,778
  • 15
  • 68
  • 99
  • 1
    Fascinating. What is the scenario you have in mind in which the second version doesn't work but the first does? (Assuming the elided loop contents contain no further modifications of `i` or the string.) – John Marshall Aug 02 '10 at 13:27
  • for example take string " world is best" what about ' '? –  Aug 02 '10 at 13:31
  • 1
    @davit: `' '` is a space, not a null character – Nathan Fellman Aug 02 '10 at 21:44
  • @mb14: Reread the assumption stated in my comment. Considering that Ash's suggestion also differs from the OP's first version when the body of the loop changes the length of the string, one assumes that he had something else in mind by "your second may not work 100% percent of the time". (Really all bets are off due to the omitted loop contents... but the question is only interesting if the loop does not modify the string or further modify `i`, so I think it's not unreasonable to assume for the purposes of discussion that that is the case.) – John Marshall Aug 03 '10 at 15:11
  • There could be a separate thread modifying the string contents. – sudo Jan 27 '14 at 21:59
3

I can suppose that in first variant you find strlen each iteration, while in second variant you don't do that.
Try this to check: 

int a = strlen(x); 
for (int i = 0; i < a; i++) {...}
apaderno
  • 28,547
  • 16
  • 75
  • 90
foret
  • 728
  • 6
  • 14
  • Good because it does not trust the compiler, and can therefore be leveraged by other programmers. Assumes we will always want the strict string length, whereas we might use complementary span to scope to EOL or other sentinel values. Coming up on 10 years so it must have a few views. – mckenzm Oct 01 '19 at 23:55
2

If no there's no compilation optimization. Yes because strlen will iterate on every byte of the string every time and the second implementation will do it only once.

Eric Fortin
  • 7,533
  • 2
  • 25
  • 33
2

I guess the compiler could optimize (check Gregory Pakosz comment) your first for loop so that you would be like this:

int len = strlen(x);
for (int i = 0; i < len; i++)

Which is still O(n).

Anyway, I think your second for loop will be faster.

  • 3
    The compiler can't move the strlen() call out of the loop unless it knows that strlen() has no side effects and that the length of the string cannot change inside the loop. – JeremyP Aug 02 '10 at 13:17
  • 2
    actually GCC can optimize `strlen` out of the loop because it's recognized as a built-in function, see http://ridiculousfish.com/blog/archives/2010/07/23/will-it-optimize/ – Gregory Pakosz Aug 02 '10 at 13:20
  • But it's not `2*O(n)`, it's `O(n**2)`. It runs an O(n) each iteration for n iterations. – Dave McClelland Aug 02 '10 at 13:22
  • 2
    @Dave McClelland Uh, no? If the strlen is optimized out of the loop, it's run once, so it just does that O(n) operation, and then the loop, another O(n) operation, since it's just doing a comparison, now. Did you actually read the answer? – Colin DeClue Aug 02 '10 at 13:26
0

It's worth noting that you may be opening yourself up to buffer overflow problems if you don't also test the index against the size of the buffer containing the string. Depending on what you're doing with this code, this may or may not be a practical issue, but it rarely hurts to have extra checks, and it's a good habit to get into.

I'd suggest: for (i = 0; i < buf_size && x[i] != '\0'; i++)

Where:

  • buf_size is the predetermined size of the buffer. If x is an array, this will be sizeof(x); if x is a pointer, you should have the buffer size available.
  • I've removed the declaration of i from the loop because it's only valid c99. If you're only compiling under c99, feel free to put it back in.
Thom Smith
  • 13,916
  • 6
  • 45
  • 91
-1

Of course the first one will take longer than the second. They don't actually do the same thing at all--the first one is calculating the length of the string each time; the second one is (effectively) doing it only once.

The first version is equivalent to this:

for (int i=0; x[i] != 0; i++)
  for (int j=0; j<i; j++)
    ;

Maybe you meant to say "is it more efficient to call a library strlen() than to implement my own?" The answer to that is, of course, "it depends". Your compiler may have intrinsic versions of strlen() that are optimized beyond what you would expect from source, you may be on a platform on which function calls are expensive (rare nowadays), etc.

The only answer that's both general and correct is "profile and find out".

Tim Lesher
  • 6,341
  • 2
  • 28
  • 42