[NumPy-Tickets] [NumPy] #1266: Extremely long runtimes in numpy.fft.fft

[NumPy Trac]

#1266: Extremely long runtimes in numpy.fft.fft
-----------------------+----------------------------------------------------
 Reporter:  koehler    |       Owner:  somebody
     Type:  defect     |      Status:  new     
 Priority:  normal     |   Milestone:          
Component:  numpy.fft  |     Version:  1.1     
 Keywords:             |  
-----------------------+----------------------------------------------------

Old description:

> Although the documenttation of numpy.fft.fft states that:
> "This is most efficient for n a power of two. This also stores a cache of
> working memory for different sizes of fft's, so you could theoretically
> run into memory problems if you call this too many times with too many
> different n's." ,I think that it may be important to report this oddity
> in the fft runtime.
> Dependent on the array length, the fft runtime varies really extreme:
> [ipython shell, from numpy import *]
> In [1]: %time fft.fft(zeros(119516))
> CPU times: user 22.83 s, sys: 0.39 s, total: 23.23 s
> Wall time: 23.53 s
>
> In [3]: %time fft.fft(zeros(119517))
> CPU times: user 36.33 s, sys: 0.08 s, total: 36.40 s
> Wall time: 36.51 s
>
> In [5]: %time fft.fft(zeros(119518))
> CPU times: user 4.88 s, sys: 0.08 s, total: 4.96 s
> Wall time: 5.02 s
>
> In [7]: %time fft.fft(zeros(119519))
> CPU times: user 0.45 s, sys: 0.00 s, total: 0.45 s
> Wall time: 0.45 s
>
> In [9]: %time fft.fft(zeros(119515))
> CPU times: user 0.07 s, sys: 0.00 s, total: 0.08 s
> Wall time: 0.08 s
>
> In [11]: %time fft.fft(zeros(119514))
> CPU times: user 15.84 s, sys: 0.06 s, total: 15.90 s
> Wall time: 15.95 s
>
> In [13]: %time fft.fft(zeros(119513))
> CPU times: user 272.75 s, sys: 1.03 s, total: 273.78 s
> Wall time: 275.63 s

New description:

 Although the documenttation of numpy.fft.fft states that:
 "This is most efficient for n a power of two. This also stores a cache of
 working memory for different sizes of fft's, so you could theoretically
 run into memory problems if you call this too many times with too many
 different n's." ,I think that it may be important to report this oddity in
 the fft runtime.
 Dependent on the array length, the fft runtime varies really extreme:
 {{{
 [ipython shell, from numpy import *]
 In [1]: %time fft.fft(zeros(119516))
 CPU times: user 22.83 s, sys: 0.39 s, total: 23.23 s
 Wall time: 23.53 s

 In [3]: %time fft.fft(zeros(119517))
 CPU times: user 36.33 s, sys: 0.08 s, total: 36.40 s
 Wall time: 36.51 s

 In [5]: %time fft.fft(zeros(119518))
 CPU times: user 4.88 s, sys: 0.08 s, total: 4.96 s
 Wall time: 5.02 s

 In [7]: %time fft.fft(zeros(119519))
 CPU times: user 0.45 s, sys: 0.00 s, total: 0.45 s
 Wall time: 0.45 s

 In [9]: %time fft.fft(zeros(119515))
 CPU times: user 0.07 s, sys: 0.00 s, total: 0.08 s
 Wall time: 0.08 s

 In [11]: %time fft.fft(zeros(119514))
 CPU times: user 15.84 s, sys: 0.06 s, total: 15.90 s
 Wall time: 15.95 s

 In [13]: %time fft.fft(zeros(119513))
 CPU times: user 272.75 s, sys: 1.03 s, total: 273.78 s
 Wall time: 275.63 s
 }}}

--

Comment(by rgommers):

 <reformat description>

-- 
Ticket URL: <http://projects.scipy.org/numpy/ticket/1266#comment:3>
NumPy <http://projects.scipy.org/numpy>
My example project