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