Effective vector operations of linear algebra in Common Lisp, especially SBCL?

Question

The program below seems very inefficient. This takes 28.980 GC time, as opposed to 6.361 seconds without GC time, with SBCL 1.0.53.

(deftype vec3 () '(simple-array double-float (3))) (declaim (inline make-vec3 vec3-zero vec3-x vec3-y vec3-z vec3-+)) (defun make-vec3 (xyz) (declare (optimize (speed 3) (safety 0))) (make-array 3 :element-type 'double-float :initial-contents (list xyz))) (defun vec3-zero () (make-vec3 0.0d0 0.0d0 0.0d0)) (defun vec3-x (x) (declare (optimize (speed 3) (safety 0))) (declare (type (simple-array double-float (3)) x)) (aref x 0)) (defun vec3-y (x) (declare (optimize (speed 3) (safety 0))) (declare (type (simple-array double-float (3)) x)) (aref x 1)) (defun vec3-z (x) (declare (optimize (speed 3) (safety 0))) (declare (type (simple-array double-float (3)) x)) (aref x 2)) (defun vec3-+ (ab) (declare (optimize (speed 3) (safety 0))) (make-vec3 (+ (vec3-x a) (vec3-x b)) (+ (vec3-y a) (vec3-y b)) (+ (vec3-z a) (vec3-z b)))) ;; main (defun image (xy) (make-array (* xy) :element-type 'vec3 :initial-element (vec3-zero))) (defun add (to from val) (declare (type (simple-array vec3 (*)) to from) (type vec3 val) (optimize (speed 3) (safety 0))) (let ((size (array-dimension to 0))) (dotimes (i size) (setf (aref to i) (vec3-+ (aref from i) val))))) (defun main () (let ((to (image 800 800)) (x (make-vec3 1.0d0 1.0d0 1.0d0))) (time (dotimes (i 200) (add to to x))) (print (aref to 0)))) 

Time:

 * (main) Evaluation took: 39.530 seconds of real time 35.340237 seconds of total run time (25.945526 user, 9.394711 system) [ Run times consist of 28.980 seconds GC time, and 6.361 seconds non-GC time. ] 89.40% CPU 83,778,297,762 processor cycles 46 page faults 6,144,014,656 bytes consed #(200.0d0 200.0d0 200.0d0) #(200.0d0 200.0d0 200.0d0) 

Is there any approach to computing it in a more efficient way while preserving the abc3 abstraction?

For example, implementing a Worker / Wrapper transform using a macro may exclude vec3 conses.

As another way, creating a cons pool for vec3 will reduce memory allocation.

Ideally, it would be nice that SBCL supports descriptor-free representations for some data structure, such as vec3, as elements of an array.

Answer 1

I think using macros in these situations might be a good idea. Then I always hesitate to declare (security 0), it brings very small performance gains and can lead to strange behavior, if only the code inside defun, but also all the code that calls defun, is not completely correct.

The important thing here, I think, is not to create a new list object in make-vec3. I am applying some quick and dirty optimization of your code. On my machine, the source code works in

 ; cpu time (non-gc) 27.487818 sec user, 0.008999 sec system ; cpu time (gc) 17.334368 sec user, 0.001999 sec system ; cpu time (total) 44.822186 sec user, 0.010998 sec system ; real time 44.839858 sec ; space allocation: ; 0 cons cells, 45,056,000,000 other bytes, 0 static bytes 

and my version works in

 ; cpu time (non-gc) 4.075385 sec user, 0.001000 sec system ; cpu time (gc) 2.162666 sec user, 0.000000 sec system ; cpu time (total) 6.238051 sec user, 0.001000 sec system ; real time 6.240055 sec ; space allocation: ; 8 cons cells, 8,192,030,976 other bytes, 0 static bytes 

This is the use of Allegro. YMMV on other foxes. You mention memory / memory pooling for vec3 arrays, and I think that reusing these objects i.e. Changing them destructively is a good idea when you have the opportunity to do so. On my lisp, vec3 takes up 64 bytes, which is quite a bit ... Another useful thing is, of course, calling the profiler to find out where the time is spent. In addition, in these mathematical problems, it is important that references to arrays and arithmetic are as open as possible. Mosts lisp can (disassemble "my-function"), which gives an idea of ​​whether these operations were actually encoded or run time was running.

 (deftype vec3 () '(simple-array double-float (3))) (declaim (optimize (speed 3) (debug 0) (safety 1))) (defmacro make-vec3 (xyz) `(let ((vec3 (make-array 3 :element-type 'double-float :initial-element 0.0d0))) (setf (aref vec3 0) ,x (aref vec3 1) ,y (aref vec3 2) ,z) vec3)) (defun vec3-zero () (make-vec3 0.0d0 0.0d0 0.0d0)) (defmacro vec3-x (x) `(aref ,x 0)) (defmacro vec3-y (x) `(aref ,x 1)) (defmacro vec3-z (x) `(aref ,x 2)) (defun vec3-+ (ab) (declare (type vec3 ab)) (make-vec3 (+ (vec3-x a) (vec3-x b)) (+ (vec3-y a) (vec3-y b)) (+ (vec3-z a) (vec3-z b)))) (defun image (xy) (make-array (* xy) :element-type 'vec3 :initial-element (vec3-zero))) (defun add (to from val) (declare (type (simple-array vec3 (*)) to from) (type vec3 val)) (let ((size (array-dimension to 0))) (dotimes (i size) (setf (aref to i) (vec3-+ (aref from i) val))))) (defun main () (let ((to (image 800 800)) (x (make-vec3 1.0d0 1.0d0 1.0d0))) (time (dotimes (i 200) (add to to x))) (print (aref to 0))))