Unboxed structures (yes, again, only this time for real)

> On 7 Jan 2026, at 21:08, Martin Simmons <[email protected]> wrote:
> 
> Structure and CLOS instance slots are always boxed in LW.

With all due respect, Martin turned out to be wrong on this one.

It gives me a lot of heartache to say it, as I spent last couple of days implementing high performance custom structs based on sys:typed-aref arrays, being proud how well it was coming out, only to see that after finishing it and benchmarking it against the vanilla structs that they were both running neck to neck.

My structs are a smidge faster (~5ms for a set of 10M structs) but the performance difference may not be worth developing your own struct type. My approach was to inline all the structs into a single byte array (rather than access each one by a pointer) which is how you optimise the memory access to the T, however it appears that the LW compiler knows how to pack structs when the :type field parameter was suppled, plus it also evidently packs them into an array when doing 

(make-array +num-particles+ :element-type ‘particle)

so essentially we both ended up with the same data layout serialised into a single byte array and unsurprisingly the performance was almost identical.

What I did was an implementation of a 2D particle struct, that could be used for physics modelling, or animation, as such a model is fairly convenient for testing numerical performance. I won’t bore you with my code as it is somewhat hairy with macros writing macros (nobody has the time to detangle that, myself included), but at the end of the email you will find the vanilla struct test code to see how to get the most out of the regular Common Lisp structures.

This is the example layout of the custom particle struct definition, which is identical to the vanilla struct implementation that you will see at the end of the email:

(def-struct particle
  (:u32 id)
  (:u32 last-col-id) ; last collision particle id
  (:float x)         ; position on x axis
  (:float y)         ; position on y axis
  (:float vel-x)     ; velocity in x axis
  (:float vel-y)     ; velocity in y axis
  (:float mass 1.0)
  (:float size 1.0))

In a pinch, my custom struct benchmark code was doing this:

(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))))

Do not get confused by the naming of the set-particle-put macro and its ilk — it just means “take a PARTICLE in a SET of particles at index I, and PUT a value into its field :X). Essentially these expressions macroexpand to a bunch of type casting array accesses like this:

