Re: LW compiler optimizations

> 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