Loop Invariant Analysis

Briefly, remove constant forms from inside loops -- EddieEdwards

Your compiler does this for you. At least, it should. -- StephanHouben

Ideally it should, but usually the compiler doesn't know. You may be calling some external function, the typical beginner mistake in C being "for (int i = 0; i < strlen(text); ++i)". Assuming strlen(text) is constant, the compiler just has no simple way to verify it so it doesn't (it depends on if text is modified within the loop or even in another thread). It'd take a pretty damn smart compiler to optimize such invariants.

Even so, source code is often easier to understand if constant forms are outside the loop. Minimizing the amount of stuff inside a loop makes it clearer. The improvement in performance is an additional bonus. -- KrisJohnson

Is this the same as CodeHoisting??

I thought you were going to discuss inventing a loop by declaring its invariant. A much more fun discussion (e.g. see the ones in BinarySearchCodeOnly). -- AlistairCockburn

Relation to FixedPointCombinator ?

It's not particularly related. The invariant under discussion is a constant, whereas fixed points concern variables that are invariant under a transformation. An example of the latter is x = f(x). It's x that is the fixed point. The fact that it's also true that 1*x = f(1 * x) doesn't make the constant 1 a fixed point. It's irrelevant to the issue.

To put it another way, a fixed point is the solution to a relation (the word "solution" can be, and often has been, defined thusly). There may be only zero or one such. But loop invariants can exist even when there is no solution to the relation that the loop is searching for.

This is an optimization of this form:

for (loop conditions)

  const x = method()
  ...code...

this can be optimized by moving to this form:

const x = method() for (loop conditions)

  ...code...

In other words, perform calculations with a constant result outside the loop to save an order of magnitude in performance.

CategoryOptimization