Implement FFT using a JIT that over any length of time/samples is faster than FFTW [1] or an h.264 encoder faster than x.264 [2] .
[1] - http://www.fftw.org/
> The optimizations that can be done ahead of time are a subset of the optimizations that can be done at runtime.
I don't think so. It's the other way around. That's because ahead-of-time you can do anything that takes any amount of time, including running the program. As long as your actual problem is predictable you can always do a better job AOT. In fact the process that a lot of performance driven AOT development goes through is running the program through sample data, analysing the results, including looking at the generated code, and figuring out ways to make it run faster. If the fastest solution for a specific problem involves generating native code then your AOT program can generate native code (if you want to say that's cheating than go ahead :-) ). The mere ability to produce your native code upfront is a performance advantage and there is no disadvantage. In theory including compilation time in run-time, over long periods, makes that delta as small as you want but it's still a delta and also we've not approached the theoretical bound in real world programs.
To be absolutely honest, when taken to the extreme there is no AOT or JIT. The thing is that people usually refer to JIT as spending some limited effort during run-time to generate some native code for some specific code sections. At the extreme JIT and AOT merge.