Matrix-Multiplikation in Common Lisp

Question

Ich schreibe das Programm in CL (mit SBCL 1.2.15), die lineare Algebra verwendet. Während der Ausführung multipliziert es oft eine Matrix mit einem Vektor.

Profiler zeigte, dass die meiste Zeit (80%) das Programm genau das tut, multipliziert Matrix mit Vektor. Es zeigt auch, dass diese Funktion sehr viel kostet (80.000.000 für ~ 100 Aufrufe für 100x100 Matrizen), was ebenfalls GC auslöst. Wenn Sie in F # etwas Ähnliches getan haben (das hat den Vorteil, dass statische Typen überprüft werden, aber SBCL normalerweise nicht übertrifft), läuft das F # -Programm 10-mal schneller.

Mache ich es falsch?

(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. Ich habe auch versucht, DOTIMES anstelle von inneren LOOP zu verwenden - kein Unterschied

PPS. Die nächste Option kann BLAS von CL verwenden, aber (i) Ich freue mich nicht darauf, dass es unter Windows funktioniert, (ii) muss Marshalling-Matrizen/Vektoren hin und her übertragen werden.

Answer 1

Das übliche Problem ist, dass Float-Arithmetik, hier mit Double-Floats, (unabhängig vom umgebenden Code wie Matrixmultiplikation) verzerrt.

Im allgemeinen ist das erste, was mit SBCL in solchen Fällen zu tun:

den Code in einer Datei speichern, und es

Der Compiler kompiliert wird dann ausgegeben viele Optimierungsprobleme, da ein compiliert für Geschwindigkeit. Sie müssten dann die Notizen untersuchen und sehen, was Sie tun können.

Hier fehlt zum Beispiel die LOOP Summe Typ Informationen.

Es gibt tatsächlich eine LOOP Syntax, um den Typ der Summenvariablen zu deklarieren. Ich weiß nicht, ob SBCL davon profitiert:

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

SBCL 1.3.0 auf 32-Bit-ARM für Ihren Code:

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