(SYSTEM:TYPED-AREF 'SINGLE-FLOAT PARTICLES (+ (* (THE FIXNUM I) 32) 8))

In the code above we just update the particle position according to its velocity, where dt variable is the update time frame equalling 1/60s (refresh rate of a standard office monitor, gaming ones can go up to 240Hz). For comparison, this is the main loop implemented with regular structs:

(dotimes (i (length particles))
    (let ((p (aref particles i)))
      (setf (particle-x p) (+ (particle-x p) (* (particle-vel-x p) dt)))
      (setf (particle-y p) (+ (particle-y p) (* (particle-vel-y p) dt)))))

And here is the timing results of the custom code with all the performance flags on (10M particles):

User time    =        0.041
System time  =        0.000
Elapsed time =        0.039
Allocation   = 26544 bytes
20 Page faults
GC time      =        0.000

These are the results for the native CL structs in LW (also 10M particles):

User time    =        0.033
System time  =        0.012
Elapsed time =        0.044
Allocation   = 12728 bytes
2 Page faults
GC time      =        0.000

The elapsed time (user time + system time, basically) is ~39ms (custom structs) vs ~44ms (vanilla structs) which is around 12% faster. Not entirely insignificant but I am not sure after digging in hairy array access fiddling for two days (wrapped into two backtick layers for a good measure) that it is worth it, I was expecting something more respectable, say 50% at least.

However I am curious why my code consistently shows 0ms system time against 12ms for regular structs (system time is essentially OS kernel calls), yet the number of page faults (memory requests from the OS, I think) is 20 for the custom structs and 2 for the regular structs. In theory it should not differ too much as we are processing identical amounts of data (10M structs 32 bytes each, or 320MB in total) so the memory access patterns should be less dissimilar, in my opinion. (I ran a few more tests after and actually it sometimes looks the other way around, custom structs show 2 page faults, whereas the regular ones would show 17. Nvm.)

My calculations show that at 3.2GHz clock speed of the ARM64 machine I am running it on, the struct update code takes about 12 cycles per struct, whereas I counted 10 operations in total:

1. Loading 4 registers from the stack for each struct (x, y, vel-x, vel-y fileds).
2. 2 multiplications.
3. 2 additions.
4. 2 writes back to update the x and y fields.

This means that the overhead of running the loop is another 2 cycles, which adds up — we need to increment the loop counter at each iteration (1 addition), as well as do the the loop termination check (1 comparison). As we can see, the loop is very tight, no overhead unaccounted for. The 12% overhead we have seen with the vanilla structs over the custom ones is evidently an extra cycle getting used somewhere that the custom code does not need. The cause for that is not very clear to me, but it was probably loading the particle's stack offset into a register with this LET binding:

(let ((p (aref particles i)))
    :body)

Either way, there is about zero optimisation opportunity for single threaded code here, bar resorting to SIMD computation, which would give us about 3x speedup on ARM processors (they have somewhat anaemic SIMD functionality, limited to 128 bits, or 4 single floats, wheras x64 routinely sports 256 and 512 bits wide SIMD registers). With SIMD support we could update  ~825M particles per second in our custom structure case.  Not quite a GPU type of performance, but GPUs come with their own optimisation and host program communication headaches. We could probably outdo the standard struct code by a huge margin here, because we would be easily able to optimise our struct set layout to be SIMD register friendly, while with vanilla structs you would be restricted to the sequential scalar field layout in a byte array.

Overall one could get some decent, close to native machine performance from the LW compiler with just a few basic repeatable tricks — use typed arrays, specify field types for regular structs, do not forget the compiler type and optimisation declarations, and you are good to go. I wonder why SBCL seems to outdo LW consistently on the performance front, if you believe the messages in this list, I just do not see how in this particular case it could do 2x better and this seemingly simple test case covers a lot of scalar high throughput requirements (neural nets included, although you typically do not use structs for those altogether, just packed arrays of floats).

PS: The conventional struct test code below. Note the usage of the :type parameter — evidently it instructs the compiler to pack the data fields into the body of the struct. Also note that defclass supports this parameter too — does it mean that classes can also be packed? Good news if so.

(defpackage :struct-test
  (:add-use-defaults t)
  (:use :custom))

(in-package :struct-test)

;;; ------------------------------------------------------------------
;;; 1. SETUP: Define the struct and generate data
;;; ------------------------------------------------------------------

(defconstant +num-particles+ 10000000) ; 10M structs
(defconstant +dt+ 0.016) ; 60 FPS timestep

(defstruct particle
  (id 0          :type (unsigned-byte 32))
  (last-col-id 0 :type (unsigned-byte 32))
  (x 0.0         :type single-float)
  (y 0.0         :type single-float)
  (vel-x 0.0     :type single-float)
  (vel-y 0.0     :type single-float)
  (mass 1.0      :type single-float)
  (size 1.0      :type single-float))

;; Initialize array of particles
(defparameter *particles* (make-array +num-particles+ :element-type 'particle))

(format t "Generating ~:d particles...~%" +num-particles+)
(dotimes (i +num-particles+)
  ;; should not access dynamic vars in 
  ;; tight loops like that, but anyway
  (setf (aref *particles* i) 
        (make-particle :x (random 100.0) :y (random 100.0) 
                       :vel-x (random 5.0) :vel-y (random 5.0))))

;;; ------------------------------------------------------------------
;;; 2. THE "SLOW" FUNCTION (No Inline, High Safety)
;;; ------------------------------------------------------------------

;; we explicitly prevent inlining to simulate a generic function call
(declaim (notinline particle-x particle-y particle-vel-x particle-vel-y 
                    (setf particle-x) (setf particle-y)))

(defun update-particles-slow (particles dt)
  (declare (type vector particles)
           (type single-float dt)
           (optimize (speed 1) (safety 3) (debug 3)))
  (dotimes (i (length particles))
    (let ((p (aref particles i)))
      ;; this involves function call overhead and type checking on every access
      (setf (particle-x p) (+ (particle-x p) (* (particle-vel-x p) dt)))
      (setf (particle-y p) (+ (particle-y p) (* (particle-vel-y p) dt))))))

;;; ------------------------------------------------------------------
;;; 3. THE "FAST" FUNCTION (Inlined, Unsafe)
;;; ------------------------------------------------------------------

;; restore default inlining behavior
(declaim (inline particle-x particle-y particle-vel-x particle-vel-y 
                 (setf particle-x) (setf particle-y)))

(defun update-particles-fast (particles dt)
  (declare (type (simple-array particle (*)) particles)
           (type single-float dt)
           (optimize (speed 3) (safety 0) (debug 0) (float 0)))
  (dotimes (i (length particles))
    (let ((p (aref particles i)))
      ;; compiler will replace these with direct memory offsets
      ;; It will also use CPU registers for the float math (no boxing)
      (setf (particle-x p) (+ (particle-x p) (* (particle-vel-x p) dt)))
      (setf (particle-y p) (+ (particle-y p) (* (particle-vel-y p) dt))))))

;;; ------------------------------------------------------------------
;;; 4. EXECUTION AND RESULTS
;;; ------------------------------------------------------------------

(defun test-structs nil
  (format t "~%--- STARTING NATIVE STRUCT BENCHMARK ---~%")

  ;; run GC to clear runtime noise
  (clean-down)

  (format t "~%1. Running SLOW update (Safety 3, Not Inline):~%")
  (time (update-particles-slow *particles* +dt+))

  ;; run GC again
  (clean-down)

  (format t "~2%2. Running FAST update (Speed 3, Safety 0, Inline):~%")
  (time (update-particles-fast *particles* +dt+)))