Better For Loop Construct

The common way of coding an for statement is as follows:

 for (int i=0;i<upperbound;i++) {
   ... do something
 }

When you know upperbound is invariant, sometimes a different idiom can speed this loop up a little.

• calculate upperbound once

• count down

calculate upperbound once

In the vast majority of cases, upperbound is an invariant value obtained though some function call such as array.length, string.length() or arraylist.size().

Most compilers are so dumb that they call that function on every iteration, just in case it has changed.

Don't know about Java, but C/C++ compilers are prohibited (in general) from optimizing out such function calls; as there is no way for the compiler to know whether or not the function has SideEffects or depends on external state (and might return different values on successive calls). [in the case of java strings and arrays, strings are immutable, and arrays are fixed-size, so the compiler can confidently hoist the upperbound calculation out of the loop (the same holds for strings and arrays in .net languages, too, although in c# I'd just use a foreach, since the compiler will produce IL exactly equivalent to the for loop)]

Most of the time,the programmer knows it is an invariant. (Sometimes a really smart compiler will also figure this out).

When upperbound really is invariant, the following syntax causes the invariant upperbound value to be calculated once.

 for(int i=0,iMax=upperbound;i<iMax;i++) {
   ... do something
 }

-- StevePritchard

Is the gain significant? What should be indicated is whether or not the upperbound needs to be recalculated.

The significance of the gain is a function of what is the cost of calculating the upperbound and how many times we will go through the loop. For array.length it would eliminate a dereference. For string.length() and arraylist.size() it would eliminate a function call and dereference. In other cases it could involve an expensive function call. The main point is that since there is no penalty for using this construct in simple variable cases, acquiring the habit to use it in all cases improves performance for the situations where it really matters.

-- StevePritchard

True. But setting iMax in a separate line makes it easier to add a comment as to why you're doing it. Though it needn't apply in this case, it can be handy to group critical variables together just to make it slightly easier to check their values make sense while you're verifying all is well.

Count down

(sometimes called "counting backwards")

 for( int i=upperbound; i--; ) {
     ... do something ...
 }

 for( int i=upperbound; 0 != i--; ) {
     ... do something ...
 }

This is a common idiom for (former?) assembly language programmers, because it makes the executable code smaller and faster in most assembly languages (what about Java bytecode?). 68000 assembly language has dedicated instructions for counting down - dbcc = "Decrement and Branch if this doesn't carry, unless (Condition Code)" - though these are relatively slow. DSP processors often have "zero-overhead looping".

Besides ReduceUnimportantInformation, this has the additional benefit of making the conditional-expression more efficient, as the test for zero is automatic with the decrement. The assembler can jz immediately after dec i.

If upperbound is some parameter value to the function or other variable that you won't need after the loop, you can use that variable name directly instead of declaring the new variable i.

A common idiom for string parsing functions that are given the length of the string as a parameter, such as memcpy() or substring(), as upperbound is typically the length of the string. This has much greater parsimony than the normal for triple-expression, and I think it's consequently more readable since I'm used to the idiom. Then again, I recall losing a mark on an exam because the TA thought I was off-by-one. -- SunirShah?

I gather this idiom is indeed too confusing. I recommend sticking with for( int i = 0; i < upperbound; i++ ). -- SunirShah?

There seem to be two quite separate issues - avoidance of unnecessary recalculation, and efficient loop construction.

The original is certainly not too confusing if explained with a comment.

If it needs a comment, it's too confusing.

Do you remember seeing code like ... ?

 mov ax, 3      ; ax = 3
 dec ax         ; decrement ax
 imul bx        ; ax *= bx

What's wrong with commenting a for loop expression?

 // for (upperbound-1) .. 0 by -1
 while( upperbound-- ) {
     ... do something ...
 }

Why not just write SelfDocumentingCode?

 for( int i = 0; i < upperbound; i++ ) {
     ... do something ...
 }

Or one could argue that programmers who aren't familiar with (or at least unable to understand) while( upperbound-- ) are in over their heads. Depends on your perspective and your coworkers. By the way, the "SelfDocumentingCode" has a higher probability of having bugs than the parsimonious while loop. Trust me on that one; I've measured it a few times privately. -- SunirShah?

It's fine if you don't believe me. It's not an important claim. -- SunirShah?

I would be curious to see the measurements and analysis. Can it be provided?

Very few C/C++ programmers really understand the difference between "upperbound--" and "--upperbound." Also, it is confusing to have an implied test rather than an explicit test for zero. Finally, it is also confusing if the test variable is decremented before the code it is controlling. It is better to stick with the more common for loop that most programmers know and recognize than to throw in constructs to cause programmers to "be in over their heads." -- WayneMack

