[SciPy-dev] fft code for testing

Pearu Peterson pearu at scipy.org
Sat May 31 04:22:49 CDT 2003


On 31 May 2003, Charles R Harris wrote:

> Hi all,
> 
> here is a testing distribution of my fft code. Note that
> there is no error checking as yet for such things as
> powers of two, so use with care. The real transform
> returns results in the same form as FFTW, so can't be
> directly compared to the fftpack transforms.
> 
> I am curious as to what the benchmark results are.

Here are the results of fftwork benchmark for 
(additional notes follow below)

1) Pentium III, 2x994MHz, RedHat 7.3

                 Fast Fourier Transform
====================================================
           |    real input     |   complex input    
----------------------------------------------------
 size      |  scipy  | testing |  scipy  | testing  
----------------------------------------------------
       256 |    4.51 |    3.66 |    5.07 |    4.65  (10000 calls)
       512 |    2.88 |    2.57 |    3.82 |    3.01  (5000 calls)
      1024 |    2.11 |    1.83 |    3.03 |    2.54  (2000 calls)
      2048 |    1.73 |    1.47 |    3.14 |    2.50  (1000 calls)
      4096 |    2.11 |    1.53 |    4.40 |    3.11  (500 calls)
      8192 |    2.78 |    2.57 |    9.14 |    4.94  (200 calls)
     16384 |    5.47 |    2.45 |   10.25 |    4.84  (100 calls)
     32768 |    7.69 |    3.23 |   10.68 |    5.52  (50 calls)
     65536 |    7.15 |    3.71 |   10.25 |    6.60  (20 calls)
    131072 |    8.74 |    5.05 |   12.85 |    7.25  (20 calls)
    262144 |    8.22 |    5.20 |   12.32 |    7.06  (10 calls)
.
----------------------------------------------------------------------
Ran 1 tests in 80.806s


2) Pentium II, 400MHz, Debian Woody

                 Fast Fourier Transform
====================================================
           |    real input     |   complex input    
----------------------------------------------------
 size      |  scipy  | testing |  scipy  | testing  
----------------------------------------------------
       256 |   10.21 |    8.38 |   12.61 |   10.92  (10000 calls)
       512 |    6.01 |    5.76 |    8.01 |    8.01  (5000 calls)
      1024 |    4.30 |    4.65 |    7.33 |    6.83  (2000 calls)
      2048 |    3.71 |    4.10 |    6.21 |    6.92  (1000 calls)
      4096 |    4.05 |    4.34 |    7.63 |    7.16  (500 calls)
      8192 |    5.35 |    5.28 |    9.62 |    9.89  (200 calls)
     16384 |    7.55 |    5.66 |   10.50 |   11.01  (100 calls)
     32768 |    8.57 |    7.28 |   10.63 |   12.62  (50 calls)
     65536 |    9.15 |    8.46 |   10.18 |   12.18  (20 calls)
    131072 |    8.74 |    8.90 |   10.39 |   13.34  (20 calls)
    262144 |    8.26 |    8.53 |   10.49 |   13.02  (10 calls)
.
----------------------------------------------------------------------
Ran 1 test in 119.113s


3) Pentium II, 2 x 350MHz, Debian Woody
                 Fast Fourier Transform
====================================================
           |    real input     |   complex input    
----------------------------------------------------
 size      |  scipy  | testing |  scipy  | testing  
----------------------------------------------------
       256 |   14.93 |   11.06 |   16.77 |   13.60  (10000 calls)
       512 |    9.27 |    7.76 |   10.96 |   10.58  (5000 calls)
      1024 |    7.89 |    5.49 |    9.09 |   10.28  (2000 calls)
      2048 |    7.04 |    5.76 |    9.09 |   12.23  (1000 calls)
      4096 |    7.46 |    6.75 |    8.69 |   11.74  (500 calls)
      8192 |    6.77 |    7.72 |    8.74 |   12.19  (200 calls)
     16384 |    6.92 |    7.23 |   10.32 |   12.45  (100 calls)
     32768 |    7.92 |    7.81 |   10.80 |   14.38  (50 calls)
     65536 |    9.29 |    8.81 |   11.90 |   14.58  (20 calls)
    131072 |    9.13 |   10.04 |   10.68 |   15.47  (20 calls)
    262144 |    8.84 |    9.91 |   11.74 |   15.10  (10 calls)
.
----------------------------------------------------------------------
Ran 1 test in 144.140s

4) Athlon 2600, Debian Woody

                 Fast Fourier Transform
====================================================
           |    real input     |   complex input    
----------------------------------------------------
 size      |  scipy  | testing |  scipy  | testing  
----------------------------------------------------
       256 |    2.04 |    1.34 |    2.25 |    1.69  (10000 calls)
       512 |    1.25 |    0.94 |    1.31 |    1.19  (5000 calls)
      1024 |    0.77 |    0.70 |    0.99 |    1.06  (2000 calls)
      2048 |    0.58 |    0.58 |    0.90 |    1.02  (1000 calls)
      4096 |    0.53 |    0.53 |    0.88 |    0.94  (500 calls)
      8192 |    1.02 |    0.68 |    2.91 |    1.35  (200 calls)
     16384 |    1.76 |    1.20 |    3.46 |    2.26  (100 calls)
     32768 |    2.76 |    1.70 |    3.46 |    2.82  (50 calls)
     65536 |    3.44 |    1.93 |    4.06 |    3.03  (20 calls)
    131072 |    3.46 |    2.43 |    3.79 |    3.27  (20 calls)
    262144 |    3.30 |    2.57 |    3.82 |    3.36  (10 calls)
.
----------------------------------------------------------------------
Ran 1 tests in 36.190s


Notes:
------
1) When running benchmarks multiple times, then the variance
   of results seem to vary from 0.1 to 0.5 for increasing size.
2) In all cases scipy.fftpack uses FFTW.
3) fftwork appears to be faster than scipy.fftpack on faster machines.
   Considering the variance of test results, fftwork and scipy (using
   FFTW) have comparable performance.

In conclusion, I think it makes sense working further with fftwork
in order to speed up power-of-two fft for those scipy users 
who don't/won't have fftw libraries installed.
Integration of fftwork with scipy.fftpack should be very
similar to how djbfft is wrapped by scipy.fftpack. I'll
try making the corresponding patch later on.

Btw, does anybody know an efficient way how to test if
an integer is a power-of-two in C? Currently djbfft wrapper
uses
  switch (n) {
    case 2:;case 4:;... case 8192: ..
  }
but there must be a better way.

Chuck, do you have write access to scipy CVS? 
If not, can this be arranged?

Thanks,
	Pearu






More information about the Scipy-dev mailing list