간단한 Common Lisp gibbs sampler 프로그램을 최적화하는 방법

Question

연습을 위해 Darren Wilkinson이 블로그 게시물 Gibbs sampler in various languages (revisited)에 예제 프로그램을 작성했습니다.

아래 코드가 나타납니다. 이 코드는, SBCL 1.0.56을 사용 buildapp를 사용하여 코어 이미지를 생성하고이 타이밍이 계산 된 방법 이었기 때문에

time ./gibbs > gibbs.dat 

으로 실행, 주변 53초 내 (5 세) 컴퓨터에서 실행 게시물의 다른 언어들, 나는 비슷한 것을 할 것이라고 생각했다. 게시물의 C 코드는 약 25 초 만에 실행된다. 가능하다면 Lisp 코드의 속도를 높이고 싶습니다.

############################## 
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)) 

은 그럼 아래에 재현 SBCL 1.0.56로 컴파일 할 때 나는 6 개 컴파일러 메모를 얻을 gibbs.sh

################## 
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 

로와 sh gibbs.sh를 호출하여 실행 gibbs을 만들었습니다. 나는 그들에 대해 무엇을해야할지 모르지만, 어떤 힌트에도 감사 할 것입니다.

; 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 SQRT의 인수가 즉

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

컴파일러가 불평했다, 내가보고 된 알려지지 않은 컴파일러 노트의 원천이었다 , 음수가 될 수 있음을 지적 인수의 값이 양수인지 여부를 알지 못했기 때문에 결과는 복소수가 될 수 있습니다. 이 예에서 값 x은 감마 분포의 샘플 변량이므로 은 항상 0보다 큽니다. Stephan은 SBCL 사용자 메일 링리스트 에서 유용하게 지적했습니다 (스레드 "Optimizing a simple Common Lisp Gibbs sampler program"의 두 번째 메시지 참조). 이것은

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

관련 문서에 대한 FLOAT types 및 Interval Designators.

티의 커먼 리스프 HyperSpec을 참조로 다음과보다 제로 클 X를 선언함으로써 해결 될 수있다 코드의 속도가 빨라지는 것 같습니다. 이제는 안정적으로 52 초 미만이지만 그래도 이득은별로 없습니다. 이것은 어떤 이유로, 나는 이유를 알고 싶습니다 고칠 수없는 경우 이것은 또한

note: doing float to pointer coercion (cost 13) 

대한 메모를 남긴다. 또한 노트가 의미하는 바에 대한 설명은 상관없이 흥미로울 것입니다. 특히 여기에 단어 pointer은 무엇을 의미합니까? 이것은 C 함수가 호출된다는 사실과 관련이 있습니까? 또한 비용 13은 처럼 보이지 않습니다. 무엇이 측정되고 있습니까?

또한 라이너 (Rainer)는 consing을 줄이는 것이 가능하여 런타임을 단축시킬 수 있다고 제안했습니다. consuction reduction이 가능한지 또는 런타임이 단축되는지 여부는 알지 못합니다. 하지만 의견이나 접근 방식에 관심이 있습니다. 전반적으로이 기능의 성능을 향상시키는 것은 그리 많지 않습니다. 어쩌면 너무 작고 간단합니다.

Answer 1

Common Lisp에는 THE 특수 연산자가 있습니다. 표현식 결과에 대한 유형을 선언 할 수 있습니다. 예를 들어 가능한 경우 유형을 좁힐 수 있습니다.

예를 들어, 의 결과는 무엇입니까? 부동 소수 일 수 있지만 somefloat이 음수이면 복소수가 될 수 있습니다. 일부 플로트가 항상 긍정적 인 경우 (그리고 그때 만) (the double-float (sqrt somefloat))을 쓸 수 있습니다. 컴파일러는보다 효율적인 코드를 생성 할 수 있습니다.

Common Lisp에는 OPTIMIZE 선언이 있습니다. 가장 빠른 코드를 원한다면 적절하게 설정해야합니다. 개별 기능에 대해서만 가능합니다. 일반적으로 매우 적극적인 것으로 글로벌하게 최적화를 변경하는 것보다 낫습니다.

Common Lisp에는 컴파일 된 코드를 볼 수있는 DISASSEMBLE 함수가 있습니다.

매크로 TIME이 있습니다. 당신이 얻는 재미있는 정보는 그것이 얼마나 많은 consing인지를 포함합니다. double-float 산술로 인해 아마도 많은 양의 consing이있을 것입니다. SBCL 메일 링리스트에서 도움을 요청하는 것이 유용 할 것입니다. 어쩌면 누군가가 그 합의를 피할 수있는 방법을 알려줄 수 있습니다.

Answer 2

이 나를 위해 작동합니다

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