Or maybe the vast army of C/C++ programmers are really Pascal programmers in costume. Or maybe almost all programmers are Pascal programmers searching for a Pascal. Doesn't that mean we should all be using Delphi? -- SunirShah?

While the first advice is good advice (hoisting invariant expressions out of the loop that the compiler is not allowed to hoist itself), this second section smells like OutsmartingTheCompiler. Advice as to whether incrementing or decrementing is faster, or pre- or post-increments, etc. is very hardware specific in general. Unless a) you are doing the inner loop of a weather simulation, b) you know the dirty details of the supercomputer you are running on, and c) profiling has demonstrated that the compiler's loop optimization is inadequate, don't do this!. It's PrematureOptimization. It makes the code less understandable to the reader. And unlike the first case, where the compiler often cannot help you - in this case the compiler usually can help you, and will do a better job with the loop than you will.

That sounds as though a whole article could be written on the topic of optimal string-handling on the PC... takes me back to when I knew about such matters for the DEC PDP10! (It had pointers to "characters" within a "string", where the number of bits per character was specified.)

for each - focus on making programs easier to *write*, not HelpingTheCompiler

A lot of this page seems like PrematureOptimization to me.

I think that a "BetterForLoopConstruct" would be...

  For Each oItem In oCollection
    // Body of loop
  Next oItem

 oCollection do: [ :oItem | "body goes here" ].

In Java, [] would translate to an anonymous inner class with one method. [] is a function literal or block. In JavaScript, for a syntax example, it would look like this.

aList.Do(function(anItem){"body here"});

Using the word function is basically declaring an inline function with no name, more importantly, it's body has access to all variables in the scope of where it was defined, this is called LexicalScope. I think smalltalk got it right by having a special syntax for literal functions, make writing them more idiomatic.

Another way to do it in Java is to use the new (in Java 1.5.0? or before?) for-each construct:

// Returns the sum of the elements of array a int sum(int[] a) {

    int result = 0;
    for (int i : a)
        result += i;
    return result;

