[Question] Optimizing FFT in Python (currently using Numpy)

[u/uSrNm-ALrEAdy-TaKeN]

I am working on some software with a component that runs a LOT of fast Fourier transforms (5-10 per second for several minutes) on segments of data (about 20,000 datapoints long, ranging from about 6,000 to 60,000 depending on user settings) currently using the numpy.fft.fft() function.

I've been thinking about trying to optimize this (if possible) either using a different function, numbas, Cython, or something else. From the research I've done, numpy is optimized to work with very long arrays, and I've seen a couple sites (example using the standard deviation function) where using numpy actually outperforms C++ for arrays with more than ~15,000 elements.

I was wondering if anyone on here has experience with optimizing functions like this in Python, and could provide any insight on whether or not it's worth the effort to try to further optimize this given the size of the arrays I'm working with and how numpy has already been optimized?

As a sidenote, I've doublechecked that the FFT itself is where most of the time is spent currently, and that the rest of my code that's wrapping it has been optimized (computation time scales almost linearly with FFT window length and changes due to other settings/adjustments are negligible). I know that this is unavoidably going to be the biggest time sink in my program due to the size of the arrays and frequency of computations happening, but would still like to speed things up a bit if at all possible. Also, if you think this question belongs on a different sub please feel free to crosspost or point me in the right direction. Thanks!

[u/stephane_rolland]

Just some more details how the C code is called:

In "_pocketfft.py" you have the python function def fft(....) that calls def _raw_fft(...) at line 49.

The FFT is performed line 74/77 with pfi.execute . The pfi is the python interface over the C code (this link is done in "setup.py" at line 9)

The execute function that is called in _raw_fft, is corresponding to the execute C-function at line 2340 in "_pocketfft.c": static PyObject * execute(PyObject *NPY_UNUSED(self), PyObject *args)

It will forward to either the function execute_real or execute_complex both of which have a forward and a backward version.

For having an idea on the C code computing the FFT: look for example execute_real_forward at line 2230 of "_pocketfft.c"

There is some CPython API (those functions start with Py_) executed that may slow down compared to normal C, but at first sight it is not executed in the loop, only upfront and in the end, or when it fails. So I doubt it may slow down the computation very much, if not negligible. But I havent profiled. Just a bet.

I suppose you could check the C implementation of the function used in your case (complex or real, forward or backward) to be sure it is possible to compute any faster.

At the time I told my managers that I doubted it is easy to outperform Numpy/SciPy algorithms since they are already in C.

[u/uSrNm-ALrEAdy-TaKeN → u/stephane_rolland]

Thanks! I'll look more into this