Re: More on compiler optimization

> On 12 Feb 2025, at 20:21, Paul Werkowski (as pw at snoopy dot qozzy dot com) <[email protected]> wrote:
> 
> My implementation is attached for the readers entertainment. Compiling the file will produce, in the :FFT package, CFFT-DOUBLE-FLOAT & CFFT-SINGLE-FLOAT.

I had a look at the code, it appears that you are doing the bit reversal sort the old school, by swapping the array elements physically over a series of passes. This is actually quite a heavy procedure (due to thrashing the RAM excessively) and it should be possible to speed it up by computing the bit reversal positions of the indices in the array directly, using this bit shuffling trick from C, for example:

uint32_t reverse_bits(uint32_t n){
 n = ((n & 0xFFFF0000) >> 16) | ((n & 0x0000FFFF) << 16);
 n = ((n & 0xFF00FF00) >> 8)  | ((n & 0x00FF00FF) << 8);
 n = ((n & 0xF0F0F0F0) >> 4)  | ((n & 0x0F0F0F0F) << 4);
 n = ((n & 0xCCCCCCCC) >> 2)  | ((n & 0x33333333) << 2);
 n = ((n & 0xAAAAAAAA) >> 1)  | ((n & 0x55555555) << 1);

 return n; 
}

Additionally, if you are deploying on the ARM64 platform (including Apple’s M series), there is a CPU instruction for that, which is multiple times faster as the above, however you would need to use a foreign callable for that (and you’d better batch the calls together, obviously):

#include <arm_neon.h>  // For ARM intrinsics 
uint32_t reverse_bits(uint32_t n){ 
  // Explicitly use RBIT instruction 
  return __builtin_bitreverse32(n); 
}

Using it I was seeing speed of 100 picoseconds per reversal in vectorised code, which is 1/3 of a single clock cycle (yes, that is right) on M1 but it should show a similar improvement on all arm64 platforms. For some strange reason x64 does not have such an instruction so there one has to rely on the bit shuffling approach, although one can get very decent timings with it too, especially given that desktop x64 CPUs can go over 5GHz in clock speed nowadays.

Of course if your goal is to implement the entire FFT in lisp the intrinsic above won’t do, but the bit shuffling approach should work. Also, in some cases you may be able to skip the bit reversal altogether and do the FFT on an unscrambled array, for example, when you are intending to do convolution in the time domain by doing multiplication in the frequency domain.