loop invariant

A loop invariant is a piece of information that does not change within the body of a control structure.

If calculating a loop invariant is expensive, then caching the result of the calculation outside of the loop can improve performance. Loop invariants are one of the first options considered for increasing run-time performance. However, caching the loop invariant will not change the computation complexity of the loop.

Here is an example.

Imagine that you want to loop through a twenty element array and check to see if any of the elements are equal to e * pi ^ 2.

for i = 0 .. 19
   if elementi = Math.e() * Math.pi() * Math.pi() then
      print "Match found."
   end if
end for loop

In this example, the invariant is Math.e()*Math.pi()*Math.pi() . This has a cost of two multiplies and three function calls, each of which may actually do the work of calculating e and pi, which is very expensive.

Obviously, this amount will not change in the loop.*

So we can achieve a performance increase by caching the results of this calculation outside of the loop. Let's use a variable to store this value, and call it eTimesPiTimesPi. **

var eTimesPiTimesPi = Math.e() * Math.pi() * Math.pi();
for i = 0 .. 19
   if elementi = eTimesPiTimesPi then
      print "Match found."
   end if
end for loop

This has an immediate effect on the run-time speed, with no actual modification of the algorithm necessary. The costs associated with this approach are time and code clarity.

* (in fact, it will never change, but that's a different story.)

** I like to use descriptive variable names like this, but you may wish to use a shorter variable name like epp.