Home

loop

2010/07/16

for (i = 0; i < strlen(string); i++) {
  :
}

This is a C version of a loop that I recently bumped into while copy-pasting some code. In the above loop strlen(string) is called strlen(string) times instead of just once (unless the length of string changes while in the loop):

int len;
:
len = strlen(string);
for (i = 0; i < len; i++) {
  :
}

Unless the compiler detects this and optimizes the loop, this is very bad practice. Yes, most of the compilers do detect this, but this does not mean that the programmer must rely on the compiler's optimizations. What if it does not get optimized in the end?

This is not a rant about wasted CPU cycles. It is mostly a rant about laziness in our thinking.

The Slow Loop

Advertisements

8 Responses to “loop”


  1. If the first code snippet does not work as fast as the second one, it is a compiler problem. A programmer should work around it only if it is crucial for the performance of its program, otherwise the first one is more readable.

    Every decent compiler should “cache” the results of a function which gets called with a specific argument many times, at least when this function does not have side effects (like strlen).

    PS: Plus, I don’t like assignments. If you insist on the second one, it should be imho:
    int len = strlen(string);
    // …

  2. Michael Iatrou Says:

    One should adapt his coding idioms to the specific of the language and the environment of it (compiler, debug tools etc) but also to general aesthetics. Regarding the latter, the first version is much more elagant and compact. Furthermore, optimizing this loop is trivial for a C compiler. Maybe it is laziness but in this case it feels like the first version is the right thing to do.

    On the other hand, if we were talking about e.g. PHP which is notorious for not optimizing the specific loop, I would have to completely agree with you.

  3. adamo Says:

    The original loop was in Java and called string.length(). According to my Java goto guy, it does not always get optimized. I chose the example to be in C, because when I started programming in C (1990) such optimizations were not obvious, and are not even today in some embedded systems, with processors and whole systems being obsoleted in ~1 year after initial deployment (I happened into such a case last year, and it was on an educational ARM board).


  4. It’s a bit sad that we don’t have compilers “smart enough” to optimize the first version.

    Seeing that the body of the block-statement is empty, this seems equivalent to i = strlen(string). If the text of the string is actually used through string[i], then it might be nice to have “smart enough” compilers to find the loop invariant.

    Then there are cases where actually thinking a bit about the effects of the loop is a very good idea. The classic example of a tiny loop that may benefit a lot from a bit of thinking is the initialization of an array with a randomized copy of the numeric sequence [0 .. (n-1)]:

    #include <stdio.h>
    #include <stdlib.h>
     
    #define SIZE 10
    
    int
    main(void)
    {
        size_t j, k, vsize;
        int *vec;
     
        vsize = SIZE;
        vec = malloc(vsize * sizeof(*vec));
        for (j = 0; j < vsize; j++) 
            vec[j] = j;
     
        /* Randomization loop with a few non-obvious properties. */
        srand(0);
        for (j = 0; j < vsize; j++) {
            int tmp;
     
            k = rand() % vsize;
            tmp = vec[j];
            vec[j] = vec[k];
            vec[k] = tmp;
        }
    
        for (j = 0; j < vsize; j++)
            (void)printf("%d", vec[j]);
        putchar('\n');
        (void)fflush(stdout);
        return EXIT_SUCCESS;
    }
    
    

    The code looks straight-forward and easy to read. There are a few gotchas hidden in there though, e.g.:

    – Is the number of swaps done to vec[n] for each n in [0.. (vsize-1)] “normalized” for the entire set of indexes?

    – Is there a better way to write the loop so that each vec[n] for n in [0..(vsize-1)] swapped exactly *once* with another index?

    – Is it better to use arc4random() instead of srand() and rand()?

    My understanding so far is that we can definitely strive for better compilers and smarter ones at that, but we also have to actually think about all the characteristics of the code we are writing. So the best of both worlds lies somewhere in the middle, gray area between the two extremes: super-smart compilers that think for us before we do, and having to manually specify every tiny detail of our programs in excruciatingly painful detail.

    • Michael Iatrou Says:

      My interpretation of the original code is that ‘string’ has actually ‘const char *string’ semantics. And this is exactly the case where you expect the compiler to optimize version 1.

      Of course, if the hardware platform/compiler/project has a one year expiration date, one would assume that the least of your problems is this type of coding mannerisms and compiler optimizations.

      I don’t believe that the questions Giorgos arises can be answered in a general context. For example, is this code part of a Monte Carlo simulator or a cryptographic application ? Depending on the answer rand() can be acceptable or plain disaster.


  5. […] This post was mentioned on Twitter by Yiorgos Adamopoulos, Giorgos Keramidas. Giorgos Keramidas said: It's simple but not as simple as it seems RT @hakmem loop http://ff.im/-nLLXj […]

  6. Greek Warrior Says:

    Ah, the good old times…
    Why use strlen, and integer i, in the first place? The real C programmers do it with pointers.

    for (s=string; s; s++) {
    }


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: