I released version 1.3 of my Common Lisp Fourier Transform library today. It is significantly faster than yesterday’s version. On my MacBook Pro in SBCL 1.0.30 with a 512 by 512 by 16 array, version 1.3 takes 3.74 seconds where version 1.2 took 9.77 seconds and version 1.0 took 25.31 seconds. For a breakdown of performance on various array sizes with various Lisp implementations, see the performance section of the library page.
Most of the speed improvement in this version came from memory improvements. Version 1.3 doesn’t cons at all in SBCL during the processing of each row. Version 1.2 inadvertently consed three rows worth of complex numbers for every row transformed.
My library is still about 25% slower than Bordeaux FFT for one-dimensional arrays. My library, however, has full support for multi-dimensional arrays where Bordeaux-FFT does not.
I also included some validation test cases using NST to this release. To try them, go to the library directory, hop in your Lisp, and load regression.lisp
.
I noticed when looking at some of the git history that you use (simple-array (complex double-float) *) type declarations when accessing one-dimensional arrays (e.g. CALCULATE-COEFFICIENTS). Your code would be faster if you used a proper declaration: (simple-array (complex double-float) (*)).
Thank you. That’s a great catch. Many of my arrays are n-dimensional, but the three that get used the most are all 1-D.
Further, I should know this because I had a heck of a time until I figured out that this was wrong:
(declare (type (simple-array fixnum 10) aa))
...)
(For those playing the home game, the 10 in the MAKE-ARRAY means an array of 10 elements, but the 10 in the DECLARE means a ten-dimensional array. Whee!)
As a comparison point, can you include timings from a FFI call to libfftw?
I spent two hours one day trying to get FFTW and the corresponding FFI library running. I gave up and wrote this. I will try to get it running again though. Everyone wants to know.