A fork of Julien Pommier's Pretty Fast FFT (PFFFT) library, with several additions
A fork of Julien Pommier's Pretty Fast FFT (PFFFT) library, with several additions
PFFFT does 1D Fast Fourier Transforms, of single precision real and complex vectors. It tries do it fast, it tries to be correct, and it tries to be small. Computations do take advantage of SSE1/AVX/AVX2 instructions on x86 cpus, Altivec on powerpc cpus, NEON on ARM cpus (including Apple Silicon), and WASM SIMD on WebAssembly. The license is BSD-like.
PFFFT is a fork of Julien Pommier's library on bitbucket with some changes and additions.
PFFASTCONV does fast convolution (FIR filtering), of single precision real vectors, utilizing the PFFFT library. The license is BSD-like.
PFDSP contains a few other signal processing functions. Currently, mixing and carrier generation functions are contained. It is work in progress - also the API! The fast convolution from PFFASTCONV might get merged into PFDSP.
I (Julien Pommier) was in search of a good performing FFT library , preferably very small and with a very liberal license.
When one says "fft library", FFTW ("Fastest Fourier Transform in the West") is probably the first name that comes to mind -- I guess that 99% of open-source projects that need a FFT do use FFTW, and are happy with it. However, it is quite a large library , which does everything fft related (2d transforms, 3d transforms, other transformations such as discrete cosine , or fast hartley). And it is licensed under the GNU GPL , which means that it cannot be used in non open-source products.
An alternative to FFTW that is really small, is the venerable FFTPACK v4, which is available on NETLIB. A more recent version (v5) exists, but it is larger as it deals with multi-dimensional transforms. This is a library that is written in FORTRAN 77, a language that is now considered as a bit antiquated by many. FFTPACKv4 was written in 1985, by Dr Paul Swarztrauber of NCAR, more than 25 years ago ! And despite its age, benchmarks show it that it still a very good performing FFT library, see for example the 1d single precision benchmarks here. It is however not competitive with the fastest ones, such as FFTW, Intel MKL, AMD ACML, Apple vDSP. The reason for that is that those libraries do take advantage of the SSE SIMD instructions available on Intel CPUs, available since the days of the Pentium III. These instructions deal with small vectors of 4 floats at a time, instead of a single float for a traditionnal FPU, so when using these instructions one may expect a 4-fold performance improvement.
The idea was to take this fortran fftpack v4 code, translate to C, modify it to deal with those SSE instructions, and check that the final performance is not completely ridiculous when compared to other SIMD FFT libraries. Translation to C was performed with f2c. The resulting file was a bit edited in order to remove the thousands of gotos that were introduced by f2c. You will find the fftpack.h and fftpack.c sources in the repository, this a complete translation of fftpack, with the discrete cosine transform and the test program. There is no license information in the netlib repository, but it was confirmed to me by the fftpack v5 curators that the [same terms do apply to fftpack v4] (http://www.cisl.ucar.edu/css/software/fftpack5/ftpk.html). This is a "BSD-like" license, it is compatible with proprietary projects.
Adapting fftpack to deal with the SIMD 4-element vectors instead of scalar single precision numbers was more complex than I originally thought, especially with the real transforms, and I ended up writing more code than I planned..
The FFT API is very very simple, just make sure that you read the comments in pffft.h.
The Fast convolution's API is also very simple, just make sure that you read the comments
in pffastconv.h.
A simple C++ wrapper is available in pffft.hpp.
This archive's source can be downloaded with git (without the submodules):
git clone https://github.com/marton78/pffft.git"Only two files, in good old C, pffft.c and pffft.h"
This statement does NO LONGER hold!
With new functionality and support for AVX, there was need to restructure the sources. But you can compile and link pffft as a static library.
There's now CMake support to build the static libraries libPFFFT.a
and libPFFASTCONV.a from the source files. The additional
libFFTPACK.a library is built only when tests or benchmarks are enabled.
There are several CMake options to modify library size and optimization.
You can explore all available options with cmake-gui or ccmake,
the console version - after having installed (on Debian/Ubuntu Linux) one of
sudo apt-get install cmake-qt-gui
sudo apt-get install cmake-curses-guiSome of the options:
PFFFT_USE_TYPE_FLOAT to activate single precision 'float' (default: ON)PFFFT_USE_TYPE_DOUBLE to activate 'double' precision float (default: ON)PFFFT_USE_SIMD to use SIMD (SSE/AVX/NEON/ALTIVEC/WASM SIMD) CPU features? (default: ON)DISABLE_SIMD_AVX to disable AVX CPU features (default: OFF)PFFFT_USE_SIMD_NEON to force using NEON on ARM (requires PFFFT_USE_SIMD) (default: OFF)PFFFT_USE_SCALAR_VECT to use 4-element vector scalar operations (if no other SIMD) (default: ON)PFFFT_USE_WASM_RELAXED_SIMD to use WebAssembly Relaxed SIMD multiply-add instructions, which may be fused when supported by the runtime (default: OFF)Options can be passed to cmake at command line, e.g.
cmake -DPFFFT_USE_TYPE_FLOAT=OFF -DPFFFT_USE_TYPE_DOUBLE=ONMy Linux distribution defaults to GCC. With installed CLANG and the bash shell, you can use it with
mkdir build
cd build
CC=/usr/bin/clang CXX=/usr/bin/clang++ cmake -DCMAKE_BUILD_TYPE=Debug ../
cmake -DCMAKE_BUILD_TYPE=Debug -DCMAKE_INSTALL_PREFIX=~ ../
ccmake . # or: cmake-gui .
cmake --build . # or simply: make
ctest # to execute some tests - including benchmarks
cmake --build . --target install # or simply: [sudo] make installWith MSVC on Windows, you need some different options. Following ones to build a 64-bit Release with Visual Studio 2019:
mkdir build
cd build
cmake -G "Visual Studio 16 2019" -A x64 ..
cmake --build . --config Release
ctest -C Releasesee https://cmake.org/cmake/help/v3.15/manual/cmake-generators.7.html#visual-studio-generators
With Emscripten for WebAssembly (requires the Emscripten SDK):
mkdir build
cd build
emcmake cmake ..
cmake --build .
ctestWASM SIMD is enabled automatically when building with Emscripten; see Performance and architecture notes for the Relaxed SIMD option and the non-CMake build flags.
Compiler- and architecture-specific tips for getting the best performance out of pffft.
On x86 the fused multiply-add paths are opt-in, and the default build does
not get them. VMADD/VMSUB -- used by the complex multiply at the heart of
pffft_zconvolve*() and of every radix codelet -- lower to a real FMA
instruction only when the compiler guarantees FMA3:
| compiler | how to enable |
|---|---|
| gcc / clang | -DTARGET_C_ARCH=haswell (or a later -march value) |
| MSVC | -DTARGET_C_ARCH=AVX2 |
Without it, each fused operation costs a separate multiply plus add. Measured
on the pffft_zconvolve_accumulate() inner loop, identical for gcc 12 and
clang 14, x86-64 and i686, float (SSE) and double (AVX): 20 floating point
operations per iteration instead of 12.
cmake -DTARGET_C_ARCH=haswell -DTARGET_CXX_ARCH=haswell ..This is not the default on purpose: FMA3 requires an Intel Haswell (2013) or
AMD Piledriver CPU, so enabling it unconditionally would break older hardware.
cmake prints a reminder when the selected x86 architecture has no FMA.
Note that FMA changes results by up to one ULP, since it rounds once where the separate multiply and add round twice.
On 32-bit ARM, gcc emits very inefficient assembly, with a lot more
operations that clang does. Measured over the whole float translation unit,
both at -O3 -march=armv7-a -mfpu=neon:
64-bit vldr/vstr |
128-bit vld1/vst1 |
|
|---|---|---|
| gcc 12.2 | 1600 | 344 |
| clang 14 | 181 | 797 |
GCC's bad code generation affects roughly 19 functions, including the hot ones
(pffft_real_finalize, pffft_real_preprocess, pffft_cplx_finalize,
pffft_zreorder, passf4_ps, radf4_ps, ...). This caveat applies to all versions
including GCC 16.1 (newest at time of writing), so this is not about old toolchains.
There is a GCC ticket
reporting this since 2010 and it hasn't been fixed since. No flag changes it
(fourteen combinations were tried, including -mtune=cortex-a9/a15, -mcpu=...,
-mfpu=neon-vfpv4, -mvectorize-with-neon-quad, -m[no-]unaligned-access, -O2,
and the Raspberry Pi 3/4 presets). It doesn't seem like this problem is ever going
to be fixed, see this comment
by the ARM maintainer. So we recommend to use Clang when targeting ARMv7.
cmake prints a reminder when it sees gcc targeting ARMv7. Note that this applies
only to 32-bit ARM, on AArch64 both compilers are fine.
pffft has a dedicated WASM SIMD backend using native wasm_simd128.h
intrinsics for both float and double precision.
Performance tip: enable Relaxed SIMD for a measured 6-11% throughput gain on FFT sizes of 1024 and up, on runtimes that support it (e.g. V8/Chrome, Node.js):
emcmake cmake -DPFFFT_USE_WASM_RELAXED_SIMD=ON ..This uses relaxed multiply-add instructions, which the runtime may fuse into a single-rounding FMA, or fall back to a two-rounding multiply followed by add/subtract. It is off by default because relaxed SIMD results are not guaranteed bit-identical across engines or hardware (unlike the default WASM SIMD path); enable it only if your application tolerates ULP-level differences between runtimes.
If you build for Emscripten without the bundled CMake config (e.g. a raw
emcc/Makefile/Bazel invocation), compile with -msimd128 -DPFFFT_ENABLE_WASM=1
to select the WASM SIMD backend; the previous PFFFT_ENABLE_NEON recipe no
longer enables it and now silently falls back to scalar code.
pffft can be included as a dependency in your CMake project via FetchContent or add_subdirectory(). When used this way, tests, benchmarks, examples, and the standalone uninstall helper target are automatically disabled, so pffft won't pollute your build or ctest runner with unnecessary targets or cause target-name collisions.
No open issues yet, or sync has not completed.