Steve Steve - 2 months ago 9
C++ Question

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?

UPDATE

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?


Answer

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.

Comments