Optimierung einfach Common Lisp gibbs Sampler-Programm

Question

Als Übung schrieb ich das Beispielprogramm im Blogpost Gibbs sampler in various languages (revisited) von Darren Wilkinson um.

Der Code erscheint unten. Dieser Code läuft auf meinem (5 Jahre alt) Maschine in etwa 53 Sekunden mit SBCL 1.0.56, ein Kern Bild mit BUILDAPP erstellen, und dann läuft es mit

time ./gibbs > gibbs.dat 

Da dies, wie die Zeitpunkte für die berechnet wurden die anderen Sprachen in der Post, ich dachte, ich würde etwas Vergleichbares tun Der C-Code in der Post läuft in rund 25 Sekunden. Ich möchte versuchen, den Lisp-Code wenn möglich zu beschleunigen.

############################## 
gibbs.lisp 
############################## 
(eval-when (:compile-toplevel :load-toplevel :execute) 
    (require :cl-rmath) (setf *read-default-float-format* 'double-float)) 

(defun gibbs (N thin) 
    (declare (fixnum N thin)) 
    (declare (optimize (speed 3) (safety 1))) 
    (let ((x 0.0) (y 0.0)) 
    (declare (double-float x y)) 
    (print "Iter x y") 
    (dotimes (i N) 
     (dotimes (j thin) 
    (declare (fixnum i j)) 
    (setf x (cl-rmath::rgamma 3.0 (/ 1.0 (+ (* y y) 4)))) 
    (setf y (cl-rmath::rnorm (/ 1.0 (+ x 1.0)) (/ 1.0 (sqrt (+ (* 2 x) 2)))))) 
     (format t "~a ~a ~a~%" i x y)))) 

(defun main (argv) 
    (declare (ignore argv)) 
    (gibbs 50000 1000)) 

Dann baute ich die ausführbare gibbs mit sh gibbs.sh mit gibbs.sh als

################## 
gibbs.sh 
################## 
buildapp --output gibbs --asdf-tree /usr/share/common-lisp/source/ --asdf-tree /usr/local/share/common-lisp/source/ --load-system cl-rmath --load gibbs.lisp --entry main 

I 6 Notizen Compiler erhalten Aufruf, wenn sie mit SBCL 1.0.56, Kompilieren, die unten zu reproduzieren. Ich bin mir nicht sicher, was ich mit ihnen machen soll, aber wäre dankbar für Hinweise.

; compiling file "/home/faheem/lisp/gibbs.lisp" (written 30 MAY 2012 02:00:55 PM): 

; file: /home/faheem/lisp/gibbs.lisp 
; in: DEFUN GIBBS 
;  (SQRT (+ (* 2 X) 2)) 
; 
; note: unable to 
; optimize 
; due to type uncertainty: 
; The result is a (VALUES (OR (DOUBLE-FLOAT 0.0) (COMPLEX DOUBLE-FLOAT)) 
;       &OPTIONAL), not a (VALUES FLOAT &REST T). 

;  (/ 1.0d0 (SQRT (+ (* 2 X) 2))) 
; 
; note: unable to 
; optimize 
; due to type uncertainty: 
; The second argument is a (OR (DOUBLE-FLOAT 0.0) 
;        (COMPLEX DOUBLE-FLOAT)), not a (COMPLEX 
;                DOUBLE-FLOAT). 
; 
; note: forced to do static-fun Two-arg-/ (cost 53) 
;  unable to do inline float arithmetic (cost 12) because: 
;  The second argument is a (OR (DOUBLE-FLOAT 0.0) (COMPLEX DOUBLE-FLOAT)), not a DOUBLE-FLOAT. 
;  The result is a (VALUES (OR (COMPLEX DOUBLE-FLOAT) (DOUBLE-FLOAT 0.0)) 
;        &OPTIONAL), not a (VALUES DOUBLE-FLOAT &REST T). 

;  (CL-RMATH:RGAMMA 3.0d0 (/ 1.0d0 (+ (* Y Y) 4))) 
; 
; note: doing float to pointer coercion (cost 13) 

;  (SQRT (+ (* 2 X) 2)) 
; 
; note: doing float to pointer coercion (cost 13) 

;  (CL-RMATH:RNORM (/ 1.0d0 (+ X 1.0d0)) (/ 1.0d0 (SQRT (+ (* 2 X) 2)))) 
; 
; note: doing float to pointer coercion (cost 13) 
; 
; compilation unit finished 
; printed 6 notes 

; /home/faheem/lisp/gibbs.fasl written 
; compilation finished in 0:00:00.073 

UPDATE 1: Rainer Joswig's answer wies darauf hin, dass das Argument der SQRT negativ sein könnte, die die Quelle der obskuren Compiler Notizen war ich sah, nämlich

The result is a (VALUES (OR (DOUBLE-FLOAT 0.0) (COMPLEX DOUBLE-FLOAT)) 
    ;       &OPTIONAL), not a (VALUES FLOAT &REST T). 

Der Compiler beschwerte sich, dass da es nicht wusste, ob der Wert des Arguments positiv war, konnte das Ergebnis eine komplexe Zahl sein. Da im Beispiel der Wert x eine Stichprobenvariable aus der Gammaverteilung ist, ist er immer größer als 0. Es wurde von Stephan in der SBCL-Benutzer-Mailingliste hilfreich hervorgehoben (siehe zweite Nachricht im Thread "Optimizing a simple Common Lisp Gibbs sampler program") könnte dies, indem er erklärt x gelöst werden, dass sie größer als oder gleich Null wie folgt

(declare (type (double-float 0.0 *) x)) 

die Common Lisp Hyperspec Siehe für die entsprechende Dokumentation über FLOAT types und Interval Designators.

Thi s scheint den Code etwas zu beschleunigen. Es ist jetzt zuverlässig unter 52 Sekunden, aber immer noch nicht viel von einem Gewinn. Dies lässt auch die Hinweise über

note: doing float to pointer coercion (cost 13) 

Wenn dies aus irgendeinem Grund nicht reparierbar ist, würde ich wissen, warum mögen. Auch eine Erklärung dessen, was die Note bedeutet, wäre unabhängig davon interessant. Spezifisch, was bedeutet das Wort pointer hier? Ist das mit der Tatsache verbunden, dass C-Funktionen aufgerufen werden? Auch scheint Kosten 13 nicht sehr nützlich. Was wird gemessen?

Auch Rainer schlug vor, dass es möglich sein könnte, Consing zu reduzieren, was die Laufzeit reduzieren könnte. Ich weiß nicht, ob eine Reduzierung entweder möglich ist, oder ob es die Laufzeit reduzieren würde, aber ich würde mich für Meinungen und Ansätze interessieren. Insgesamt scheint es nicht viel zu tun, um die Leistung dieser Funktion zu verbessern. Vielleicht ist es zu klein und einfach.

Answer 1

Beachten Sie, dass Common Lisp einen speziellen Operator THE hat. Sie können Typen für Ausdrucksergebnisse deklarieren. So können Sie zum Beispiel Arten eingrenzen, wenn möglich.

Zum Beispiel was ist das Ergebnis (SQRT somefloat)? Es kann ein Float sein, aber es könnte eine komplexe Zahl sein, wenn somefloat negativ ist. Wenn Sie wissen, dass einige Float immer positiv ist (und nur dann), dann könnten Sie (the double-float (sqrt somefloat)) schreiben. Der Compiler kann dann möglicherweise effizienteren Code generieren.

Beachten Sie auch, dass Common Lisp OPTIMIZE Deklarationen hat. Wenn Sie schnellsten Code möchten, müssen Sie sicherstellen, dass Sie sie entsprechend einstellen. Möglicherweise nur für einzelne Funktionen. Normalerweise ist es besser, als die Optimierung global zu ändern, um sehr aggressiv zu sein.

Common Lisp hat eine Funktion DISASSEMBLE, mit der Sie den kompilierten Code betrachten können.

Dann gibt es das Makro TIME. Interessante Informationen, die Sie daraus erhalten, schließen ein, wie viel es kostet. Bei der Double-Float-Arithmetik gibt es wahrscheinlich eine große Menge an Consing. Es wäre sinnvoll, auf der SBCL-Mailingliste nach Hilfe zu fragen. Vielleicht kann Ihnen jemand sagen, wie Sie das vermeiden können.

Answer 2

Dies funktioniert für mich:

(sqrt (the (double-float 0d0) (+ (* 2d0 x) 2d0)))