I released version 1.2 of my Common Lisp Fourier Transform library today. It is significantly faster than the old version. On my MacBook Pro in SBCL 1.0.30 with a 512 by 512 by 16 array, version 1.2 takes 9.77 seconds where version 1.0 took 25.31 seconds. Version 1.2 consed 2.4M while version 1.0 consed 7.4M. Neither version should have to cons nearly that much, so there’s still work to be done.
This release is significantly faster under Clozure64 1.3-r11936, too. For a 512 by 512 array, version 1.2 takes 2.72 seconds (single-threaded) and 2.07 seconds (multi-threaded) where version 1.0 took 4.45 seconds (single-threaded) and 3.06 seconds (multi-threaded).
My library is still about 1/2 to 1/3 the speed of Bordeaux FFT and still allocates memory in situations that Bordeaux does not. Hopefully, I can close those gaps most of the way soon.
Is it true that the sample matrix is the same between SBCL and Clozure? Since in the SBCL phrase you mention an additonal x16 that is not in the Clozure.
If that is true, does that mean that Clozure is faster than SBCL?
No, I didn’t bother mentioning that the 512 by 512 in SBCL runs in about 0.25 seconds. And, I never bothered waiting for the 512 by 512 by 16 with Clozure… but here it is… the 512 by 512 by 16 in Clozure takes 131.71 seconds (single-threaded).
To be fair, I know there are different ways to declare things so that Clozure knows more of the data types. I haven’t spent any time yet trying to make the Clozure run faster. I’ve been focused on the SBCL until now.
Actually, I just kicked my memory-allocation problem with SBCL, so I will probably release a new version tomorrow that does the 512 by 512 in 0.14 seconds under SBCL and does the 512 by 512 by 16 in 3.79 seconds (which used to takes more than 9 seconds in version 1.2 and took more than 25 seconds in version 1.0). The latest version does a 1,048,576 in 0.73 seconds. Bordeaux-FFT does it in 0.57 seconds. So, I’m pretty close now… especially considering where I started.
I’ll have to look and make sure I’m still spitting out the right answers. If so, then I’ll get this released tomorrow and start working on optimizing for other Lisp implementations. I’ll push it to git right now though.
For that matter, I should probably rebuild Clozure under Snow Leopard. I also need to get ECL and CMUCL and such running again since I’ve installed Snow Leopard.