Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.

## [Sbcl-help] Optimizing a simple Common Lisp Gibbs sampler program

 [Sbcl-help] Optimizing a simple Common Lisp Gibbs sampler program From: Faheem Mitha - 2012-05-30 23:59:33 ```Hi, I posted the following at http://stackoverflow.com/questions/10813398/optimizing-simple-common-lisp-gibbs-sampler-program I reproduce the question below. The cl-rmath is a wrapper for R's math library, and it located at https://github.com/tpapp/cl-rmath. As the question says, I'm looking for optimization hints. This is just an exercise; I took it from Darren Wilkinson's blog, and it looked simple enough to be something I could learn from. First, I should mention that trying this code without any attempt at optimization or type declaration, I got slightly over 1 minute runtime. With the added declarations etc, it is now about 52/54 seconds; not a dramatic improvement. The C code runs about 25 seconds, so this is not too bad, but I'd like to see if I can get some improvement. BTW, by way of comparison, Darren's Python version runs on my machine at around 9 1/2 minutes. Per Rainer's feedback, I tried wrapping the sqrt value in a double-float d (the double-float (sqrt (+ (* 2 x) 2))) However, I still get the following note, but I'm not sure what the compiler is complaining about now. If I understand this correctly, the issue is that the argument to sqrt might be negative, and hence the result might be complex. However, I've said that the sqrt expression is double-float. The only other thing I can think of, is to tell the compiler that (+ (* 2 X) 2) is always positive, but there doesn't seem to be a way to do that. ; 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). Furthermore, I'm also not sure what to do about the note: doing float to pointer coercion (cost 13) notes. This is wrt the x and y assignments, I think. From browsing on the net, it seems that this is another case where the compiler is not sure about type, but I tried wrapping the rhs of each assignment in a (the fixnum), but it doesn't make any difference. I realise that fixing these compiler notes might not make any difference to the runtime of the program, but I just wanted to get some practice learning to understand how the compiler thinks. Rainer also suggested That I try running TIME and DISASSEMBLE. The time shows a lot of consing - I get Evaluation took: 62.979 seconds of real time 59.695730 seconds of total run time (59.267704 user, 0.428026 system) [ Run times consist of 1.568 seconds GC time, and 58.128 seconds non-GC time. ] 94.79% CPU 126,548,820,533 processor cycles 2 page faults 5,902,262,600 bytes consed I'm not clear whether the consing accounts for a significant fraction of the runtime. If it does, then any hints how I can reduce it? Also, how much bearing does consing/garbage collection have on memory usage? According to top, the usage for the lisp executable seemed to stay fairly steady around 30M, though the virtual memory was high. at 524m. PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND 25805 faheem 20 0 524m 30m 3468 R 99 0.8 0:29.61 ./gibbs I assume all the consing is coming from the creation of those temporary values in the x and y assignments. The disassemble output is quite large, but means little to me. Lastly, I'm Ok with SBCL-specific optimization techniques. Thanks in advance. Please CC me on any reply. Regards, Faheem ############################################################################################################################################################################ As an exercise, I rewrote the example program in the blog post [Gibbs sampler in various languages (revisited)](http://darrenjw.wordpress.com/2011/07/16/gibbs-sampler-in-various-languages-revisited/) by Darren Wilkinson. The code appears below. This code runs on my (5 year old) machine in around 53 seconds, using SBCL, creating a core imsage using buildapp, and then running it with time ./gibbs > gibbs.dat Since this was how the timings were calculated for the other languages in the post, I thought I would do something comparable The C code in the post runs in around 25 seconds. I'd like to try and speed up the Lisp code if possible. ############################## 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)) Then I built the executable `gibbs` by calling `sh gibbs.sh` with `gibbs.sh` as ################## 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 get 6 compiler notes when compiling with SBCL 1.56, which reproduce below. I'm not sure what to do about them, but would be grateful for any hints. ; 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 ```