From: ······@fisica.unige.it
Subject: CL and iterators - a newbie question
Date:
Message-ID: <873c5rxa5n.fsf@statpro.com>
Hello,
I'm learning lisp and, as an exercise, trying to implement iterators
with CL. I implemented a simple as follows, using a closure:
(defun sarray-iterator (v &key (start 0))
(declare (type (simple-array double-float) v)
(type fixnum start))
(let ((next-position start))
(declare (type fixnum next-position)
(type double-float result))
#'(lambda ()
(let ((result 0d0))
(setq result (aref v next-position))
(incf next-position)
result))))
I tried to profile it a bit using the following code:
(setf (symbol-function 'try2) (sarray-iterator
(make-array 500000
:element-type 'double-float
:initial-element 1.0d0)
:start 0))
(profile:profile try2)
(try2)
(profile:report-time)
the profiler (cmucl) reported
Consed | Calls | Secs | Sec/Call | Bytes/C. | Name:
-----------------------------------------------------------------------
16 | 1 | 0.000 | 0.00000 | 16 | TRY2
so it seems the iterator conses 16 bytes per call (2 double
floats?), am I right? Where does the cons happen? Is it possible to
write a non-consing iterator?
Thanks in advance,
e.
--
Enrico Sirola
> I do not have access to CMUCL but it probably has something to
> do with boxing floats.
The original poster should try compiling the code in CMUCL with
(proclaim '(optimize speed))
at the top of the file. CMUCL's compiler is good about catching
inefficiencies with numbers.
From: ······@fisica.unige.it
Subject: Re: CL and iterators - a newbie question
Date:
Message-ID: <87lljiq43u.fsf@statpro.com>
Hi Wade,
thanks for your reply,
>>>>> "Wade" == Wade Humeniuk <········@telus.delete.net> writes:
Wade> Try this:
[...]
Wade> I do not have access to CMUCL but it probably has something
Wade> to do with boxing floats.
I just tried, but your implementation shows the same behavior as
mine. Any idea? BTW, what does "boxing floats" mean?
Thanks,
e.
--
Enrico
On Sun, 23 May 2004 18:36:51 +0000, sirola wrote:
> the profiler (cmucl) reported
>
> Consed | Calls | Secs | Sec/Call | Bytes/C. | Name:
> -----------------------------------------------------------------------
> 16 | 1 | 0.000 | 0.00000 | 16 | TRY2
>
> so it seems the iterator conses 16 bytes per call (2 double
> floats?), am I right? Where does the cons happen? Is it possible to
> write a non-consing iterator?
> Thanks in advance,
> e.
I tried your code on both cmucl (18e) and sbcl (0.8.10). I saw the
consing behaviour on cmucl but not on sbcl, so it may be that sbcl is a
more "sufficiently smart" compiler than cmucl at least in this instance.
Cheers,
Bill.
--
Dr. William Bland.
It would not be too unfair to any language to refer to Java as a
stripped down Lisp or Smalltalk with a C syntax. (Ken Anderson).
From: Alexey Dejneka
Subject: Re: CL and iterators - a newbie question
Date:
Message-ID: <m33c5q1qzj.fsf@comail.ru>
Hello,
William Bland <····@abstractnonsense.com> writes:
> On Sun, 23 May 2004 18:36:51 +0000, sirola wrote:
> > the profiler (cmucl) reported
> >
> > Consed | Calls | Secs | Sec/Call | Bytes/C. | Name:
> > -----------------------------------------------------------------------
> > 16 | 1 | 0.000 | 0.00000 | 16 | TRY2
[...]
> I tried your code on both cmucl (18e) and sbcl (0.8.10). I saw the
> consing behaviour on cmucl but not on sbcl, so it may be that sbcl is a
> more "sufficiently smart" compiler than cmucl at least in this instance.
SBCL conses the same 16 bytes per call. Maybe its space profiler is
not accurate; try (TIME (DOTIMES (I 100000) (TRY2))).
--
Regards,
Alexey Dejneka
"Alas, the spheres of truth are less transparent than those of
illusion." -- L.E.J. Brouwer
From: Alexey Dejneka
Subject: Re: CL and iterators - a newbie question
Date:
Message-ID: <m38yfi1r6e.fsf@comail.ru>
Hello,
······@fisica.unige.it writes:
> I'm learning lisp and, as an exercise, trying to implement iterators
> with CL. I implemented a simple as follows, using a closure:
>
> (defun sarray-iterator (v &key (start 0))
> (declare (type (simple-array double-float) v)
> (type fixnum start))
> (let ((next-position start))
> (declare (type fixnum next-position)
> (type double-float result))
^^^^^^^^^^^^^^^^^^^^^^^^^^
This declaration has no effect; it should be after (let ((result 0d0)).
And for CMUCL it is superfluous.
> #'(lambda ()
> (let ((result 0d0))
> (setq result (aref v next-position))
Or just (let ((result (aref v next-position)))
> (incf next-position)
> result))))
>
> I tried to profile it a bit using the following code:
>
> (setf (symbol-function 'try2) (sarray-iterator
> (make-array 500000
> :element-type 'double-float
> :initial-element 1.0d0)
> :start 0))
> (profile:profile try2)
> (try2)
> (profile:report-time)
>
> the profiler (cmucl) reported
>
> Consed | Calls | Secs | Sec/Call | Bytes/C. | Name:
> -----------------------------------------------------------------------
> 16 | 1 | 0.000 | 0.00000 | 16 | TRY2
>
> so it seems the iterator conses 16 bytes per call (2 double
> floats?), am I right?
No. It boxes one double float, which representation includes 8-byte
header.
> Where does the cons happen?
If you compile your code with (DECLARE (OPTIMIZE SPEED)), you'll see:
; Note: Doing float to pointer coercion (cost 13) from RESULT to "<return value>".
So it conses the returned value.
> Is it possible to
> write a non-consing iterator?
Read "CMUCL User Manual", part "Representation of objects". A value,
returned from a non-local function, must use descriptor
representation. Moving from non-descriptor to descriptor requires
consing. If you create iterator and iterate in the same function,
declare SARRAY-ITERATOR INLINE. Another trick is
#'(lambda (box)
(declare (type (simple-array double-float (1)) box))
(let ((result 0d0))
(setq result (aref v next-position))
(incf next-position)
(setf (aref box 0) result)
nil))
and use it with
(let ((box (make-array 1 :element-type 'double-float)))
(dotimes (i 50000)
(try2 box)
(use-number (aref box 0))))
Thus you move the need of boxing to the caller.
--
Regards,
Alexey Dejneka
"Alas, the spheres of truth are less transparent than those of
illusion." -- L.E.J. Brouwer
From: ······@fisica.unige.it
Subject: Re: CL and iterators - a newbie question
Date:
Message-ID: <8765amlzmq.fsf@statpro.com>
Hi Alexey,
>>>>> "Alexey" == Alexey Dejneka <········@comail.ru> writes:
>> so it seems the iterator conses 16 bytes per call (2 double
>> floats?), am I right?
Alexey> No. It boxes one double float, which representation
Alexey> includes 8-byte header.
ok, thanks
>> Is it possible to write a non-consing iterator?
Alexey> Read "CMUCL User Manual", part "Representation of
Alexey> objects". A value, returned from a non-local function,
Alexey> must use descriptor representation. Moving from
Alexey> non-descriptor to descriptor requires consing. If you
Alexey> create iterator and iterate in the same function, declare
Alexey> SARRAY-ITERATOR INLINE. Another trick is
I've just finished a quick read of the relevant part of CMUCL user
manual and you are right. It seems the trick relies in declaring local
functions so to be able to leverage the inline facility. I also tested
the code I posted last time and it does not cons when the iterator
creation is properly inlined.
[...]
Alexey> Thus you move the need of boxing to the caller.
Well, I'm not a fan of explicit boxing - I think it's more natural to
return values than to use "out parameters".
Thanks a lot for your help,
e.
--
Enrico Sirola