Re: More on compiler optimization

Unless I misunderstand your code, it seems interesting that you don’t pre-compute, nor memoize, twiddle factors, but rather compute the CIS of the angles on the fly.

Even the high-performance libs in C (e.g., Apple’s vDSP) use precomputed and memoized twiddles.

I also understand that your code applies specifically to Intel architecture. Does ARM behave significantly different with respect to boxing and garbage generation?




> On Feb 12, 2025, at 12:19, Paul Werkowski (as pw at snoopy dot qozzy dot com) <[email protected]> wrote:
> 
> For the the past month or so I have been searching for the cause of lisp garbage generation where compiling with (declare (:explain :boxing)) was silent. My test case was/is my Lispworks implementation of the Fast Fourier Transform (FFT) algorithm commonly used in Digital Signal Processing. I have now succeeded in creating a zero allocation (garbage) implementation.
> 
> While my implementation generates versions for both single-float and double-float data types, only the double-float version on 64-bit LW 8.0.1 fits that description.
> 
> The main thing to get zero garbage (in addition to proper type and optimize declarations) is to ensure a boxed object, like a DOUBLE-FLOAT value, does not escape the compilation environment it exist in. Such an object can exist on the heap (default), as a raw value in a typed array, or on the control stack. They may also be created by compiler internal functions. It is the later case that can only be found by examining a disassembly listing.
> 
> Finding   one of a family of names starting COMPILER::RAW-FAST-BOX- in the listing is a sure sign that an allocation is happening. Such is necessary if the boxed item is to be an argument to an external (to the compilation environment) function which is expecting a pointer an object containing the raw value.
> 
> What works is to place functions that need to efficiently pass double-float values around in local functions via FLET. Also it helps to avoid generic CL library functions such as cl:cis.
> 
>  (flet ((%%cis (x) (complex (cos x)(sin x)))) ....)
> 
> Results? On my 2016 Dell XPS 8910 with quad 4 GHZ dual core processors, a 1024 point transform executes in 40 microseconds (down from 120) with 0 bytes allocated (down from 171,728).
> 
> That is for the double-float version. A single-float version (created from same code but with double-float changed to single-float) takes 3.6 milliseconds with 687,576 bytes of garbage generated. LW 8.0.1 seems to not optimize AREFs into a typed array.
> 
> My implementation is attached for the readers entertainment. Compiling the file will produce, in the :FFT package, CFFT-DOUBLE-FLOAT & CFFT-SINGLE-FLOAT.
> 
> Enjoy!
> 
> Paul
> 
> 
> 
> 
> 
> 
> <cfft-export.lisp>


_______________________________________________
Lisp Hug - the mailing list for LispWorks users
[email protected]
http://www.lispworks.com/support/lisp-hug.html