Come esercizio, ho riscritto il programma di esempio nel post del blog Gibbs sampler in various languages (revisited) di Darren Wilkinson.ottimizzazione del semplice programma di campionamento di Gibits Lisp comune
Il codice viene visualizzato di seguito. Questo codice viene eseguito sul mio (5 anni) la macchina in circa 53 secondi, usando SBCL 1.0.56, la creazione di un'immagine di base utilizzando BUILDAPP, e poi eseguirlo con
time ./gibbs > gibbs.dat
Dato che questo era il modo i tempi sono stati calcolati per le altre lingue nel post, ho pensato di fare qualcosa di simile Il codice C nel post viene eseguito in circa 25 secondi. Mi piacerebbe provare e accelerare il codice Lisp se possibile.
##############################
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))
Poi ho costruito l'eseguibile gibbs con chiamando sh gibbs.sh con gibbs.sh come
##################
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
ottengo 6 note compilatore quando si compila con SBCL 1.0.56, che riporto qui di seguito. Non sono sicuro di cosa fare con loro, ma sarei grato per qualsiasi suggerimento.
; 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 ha sottolineato che l'argomento del SQRT potrebbe essere negativa, che era la fonte delle note compilatore oscuri che stavo vedendo, e cioè
The result is a (VALUES (OR (DOUBLE-FLOAT 0.0) (COMPLEX DOUBLE-FLOAT))
; &OPTIONAL), not a (VALUES FLOAT &REST T).
Il compilatore si lamentava che dal momento che non sapeva se il valore dell'argomento era positivo, il risultato poteva essere un numero complesso. Poiché nell'esempio, il valore x è una variabile di esempio dalla distribuzione gamma, è sempre maggiore di 0. È stato utile indicato da Stephan nella mailing list dell'utente SBCL, (vedere il secondo messaggio nella thread "Optimizing a simple Common Lisp Gibbs sampler program", che questo potrebbe essere risolto dichiarando x per essere maggiore o pari a zero come segue,
(declare (type (double-float 0.0 *) x))
Vedere le Lisp Hyperspec comune per la relativa documentazione su FLOAT types e Interval Designators.
Thi s sembra accelerare un po 'il codice. Ora è affidabile al di sotto di 52 secondi, ma ancora, non molto di un guadagno. Questo lascia anche le note su
note: doing float to pointer coercion (cost 13)
Se questo non è risolvibile per qualche motivo, mi piacerebbe sapere perché. Inoltre, una spiegazione di ciò che significa la nota sarebbe interessante, a prescindere. In particolare, che significato ha la parola pointer qui? Questo è legato al fatto che vengono chiamate le funzioni C? Inoltre, il costo 13 non sembra molto utile. Cosa viene misurato?
Inoltre, Rainer ha suggerito che potrebbe essere possibile ridurre l'inclinazione, che potrebbe ridurre il runtime. Non so se sia possibile una riduzione del consumo, o se ridurrebbe il tempo di esecuzione, ma sarei interessato a opinioni e approcci. Nel complesso, sembra che non si possa fare molto per migliorare le prestazioni di questa funzione. Forse è troppo piccolo e semplice.
Ciao, Rainer. Grazie per il commento, ma speravo in qualcosa di più specifico. Sto già usando 'OPTIMIZE'. Ho provato a usare' THE', ma non vedo dove sarebbe utile se non sugli RHS dei compiti 'x' e' y', e in quei casi, mi aspetterei che il compilatore potrebbe dedurre che tutte quelle espressioni, che derivano dal doppio, sono esse stesse doppie. L'ho provato, ma non fa alcuna differenza evidente. Per mancanza di idee migliori, mi piacerebbe sbarazzarmi delle note del compilatore, ma non capisco cosa mi stanno dicendo. –
Potrei anche provare il profiling, ma non sono sicuro di quanto sarebbe utile per un pezzo così piccolo di codice. Senza dichiarazioni speciali, ho ottenuto un po 'più di 1 minuto, e ora ho circa 52 secondi, quindi le dichiarazioni non hanno fatto molta differenza. –
Ah, buon punto sulla radice quadrata. Ho perso questo. Grazie. –