Эффективные векторные операции линейной алгебры в Common Lisp, особенно SBCL? - PullRequest
Новая
       25

Эффективные векторные операции линейной алгебры в Common Lisp, особенно SBCL?

7 голосов
/ 02 декабря 2011

Программа, представленная ниже, кажется очень неэффективной.Это занимает до 28,980 GC времени, в отличие от 6,361 секунды без GC, с 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 (x y z)
  (declare (optimize (speed 3) (safety 0)))
  (make-array 3 :element-type 'double-float
                :initial-contents (list x y z)))

(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-+ (a b)
  (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 (x y)
  (make-array (* x y) :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)

Есть ли какой-либо подход к вычислениюэто более эффективно, сохраняя абстракцию vec3?

Например, реализация преобразования Worker / Wrapper с помощью макроса может устранить константы vec3.

В качестве другого способа создание пула консолей для vec3 уменьшитсяраспределение памяти.

В идеале было бы неплохо, чтобы SBCL поддерживал не дескрипторные представления для некоторой структуры данных, такой как vec3, в качестве элементов массива.

1 Ответ

5 голосов
/ 02 декабря 2011

Я думаю, что в этих ситуациях использование макросов может быть хорошей идеей. Далее, я бы всегда стеснялся объявлять (безопасность 0), это приводит к очень незначительному приросту производительности и может привести к странному поведению, если только код внутри defun, но также и весь код, вызывающий defun, не совсем корректен.

Мне кажется, здесь важно не создавать новый объект списка в make-vec3. Я прилагаю довольно быструю и грязную оптимизацию вашего кода. На моей машине оригинальный код работает в 

; 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

и моя версия запускается в 

; 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

Это использует Аллегро. YMMV на других губах. Вы упоминаете объединение conses / memory для массивов vec3, и я думаю, что повторное использование этих объектов, т.е. их деструктивное изменение, является хорошей идеей, когда у вас есть возможность сделать это. На моем lisp vec3 занимает 64 байта, что немного ... Еще одна полезная вещь, конечно, это вызвать профилировщик, чтобы увидеть, где тратится время. Кроме того, в этих сложных математических задачах важно, чтобы ссылки на массивы и арифметика были максимально открытыми. Mosts lisp может (дизассемблировать 'my-function), что дает хорошее представление о том, действительно ли эти операции были с открытым кодом или если вызывается среда выполнения. 

(deftype vec3 () '(simple-array double-float (3)))

(declaim (optimize (speed 3) (debug 0) (safety 1)))

(defmacro make-vec3 (x y z)
  `(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-+ (a b)
  (declare (type vec3 a b))
  (make-vec3 (+ (vec3-x a) (vec3-x b))
             (+ (vec3-y a) (vec3-y b))
             (+ (vec3-z a) (vec3-z b))))

(defun image (x y)
  (make-array (* x y) :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))))
...