efficiency and nested loops

[Phlip]

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?

Efficient for the programmer? or for the CPU?

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

Note those should use "for (int k = 0; ...". That follows the guideline that
you should give all variables the most restrictive scope possible.

Next, use /el Goog/ to search for "premature optimization is the root of all
evil". If you profiled these statements and figured which sequence was more
optimal, and you cross-profiled for the various hardware and swapper file
conditions you may meet, you will spend more time profiling than your
resulting program will save, in cumulative time, if it ran from now until
the Sun goes off main sequence.

Write whatever's easiest to program, write lots of unit tests, and leave
things easy to change. C++ will optimize simple loops like these very well.
If this code ever becomes your bottleneck, you should switch to a better
algorithm, such as a sparse array.

 

[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]

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[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= 1;

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

Stephen Howe

 

[red floyd]

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.