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

 Re: [Sbcl-help] Optimizing a simple Common Lisp Gibbs sampler program From: - 2012-05-31 07:37:10 ```Hi Fareen, the (the double-float ...) tells the compiler that you insist that the result is a double-float; though you may lie to the compiler if x assumes non-appropriate values for this declaration. I see in the Stackoverflow thread that you want to declrare x as beaing a d-f >= 0.0. If this is the case than you can try: (declare (type (double-float 0.0 *) x)) Then you should also be able to remove the (the double-float ...) since the compiler should be able to infer that the result can only be a double-float. Furthermore you will get automatically a type/range-check for the correct values of x. Hope this helps. Best regards, Stephan > 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 > > > ------------------------------------------------------------------------------ > Live Security Virtual Conference > Exclusive live event will cover all the ways today's security and > threat landscape has changed and how IT managers can respond. Discussions > will include endpoint security, mobile security and the latest in malware > threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ > _______________________________________________ > Sbcl-help mailing list > Sbcl-help@... > https://lists.sourceforge.net/lists/listinfo/sbcl-help > ```