Spek — Acoustic spectrum analyser

Share this post

Faster Fast Fourier Transform

www.spek.cc

Faster Fast Fourier Transform

Aug 31, 2014
2
Share this post

Faster Fast Fourier Transform

www.spek.cc
Share

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:

fft-bench-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.

2
Share this post

Faster Fast Fourier Transform

www.spek.cc
Share
Comments
Top
New
Community

No posts

Ready for more?

© 2023 Alexander Kojevnikov
Privacy ∙ Terms ∙ Collection notice
Start WritingGet the app
Substack is the home for great writing