Hello,
I'm working on my first non-toy lisp program (a Monte Carlo simulation
code). I was experimenting with different ways of writing a function
when I accidentally noticed the following: it seems that declaring the
element-type of an array makes the code slower (and also cons more),
but I was under the impression that the opposite should be the case.
Can somebody please enlighten me? (I hope this question is not too
stupid)
(Note, I am aware the snippet below is completely pointless. I'm not
looking for better ways to write it. I just want to understand why,
written as it is, it behaves the way it does.)
Using SBCL 1.0
(let* ((n 10000)
(random-array (loop repeat n collect (random 1d0))))
(defun sum-cos-random-array ()
(let ((a (make-array n :element-type 'double-float :initial-
element 0d0)))
(loop for x in random-array
for i from 0
do (incf (aref a i) x))))
(defun sum-cos-random-array-no-element-type ()
(let ((a (make-array n :initial-element 0)))
(loop for x in random-array
for i from 0
do (incf (aref a i) x)))))
;; Test specialized array
CL-USER> (time (loop repeat 10000 do (sum-cos-random-array)))
Evaluation took:
11.329 seconds of real time
10.88868 seconds of user run time
0.220014 seconds of system run time
[Run times include 2.377 seconds GC run time.]
0 calls to %EVAL
0 page faults and
4,000,094,192 bytes consed.
;; Test unspecialized array
CL-USER> (time (loop repeat 10000 do (sum-cos-random-array-no-element-
type)))
Evaluation took:
6.448 seconds of real time
6.24439 seconds of user run time
0.16401 seconds of system run time
[Run times include 1.468 seconds GC run time.]
0 calls to %EVAL
0 page faults and
2,000,089,464 bytes consed.
In article <························@e65g2000hsc.googlegroups.com>,
·················@gmail.com wrote:
> Hello,
>
> I'm working on my first non-toy lisp program (a Monte Carlo simulation
> code). I was experimenting with different ways of writing a function
> when I accidentally noticed the following: it seems that declaring the
> element-type of an array makes the code slower (and also cons more),
> but I was under the impression that the opposite should be the case.
> Can somebody please enlighten me? (I hope this question is not too
> stupid)
If the array is specialized, then every time you extract an element from
it the system has to allocate an object to hold it -- this is
traditionally called "boxing".
On the other hand, if the array is general then it just contains
pointers to the objects, and extracting from the array just involves
returning that pointer.
Boxing can be avoided if you provide enough declarations that the
compiler can generate code that operates directly on the specialized
representation. Your code doesn't have any type declarations, so
everything ends up being done with generic code.
--
Barry Margolin, ······@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 ***
On Mar 30, 9:51 pm, Barry Margolin <······@alum.mit.edu> wrote:
> In article <························@e65g2000hsc.googlegroups.com>,
>
> ·················@gmail.com wrote:
> > Hello,
>
> > I'm working on my first non-toy lisp program (a Monte Carlo simulation
> > code). I was experimenting with different ways of writing a function
> > when I accidentally noticed the following: it seems that declaring the
> > element-type of an array makes the code slower (and also cons more),
> > but I was under the impression that the opposite should be the case.
> > Can somebody please enlighten me? (I hope this question is not too
> > stupid)
>
> If the array is specialized, then every time you extract an element from
> it the system has to allocate an object to hold it -- this is
> traditionally called "boxing".
>
> On the other hand, if the array is general then it just contains
> pointers to the objects, and extracting from the array just involves
> returning that pointer.
>
> Boxing can be avoided if you provide enough declarations that the
> compiler can generate code that operates directly on the specialized
> representation. Your code doesn't have any type declarations, so
> everything ends up being done with generic code.
>
> --
> Barry Margolin, ······@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 ***
Very interesting -- so if you use an :element-type argument to make-
array you're not likely to get any benefit unless you also use type
declarations when you use that array?
In article <························@p77g2000hsh.googlegroups.com>,
·············@gmail.com" <············@gmail.com> wrote:
> On Mar 30, 9:51 pm, Barry Margolin <······@alum.mit.edu> wrote:
> > In article <························@e65g2000hsc.googlegroups.com>,
> >
> > ·················@gmail.com wrote:
> > > Hello,
> >
> > > I'm working on my first non-toy lisp program (a Monte Carlo simulation
> > > code). I was experimenting with different ways of writing a function
> > > when I accidentally noticed the following: it seems that declaring the
> > > element-type of an array makes the code slower (and also cons more),
> > > but I was under the impression that the opposite should be the case.
> > > Can somebody please enlighten me? (I hope this question is not too
> > > stupid)
> >
> > If the array is specialized, then every time you extract an element from
> > it the system has to allocate an object to hold it -- this is
> > traditionally called "boxing".
> >
> > On the other hand, if the array is general then it just contains
> > pointers to the objects, and extracting from the array just involves
> > returning that pointer.
> >
> > Boxing can be avoided if you provide enough declarations that the
> > compiler can generate code that operates directly on the specialized
> > representation. Your code doesn't have any type declarations, so
> > everything ends up being done with generic code.
>
> Very interesting -- so if you use an :element-type argument to make-
> array you're not likely to get any benefit unless you also use type
> declarations when you use that array?
There's still benefit in some cases. If the array is large, specialized
arrays of small integer types can use much less memory. E.g. :TYPE
(UNSIGNED-BYTE 8) will just use one byte per element, rather than 4 (or
8 if you have a 64-bit Lisp).
--
Barry Margolin, ······@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 ***
·············@gmail.com" <············@gmail.com> writes:
> Very interesting -- so if you use an :element-type argument to make-
> array you're not likely to get any benefit unless you also use type
> declarations when you use that array?
I've piled in lots of type declarations
(declaim (optimize speed))
(let* ((n 1000000)
(random-array (loop repeat n collect (random 1d0))))
(declare (fixnum n))
(defun sum-cos-random-array ()
(let ((a (make-array n :element-type 'double-float :initial-element 0d0)))
(declare (type (simple-array double-float (*)) a))
;; promise Lisp that a is one dimensional and we will
;; not adjust it
(loop for x of-type double-float in random-array
for i of-type fixnum from 0
do (incf (aref a i) x))))
(defun sum-cos-random-array-no-element-type ()
(let ((a (make-array n :initial-element 0)))
(loop for x in random-array
for i from 0
do (incf (aref a i) x)))))
and I increased n to one million to compensate for
remembering to compile the program :-)
Now sum-cos-random-array doesn't cons, that is, it only uses
the 8Mbyte needed for a million double floats
CL-USER> (time (sum-cos-random-array))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 0.25 seconds of real time
; 0.183437 seconds of user run time
; 0.0 seconds of system run time
; 87,451,042 CPU cycles
; 0 page faults and
; 8,000,008 bytes consed.
;
NIL
CL-USER> (time (sum-cos-random-array-no-element-type))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 1.56 seconds of real time
; 1.310301 seconds of user run time
; 0.046282 seconds of system run time
; 547,026,431 CPU cycles
; [Run times include 0.83 seconds GC run time]
; 0 page faults and
; 20,018,416 bytes consed.
;
NIL
Alan Crowe
Edinburgh
Scotland
> I've piled in lots of type declarations
>
> (declaim (optimize speed))
>
...snipped..
No surprises there then.
Remember that when SBCL can't directly infer types, it treats all type
declarations as assertions to be checked, unless told not to.
http://www.sbcl.org/manual/Declarations-as-Assertions.html#Declarations-as-Assertions
So unless you explicitly optimise for speed, declarations act as a
debugging tool that may well slow your code further.