CODEWITHSUNDEEP
c++performanceloopsnested-loops
Wallace
Wallace

Reputation: 651

Is a big loop within a small loop always faster than a small loop within a big one?

I just read this post, and wonder if we can draw the conclusion that a big loop within a small loop must always run faster than a small loop within a big one, no matter what the code does inside the nested loop? Take an example.

int m, n; 
m = 1000000;
n = 10;

Snippet A

for (int i = 0; i < n; i++)         
    for (int j=0; j < m; j++)               
       {       
           DoSomething();        
       }

Snippet B

for (int j = 0; j < m; j++)               
    for (int i=0; i < n; i++)           
       {       
          DoSomething();          
       }

Can we say that, no matter what DoSomething() actually does, snippet A always runs faster thant snippet B?

As pointed out by @stackmate, I want to expand this question into two

  1. When the code inside nested loop is DoSomething() which means DoSomething() has nothing to do with variable i and j. What is the performance difference?

  2. When the code inside nested loop is DoSomething(i, j) which means DoSomething(i, j) has relateship with variable i and j. What is the performance difference?

Upvotes: 10

Views: 13001

Answers (7)

Frank
Frank

Reputation: 2230

I think there's a good deal of optimization going on here. Check out this jsben.ch: https://jsben.ch/FjXuL

var big = 10000;
var little = 10;

var x = 0;

// Little loop in Big loop
for (var i = 0; i < big; i++) for (var j=0; j < little; j++) { x++; }

// Big loop in Little loop
for (var i = 0; i < little; i++) for (var j=0; j < big; j++) { x++; }

// Little loop in Big loop (single initializations)
var j;

for (var i = 0; i < big; i++) for (j=0; j < little; j++) { x++; }

// Big loop in Little loop (single initializations)
var j;

for (var i = 0; i < little; i++) for (j=0; j < big; j++) { x++; }

When tested individually, Little loop in Big loop always comes out ahead in Chrome. Declaring j outside of the first loop in the "single initialization" tests doesn't seem to help - and actually slows down the Little loop in Big loop (single initialization) test significantly.

That being said, results could vary greatly by browser implementation / compiler.

I think it makes logical sense that nesting the bigger loop would be advantageous because you would be initializing the nested j variable less times, but apparently in Chrome this isn't a big factor in performance because nesting the smaller loop is faster.

Upvotes: 0

Vaibhav Jain
Vaibhav Jain

Reputation: 2407

for(int i = 0; i < 1000; i++)
{
        for(int j = 0;

in above code if you see we are initializing j 1000 times. 

for(int i = 0; i < 1000000; i++)
{
    for(int j = 0;

while in this second code we are initializing j 1000000 times which clearly shows that second code has extra overhead.

Upvotes: 0

Eugen
Eugen

Reputation: 2820

An observation. If you have read operations inside the nested loop like the following

for (int i = 0; i < n; i++)
    a = aList.get(i);         
    for (int j=0; j < m; j++)               
       {   
           b = bList.get(j)
           DoSomething(a, b);        
       }

then having n < m results in less someList.get-operations than n > m. With n=1 and m=2 there will be three read operations while with n=2 and m=1 there will be four read operations. In the case n > m there will be more repititive read operations. Or put another way the runtime is n + n*m. The value n*m stays the same whether n > m or n < m but the first addend changes.

(I assumed no compiler optimizations and ignored caching behavior)

Upvotes: 1

user3451749
user3451749

Reputation:

In Snippet A: n=10 times switch to outer For loop But in Snippet B: m=1000000 times switch to outer For loop. And this reason (More switches between two For loop) makes to Snippet A is faster than Snippet B.

Upvotes: 0

Reto Koradi
Reto Koradi

Reputation: 54602

@Cool_Coder already covered one main reason (memory access patterns resulting in better cache hit rates) why having the smaller loop as the inside loop can be beneficial.

Another scenario is that the inner loop could be unrolled. Particularly if the size of the smaller loop is really small and fixed, the compiler will unroll the inner loop if it's beneficial. The resulting code will then have only one loop instead of two nested loops, with a reduction in branches.

If you have a situation like this in highly performance critical code, you need to try both, and benchmark carefully. If the code is not very performance critical, it's probably not worth worrying about.

Upvotes: 2

Cool_Coder
Cool_Coder

Reputation: 5073

There cannot be a specific answer to your question. The parameter deciding whether it will be fast or not is what you are doing inside the loops. For example say you are adding 2 arrays and storing them in a third array:

Code 1:
for(int i = 0; i < 1000; i++)
{
    for(int j = 0; j < 1000000; j++)
         C[i][j] = A[i][j] + B[i][j];
}

Code 2:
for(int i = 0; i < 1000000; i++)
{
    for(int j = 0; j < 1000; j++)
         C[j][i] = A[j][i] + B[j][i];
}

Code 1 will be much faster than code 2. The reason is cache. Take a look at this question for more details. The answers are superbly informative and there is no point in me explaining the concept of cache again over here.

Upvotes: 9

AlexanderBrevig
AlexanderBrevig

Reputation: 1987

It depends.

If you do anything other between the for loops then the one iterating m first will take longer to execute, simply because it does more work because of that extra added work before entering the next loop.

If not, then

n * m = m * n

Andy T's comment is also correct. When you have the outer loop be the longest one, then the initialization of the inner loop happens more often. If this is c++ though, I'd expect the compiler to optimize this away so that benchmarking your code would probably yield the same result for both loops.

Upvotes: 0

Related Questions