Inner loop

In computer programs, an important form of control flow is the loop . For example, this small pseudo-code program uses two nested loops to iterate over all the entries of an n × n matrix, changing their values so that the matrix becomes an identity matrix:

for a in 1..n for b in 1..n if a = b M[a,b] := 1 else M[a,b] := 0

However, note that the comparison a = b is made n^2 times, which is a lot if n is large. We can do better:

for a in 1..n for b in 1..n M[a,b] := 0 M[a,a] := 1

At a first glance, one might think that the second variant of the algorithm is slower than the first, since it changes the value of some of the entries twice. But the number of extra changes is only n, and the number of comparisons that don t have to be done is n^2; clearly, for large enough values of n, the second algorithm will be faster no matter the relative cost of comparisons and assignment (computer science), since we do less work in the innermost loop.

Here s a second example:

for a in 1..10000 do_something_A for b in 1..10000 do_something_B

Assume that do_something_A takes 100 μs to run, and do_something_B takes 1 μs. The entire program then takes 10000*100 μs + 10000^2*1 μs = 101 s. We will spend one day optimizing this program, and during that day we can either make do_something_A 50 times faster, or do_something_B 10% faster. Which should we choose Well, the first option will bring down the total execution time to 10000*2 μs + 10000^2*1 μs = 100.02 s, and the second option will make it 10000*100 μs + 10000^2*0.9 μs = 91 s – clearly, optimizing the innermost loop is the better choice. But what if we could make do_something_A 500 times faster Or 5000 The answer is still the same, because of those initial 101 seconds, 100 seconds are spent in do_something_B, and just one second in do_something_A. Even if we could make do_something_A take no time at all, making do_something_B 10% faster would still be the better choice!

So: since almost all the program s time is spent in the innermost loops, optimizations there will have a big effect on the total time it takes to run the program. In contrast, optimizing anything but the innermost loops is often a waste of the programmer s time since it speeds up a part of the program that never did take much time.