When you ask FFTW to construct a plan, it benchmarks a variety of options and uses the fastest one.

> FFTW_MEASURE tells FFTW to find an optimized plan by actually computing several FFTs and measuring their execution time. Depending on your machine, this can take some time (often a few seconds). FFTW_MEASURE is the default planning option.

> FFTW_PATIENT is like FFTW_MEASURE, but considers a wider range of algorithms and often produces a “more optimal” plan (especially for large transforms), but at the expense of several times longer planning time (especially for large transforms).

> FFTW_EXHAUSTIVE is like FFTW_PATIENT, but considers an even wider range of algorithms, including many that we think are unlikely to be fast, to produce the most optimal plan but with a substantially increased planning time.

http://www.fftw.org/fftw3_doc/Planner-Flags.html

I believe this sort of technique is used for some cryptography libraries as well, but I don't have any specifics.