Saturday, June 16, 2007

Which "for loop" works better/faster

I was asked this question in an interview long ago and thought I would post it here.
Which of the following for loop works better assuming no special compiler play, just on programming logic. Will both code pieces execute equally fast?

1 -
for ( i=0; i <10; i++)
for (j=0; j<100; j++)

2 -
for (j=0; j<100; j++)
for ( i=0; i <10; i++)


Tair said...

OK, visually loops are same, but if one counts the total number of operator= executed in first loop...

Curtis said...

Gut feeling says #1 because branch prediction will make a mistake only 1/10th as often.

However, the difference is negligible because execution time would be dominated by the I/O.

TemporalBeing said...

Simple. The first one. Why?

Think about how the program runs. As others have pointed out per the thing of the operator= and branch predictions. But there is a simpler method to evaluate it.

Think of how often the the sets of loops will need to run. Where are you going to spend 80% of your time?

Since the 'j' loop runs 100 times, and the 'i' loop 10 times; the 'j' loop is the bigger loop to make efficient.

Think about it:

Loop #1:
i run from 0 to 9, and resets J, which runs from 0 to 99.

Loop #2:
j run from 0 to 99, and resets i, which runs 0 to 9.

Loop #2 will reset the variables many more times than Loop #1. Thus, Loop #1 is the better method. Coincidentally, this will also make your branch-predictions better for the CPU, and give you the optimizations for the operator= as other suggested.