Code optimization is often described as hand waving and magic.

But mostly its science.

Compilers implement transformations on code that results in provably identical semantic operation but that can result in faster performance, smaller code, or in some cases both (depending on what settings the particular compiler in use exposes)

LLVM uses a form known as SSA (single static assignment). This particular form makes reasoning about and proving the results of transformations are equivalent to the original code since once a value is assigned its never mutated.

SSA makes things like constant propagation & dead code elimination easier to do. Not that it could not be done in other forms compilers use juts that SSA happens to make these easier because of how SSA works.

Xojo’s use of LLVM enables some optimizations – but not all optimizations that LLVM can perform (there are literally hundreds)

So sometimes you need to perform some yourself.

  1. invariant code motion – these are statements, or portions of statements, that can be moved outside a loop and computed once because they do not change in the course of a loop. Some care needs to be taken with this optimization when performed manually as noted in the Wikipedia article. In Xojo constantly referencing picture.graphics can often be lifted outside the loop into a local and cutting down the number of calls to picture.graphics and using the cached local variable.
  2. loop unrolling – some times you can achieve a significant speed up by repeating the body of the loop operating on multiple different items in each loop pass. For instance instead of traversing an array in reverse order and deleting one element on each pass it may be faster to use a step size in the loop of 5 and remove 5 elements on each pass. Again there are some hazards with this. Often its useful to know the number of iterations of the loop at compile time in order to most effectively unroll the loop.
  3. common subexpression elimination – sometimes a portion of a calculation is repeated more than once and lifting the repeated portion out and doing it once and the reusing the pre-computed value can speed things up (it may also improve code clarity). In something like the following
    a = b * c + g
    a = b * c * e

    you might lift out the computation of b * c into a local and then just reuse the local
    bc = b * c
    a = bc + g
    a = bc * e
  4. constant folding and propagation – when known at compile time instead of generating code to compute a constant value, typically from literals, the result will be inserted instead.
    So instead of inserting code to do the computation of 24 * 60 * 60 the compiler will simply insert 86400. This optimization may also be applied to strings and other literals.

These are just 4 of many many possible optimizations. You can implement these by hand in your own code as well and some, like common subexpression elimination, may make long lines of code simpler by replace repeated calculations with a single local variable.

I’d encourage everyone to read the Wikipedia pages about these optimizations implement them in your own code.

Have fun !

One Reply to “Optimization”

  1. Great first brief insight into code optimizations Norman. Great! I would be very excited about upcoming posts on this topic 😉

Comments are closed.