title: Why does padding an FFT in NumPy make it run much slower?
body: <p>I had writted a script using NumPy's <code>fft</code> function, where I was padding my input array to the nearest power of 2 to get a faster FFT. </p>
  
  <p>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 <em>didn't</em> pad the input array, the FFT ran several times faster. </p>
  
  <p>Here's a minimal example to illustrate what I'm talking about (I ran this in IPython and used the <code>%timeit</code> magic to time the execution).</p>
  
  <pre><code>x     = np.arange(-4.*np.pi, 4.*np.pi, 1000)
  dat1  = np.sin(x)
  </code></pre>
  
  <p>The timing results:</p>
  
  <pre><code>%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
  </code></pre>
  
  <p>Padding the array to a power of 2 leads to a very drastic slowdown.</p>
  
  <p>Even if I create an array with a prime number of elements (hence the theoretically slowest FFT)</p>
  
  <pre><code>x2    = np.arange(-4.*np.pi, 4.*np.pi, 1009)
  dat2  = np.sin(x2)
  </code></pre>
  
  <p>The time it takes to run still doesn't change so drastically!</p>
  
  <pre><code>%timeit np.fft.fft(dat2)
  100000 loops, best of 3: 12.2 µs per loop
  </code></pre>
  
  <p>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?</p>
  
  <p><strong>EDIT:</strong> I was supposed to use <code>np.linspace</code> rather than <code>np.arange</code>. Below are the timing results using <code>linspace</code></p>
  
  <pre><code>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
  </code></pre>
  
  <p>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?</p>