Why does padding an FFT in NumPy make it run much slower?
Question: I had writted a script using NumPy's `fft` function, where I was padding my
input array to the nearest power of 2 to get a faster FFT.

After profiling the code, I found that the FFT call was taking the longest
time, so I fiddled around with the parameters and found that if I _didn't_ pad
the input array, the FFT ran several times faster.

Here's a minimal example to illustrate what I'm talking about (I ran this in
IPython and used the `%timeit` magic to time the execution).

    
    
    x     = np.arange(-4.*np.pi, 4.*np.pi, 1000)
    dat1  = np.sin(x)
    

The timing results:

    
    
    %timeit np.fft.fft(dat1)
    100000 loops, best of 3: 12.3 µs per loop
    
    %timeit np.fft.fft(dat1, n=1024)
    10000 loops, best of 3: 61.5 µs per loop
    

Padding the array to a power of 2 leads to a very drastic slowdown.

Even if I create an array with a prime number of elements (hence the
theoretically slowest FFT)

    
    
    x2    = np.arange(-4.*np.pi, 4.*np.pi, 1009)
    dat2  = np.sin(x2)
    

The time it takes to run still doesn't change so drastically!

    
    
    %timeit np.fft.fft(dat2)
    100000 loops, best of 3: 12.2 µs per loop
    

I would have thought that padding the array will be a one time operation, and
then calculating the FFT should be quicker. Am I missing anything?

**EDIT:** I was supposed to use `np.linspace` rather than `np.arange`. Below
are the timing results using `linspace`

    
    
    In [2]: import numpy as np
    
    In [3]: x = np.linspace(-4*np.pi, 4*np.pi, 1000)
    
    In [4]: x2 = np.linspace(-4*np.pi, 4*np.pi, 1024)
    
    In [5]: dat1 = np.sin(x)
    
    In [6]: dat2 = np.sin(x2)
    
    In [7]: %timeit np.fft.fft(dat1)
    10000 loops, best of 3: 55.1 µs per loop
    
    In [8]: %timeit np.fft.fft(dat2)
    10000 loops, best of 3: 49.4 µs per loop
    
    In [9]: %timeit np.fft.fft(dat1, n=1024)
    10000 loops, best of 3: 64.9 µs per loop
    

Padding still causes a slowdown. Could this be a local issue? i.e., due to
some quirk in my NumPy setup it's acting this way?


Answer: FFT algorithms like NumPy's are fast for array sizes that factorize into a
product of small primes, not just powers of two. If you increase the array
size by padding the computational work increases. The speed of FFT algorithms
is also critically dependent on the cache use. If you pad to an array size
that creates less efficient cache use the efficiency slows down. The really
fast FFT algorithms, like FFTW and Intel MKL, will actually generate plans for
the array size factorization to get the most efficient computation. This
includes both heuristics and actual measurements. So no, padding to the
nearest power of two is only beneficial in introductory textbooks and not
neccesarily in practice. As a rule of thumb you usually benefit from padding
if the array size factorizes to one or more very large prime.

