The simple implementation in Simple programs used a LUT to store precomputed coefficients, but for every size of sub-transform that composes a particular transform, the LUT is accessed non-contiguously, with vector gather operations of varying strides. In Vectorized loops, vector intrinsics and a sequentially accessed LUT for each size of sub-transform are shown to improve performance. Although the set of LUTs increases the memory footprint, the speed improves markedly, by over 30% in many cases.

In Improving memory locality in the leaves, a DAG representing the computation was topologically sorted so that accesses to the input data, which are effectively pseudo-random for a decimation-in-time decomposition, are ordered into sequential streams. Benchmark results in Results and discussion show that this technique, in tandem with several others, achieves good results, being faster than FFTW in many cases.

The results from the above two cases confirm the idea that accessing data in sequential streams provides big performance gains, even in the somewhat counter-intuitive case where data is duplicated and more memory is required.

Hypothesis 2 is based on the idea that memory bandwidth is a bottleneck, and on the fact that the conjugate-pair algorithm requires only half the number of twiddle factor loads.

In Results and discussion, a highly optimized implementation of the conjugate-pair algorithm is benchmarked against an equally highly optimized implementation of the ordinary split-radix algorithm. For smaller sizes of transform, the ordinary split-radix algorithm is faster, but above a certain size (4096 in this case), the conjugate-pair algorithm is faster.

Thus, Hypothesis 2 is confirmed with the proviso that the transform is larger than a particular size.

In Results and discussion, SFFT and FFTW were benchmarked on sixteen x86 machines and two ARM NEON machines, and SFFT was found to be as fast as, or faster than FFTW, suggesting that the performance of an FFT running on a certain machine can be predicted and reasoned about, and that extensive machine calibration might not be required.

In Predicting performance, a model was evaluated with 10-fold cross-validation to have 74.8% precision when using characteristics of the underlying machine and the compiler to predict performance, further supporting the idea that the performance of the FFT on SIMD microprocessors can be predicted and reasoned about.

FFTW could be instrumented to collect data on the huge space of transforms it evaluates, which could then be used to build more accurate models.

The existing FFT benchmarking infrastructure could be improved by detecting interruption by other system processes and re-running the affected results. Benchmarks could then be run on a much wider range of machines, under more controlled conditions, which would increase the accuracy of models built from the data.

It might be possible to build a classifier that predicts whether a transform is likely, given some threshold, to be the fastest. The fastest is then selected from a subset of those that are likely to be the fastest, and thus the number of transforms that must be evaluated during calibration is reduced, while sacrificing little or no performance.

SFFT could be extended to multi-dimensional, multi-threaded, real, large (megapoint and above) and arbitrary sized transforms. Additionally, support for other architectures such as POWER and Cell B.E. could be added. Code could be optimized between transforms in a library, which would reduce binary size, but there may be other effects.

So far, there have been no known attempts to seriously optimize the tangent FFT, and the results of optimizing the tangent FFT to the same degree as the conjugate-pair FFT in this thesis would be very interesting.

SFFT could be utilized in the sparse FFT algorithms which have recently been published, perhaps improving their performance even further.

Applications such as the SETI@home client could be patched to support SFFT. The results of benchmarks between SFFT, FFTW and other libraries, when used in real world applications such as SETI@home, would be of great interest.