Inner loop
Encyclopedia
In computer program
s, 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
times, which is a lot if 
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
, and the number of comparisons that don't have to be done is 
; clearly, for large enough values of 
, the second algorithm will be faster no matter the relative cost of comparisons and assignments
, 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
μs 
μs 
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 
μs 
μs 
s, and the second option will make it 
μs 
μs 
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.
Computer program
A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...
s, an important form of control flow
Control flow
In computer science, control flow refers to the order in which the individual statements, instructions, or function calls of an imperative or a declarative program are executed or evaluated....
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
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
, changing their values so that the matrix becomes an identity matrix
Identity matrix
In linear algebra, the identity matrix or unit matrix of size n is the n×n square matrix with ones on the main diagonal and zeros elsewhere. It is denoted by In, or simply by I if the size is immaterial or can be trivially determined by the context...
:
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
times, which is a lot if 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
, and the number of comparisons that don't have to be done is ; clearly, for large enough values of , the second algorithm will be faster no matter the relative cost of comparisons and assignmentsAssignment (computer science)
In computer programming, an assignment statement sets or re-sets the value stored in the storage location denoted by a variable name. In most imperative computer programming languages, assignment statements are one of the basic statements...
, 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
μs μs 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 μs μs s, and the second option will make it μs μs 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.