Re: LW compiler optimizations

I ran my set of tests on Win/11 with an AMD Rizen 5000 processor this morning. I’m seeing just slightly more terse compiler translation, from Lisp to native code, with the Intel instruction set, compared to the compiled ARM code on the Apple M1 processor. This could also be a result of RISC vs CISC comparisons.

My C code on the AMD did not make use of MMX low-grade SIMD, and yielded about half the performance we see in Apple’s vDSP. But I did use open-coded loops in the C code to boost scalar performance and minimize looping overhead. This is a trick frequently used by compiler writers, like the Oregon Group in C.

On the AMD machine my C timings were 0.66 μs/MAC pair vs 0.42 μs/MAC pair for M1 vDSP. There may well be a speed of CPU difference involved here too. But I think we are also looking at the difference between open coded scalar computations in my C code, versus possible low-grade SIMD in vDSP. (??)

My best Lisp timing was about 1.1 ns/MAC pair on AMD, versus 1.4 μs/MAC pair on M1.  That shows the two machines to be competitive. These numbers are close enough, in my mind, to consider them equal. Variations in cache configurations, background task loads, etc, might well make a ±20% variation in timings on any one machine. But my timings also indicate a realistic performance in live settings.

Overall, the biggest takeaway, for me, in writing efficient Lisp code, is to maximize the possibility for SIMPLE-1D-ARRAY of specialized types, use in-line index offset calculations, instead of compound looping, e.g.:

Use  

    (dotimes (ix nel)
      (declare (fixnum ix))
      (setq sum
            (+ sum
               (* (aref fir ix)
                  (aref vec (+ ix start2))))  ;; <— inline offset calculation
            ))


instead of

    (loop for ix fixnum from 0 below nel
          for jx fixnum from start2
          do
            (setq sum
                  (+ sum
                     (* (aref fir ix)
                        (aref vec jx)))  ;; <— offset computed in compound LOOP
            ))

                    
The compound loop is 2-3x slower than the direct DOTIMES code.

And avoid the inherent displaced array opportunities presented by Common Lisp. Tim recognized this cost, and created his own specialized macro for these restricted kinds of displaced arrays.

I’m happy that in many cases, Lisp can produce very competitive code. But for the most important primitives across large collections, nothing can beat specialized library routines.

I have one other routine, apart from FIR filtering and FFT’s, that could really use some low level boost - heterodyning, where you multiply each element of a vector by a rotating complex phasor with fixed increment in the phase between every point. I haven’t found a vDSP routine that can directly handle that situation.

- DM


> On Jan 15, 2025, at 05:42, Yuri Davidovsky (as work at disclosure dot ie) <[email protected]> wrote:
> 
> 
>> On 14 Jan 2025, at 18:47, Tim Bradshaw (as tfb at tfeb dot org) <[email protected]> wrote:
>> 
>> I added some more variants since yesterday, and with the best of them LW is not slower than SBCL and neither is slower than C (or than my C): both are about 0.94ns/step on my M1 machine
> 
> Ok, I did a good bit of testing of the code provided this morning. I concentrated on the native LW performance, but also tested the FLI versions, as well as testing the compiled executable of the C code used for the dynamic lib. I did not test the code in SBCL, but I am not seeing any reasons why it would be producing worse results that LW on my machine.
> 
> On M1 I am seeing pretty much exact the same results as Bradshaw demonstrated, both the native lisp versions, as well as the FLI versions. The testing was done allocating two 1M element arrays of double floats and doing 1000 iterations like so:
> 
> (defvar u (make-array 1000000 ;1M
>                       :element-type 'double-float
>                       :allocation :pinnable
>                       :initial-element 1.0d0))
> (defvar v (make-array 1000000 ;1M
>                       :element-type 'double-float
>                       :allocation :pinnable
>                       :initial-element 2.0d0))
> 
> (time (dot-offset u v 0 0 1000000 1000)) ;1B operations
> 
> 
> 
> Essentially we are doing 1B pair operations. This number is chosen because the output of the time function will give you the nanosecond values per pair, like so:
> 
> Elapsed time =        1.110
> 
> Since elapsed time here is 1.1 seconds approx, it means that a single operation will take 1 billionth of that, or 1.1 nanosecond. The results were these:
> 
> dot-offset-dotimes:
> User time    =        1.121
> System time  =        0.004
> Elapsed time =        1.110
> Allocation   = 160648 bytes
> 27 Page faults
> GC time      =        0.000
> 
> dot-offset-avoid-addition
> User time    =        3.481
> System time  =        0.017
> Elapsed time =        3.463
> Allocation   = 174160 bytes
> 37 Page faults
> GC time      =        0.000
> 
> dot-offset-do
> User time    =        0.974
> System time  =        0.005
> Elapsed time =        0.965
> Allocation   = 177776 bytes
> 53 Page faults
> GC time      =        0.000
> 
> dot-offset-do-u2
> User time    =        0.970
> System time  =        0.003
> Elapsed time =        0.961
> Allocation   = 157544 bytes
> 1 Page faults
> GC time      =        0.000
> 
> dot-offset
> User time    =        0.971
> System time  =        0.004
> Elapsed time =        0.957
> Allocation   = 158672 bytes
> 12 Page faults
> GC time      =        0.000
> 
> dot-offset-smarter
> User time    =        0.956
> System time  =        0.003
> Elapsed time =        0.945
> Allocation   = 161200 bytes
> 20 Page faults
> GC time      =        0.000
> 
> 
> At 3.2GHz clock of the M1 CPU that means that a single pair operation takes about 3 clock cycles — you probably won’t be able to significantly exceed that without using the SIMD instructions, which should improve it to a single cycle per operation, but that won’t be possible to do in LW (at this time) and foreign code would need to be used.
> 
> These tests have solidly confirmed an old claim that in fact C-like performance can be achieved in Common Lisp. It takes some work, but it is doable and apart from some fringe cases (like the confusing results in dot-offset-avoid-addition) it can in fact show comparable performance. Up to this point I have never seen anyone testing this claim and at some stage started to consider it a myth. 
> 
> I found this discussion and testing experience rather enlightening, my understanding of how to optimise Lisp code was rather hazy at best before it, and at this stage I think I have a very solid grasp on how it is done.
> 
> It also needs to be highlighted that the code that was used while looking much like a synthetic benchmark is nothing of the sort, as dot product calculation is a fundamental operation in neural nets, as well as in a host of DSP stuff. If you can get this one operation run as fast as it can you have probably addressed the biggest potential bottleneck in your algorithm.
> 
> Also, I compiled the provided C functions to see what their barebone executable performance would be like and it showed a marginal difference to both the native Lisp and FLI versions, literally hundredths of a nanosecond:
> 
> Benchmarking with:
> Array size: 1000000
> Iterations: 1000
> Runs: 5
> 
> Original dot_offset:
>   Average time: 937410.40 microseconds
>   Operations per second: 1066.77 million
>   Result checksum: 622056.2
> 
> Optimized dot_offset_smarter:
>   Average time: 936505.40 microseconds
>   Operations per second: 1067.80 million
>   Result checksum: 622056.2
> 
> 
> 
> 
>