Help me understand FFT and IPP (and other libs)
-
Hi, I'm new to algorithms and C++ and all the tough stuff. I saw a few videos on FFT (Fast Fourier Transform) and the basics of shortening down lots of big iterations, especially for waveform based calculations and deductions. Still, it's a bit fuzzy.
My main question is:
-
If an FFT library (such as IPP or FFTW3) is used, is the end code binary (hise executable or your end-software/plugin executable) going to run faster? Or is it just the compilation time that is reduced via the FFT algorithms?
-
- aka, does my plugin run faster during it's use if I use IPP/FFTW3 during compilation of it?
-
-
Actually you don't need to know how an FFT works (I also just understand the very basics of the Fourier transform but never looked how the FFT implementation actually works, all you need to know is that it's one of the most remarkable algorithms out there and maybe the single most important algorithm for all DSP).
And yes, using a better FFT library has a vast impact on your plugin's performance, but only if you're using convolution reverbs or the spectrum analyzer. And what FFT library is used is dependent on your build configuration. Currently those are the best options for each OS:
- Windows: IPP
- macOS: VDSP (the "native" DSP framework from Apple. On Intel CPUs, the IPP might be a little bit faster, but that's rather in the range of 1-2% and on M1 machines you can't use IPP at all if you want to run a Apple Silicon build)
- Linux: IPP or if you're using GPL v3 as license for your plugin, you can use FFTW.
-
You might enjoy this video:
-
@Christoph-Hart Thanks for the clarification!
The CPUs instruction set for SIMD seems to be a big factor for the actual gains. I found a nice thesis by a guy named Anthony Blake called "Computing the fast Fourier transform on SIMD microprocessors", including lots of comparisons from quite recent machines (i7-2600, around 7yrs old "only":=). It included a high-performance FFT library called SFFT / Spiral, vDSP, Intel IPP and FFW3: (page 140 in pdf)
https://www.cs.waikato.ac.nz/~ihw/PhD_theses/Anthony_Blake.pdf
According to the benchmarks, another library called SFFT (Sparse Fast Fourier Transform) was used that partially trashed the others (FFW3/vDSP/IPP) around the 4-64 bit sets in lots of tests. But according to the Spiral SFFT page:
the algorithm can be faster than modern FFT libraries. However, the reference implementation is not optimized for modern hardware features such as the cache hierarchy, vector instruction sets, or multithreading.
Too bad, would have loved to stare at some more graphs and then going "I wish I understood the context". :) It is now being used in 3D FFT to analyze the trajectories of gravitational pulls or ... well space n shit
@d-healey Thanks for the video, I saw it yesterday and it is really good. He explains it perfectly.
