Faster Fast Fourier Transform

Spek is already pretty fast at analyzing audio files and creating their spectrograms. Apparently, it can be made even faster!

A sizable chunk of processing time is spent calculating discrete Fourier transforms of audio samples. In this post I'm going to explore a few DFT libraries and compare their performance to what Spek is currently using.

This won't be a comprehensive overview of all available libraries. I'm going to benchmark only what Spek needs:

• Relatively small, power of 2 transform sizes. The default size in Spek is 2¹¹, this will be adjustable in the future, but not by much.

• Single precision floating point numbers. 24-bit significand is enough when working with audio samples.

• Only one-dimensional forward real transforms.

• Last but not least, the DFT library should be free software, actively maintained, fairly popular and multi-platform.

The list of candidates is surprisingly short:

• avfft, which is part of the FFmpeg project. This is what Spek uses.

• FFTW. Probably the most respectable FFT library of all. Supports both in-place and out-of-place transforms.

• djbfft by Dr. Bernstein of daemontools fame. It's not as performance tuned as the other two (e.g. it doesn't use SIMD instructions), but I want to see how it fares against them.

The test setup is straightforward (the code is on GitHub in case you're curious):

• Generate pseudo-random single-precision floating point samples. The number of samples corresponds to 10 minutes of signal at standard 44.1 kHz sampling rate.

• For all libraries and for all transform sizes from 2⁹ to 2¹³ run non-overlapping FFTs for the entire signal.

• Measure wall clock time only for FFTs (exclude sample generation and library initialization), take 5 measurements for every combination, report the fastest.

Results:

As expected, djbfft is the slowest, using SIMD instructions does make things faster. I am however surprised how fast the FFTW is compared to avfft (approximately 60% faster!)

Conclusion: Next version of Spek will switch to FFTW.