Re: More on Lisp structures performance

Wow!! Bravo !!!

You did a magnificent job! But the conclusions leave me a bit unsettled. 

> The answer is simple — by doing something (rather innocuous) to the variable, we scared the compiler into thinking that the variable is not a constant and it cannot rely on it being possible to inline at all times. So it wisely chooses to write and keep that in a register permanently instead. This
> 
> (* g-till 1)

In effect we have to diddle a var at the beginning in hopes of keeping it assigned to a register. But we don’t have any real control over register spilling, do we? What limits must we observe to ensure that the var remains in a register? Or perhaps it all comes down to disassembly and double checking that we haven’t damaged our intent...

- DM

> On Jan 23, 2026, at 09:07, Yuri Davidovsky (as work at disclosure dot ie) <[email protected]> wrote:
> 
> 
>> On 22 Jan 2026, at 15:48, Yuri Davidovsky (as work at disclosure dot ie) <[email protected]> wrote:
>> 
>> How much better we can do will be discussed in another email, but before that, does anyone believe we could break the 1B particles per second sonic boom barrier? While remaining in the scalar domain, of course (i.e. computing just one particle at a time). Take note of your guess and we’ll see if that was correct later.
> 
> In the previous episode we tested the performance of a conventional Lisp structure in LispWorks, with some decent results. However, it appears that there is still a room for improvement, as it turns out that thanks to parallel execution pipelines on the ARM64 architecture our cycle budget is not actually equal to the clock speed of the CPU, but rather
> 
> CS * Tn
> 
> where CS stands for clock speed and Tn means the number of scalar parallel execution threads. On the M1 machine that the tests were performed on, it would be
> 
> 3.2×10⁹ * 4 = 12.8×10⁹
> 
> Given that we run 12 cycles per iteration to compute a single struct (see the previous email), it follows that we should be hitting close to 1B structs of throughput every second, however we hit only slightly over 500M in the previous test. Evidently there is some substantial overhead still that we could try to eliminate. Let’s start with something simple, a macro that accesses individual struct fields in a vector of bytes created by SYS:MAKE-TYPED-AREF-VECTOR, which actually creates an array of packed double floats, presumably for the purpose of correct memory alignment on 64 bit machines:
> 
> (type-of (sys:make-typed-aref-vector 30))
> (SIMPLE-ARRAY DOUBLE-FLOAT (4))
> 
> We could simply create an array like that by 
> 
> (make-array 4 :element-type ‘double-float)
> 
> and it would work just fine. With this little intro out of the way we may now proceed onto the main processing loop of the conventional Lisp structures:
> 
> (dotimes (i +num-particles+)
>   (set-particle-put particles i :x
>                     (+    (set-particle-get particles i :x)
>                        (* (set-particle-get particles i :vel-x) dt)))
>   (set-particle-put particles i :y
>                     (+    (set-particle-get particles i :y)
>                        (* (set-particle-get particles i :vel-y) dt)))))
> 
> We discussed how the macro works previously, but the intent should be very clear anyway: we simply create a set of macros that use the I index parameter to calculate the necessary offset into the byte array and read a value of the appropriate type using SYS:TYPED-AREF, so an expression like
> 
> (set-particle-get particles i :x)
> 
> would macroexpand into something similar to 
> 
> (SYSTEM:TYPED-AREF 'SINGLE-FLOAT PARTICLES (+ (* I SIZE) OFFSET))
> 
> Setting the values will be done the same way, by wrapping the expression above into a SETF form like so
> 
> (set-particle-put particles i :x value) ->
> 
> (SETF (SYSTEM:TYPED-AREF 'SINGLE-FLOAT PARTICLES (+ (* I SIZE) OFFSET))
>       VALUE)
> 
> That would make for some good start of the macro interface design, but I would also suggest to create a custom looping construct — since somewhat complex macros will be created in the process, a lot of macroexpansion will be done during debugging, and I find that some of the standard macros in LW can be rather noisy, so here it is, short and sweet:
> 
> (defmacro for ((till &optional (var (gensym "I-")) (from 0) (by 1)) &body body)
>   (let ((g-till (gensym "G-TILL-"))
>         (g-from (gensym "G-FROM-"))
>         (g-by   (gensym "G-BY-")))
>     `(let ((,g-till ,till)
>            (,g-from ,from)
>            (,g-by   ,by))
>        (let ((,var ,g-from))
>          (declare (type (unsigned-byte 48) ,g-till ,g-from ,g-by ,var))
>          (tagbody :start (unless (< ,var ,g-till)
>                            (go :end))
>                   ,@body
>                   (setq ,var (the (unsigned-byte 48) 
>                                   (+ ,var ,g-by)))
>                   (go :start)
>                   :end)))))
> 
> For our beginner friends in Lisp on this list, the GENSYM bindings at the start of the lexical scope are needed to create variable names that won’t be captured accidentally by the BODY of code supplied to the macro. You could think of GENSYM as a random variable name generator that is baked into the language, and it is very useful when you want to avoid the problem of accidentally using (or shadowing) variables created or used by the macro the body code.
> 
> Also note the (UNSIGNED-BYTE 48) part in the variable type declaration — that is actually not a data type per se, but actually a message for the compiler saying that the variable’s value will never exceed 2⁴⁸ so we do not need a bignum check and can remain in the fixnum domain at all times to reduce overhead when doing arithmetics. This this type specifier and its likes is what I personally call type looseness in Lisp: some of the types in it are actual data types (like fixnum and single-float), but other times they are compiler constraints, like the mentioned (UNSIGNED-BYTE 48). However sometimes the compiler constraints can also act as data types too, like in this expression:
> 
> (make-array 16 :element-type '(unsigned-byte 16))
> 
> The following part is also crucial when doing arithmetic operations in Lisp when you want to avoid summoning the bignum sledgehammer:
> 
> (the (unsigned-byte 48) (+ ,var ,g-by))
> 
> While the variables VAR and G-BY were declared to be unsigned bytes of 48 bits previously, it does not guarantee that the result of an arithmetic operation of the two of them will not overflow their compiler constraints. So we need to additionally let the compiler know that the result is not going to require a bignum, hence the declaration. Such size is chosen instead of the typical 32 bits since our tests may be potentially running in billions of iterations and the 32 bit size only gives us a tad over 4×10⁹ repetitions, which may not be sufficient.
> 
> Just out of curiosity let us compare the performance of the regular DOTIMES loop to our custom FOR loop by incrementing a variable 10B times:
> 
> (defun loop-test nil
>   (let ((count-a 0)
>         (count-b 0)
>         (repeat (floor 1d10))) ; 10B times
>     (declare (type (unsigned-byte 48) count-a count-b repeat)
>              (optimize (speed 3) (safety 0) (debug 0) (float 0)))
>     (time (dotimes (i repeat)
>             (setq count-b (+ count-b 1))))
>     (time (for (repeat) 
>             (setq count-a (+ count-a 1))))
>     (values count-a count-b)))
> 
> The results are as follows:
> 
> Timing the evaluation of (DOTIMES ...)
> 
> User time    =        5.296
> System time  =        0.016
> Elapsed time =        5.282
> Allocation   = 173240 bytes
> 5 Page faults
> GC time      =        0.000
> 
> 
> Timing the evaluation of (FOR …)
> 
> User time    =        5.287
> System time  =        0.014
> Elapsed time =        5.284
> Allocation   = 43056 bytes
> 2 Page faults
> GC time      =        0.000
> 10000000000
> 10000000000
> 
> As we can see, both are running neck-to-neck, which is great news, and the macroexpand output looks a lot less noisy for the FOR construct, but just for sanity, let us check out what is going on on the machine level when the FOR loop gets assembled:
> 
> ;; setting up increment variable in register X0:
> 32  movz  x0, 0          ; accumulator COUNT-A in X0
> 36  movz  symbol{x21}, 0 ; loop counter in X21
> 
> ;; below is value construction in register X11
> ;; (this is our target number or loop cycles)
> 40  movz  tmp1{x11}, 149, lsl #16
> 44  movk  tmp1{x11}, 761
> 
> ;; loop termination check below
> ;; if (X21 - (X11 << 13) >= 0)
> 48  subs  xzr, symbol{x21}, tmp1{x11}, lsl #13
> 52  b.ge  76  ; done, go to line 76 if above is true
> 
> ;; update loop counter in X21 and accumulator in X0
> 56  add   x0, x0, #8 ; (1+ count-a) 
> 60  add   symbol{x21}, symbol{x21}, #8 ; increment loop counter
> 64  b     40 ; go back to loop start (unconditionally)
> 
> Looks very concise and down to the point, but let us have a closer look at some possibly confusing parts. Here is what we have on the following lines:
> 
> 32 — 36 : straight forward stuff, we zeroed the accumulator and the loop counter vars in registers X0 and X21.
> 40 — 44 : now this is a bit trickier, what is happening here is that we are writing a large integer value into the register X11, which takes two operations and looks (admittedly) somewhat complicated. Why can't we simply write a numeric literal like so on the ARM platform in order to put the number into the register?
> 
> MOV X11, #10000000000
> 
> Well, the truth is, we can actually do that in an assembly editor, but it will get expanded into two machine instructions like those above regardless. Why? This is so since even on the ARM64 platform the instruction size is 32 bits and only a limited number of bits are available for storing numeric literals within it, the available range being only 16 bits (if I remember correctly, it could be fewer). As such one has to resort to bit shifting and addition in order to fill up the register with the required literal value.
> 
> 48 — 52 : now we do the loop termination check comparing by subtracting the loop counter in X11 from the target number of iterations in X21. Note the lsl #13 part which means (X11 << 13). Why is it there? Two reasons:
> 
> a) we actually did not write the 10B iterations number into the register X11 but rather 
> 
> (+ (ash 149 16) 761) ; (149 << 16) + 761
> 9,765,625 ; this is what is stored in X11
> 
> b) the LSL instruction as used in the listing above is free, so now we get
> 
> (ash * 13) ; 9765625 << 13
> 80,000,000,000 ; target value 
> 
> 56 — 60 : update the counter and accumulator variables.
> 64 : branch to the beginning of the loop for a new iteration.
> 
> I can already see some hands raised about why we are incrementing the register variables by 8, rather than 1, and why we are comparing against 80B rather than 10B as planned initially? The answer is simple — fixnums. In LW each fixnum has a tag of 000, which is essentially a shift left by 3 bits, like so
> 
> 1   << 3 = 8
> 10B << 3 = 80B
> 
> This is important. This is the very reason why we can’t run our numeric computations at full tilt, which I will explain soon. But there is also another snag here that is easy to overlook, have a look at the line 64 where we branch back to the loop start at line 40. 
> 
> Once the cursor of the loop goes to this line we suddenly have to recreate the target variable from scratch on the lines 40 — 44, and we evidently have to do that every iteration. That is not right, let us have a look what is going on in our source code of the FOR loop again:
> 
>   ...
> `(let ((,g-till ,till) ; <- our 10B var
>   ...
>     (tagbody :start (unless (< ,var ,g-till) ; <- g-till var here
>                       (go :end))
>                   ,@body
> 
> What is happening here is a bit obscure — our G-TILL variable was never written to, and in such cases LW compiler appears to promote variables to constants and it inlines their values verbatim in the code. Not a big deal, right, that is only a number, isn’t it? It should also make things faster, it seems, as constants are cheap to read.
> 
> Well, yes, but on the ARM64 assembly level 80B is more than just a literal number and requires some work to have it written into the register (as we have seen above), so now we ended up recreating the value at each iteration spending 2 cycles additionally as the overhead. This is huge. If your budget is 10 cycles per iteration, 2 of those will be spent on the loop termination check instantly, creating a 20% overhead from the get-go, but now we have 2 more cycles to burn on the loop’s book-keeping. Suddenly we end up with only 6 cycles of available computation and an impressive 40% loop iteration overhead.
> 
> Something has to be done about it. Let us have a look at the quick and easy solution:
> 
> ...
> `(let ((,g-till ,till)
>        (,g-from ,from)
>        (,g-by   ,by))
>    (setq ,g-till (the (unsigned-byte 48)
>                       (* ,g-till 1))) ; <- 'bake' value into register
> ...
> 
> Now the assembly output:
> 
> 32  movz  x0, 0 ; COUNT-A in X0
> 
> ;; recreate the 80B fixnum value: note that
> ;; compiler did it differently this time
> ;; 8192 + (41055 << 16) + (18 << 32)
> 36  movz  x19, 8192
> 40  movk  x19, 41055, lsl #16
> 44  movk  x19, 18, lsl #32   ; X19 is 80B now
> 
> 48  movz  symbol{x21}, 0     ; loop counter in X21
> 
> ;; if (X21 - X19) >= 0
> 52  subs  xzr, symbol{x21}, x19 ; note lack of LSL
> 56  b.ge  80 ; finish loop if above is true
> 
> 60  add   x0, x0, #8                   ; increment COUNT-A
> 64  add   symbol{x21}, symbol{x21}, #8 ; increment counter
> 68  b     52 ; no value recreation, just a jump to check
> 
> We can verify that the target value was calculated correctly by
> 
> (+ 8192 (ash 41055 16) (ash 18 32))
> 80,000,000,000
> 
> As we can see above, the repeated recreation of the loop's iterations target is gone now, so we are back to the standard 2 cycles overhead per loop iteration. One may ask, however, what is that with this value bake-in into the register philosophy?
> 
> The answer is simple — by doing something (rather innocuous) to the variable, we scared the compiler into thinking that the variable is not a constant and it cannot rely on it being possible to inline at all times. So it wisely chooses to write and keep that in a register permanently instead. This
> 
> (* g-till 1)
> 
> expression is nowhere to be seen in the assembly output for the reason that the compiler also correctly deduces that it will not actually change the value, but it will still remain in the high alert mode. And as one final touch, let us check if this change made a difference on the performance front:
> 
> Timing the evaluation of (FOR …)
> 
> User time    =        3.152
> System time  =        0.009
> Elapsed time =        3.137
> Allocation   = 168640 bytes
> 3 Page faults
> GC time      =        0.000
> 10000000000
> 
> Yep, looks good to me. We got a 5.284 / 3.137 = 1.68, or nearly 70% improvement in performance over the vanilla DOTIMES loop. Also note that we are doing about 3B increments of an integer per second on a 3.2GHz processor, and if we include the loop counter that we also increment in parallel, that will actually make it 6B increments per second. Branching and loop termination check evidently eat 1 cycle each at every iteration, so we nicely arrive at the ~12B cycle budget we established at the beginning of this article. It does feel good when maths align, doesn’t it.
> 
> This little assembly detour took a bit longer than planned, hopefully things will pick up from here on.
> 
> Now that we have our super loop the only thing we have to worry about is actual struct data reading and writing, but things did not go according to the plan at the time (despite the super loop) and the assembly that was generated was 4 times longer than that of the regular structs we have tested already, while the performance was about half of those, at about 250M structs per second. There was evidently a huge blocker but the cause was not difficult to find with some careful examination of the assembly output and the clear culprit was this part:
> 
> (SYSTEM:TYPED-AREF 'SINGLE-FLOAT PARTICLES (+ (* I SIZE) OFFSET))
> 
> It kept generating bignum arithmetics at every invocation. That wasn’t a very difficult problem to solve, however, after a bit of trial and error the following Lisp form was devised that worked as expected:
> 
> (let ((jump (the (unsigned-byte 32) (* i index))))
>   (let ((offset (the (unsigned-byte 32) (+ jump shift))))
>     (sys:typed-aref 'single-float arr offset)))
> 
> where it solved nicely the attempts of the assembly code to whack itself on the head with the bignum sledge hammer. At that stage the performance of the custom structs exceeded that of the vanilla structs and it was mostly smooth sailing from here on. At this point in time the test code for custom structs looked like so:
> 
> (for (100)
>   (for (+num-particles+ i) ; 10B particles
>     (let ((x     (set-particle-get particles i :x))
>           (vel-x (set-particle-get particles i :vel-x))
>           (y     (set-particle-get particles i :y))
>           (vel-y (set-particle-get particles i :vel-y)))
>        (set-particle-put particles i :x (+ x (* vel-x dt)))
>        (set-particle-put particles i :y (+ y (* vel-y dt)))))))
> 
> But there was still a room for improvement. In the code above each macro expands into a calculation of the field offset during each access. Given that in the code we reference each of the :x and :y fields twice, it means that we have 2 calculations that are unnecessary, the ones like
> 
> (+ (* i struct-size) field-offset)
> 
> Which is 2 cycles each, meaning we can save 4(!) cycles per iteration. To address that we need to change our tactic a bit and create a different macro that checks its body and caches the required offsets in a lexical scope to avoid their recalculation constantly. This could look like so:
> 
> ;; particles is an array of structs
> ;; while 0 is current particle index
> (with-set-particle (particles 0) 
>   (put :x (+ (get :x) (* (get :vel-x) dt)))
>   (put :y (+ (get :y) (* (get :vel-y) dt))))
> 
> This is an example of a macro that uses as small domain specific language (DSL) of two operators:
> 
> 1. GET — read a struct value.
> 2. SET — write a struct value.
> 
> It makes for a much shorter syntax of the macro body (compare to the code block prior) but it also gives us another advantage, making the macro implementation much easier: during macroexpansion it traverses the code body and uses the names of the operators as markers for the fields whose offset needs to be calculated and cached. This would make for a basic entry in a  "100 exercises in Lisp” (section "Recursive List Processing”) type of writing and a solution could look something like this:
> 
> (let (fields)
>  (labels ((search (list) ; search for field references
>             (loop for el in list
>                   when (listp el) do
>                       (case (car el)
>                         (get (pushnew (cadr el) fields))
>                         (put (pushnew (cadr el) fields)
>                              (search (cdr (cdr el))))
>                         (t (search el))))))
>    (search body))
>   :body)
> 
> That was the most complicated part of the macro, which has a signature of 
> 
> (defmacro with-set-particle ((particle-array byte-index) &body body)
>    :body)
> 
> The output will end up looking similar to:
> 
> (LET* ((BYTE-INDEX (THE (UNSIGNED-BYTE 32) 0))
>        (X     (THE (UNSIGNED-BYTE 32) (+ BYTE-INDEX 8)))
>        (Y     (THE (UNSIGNED-BYTE 32) (+ BYTE-INDEX 12)))
>        (VEL-X (THE (UNSIGNED-BYTE 32) (+ BYTE-INDEX 16)))
>        (VEL-Y (THE (UNSIGNED-BYTE 32) (+ BYTE-INDEX 20))))
>   (MACROLET ((GET (FIELD)
>                (WHEN (KEYWORDP FIELD)
>                  (SETQ FIELD (INTERN (SYMBOL-NAME FIELD))))
>                (LET ((SPEC
>                       (ASSOC FIELD
>                              '((X SINGLE-FLOAT 8)
>                                (Y SINGLE-FLOAT 12)
>                                (VEL-X SINGLE-FLOAT 16)
>                                (VEL-Y SINGLE-FLOAT 20)))))
>                  `(SYSTEM:TYPED-AREF ',(CADR SPEC) PARTICLES ,FIELD)))
>              (PUT (FIELD VALUE)
>                  ...
>                  ; same prologue as in SET here
>                  `(SETF (SYSTEM:TYPED-AREF ',(CADR SPEC) PARTICLES ,FIELD)
>                         ,VALUE))))
>     (PUT :X (+ (GET :X) (* (GET :VEL-X) DT)))
>     (PUT :Y (+ (GET :Y) (* (GET :VEL-Y) DT)))))
> 
> That was it. At this stage we were well ahead of the vanilla structs code on the speed, but there is still room for improvement. Remember from our previous discussions that the speculative execution threads like to have independent stream of calculations in the code? We could make them happy by inlining several structs to be processed in a single cycle. We already satisfy this requirement partially by calculating each of the :x and :y fields without any interdependencies, but if we added another struct into the mix, we would be calculating 4 fields at the same time — exactly 1 field for each for the 4 threads we have on the CPU.
> 
> But there is another benefit to doing that, and more over, we could process a whole bunch of structs in a single iteration, and even without speculative threads we would still see some (potentially big) improvement. This is what loop unrolling is about, which is when a programmer serialises a part of the loop manually to reduce the total number of iterations the loop has to do, and thus reduce its overhead. Lets demonstrate it with a single example by going back to our optimised FOR iterator:
> 
> (let ((count-a 0)
>       (repeat (floor 1d10))) ; 10B times
>   (for (repeat) 
>      (setq count-a (+ count-a 1)))
>   count-a)
> 
> Each iteration requires 4 cycles:
> 
> 1. 2 integer additions (accumulator and loop counter),
> 2. 1 loop termination check,
> 3. 1 jump.
> 
> 75% tax here (only 1 cycle is used to process the payload per iteration). But what is going to happen if we do this:
> 
> (let ((count-a 0)
>       (repeat (floor 1d10))) ; 10B times
>   (for (repeat i 0 8)
>      (setq count-a (+ count-a 1)))
>      (setq count-a (+ count-a 1)))
>      (setq count-a (+ count-a 1)))
>      (setq count-a (+ count-a 1)))
>      (setq count-a (+ count-a 1)))
>      (setq count-a (+ count-a 1)))
>      (setq count-a (+ count-a 1)))
>      (setq count-a (+ count-a 1)))
>   count-a)
> 
> Here we process 8 increments, and as such the number of cycles per iteration is:
> 
> 1. 3 loop overhead cycles (increment, compare and jump),
> 2. 8 increments.
> 
> With a total of 11 cycles per iteration, but instead of 75% overhead, we now only have ~27% overhead. And if we unroll 300 iterations, suddenly our loop overhead tax is roughly 1%. That is not a small thing, reduction of overhead by a factor of 75 is substantial. And I am not the one to tell you that unrolling things using Lisp macros is an easy thing to do, something like that:
> 
> (across-particle-set (particles 10)
>   (put :x (+ (get :x) (* (get :vel-x) dt)))
>   (put :y (+ (get :y) (* (get :vel-y) dt))))
> 
> In the example above we simply create and unroll the loop body in bulks of 10 structs (iterations). Unlike in the example above, using high number of unrolled computations here is not necessarily beneficial, after about 10 one starts to hit diminishing returns and on very high count of 100 or 200 the performance begins to decrease. Not quite sure why would that be, but it is not too important in the context of the current discussion.
> 
> Here I started to run out of ideas how to optimise the algorithm further and considered it to be the destination point. At this stage the custom structure calculations ran substantially faster, and this is the timing results to confirm that:
> 
> Timing the evaluation of (UPDATE-PARTICLES ...)
> 
> User time    =        1.093
> System time  =        0.004
> Elapsed time =        1.089
> Allocation   = 20640 bytes
> 2 Page faults
> GC time      =        0.000
> NIL
> 
> We did not hit the 1B per second target, unfortunately, but got respectably close. Let us see how many cycles it costs us to run each struct update:
> 
> (* 1.089 3.2d9 1d-9)
> 
> Which makes it ~3.5 cycles per structure. However according to our estimates of the cycle budget of ~12B cycles at the beginning of the article that we have on the test bench at our disposal, in an ideal scenario of very efficient code we should be hitting around 3 cycles per struct (given that a single struct takes 10 cycles + the loop tax), so we still have around 17% overhead here that hasn’t been accounted for. What is this overhead, where does it come from, and is it possible to eliminate it, or at least reduce it enough so that we could break the 1B structs per second barrier, while remaining in LispWorks only?
> 
> And this we will find out in the next episode of our miniseries of Common Lisp code optimisation.
> 
> PS: I was planning to discuss this mysterious overhead in this email, but it just got waaaaaay too long at this stage, so let’s leave it as a subject for yet another email that will hopefully bring us to a closure.
> 
> 
> 
> 
> 
> 
>