Tools

When you can't figure-out a better way, why not let the computer do it for you? These are tools and techniques based on having the computer search for better implementations.

The strangest thing is that most of these types of tools have fallen out of favor in recent years. There was a huge push for them in the 1990s, but it seems that as machines got faster, people got sloppier about tuning for them.

Superoptimizer: a look at the smallest program

Henry Massalin's 1987 paper that started this whole approach.

Superopt, the GNU Superoptimizer

The GNU superoptizier works for a variety of targets. The actual source tar file is here, currently dating from 1995!

Henry Warren's Aha!

A RISC-oriented superoptimizer.

Denali: a goal-directed superoptimizer

A theorem-proving superoptimizer (code not available).

ATLAS

This "Automatically Tuned Linear Algebra Software" basically exhaustively tries a huge number of alternative codings of matrix and vector multiplies.

FFTW

"Fastest Fourier Transform in the West," which is also semi-automatically tuned

Genetic Programming

A method whereby programs to solve problems are evolved from an initial population of random programs. Lots of links here. John Koza is generally credited with founding this approach.

CMix

A C program specializer (partial evaluator)

Tempo

Another program specializer for C