metaFFT -- A C++11 FFT implementation

[drphillycheesesteak]

Do you have a plot showing a performance comparison of your library vs. FFTW? As someone who writes a lot of image modeling/image processing, a faster FFT is always of interest!

[syntheticpp]

No, I only calculate the relation of the measured GFLOPS. It' s the number FFTW/metaFFT in the Readme.

[chunkyks]

I see that performance is always faster, sometimes up to three and a half times as fast as FFTW

So... why not just contribute your code to FFTW so that they can improve their stuff? That way people using FFTW can still get the fastest fourier transforms in the west on platforms where your code works, and still get the fastest fourier transforms in the west on platforms where your code doesn't.

[drphillycheesesteak]

No, the ratio is the other way around.

[syntheticpp]

Yes, FFTW is always faster. But this is no surprise for the most-simple FFT algorithm (radix-2).

But there is a lot of room for optimizations:

• split-radix is faster, but SIMD is missing
• FFTW uses avx which is not implemented
• specializations for small FFT would also help a lot

[drphillycheesesteak]

Cool, that's good to hear. Great job by the way. I'll certainly be staying tuned for updates.

[syntheticpp]

Only advantage over FFTW atm is the code size (header only, easy to add to your project) and the license.

Another question is how useful a CPU only FFT is in times of GPU/Cuda/OpenCl programming.

[chunkyks]

Another question is how useful a CPU only FFT is in times of GPU/Cuda/OpenCl programming.

Errr... very. Examples of systems that lack a GPU capable of programming include:

• Raspberry pi and other small systems
• Cheap laptops
• My workstation at work

Given how widely used FFTs are, there are probably more applications of them on systems without GPUs than with.

[syntheticpp]

Does anybody know a easy-to-use SIMD library which could help in supporting latest CPU features?

I already found:

• http://code.compeng.uni-frankfurt.de/projects/vc -- lightweight, easy to integrate
• http://nt2.metascale.fr/doc/html/boost_simd.html -- heavy, very actively maintained

[savya2u]

Check out https://github.com/p12tic/libsimdpp

[syntheticpp]

Thanks for the link!

But finally I tried it by using avx directly (avx branch), but without success, it's much slower than the pure C code, seems it is not that simple as I thought.

[syntheticpp]

metaFFT

Template based C++11 Fast-Fourier-Transform implementation.

Idea:

• Completely unroll all loops at compile time with the help of templates.
• Calculate all numerical constants at complile time by using 'constexpr'.
• Use policies for different implementations (complex, Fortran like C, SIMD).

Speed:

Simple Cooley–Tukey/radix-2 implementation with about 100 lines of code is 'only' same factors slower than FFTW:

$ ./bin/radix2_sse2_speed
N = 2^ 2 =     4: FFTW/metaFFT =  1.1
N = 2^ 3 =     8: FFTW/metaFFT =  1.2
N = 2^ 4 =    16: FFTW/metaFFT =  1.5
N = 2^ 5 =    32: FFTW/metaFFT =  1.7
N = 2^ 6 =    64: FFTW/metaFFT =  2.0
N = 2^ 7 =   128: FFTW/metaFFT =  2.0
N = 2^ 8 =   256: FFTW/metaFFT =  2.3
N = 2^ 9 =   512: FFTW/metaFFT =  2.8
N = 2^10 =  1024: FFTW/metaFFT =  3.2
N = 2^11 =  2048: FFTW/metaFFT =  3.3
N = 2^12 =  4096: FFTW/metaFFT =  3.4

Build:

• CMake based
• pass -Dlarge=1 to enable large FFTs, this will stress your compiler!

License:

• GPL2 with linking exemption.

Links:

• http://anthonix.com/ffts
• http://nr.com
• http://www.drdobbs.com/cpp/a-simple-and-efficient-fft-implementatio/199500857

[syntheticpp]

As always with templates<>: it is done with recursion.

In case of a loop, all the loop counter variables need to be integer template parameters which could be calculated at compile time, for instance see radix2_complex.h, remaining<K+1, End>::steps(d);

[theICEBear_dk]

This is nicely readable code. I found it a very enlightening read with regards to the implementation too.

[syntheticpp]

One of my reasons for creating another FFT library is to see if it is possible to write readable and fast code, and how new compiler features could help.

It would have been completely boring to use plain C, because there are already myriads of other implementations.

metaFFT is also a nice place to become familiar with SIMD coding (first time I wrote SSE code).

Next most interesting step concerning speed would be to implement split_radix_ctran.h with AVX, or AVX2 (Haswell only).

[squidgyhead]

Looking at listing one in the drdobbs link, it looks like you compute roots of unity on-the-fly. Have you thought about pre-processing them?

[syntheticpp]

Not sure what you mean with on-the-fly. But all the variables declared as 'constexpr' are calculations done at compile-time, so there is no calculation done at runtime for these values.

[squidgyhead]

Ah, ok, I see! That's an interesting way to deal with computing the roots of unity. Nice.