Signalsmith FFT is a small (600-line) C++ header-only FFT implementation.
I wrote it because KISS FFT (the most common one I could find with a commercial-friendly license) was slow, and I thought I could do better. It's not as fast as FFTW (when used properly), but it's pretty good. :)
It only supports some sizes (2N x 1, 3 or 9), and will round up to the closest supported size. It produces permuted results, with a separate de-permutation step.
signalsmith-fft.h - 21kb, 600 lines
You can also view it in Bitbucket.
MIT License - if you need something else, let me know.
Despite its small size, this library:
- Outperforms KISS FFT at all sample sizes
- Competes with FFTW's "estimate" configuration at larger sizes
Here are some benchmarks I ran myself on the machines I had available (64-bit, max optimisation).
The (fairly rough) benchmark code is also in Bitbucket, and if you run it yourself (or add it to any other benchmarks!), please let me know.
How to use
.fft() method produces permuted output, and
.ifft() expects permuted input.
There are methods to re-order the computed spectrum:
Not all sizes are supported. The actual size may be up to 33% larger than requested.
The actual size is returned from
You can also provide a second argument to
getFft() for parallel FFTs:
.setSize() doesn't actually change the size, it doesn't reallocate/recalculate.
If it does change, it costs as much as constructing a new object with
In a multi-threaded environment, each thread should have its own instance, because of temporary memory used for out-of-place/in-place shuffling.