Common Lisp中的矩阵乘法

Question

我正在使用线性代数的CL(使用SBCL 1.2.15)编写程序.在执行过程中,它通常将矩阵乘以向量.

Profiler显示,程序花费的大部分时间(80%)正是这样做的,将矩阵乘以向量.它还表明该函数可以进行大量的处理(对于100x100矩阵,可以进行大约100次调用),这也会触发GC.在F#中做了类似的事情(它具有静态类型检查的好处,但通常不会超过SBCL),F#程序的运行速度提高了10倍.

我做错了吗？

(defun matrix-mul (matrix vector dest)
  "Multiply MATRIX by VECTOR putting the result into DEST.
Optimized for DOUBLE-FLOAT vectors and matrices"
  (declare (type (array double-float (* *)) matrix)
           (type (vector double-float *) vector dest)
           (optimize (speed 3) (debug 0) (safety 0)))
  (destructuring-bind (rows cols) (array-dimensions matrix)
   (dotimes (i rows)
     (setf (aref dest i)
           (loop for j below cols sum (the double-float
                                           (* (aref matrix i j) (aref vector j))))))))

PS.我也尝试过使用DOTIMES而不是内部循环 - 没有区别

PPS.下一个选项可以使用CL中的BLAS,但是(i)我不期待它在Windows上运行,(ii)需要来回编组矩阵/向量.

Answer 1

通常的问题是浮点运算,这里有双浮点数(独立于周围代码,如矩阵乘法).

在这种情况下,通常首先要做的是SBCL:

将代码放入文件并进行编译

然后,编译器将输出许多优化问题,因为编译速度.然后,您需要检查注释并查看可以执行的操作.

这里例如LOOP总和缺少类型信息.

实际上有一种LOOP语法来声明sum变量的类型.我不知道SBCL是否利用了这个:

(loop repeat 10
      sum 1.0d0 of-type double-float)

用于代码的32位ARM上的SBCL 1.3.0:

* (compile-file "/tmp/test.lisp")

; compiling file "/tmp/test.lisp" (written 13 DEC 2015 11:34:26 AM):
; compiling (DEFUN MATRIX-MUL ...)
; file: /tmp/test.lisp

1)

; in: DEFUN MATRIX-MUL
;     (SETF (AREF DEST I)
;             (LOOP FOR J BELOW COLS
;                   SUM (THE DOUBLE-FLOAT (* # #))))
; --> LET* FUNCALL SB-C::%FUNCALL (SETF AREF)
; ==>
;   (SB-KERNEL:HAIRY-DATA-VECTOR-SET ARRAY SB-INT:INDEX SB-C::NEW-VALUE)
;
; note: unable to
;   avoid runtime dispatch on array element type
; due to type uncertainty:
;   The first argument is a (VECTOR DOUBLE-FLOAT), not a SIMPLE-ARRAY.

2)

;     (AREF MATRIX I J)
; --> LET*
; ==>
;   (SB-KERNEL:HAIRY-DATA-VECTOR-REF ARRAY SB-INT:INDEX)
;
; note: unable to
;   avoid runtime dispatch on array element type
; due to type uncertainty:
;   The first argument is a (ARRAY DOUBLE-FLOAT (* *)), not a SIMPLE-ARRAY.

3)

;     (AREF VECTOR J)
; ==>
;   (SB-KERNEL:HAIRY-DATA-VECTOR-REF ARRAY SB-INT:INDEX)
;
; note: unable to
;   avoid runtime dispatch on array element type
; due to type uncertainty:
;   The first argument is a (VECTOR DOUBLE-FLOAT), not a SIMPLE-ARRAY.

4)

;     (LOOP FOR J BELOW COLS
;           SUM (THE DOUBLE-FLOAT (* (AREF MATRIX I J) (AREF VECTOR J))))
; --> BLOCK LET SB-LOOP::WITH-SUM-COUNT LET SB-LOOP::LOOP-BODY TAGBODY SETQ THE
; ==>
;   (+ #:LOOP-SUM-8 (THE DOUBLE-FLOAT (* (AREF MATRIX I J) (AREF VECTOR J))))
;
; note: unable to
;   optimize
; due to type uncertainty:
;   The first argument is a NUMBER, not a (COMPLEX SINGLE-FLOAT).
;
; note: unable to
;   optimize
; due to type uncertainty:
;   The first argument is a NUMBER, not a (COMPLEX DOUBLE-FLOAT).

5)

; --> BLOCK LET SB-LOOP::WITH-SUM-COUNT LET SB-LOOP::LOOP-BODY TAGBODY WHEN IF
; --> >= OR LET IF OR THE = IF
; ==>
;   (= SB-C::X SB-C::Y)
;
; note: unable to open code because: The operands might not be the same type.

6)

;     (DOTIMES (I ROWS)
;       (SETF (AREF DEST I)
;               (LOOP FOR J BELOW COLS
;                     SUM (THE DOUBLE-FLOAT #))))
; --> DO BLOCK LET TAGBODY UNLESS IF >= IF
; ==>
;   (< SB-C::X SB-C::Y)
;
; note: forced to do static-fun Two-arg-< (cost 53)
;       unable to do inline fixnum comparison (cost 4) because:
;       The second argument is a INTEGER, not a FIXNUM.
;       unable to do inline (signed-byte 32) comparison (cost 6) because:
;       The second argument is a INTEGER, not a (SIGNED-BYTE 32).
;       etc.

7)

;     (LOOP FOR J BELOW COLS
;           SUM (THE DOUBLE-FLOAT (* (AREF MATRIX I J) (AREF VECTOR J))))
; --> BLOCK LET SB-LOOP::WITH-SUM-COUNT LET SB-LOOP::LOOP-BODY TAGBODY WHEN IF
; --> >= OR LET > IF
; ==>
;   (> SB-C::X SB-C::Y)
;
; note: forced to do static-fun Two-arg-> (cost 53)
;       unable to do inline fixnum comparison (cost 4) because:
;       The second argument is a REAL, not a FIXNUM.
;       unable to do inline (signed-byte 32) comparison (cost 6) because:
;       The second argument is a REAL, not a (SIGNED-BYTE 32).
;       etc.

8)

; --> BLOCK LET SB-LOOP::WITH-SUM-COUNT LET SB-LOOP::LOOP-BODY TAGBODY SETQ THE
; ==>
;   (+ #:LOOP-SUM-8 (THE DOUBLE-FLOAT (* (AREF MATRIX I J) (AREF VECTOR J))))
;
; note: forced to do static-fun Two-arg-+ (cost 53)
;       unable to do inline float arithmetic (cost 2) because:
;       The first argument is a NUMBER, not a DOUBLE-FLOAT.
;       The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES DOUBLE-FLOAT
;                                                                &REST T).
;
; note: doing float to pointer coercion (cost 13), for:
;       the second argument of static-fun Two-arg-+
;
; compilation unit finished
;   printed 10 notes