31 May 2012 01:59

## Optimizing a simple Common Lisp Gibbs sampler program

```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
```
(Continue reading)

31 May 2012 09:23

### Re: Optimizing a simple Common Lisp Gibbs sampler program

```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.
>
```
(Continue reading)

31 May 2012 10:31

### Re: Optimizing a simple Common Lisp Gibbs sampler program

```
Hi Stephan,

Thanks for your reply.

On Thu, 31 May 2012, crimsonf <at> cs.tu-berlin.de wrote:

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

If this declaration says that x is a double float which is greater than or
equal to 0, then that seems like a good way to resolve the problem.

Can you give me a reference for this syntax? Thanks.

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

Oh, the compiler will automatically put in a runtime check that x >= 0?
Interesting.
```
(Continue reading)

31 May 2012 10:45

### Re: Optimizing a simple Common Lisp Gibbs sampler program

```
On Thu, 31 May 2012, Faheem Mitha wrote:

>
> Hi Stephan,
>
> Thanks for your reply.
>
> On Thu, 31 May 2012, crimsonf <at> cs.tu-berlin.de wrote:
>
>> 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))

Incidentally, the compiler accepts

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

which suggests that the TYPE is redundant. Haven't found the syntax for
(double-float 0.0 *), though.

This change does seem to make the program run slightly faster. It is now
consistently below 52 sec.
```
(Continue reading)

31 May 2012 11:09

### Re: Optimizing a simple Common Lisp Gibbs sampler program

```On Thu, May 31, 2012 at 10:45 AM, Faheem Mitha <faheem <at> faheem.info> wrote:

> Incidentally, the compiler accepts
>
> (declare ((double-float 0.0 *) x))
>
> which suggests that the TYPE is redundant.

See "Notes" in:
http://www.lispworks.com/documentation/HyperSpec/Body/d_type.htm

> Haven't found the syntax for (double-float 0.0 *), though.

http://www.lispworks.com/documentation/HyperSpec/Body/t_short_.htm#double-float

------------------------------------------------------------------------------
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/
```
31 May 2012 10:08

### Re: Optimizing a simple Common Lisp Gibbs sampler program

```On Thu, May 31, 2012 at 1:59 AM, Faheem Mitha <faheem <at> faheem.info> wrote:

>     (defun gibbs (N thin)
>       (declare (fixnum N thin))
>       (declare (optimize (speed 3) (safety 1)))

Using (safety 0) does make any difference?

------------------------------------------------------------------------------
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 <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/sbcl-help
```
31 May 2012 10:33

### Re: Optimizing a simple Common Lisp Gibbs sampler program

```
On Thu, 31 May 2012, Pierpaolo Bernardi wrote:

> On Thu, May 31, 2012 at 1:59 AM, Faheem Mitha <faheem <at> faheem.info> wrote:
>
>>     (defun gibbs (N thin)
>>       (declare (fixnum N thin))
>>       (declare (optimize (speed 3) (safety 1)))
>
> Using (safety 0) does make any difference?

I tried it, but it does not have a noticeable effect. Also, I've seen
people recommending against setting safety to 0.

Regards, Faheem
```
```------------------------------------------------------------------------------
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 <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/sbcl-help
```
31 May 2012 10:43

### Re: Optimizing a simple Common Lisp Gibbs sampler program

```On Thu, May 31, 2012 at 10:33 AM, Faheem Mitha <faheem <at> faheem.info> wrote:
>
>
> On Thu, 31 May 2012, Pierpaolo Bernardi wrote:
>
>> On Thu, May 31, 2012 at 1:59 AM, Faheem Mitha <faheem <at> faheem.info> wrote:
>>
>>>     (defun gibbs (N thin)
>>>       (declare (fixnum N thin))
>>>       (declare (optimize (speed 3) (safety 1)))
>>
>> Using (safety 0) does make any difference?
>
> I tried it, but it does not have a noticeable effect. Also, I've seen people
> recommending against setting safety to 0.

In general, they are correct.  But if you are trying to squeeze the
last drop of performance from a little benchmark and comparing the
speed against C then it's it's allowed.  8^)

------------------------------------------------------------------------------
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 <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/sbcl-help
```
(Continue reading)

4 Jun 2012 23:11

### Re: Optimizing a simple Common Lisp Gibbs sampler program (redux) with fun GC issues

```
Hi,

I got some feedback, and decided to try reworking this exercise using
an array. I ran into some issues, at least one of which is quite
worrying. The code is below, and here are the issue, in descending
order of importance.

1) I'm having GC problems. If I run this code a number of times, like

Here is the output for (room) for a newly started REPL.

CL-USER> (room)
Dynamic space usage is:   92,358,952 bytes.
Read-only space usage is:      3,512 bytes.
Static space usage is:         2,224 bytes.
Control stack usage is:        5,928 bytes.
Binding stack usage is:          536 bytes.
Control and binding stack usage is for the current thread only.
Garbage collection is currently enabled.

Breakdown for dynamic space:
21,981,408 bytes for   565,633 instance objects.
15,453,048 bytes for 1,931,631 cons objects.
12,000,912 bytes for    16,217 code objects.
11,585,944 bytes for   210,891 simple-vector objects.
8,400,184 bytes for    61,316 simple-character-string objects.
5,903,840 bytes for    42,632 simple-array-unsigned-byte-32 objects.
17,717,104 bytes for 1,177,704 other objects.
93,042,440 bytes for 4,006,024 dynamic objects (space total.)
```
(Continue reading)

5 Jun 2012 00:08

