/kfft

Fast fourier transform library. KissFFT fork with some optimizations.

Primary LanguageCOtherNOASSERTION

ABOUT

LibKFFT is a free/open-source (ZLib licensed) C library providing fast fourier transform and other related operations for comlex and scalar double or float sequences.

DEVELOPMENT

LibKFFT is deeply redesigned fork KissFFT project by Mark Borgerding.

REALISED FEATURES

The features of LibKFFT include:

  • complex and scalar fourier transformation operations (forward and inverse)
    • 64-bit float type (double) as default
    • 32-bit float type (float) if set option KFFT_HALF_SCALAR
  • SIMD acceleration transform operations (now support SSE, SSE2, SSE3 (optional)) (build option)
  • Recursive Rader algorithm for prime-number lenght sequenses (build option)
  • Internal math functions (aka sqrt, sincos etc.) without system libm functions (build option)
  • Parallelization with OpenMP framework (build option)
  • 2D, convolution(+2D) operations as build-time extensions (with the ability to easily create custom extensions)
  • Detail trace log in stdout for diagnostic (build option)
  • Tiny API support for simplify code in trivial usage

BUILD AND TEST

Need sofware: meson >= 55.0, ninja >= 1.8.0 Test build on OS with CC:

  • Linux (x86-64): GCC 9.3, Clang-10
  • Windows (x86-64): MSVC 2015, 2017, Clang-10
  • RPi3 (armhf): GCC 8.3

Build: configure build in meson_options.txt if need and run meson . ./<builddir> && ninja -C ./<builddir>

Test (don't implemented on Windows): if change option enable_tests use test ninja -C ./<builddir> <target>

  • test_bot - run unit tests (need libcunit for build it)
  • test_speed[_cpx,_scr] - run speed tests and compare with popular implementations
  • test_speed_kfft[_cpx,_scr] - run speed tests for libkfft only (produce SVG and CSV)
  • test_valide[_cpx,_scr] - run validate tests (use FFTW3 for compare)

BENCHMARKS

Compare with popular implementations Test machine:

  • CPU - Intel i5-2540M (Sandy)
  • RAM - Kingstone DDR3 1333MHz 16Gb
  • OS - Linux Mint 20 (GCC 9.3.0)

Implementation:

  • FFTW (3.3.8)
  • KissFFT (commit b2e0e60).
  • KFFT (0.8.0)

Build options:

  • libfftw: build in Ubuntu 20.04 repo
  • libkiss: -DFIXED_POINT=32
  • libkfft: -DKFFT_USE_SIMD -DKFFT_USE_SYSMATH -DKFFT_USE_OPENMP -DKFFT_RADER_ALGO -DKFFT_RADER_LIMIT=25 -DKFFT_PLAN_LEVEL=7 -DKFFT_BFLY_LEVEL=5 ... libkfft and libkiss make with Meson mode release build with PGO and LTO

Bench variants:

  • Range: 1 .. 1000000
  • Step: 101

This step may test all variants such as: normal lenght, prime-lenght and other difficult cases

Bench result

Complex test evaluation compare complex test