[SciPy-dev] fft benchmarks for new routines

Pearu Peterson pearu at cens.ioc.ee
Mon May 12 12:15:57 CDT 2003


On Mon, 12 May 2003, Chuck Harris wrote:

> > > To cut down on out-of-cache overhead, I unrolled a loop, which
> > > made the code about 3x longer and somewhat ugly. The result is
> > > a sort of bastard split radix 2,4 fft.
> > 
> > What fft backend are you using in scipy? FFTPACK, FFTW, or DJBFFT? 
> 
> What is DJBFFT?

See

  http://cr.yp.to/djbfft.html

When FFTW is 'the Fastest FT in West' then DJBFFT is supposed to
be 'the fastest FT in Universe' ;)

DJBFFT also provides only power-of-two (<=8192) routines and is indeed
very fast. However, it assumes very special data ordering. Since we are
using FFTPACK convention then transformations between data orders will
kill any speed gain obtained when using DJBFFT backend.

With DJBFFT there are also some license and installation
(Win32,MacOSX) issues.

So, it would be nice to have fast power-of-two routines that does not have
above problems.

> I did my own based roughly on FFTPACK.

Then we should bench your algorithms also against FFTW as FFTW is faster
than FFTPACK.

> It is not complete, as it allocates and keeps the coefficient array
> and needs some locking and reference counting to be thread safe. Don't
> know how to do this in Python.

See

   http://www.python.org/doc/current/api/threads.html

> Also, I only did the fft call (single and double precision), 
> and should probably add in the rest, along with the fast hartley transform 
> that I use for the real case. I renamed all the basic routines because
> I got tired of spending half a minute to figure out just what the h*ll
> drfftf stood for. This is now fft_dbl_real_for, and so on. Comments?

Note that scipy.fftpack provides generic functions like fft, ifft, etc
that check their argument types and call appropriate low-level
(single, double, complex, or double complex) routine (see
fftpack/basic.py). So, there's no need for users to figure out cryptic
names like drfftf, etc.

These generic functions give additional overhead and in principle we
could implement them in C in future but right now it's better to keep
them in Python until the interface stabilizes. After all, the overhead of
calling Python functions will be relevant only for small fft sizes.

> By the way, one problem I had was that the *.so library (linux) was not
> visible in the package, although it did fine as soon as I moved it up
> into site-packages. Probably some obvious oversight on my part -- I
> suspect the __init__.py file. Any thoughts?

I would need some additional information to give any useful thoughts.
What exactly did you tried and how?

Pearu




More information about the Scipy-dev mailing list