### Re: Optimizing a simple Common Lisp Gibbs sampler program (redux) with fun GC issues

```Hi Faheem,

I'm going to answer just  one of your questions, because it is way past
my bedtime and the rest require some more thinking.

> 4) The compiler is Ok with
>
>     (declare ((integer 0 536870911) i j))
>
> (positive fixnum, basically) but not with
>
>     (declare ((integer 0 most-positive-fixnum) i j))
>
> though, if I understand this correctly, most-positive-fixnum is just
> the integer 536870911.
>

If you declare using such constants you need to use the #. reader macro.
So the following should work:

(declare ((integer 0 #.most-positive-fixnum) i j))

see http://www.lispworks.com/documentation/HyperSpec/Body/02_dhf.htm

Kind regards,
Stephan

------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and
```
(Continue reading)

5 Jun 2012 08:56

### Re: Optimizing a simple Common Lisp Gibbs sampler program (redux) with fun GC issues

```
On Tue, 5 Jun 2012, Stephan Frank wrote:

> Hi Faheem,
>
> I'm going to answer just  one of your questions, because it is way past
> my bedtime and the rest require some more thinking.
>
>> 4) The compiler is Ok with
>>
>>     (declare ((integer 0 536870911) i j))
>>
>> (positive fixnum, basically) but not with
>>
>>     (declare ((integer 0 most-positive-fixnum) i j))
>>
>> though, if I understand this correctly, most-positive-fixnum is just
>> the integer 536870911.

> If you declare using such constants you need to use the #. reader macro.
> So the following should work:
>
> (declare ((integer 0 #.most-positive-fixnum) i j))
>
> see http://www.lispworks.com/documentation/HyperSpec/Body/02_dhf.htm

Hi Stephan,

Thanks, that works. Since 'most-positive-fixnum' is an an object not an
integer, even though 'type-of' provided no clue to this, was there some
```
(Continue reading)

5 Jun 2012 00:17

### Re: Optimizing a simple Common Lisp Gibbs sampler program (redux) with fun GC issues

```oh yeah and there are way too many declares in your code. The type
analyzer should be able to figure out most of your declareration. E.g.
with just declaring N thin as

(declare ((integer 0 #.most-positive-fixnum) N thin))

you should be able to remove any declares concerning i and j since their
values are depended on N and thin.

Furthermore, I think you try to reduce overall run-time. Have you
already profiled your code to ensure that the FFI are not the main
contributing factor? You're not going to optimize away this overhead
with your type annotations....

Stephan

------------------------------------------------------------------------------
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/
```
5 Jun 2012 11:39

### Re: Optimizing a simple Common Lisp Gibbs sampler program (redux) with fun GC issues

```
On Tue, 5 Jun 2012, Stephan Frank wrote:

> oh yeah and there are way too many declares in your code. The type
> analyzer should be able to figure out most of your declareration. E.g.
> with just declaring N thin as
>
> (declare ((integer 0 #.most-positive-fixnum) N thin))
>
> you should be able to remove any declares concerning i and j since their
> values are depended on N and thin.

Good point. Done. Any other tips?

> Furthermore, I think you try to reduce overall run-time. Have you
> already profiled your code to ensure that the FFI are not the main
> contributing factor? You're not going to optimize away this overhead
> with your type annotations....

Also good point. Actually, I recently wrote in another post (on
comp.lang.lisp)

"""SBCL also has a statistical profiler. I didn't try that, since I
assumed this wouldn't give me much information for such a small simple
function, but it might at least tell me how much time is spent running the
C functions."""

I guess I should try profiling next. Is the SBCL statistical profiler the
best way to go, in your opinion?

```
(Continue reading)

5 Jun 2012 11:51

### Re: Optimizing a simple Common Lisp Gibbs sampler program (redux) with fun GC issues

```Faheem Mitha <faheem <at> faheem.info> writes:

> On Tue, 5 Jun 2012, Stephan Frank wrote:
>
>> oh yeah and there are way too many declares in your code. The type
>> analyzer should be able to figure out most of your declareration. E.g.
>> with just declaring N thin as
>>
>> (declare ((integer 0 #.most-positive-fixnum) N thin))
>>
>> you should be able to remove any declares concerning i and j since their
>> values are depended on N and thin.
>
> Good point. Done. Any other tips?
This declaration can be written as
(declare (type (and (integer 0) fixnum) N))
instead.

--

--
With best regards, Stas.

------------------------------------------------------------------------------
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/
```
5 Jun 2012 12:11

### Re: Optimizing a simple Common Lisp Gibbs sampler program (redux) with fun GC issues

```W dniu 2012-06-04 23:11, Faheem Mitha pisze:
> Hi,
>
> I got some feedback, and decided to try reworking this exercise using
> an array. I ran into some issues, at least one of which is quite
> worrying. The code is below, and here are the issue, in descending
> order of importance.
>
> 1) I'm having GC problems. If I run this code a number of times, like
>
> Here is the output for (room) for a newly started REPL.
>
> CL-USER> (room)
> Dynamic space usage is: 92,358,952 bytes.
> (...)
>
> Now I run this a bunch of times.
>
> (time (gibbs 10000 1000))
>
> The dynamic space usage keeps climbing, and eventually I get a heap
> error. At that point (room) gives
>
> CL-USER> (room)
> Dynamic space usage is: 1,010,419,640 bytes.
> (...)
>
> Yikes. After I waited a bit, the dynamic space usage did go down a bit,
> but only a little.
>
```
(Continue reading)

Gmane