(blatantly plagiarized from http://java.sun.com/j2se/1.5.0/docs/guide/language/foreach.html)

Interestingly, the literal Smalltalk translation of the "for"-loop is

  0 to: upperbound do: [:i | i doSomething]

Suppose the upperbound isn't invariant? Suppose it shrinks and we're testing for the intersection between it and i?

If the size of the collection is changing in size as you process it, you have a very complicated problem and any defined looping method will not handle all cases. There is a limited set of changes that can be applied even with the upper bound being re-evaluated each pass.

• 'do something' compiles into about 10 or fewer machine instructions and when profiled they occupy a significant fraction of the compute time and the process is compute bound.
• the function call obtain upper bound is something significant like strlen()

Notes:

even the STL's vector's V.end(); operation is not good in the conditional of a for loop IFF the loop is very short and calls no other functions, and ...

Array-based languages like JayLanguage and AplLanguage have the BetterForLoopConstruct because it's the only construct. -- SunirShah?

Why hasn't anyone suggested the use of iterators as opposed to indices within the for construct? The advantages of iterators are that the evaluation is often directly based on the data, not an abstract size, and the resulting value can be used directly, no index table look-up. I have found this eliminates any question of off by 1 looping errors and eliminates some obscure array size calculations (for example sizeof(array)/sizeof(element)). In three years of using this approach, I haven't found a for loop that could not be written with iterators as opposed to indices. Examples may exist, but I believe they occur very rarely in practice. -- WayneMack

In Java, for loops are more efficient than iterators. Also, I've written so many for loops over collections that off by 1 errors don't arise. Finally, I sometimes need to treat certain elements differently, according to index, and with iterators I'd need an additional variable.

std::for_each, anyone? [Available to C++ programmers only, your mileage may vary, void where prohibited by law.]

and for the BearSkinsAndStoneKnives contingent:

  while(count--) {
    *dst++ = f(*src++);
  }

   (map nil #'do-something my-sequence)

   (loop for x across my-vector do (something))

A quick test in C++:

    #include <vector>
    #include <string>
    #include <cstdlib>

    int sumArray(const std::vector<int> &vec)
    {
      int sum = 0;
      for (int i = 0; i < vec.size(); i++)
        sum += vec[i];
      return sum;
    }

    int sumArrayEfficiently(const std::vector<int> &vec)
    {
      int sum = 0;
      int upperBound = vec.size();
      for (int i = 0; i < upperBound; i++)
        sum += vec[i];
      return sum;
    }

    int sumArrayWithIterator(const std::vector<int> &vec)
    {
      int sum = 0;
      for (std::vector<int>::const_iterator i = vec.begin();
           i != vec.end();
           ++i)
        sum += *i;
      return sum;
    }

    int sumArrayCountDown(const std::vector<int> &vec)
    {
      int sum = 0;
      for (int i = vec.size(); i--; )
        sum += vec[i];
      return sum;
    }


    int sumArrayCountDown2(const std::vector<int> &vec)
    {
      int sum = 0;
      for (int i = vec.size(); i-->0; )
        sum += vec[i];
      return sum;
    }

    const int iterations = 100000;

    int main(int argc, char *argv[])
    {
      std::string flag = argv[1];
      std::vector<int> vec(100);
      for (int i = 0; i < vec.size(); i++)
        vec[i] = rand();

      if (flag == "-1")
        for (int i = 0; i < iterations; i++)
            sumArray(vec);
      if (flag == "-2")
        for (int i = 0; i < iterations; i++)
            sumArrayEfficiently(vec);
      if (flag == "-3")
          for (int i = 0; i < iterations; i++)
              sumArrayWithIterator(vec);
      if (flag == "-4")
          for (int i = 0; i < iterations; i++)
              sumArrayCountDown(vec);
      if (flag == "-5")
          for (int i = 0; i < iterations; i++)
              sumArrayCountDown2(vec);
    }

  time ./test -1  # sumArray

  real    0m0.082s
  user    0m0.080s
  sys     0m0.000s

  time ./test -2 # sumArrayEfficiently

  real    0m0.066s
  user    0m0.070s
  sys     0m0.000s

  time ./test -3 # sumArrayWithIterator

  real    0m0.066s
  user    0m0.060s
  sys     0m0.000s

  time ./test -4 # sumArrayCountDown

  [Not yet tested]

  time ./test -5 # sumArrayCountDown

  [Not yet tested]

"pretty" code "i-->0" from CatchDontCheckRefuted added to the above test as "sumArrayCountDown2()".

Do we really need to drag C obfuscation into this discussion? Why would anyone want to strip the whitespace out of what was a clear expression in order to simulate a non-existent syntax? A writer should not make code unclear to future readers just because the writer thinks it looks cool.

Care to test also this? Surely it expresses the programmer’s intention (to have a sum of all the elements of the array) most clearly. (Of course, inside it should look very much like sumArrayWithIterator… though this one evaluates end() OnceAndOnlyOnce.)

    inline int sumArrayWithAlgorithm(const std::vector<int>& vec)
    {
      return std::accumulate(vec.begin(), vec.end(), 0);
    }

    int sumListWithIndex(const std::list<int>& list)
    {
      int sum = 0;
      for (size_t i = 0; i < list.size(); ++i)
      {
        sum += list[i]; // Warning! [] has linear time complexity
      }
      return sum;
    }

    int sumListWithIterator(const std::list<int>& list)
    {
      int sum = 0;
      for (std::list<int>::const_iterator i = list.begin(), e = list.end(); i != e; ++i)
      {
        sum += *i;
      }
      return sum;
    }

    // almost equivalent to sumListWithIterator internally
    // but uses sum = sum + *i
    int sumListWithAlgorithm(const std::list<int>& list)
    {
      return std::accumulate(list.begin(), list.end(), 0);
    }

    // should be exactly equivalent to sumListWithIterator
    // not sure about the syntax, though…
    int sumListWithBoostLambda(const std::list<int>& list)
    {
      using boost::lambda::_1;

      int sum = 0;
      std::for_each(list.begin(), list.end(), sum += _1);
      return sum;
    }

I really dig the way BASIC does it (minus goofy block ending conventions):

  for x = 3 to 50 step 2 {....}

  for x = 3 to 50 step 2
    ....
  endfor

  <cfloop from=3 to=50 step=2 index=x>...</cfloop>

  for x = 3 to 50 step 2
    ....
    If Not(Condition) leave
    ....
    If (Condition) leave
    ....
  endfor

  for x = 3 to 50 step 2
    ....
  Until Condition
    ....
  While Condition
    ....  
  endfor

  element *end = array+n;
  int i = -n;
  do {
    /* Do stuff with end[i] */
  } while (++i);

See UseEnumerationsNotForLoops, RefactorMatchLoopToUsage

This page mirrored in JavaIdioms as of April 29, 2006