efficiency and nested loops

[Luna Moon]

My friend has three nested loops, each has 10000, 1000, 100
iterations, respectively.

What should be the most efficient way of layout out the three nested
loops?

for (i=0; i<10000; i++)
for (j=0; j<1000; j++)
for (k=0; k<100; k++)
{

do something;
}
or

for (k=0; k<100; k++)
for (j=0; j<1000; j++)
for (i=0; i<10000; i++)
{

do something;
}

???

[jg.campbell.ng]

On Sep 10, 5:42 pm, Luna Moon <[e-mail]:

My friend has three nested loops, each has 10000, 1000, 100
iterations, respectively.

What should be the most efficient way of layout out the three nested
loops?

for (i=0; i<10000; i++)
for (j=0; j<1000; j++)
for (k=0; k<100; k++)
{

do something;
}

or

for (k=0; k<100; k++)
for (j=0; j<1000; j++)
for (i=0; i<10000; i++)
{

do something;
}

???

Depends on what 'do something' is. If you are iterating through a 3D
array (volume) then you may gain performance by ensuring that the
innermost loop traverses memory with least 'hops'; this will minimise
cache misses.

The same used to be a big deal on paged virtual memory systems.

Otherwise, the advice about premature optimisation is worth noting.

Best regards,

Jon C.

[Stephen Howe]

What should be the most efficient way of layout out the three nested

loops?

Does not really make sense (you should spend more time before you post
asking yourself whether your posts are complete and unambiguous). What is
efficient?
The code is the fastest to execute?
The code is the easiest to maintain?

Assuming you mean CPU efficient, it should be such that the inmost loop is
going the memory references that are adjacent. That make it cache friendly
For C and C++, for multi-dimensional arrays, it is the right-most index.

for (i=0; i<10000; i++)
for (j=0; j<1000; j++)
for (k=0; k<100; k++)
array[i][j][k] = i * j * k; // Cache friendly

Also, it is possible sometime to unroll a 3 index loop into a 1-index loop
which can be faster. e.g..

for (i=0; i<10000 * 1000 * 100; i++)
array2[i]= 1;

or replace with a function call like memset() etc.

Stephen Howe

[red floyd]

Luna Moon wrote:

My friend has three nested loops, each has 10000, 1000, 100
iterations, respectively.

What should be the most efficient way of layout out the three nested
loops?

for (i=0; i<10000; i++)
for (j=0; j<1000; j++)
for (k=0; k<100; k++)
{

do something;
}
or

for (k=0; k<100; k++)
for (j=0; j<1000; j++)
for (i=0; i<10000; i++)
{

do something;
}

???

Someone already pointed you to Knuth's Law.

To be more precise, though, it depends.

Specifically it depends on:

1) what "do something" means
2) Your CPU
3) Your system's memory architecture
4) Your OS
5) Your compiler and optimization level.

In other words, there is no answer.

Benchmark, BENCHMARK, *BENCHMARK* and then come back if your loop really
is a bottleneck.