5
$\begingroup$

I have a MATLAB program that uses fft and ifft a lot. Now I want to translate it to C++ for production. I used OpenCV but I noticed that OpenCV's implementation of fft is 5 times slower than MATLAB's. Then I tried armadillo but it was even slower. It was 10 times slower than MATLAB. Now I wonder is there any implementation of fft in C++ that is fast enough to compete with MATLAB?

$\endgroup$
  • 2
    $\begingroup$ Depends on the processor, number of processors, caches, memory system, data type, and FFT size. But look at fftw and Accelerate/vDSP for starters. $\endgroup$ – hotpaw2 Jun 26 '15 at 4:13
  • 1
    $\begingroup$ Also depends on which licence you can or want to use and/or if you are willing to pay. FFTW is GPLed, but a commercial licence can be bought, too. $\endgroup$ – chirlu Jun 26 '15 at 6:01
9
$\begingroup$

Matlab's fft functions are all based on FFTW (this is confirmed here), so I guess the obvious choice for you should be FFTW. FFTW is hardware-independent but it can take advantage of some hardware-specific features.

$\endgroup$
  • 5
    $\begingroup$ I would add to that FFTW is indeed pretty fast, but you have to compile it with the appropriate options to take advantage of all optimizations. Like SSE instructions, OpenMP and MPI support and some others. $\endgroup$ – Loufylouf Jun 26 '15 at 8:29
3
$\begingroup$

I second the fftw suggestion. One of the nice features of fftw is "wisdom". That is, if you call many times the same Fourier Transform (with the same array size), you can ask fftw to look for the fastest way to do it, and then it will use that way for all the following computation in your code.

$\endgroup$
3
$\begingroup$

There's also FFTS (written in C, not C++, though), which has some impressive benchmarks:

https://github.com/anthonix/ffts

I compiled it under Linux, but haven't had a chance to play with it yet.

$\endgroup$
2
$\begingroup$

The two that I see being used most often are:

Ooura FFT: http://www.kurims.kyoto-u.ac.jp/~ooura/fft.html

IPP: https://software.intel.com/en-us/intel-ipp

You have to pay for a license for IPP (Intel Performance Primatives) but it would be the tool of choice for a commercial offering. Ooura FFT has good all round performance and a permissive license. On a MAC I believe Apple has a free FFT routine which offers performance comparable to IPP/FFTW.

Beware relying on benchmarks many are out of date or focus too heavily on certain use cases which may or may not apply to your use case.

$\endgroup$
2
$\begingroup$

I was also searching for fast FFT library to be used from C++. Let me share what I think the situation is in 2019.

FFTW is the most popular FFT library. It has planty of features and it's often used as the reference point, but a number of other libraries has comparable or better performance.

Intel MKL library, which is now freely redistributable, is significantly faster than FFTW. I'm curious if it's also true on non-Intel processors, but I don't have one to check. Like FFTW, it has planty of features.

KFR claims to be faster than FFTW. In the latest version it's mixed-radix implementation. It's the only one that is written in C++, others are usually in C.

FFTS (South) and FFTE (East) are reported to be faster than FFTW, at least in some cases. FFTE is actually in Fortran, but I thought it's worth mentioning anyway.

muFFT and pffft have performance comparable to FFTW while being much simpler. The performance depends strongly on the SIMD instructions that are used. muFFT has four versions: no-SIMD, SSE, SSE3 and AVX. pffft also has four variants: no-SIMD, SSE, AltiVec and NEON. These libraries don't have all the features of FFTW and MKL. muFFT supports only sizes 2^N, pffft supports radices 2, 3 and 5.

There is also a quite popular library KissFFT, which is the simplest but also the slowest one here. And PocketFFT on which the incoming version of numpy.fft will be based. They are slower as they don't make use of SIMD instructions. But in some cases they are worth considering. For example when the code is to be compiled to WebAssembly which doesn't support SIMD anyway.

I wrote down numbers from my (rather limited) benchmarks here:
https://github.com/project-gemmi/benchmarking-fft/

$\endgroup$
  • $\begingroup$ I'm curiosity why there isn't a FFTN????!!! $\endgroup$ – diverger Jun 4 at 0:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.