CODEWITHSUNDEEP
javac++cfor-loop
SpiderRico
SpiderRico

Reputation: 2036

Does a for loop re-evaluate the functions in its body in each iteration?

When I write a simple for loop like this

for (int i = 0; i < myList.size(); i++){}

in Java, C and C++, does it reevaluates myList.size() in each iteration or just for once at the beginning of the loop? If it reevaluates, does preevaluating size, i.e.,

int n = myList.size();
for (int i = 0; i < n; i++){}

gives us something significant in terms of performance?

Upvotes: 5

Views: 3470

Answers (6)

DanielHsH
DanielHsH

Reputation: 4453

I am familiar with C/C++ only, and the correct answer is: Sometimes it is evaluated and sometimes it is not. The compiler guarantee that it will evaluate in every iteration an assembly code which it THINKS IS EQUIVALENT to your original code (but not really what you intended). If you compile the code in debug mode (no compiler optimizations) or your variable has keyword volatile in its definition or you change the size of the list then the condition (size of list) will be indeed evaluated every iteration. If however you compile with speed optimization, don't change the list in a loop then modern compilers are smart enough to store the size of the list in a register and not evaluate it every iteration. Moreover, the function list.size() will be inlined and will not actually invoke the costly function call.

Note that in multi-threading programming this is disastrous. One thread may append elements to the list while the other thread which iterates over the list will never see the new elements. To force evaluation the size of list must be defined as volatile (or you can use memory barriers if you are familiar with assembly). Anyways, when you compile your application for production be sure to enable compiler optimizations and the run time penalty of alleged function call in each iteration will be nullified.

Another issue: Some very aggressive compiler optimizations may even unroll your loop. For example if your list has a size of 403 elements the compiler may perform 100 iterations each having your in-loop code repeated 4 times + 3 iterations of another loop with your original code. So there will be total 103 iteration and not 403 (so it is impossible to argue whether code is executed in each iteration because its hard to define what is iteration). Example of such aggressive optimizations: copying long strings or memory buffers. If you copy X bytes, on 64 bits machine it is actually faster to do X/8 iterations (copying 64bits at once) + a remaining 0..7 bytes in a separate loop. There are some processors which even support units of 128 and up to 512 bytes in a single operations

Last advise: It is very important to write an easy to understand code, so in this case I would use good suggestions in the answers above (about java list iterators) or deliberately save list.size() into temporal variable

const in list_size = list.size()

Just for easier readability/debugging

Upvotes: 1

dbush
dbush

Reputation: 223992

In both C and C++, the controlling expression is evaluated on each iteration of the loop.

From section 6.8.5.3 of the C standard:

The statement

for (clause-1; expression-2; expression-3) statement

behaves as follows: The expression expression-2 is the controlling expression that is evaluated before each execution of the loop body. The expression expression-3 is evaluated as a void expression after each execution of the loop body. If clause-1 is a declaration, the scope of any identifiers it declares is the remainder of the declaration and the entire loop, including the other two expressions; it is reached in the order of execution before the first evaluation of the controlling expression. If clause-1 is an expression, it is evaluated as a void expression before the first evaluation of the controlling expression.

Section 6.5.3 of the C++ standard contains similar verbiage.

So if your controlling expression involves a function call or some other potentially expensive computation that won't change in the loop body, you should evaluate it beforehand, store it in a variable, then use that variable in the controlling expression.

Upvotes: 7

GhostCat
GhostCat

Reputation: 140457

For Java:

for (int i=0; i<myList.size(); i++){}

The condition is evaluated during each loop iteration; so there is a slight performance gain by moving that call to size() in front of the loop.

But in Java you should prefer the for-each

for (Whatever thingy : list)

notation anyway (where possible).

You can read about in the Java language spec, chapter 14.14.1.

Upvotes: 9

Thomas Matthews
Thomas Matthews

Reputation: 57718

In C and C++ there is no requirement in the standard to optimize the function call (e.g. only call once).

The compiler's optimization engine needs to know the return type of the size and whether or not the value will changed. A difficult undertaking.

If you want the function to be called once, assign the result to a constant variable before the loop: 

const size_t size = myList.size();
for (size_t i = 0; i < size; ++i)
{
  // ...
}

All guarantees of off if the myList is changed within the loop. The function size will need to be called for every iteration.

Upvotes: 2

Shridhar.S
Shridhar.S

Reputation: 112

Depends on whether myList is being modified inside the for-loop. Also, the compiler (especially in C) tries to optimize such code by moving the evaluation outside the loop. The optimization is also based on whether the object is modified inside the loop or not.

Upvotes: 2

joews
joews

Reputation: 30330

Logically the condition is evaluated on each iteration.

You can tell this from looking at your example, because the value of i in the expression changes each time.

In practice it could be language or implementation dependent. The compiler or runtime may be able to cache or optimise parts of the expression. You can't necessarily tell from looking at the code in isolation.

Upvotes: 3

Related Questions