Prev: help save comp.lang.lisp from spam
Next: Reason to hate loop
From: Jeff Clough on 22 Apr 2010 08:15
Hey now,

So I'm relatively new to Lisp, but my understanding is improving
gradually. Right now I'm wondering about the various declaim, declare,
inline options. I have the following code...

(declaim (inline roll))
(defun roll (number-of-dice type-of-dice)
"Simulate a roll of several dice of the same type.
The argument NUMBER-OF-DICE is the number of dice to roll and must be a
positive integer.
The argument TYPE-OF-DICE must be a positive integer specifying the
number of sides each die will have."
(let ((result 0))
(dotimes (x number-of-dice)
(declare (optimize speed))
(incf result (+ (random type-of-dice) 1)))
result))

;; Roll 1d10d6d4 ROLLS times and count how many times each
;; particular result occurs.
(defun roll-test (rolls)
(let ((results (make-array 240 :initial-element 0)))
(dotimes (x rolls)
(declare (optimize speed))
(incf (elt results (- (roll (roll (roll 1 10) 6) 4) 1)) 1))
(dotimes (x (length results))
(format t "~a: ~a~%" (+ x 1) (elt results x)))))

It was written just to get some data on a dice-related problem. The
situation here is that when I feed this to SBCL, I get a lot of "notes"
concerning things not being optimized the way I'm asking. I *think* I
understand the problems (bignums can be used in these functions, random
uses floats to do it's thing, etc.).

Questions:

1. Can someone point me to a document that describes the various
declaim options and optimization directives? The hyperspec is nice, but
I'm wondering if there's a paper that might be more informative.

2. What would *you* do to improve the performace of the code above?

3. Am I doing it right?

Any guidance would be appreciated.

Thanks!

Jeff

From: Tim Bradshaw on 22 Apr 2010 09:18
On 2010-04-22 13:15:43 +0100, Jeff Clough said:

> The
> situation here is that when I feed this to SBCL, I get a lot of "notes"
> concerning things not being optimized the way I'm asking. I *think* I
> understand the problems (bignums can be used in these functions, random
> uses floats to do it's thing, etc.).

If you ask the system to optimize speed, but don't give it type
declarations, it will probably have a big whinge at you (if it's a
CMUCL-derived system) or just not do a terribly good job of generating
fast code (for most other systems, which tend to complain less
vigorously than CMUCL-derivatives, though you can often ask them to
complain). You generally need type declarations to help the optimizer.

From: Tim X on 22 Apr 2010 20:11
Jeff Clough <jeff(a)chaosphere.com> writes:

> Hey now,
>
> So I'm relatively new to Lisp, but my understanding is improving
> gradually. Right now I'm wondering about the various declaim, declare,
> inline options. I have the following code...
>

> (declaim (inline roll))
> (defun roll (number-of-dice type-of-dice)
> "Simulate a roll of several dice of the same type.
> The argument NUMBER-OF-DICE is the number of dice to roll and must be a
> positive integer.
> The argument TYPE-OF-DICE must be a positive integer specifying the
> number of sides each die will have."
> (let ((result 0))
> (dotimes (x number-of-dice)
> (declare (optimize speed))
> (incf result (+ (random type-of-dice) 1)))
> result))
>
> ;; Roll 1d10d6d4 ROLLS times and count how many times each
> ;; particular result occurs.
> (defun roll-test (rolls)
> (let ((results (make-array 240 :initial-element 0)))
> (dotimes (x rolls)
> (declare (optimize speed))
> (incf (elt results (- (roll (roll (roll 1 10) 6) 4) 1)) 1))
> (dotimes (x (length results))
> (format t "~a: ~a~%" (+ x 1) (elt results x)))))
>
> It was written just to get some data on a dice-related problem. The
> situation here is that when I feed this to SBCL, I get a lot of "notes"
> concerning things not being optimized the way I'm asking. I *think* I
> understand the problems (bignums can be used in these functions, random
> uses floats to do it's thing, etc.).
>
> Questions:
>
> 1. Can someone point me to a document that describes the various
> declaim options and optimization directives? The hyperspec is nice, but
> I'm wondering if there's a paper that might be more informative.

You are probably better off starting with the SBCL manual and looking at
its sections on idiosyncracies, efficiency and type declarations.

>
> 2. What would *you* do to improve the performace of the code above?
>
> 3. Am I doing it right?
>

Personally, I think you may be jumping the gun - how do you know that
SBCL isn't already generating the most efficient code possible? You
cannot optimize in a vacuum. You need to start by measuring/profiling
your codes initial performance. You also need to have some idea of what
is acceptable performance.

Most CL implementations are pretty good these days and I think its a
mistake to worry about low level optimisation too early. In fact, as you
are at a learning level, the greatest efficiency gain in both speed and
space will likely be through improving your CL style rather than with
compiler type hints etc.

things like optimze and inline are usually best thought of as hints for
the compiler. They provide some additional 'weight' to decisions it
makes on how to compile the code. However, the code also needs to lend
itself to either being inlined or optimized for there to be any effect.
Most implementations will require that you add things like type
declarations so that the compiler has more information on how it can
optimize or can decide if the code would be best inlined etc. However,
having to decide on things like types early in the develpment process
can make development more difficult as your forced to make decisions
earlier, possibly before you have a full understadning of the problem
your trying to solve.

Code optimization techniques can also adversely impact on the develpment
cycle. For example, most optimization only ocurs when you compile the
code. However, interpreted code is usually much easier to owrk with
while developing. Some optimizations can also restrict the detail or
quality of information the system can feedback regarding errors, making
debugging harder.

I would start by keeping it simple. Get your code working. Get your
application working. Do some profiling and identify the bottlenecks. See
how you can re-write your code to make it run faster. Go through this
process until you cannot improve things further by just re-writing code.

Once you have gotten to that point, then start adding type declarations
and profiling to get a measure of what impact your changes are having.
Iterate through these steps, addressing the worst bottleneck each time
until either you are happy with the performance or you run out of ideas
on how to improve things. If you have run out of ideas and the
performance is still no good, then come back and ask.

The SBCL manual has some good sections on idiosyncracies with SBCL,
efficiency and type declarations. You may also find some useful
information in the CMUCL docs. I have also found reading other peoples
code useful as you sometimes come across techniques that look
interesting. Frequently, when you do some analysis of these techniques,
you will find they have some useful effficiency gains. Initially, I
think the most important thing to do is get a real feel for what is
happening - when does your code cons, perform gc, how does a macro
expand, etc. Knowing this will tell you what abstractions and which
algorithms to use. The right abstractions and algorithms will always
give you a better result than hours of tweaking type declarations and
adding compiler hints.

HTH

Tim


--
tcross (at) rapttech dot com dot au
From: Barry Margolin on 22 Apr 2010 23:21
In article <m3eii7of80.fsf(a)logrus.localdomain>,
Jeff Clough <jeff(a)chaosphere.com> wrote:

> Hey now,
>
> So I'm relatively new to Lisp, but my understanding is improving
> gradually. Right now I'm wondering about the various declaim, declare,
> inline options. I have the following code...

If you're new, you should probably concentrate on other things. Unless
you're building large, complex applications, this part of the language
can safely be ignored. Many people program in CL for years without ever
bothering with these declarations.

--
Barry Margolin, barmar(a)alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
 | 
Pages: 1
Prev: help save comp.lang.lisp from spam
Next: Reason to hate loop