Re: CL and iterators - a newbie question

From: Alexey Dejneka (adejneka_at_comail.ru)
Date: 05/24/04 

Date: 24 May 2004 06:42:49 +0400

Hello,

sirola@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

Relevant Pages

  • Re: Need help with Vector parameter when invoking C dll from C#
    ... I have the structure CUserContextData declare correctly in C# already. ... What you could do is implement a function in a C++ wrapper that takes an array of type CUserContextData and convert this into a vector of type CUserContextData, then you need to declare a vector iterator for this vector and pass the iterator to the EncodeAsnUser function. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Help with a Remote Type / Iterator
    ... we'd rather declare all of the types in the spec and ... We've tried a passive iterator, but some of the stuff we ... > package must be a remote subprogram. ... particular partition, then do the next partition, iterate over all ...
    (comp.lang.ada)
  • CL and iterators - a newbie question
    ... (declare (type (simple-array double-float) ... (declare (type fixnum next-position) ... I tried to profile it a bit using the following code: ... so it seems the iterator conses 16 bytes per call (2 double ...
    (comp.lang.lisp)
  • Re: trying to declare an iterator for a std::vector of template pointers
    ... > int main ... > Can anyone tell me if/how to declare an iterator to a vector of template ...
    (comp.lang.cpp)