Lispworks append is too slow

Hello all,

Lispworks append is too slow.

Take a look at this code:

(defvar a (make-list 10000000))

(defvar b (make-list 10000000))

(defvar c )

(time (setf c (append a b)))

It's giving me this answer (and I compiled it)

User time = 3.468

System time = 0.091

Elapsed time = 4.027

Allocation = 120000096 bytes

Under SBCL it takes 0,001.

I was trying to rewrite this append, keeping the

last cons in a "pointer". But, it did not work.

Any clues?

Look at the code (it update two variables, thelist and the lastcons) :

(defstruct *ghost* )

(defmacro appendE (thelist lastcons element)

`(if (equal ,thelist nil) ; I am becoming a lisp programmer lol

(let () (setf ,lastcons (list (make-*ghost*))) (setf ,thelist (cons ,element ,lastcons)))

(if (typep ,lastcons '*ghost*)

(setf (car ,lastcons) ,element)

(let ((x (cons ,element nil))) (setf (cdr ,lastcons) x) (setf ,lastcons x))))

)

Thanks
--
Mauricio Toro Bermudez
Estudiante de Ingeniería de Sistemas
Pontificia Universidad Javeriana, Colombia

Stagiare à l'Ircam
1, place Igor-Stravinsky 75004 Paris,
France de 2008 à 2009

Re: Lispworks append is too slow

Unable to parse email body. Email id is 8054

Re: Lispworks append is too slow

Re: Lispworks append is too slow You have to compile your code before using ‘time’. For instance :

(defun test () (setf c (append a b)))

(time (test))

Best

Denis

Le 25/04/08 15:59, « [NOM] » <[ADRESSE]> a écrit :

Hello all,

Lispworks append is too slow.
Take a look at this code:

(defvar a (make-list 10000000))
(defvar b (make-list 10000000))
(defvar c )
(time (setf c (append a b)))

It's giving me this answer (and I compiled it)
User time    =        3.468
System time =        0.091
Elapsed time =        4.027
Allocation   = 120000096 bytes

Under SBCL it takes 0,001.

I was trying to rewrite this append, keeping the
last cons in a "pointer". But, it did not work.
Any clues?

Look at the code (it update two variables, thelist and the lastcons) :
(defstruct *ghost* )
(defmacro appendE (thelist lastcons element)
   `(if (equal ,thelist nil) ; I am becoming a lisp programmer lol
       (let () (setf ,lastcons (list (make-*ghost*))) (setf ,thelist (cons ,element ,lastcons)))
       (if (typep ,lastcons '*ghost*)
          (setf (car ,lastcons) ,element)
          (let ((x (cons ,element nil))) (setf (cdr ,lastcons) x) (setf ,lastcons x))))
)

Thanks

-------------------------------------------------------
Denis Pousseur
70 rue de Wansijn
1180 Bruxelles, Belgique

Tel : 32 (0)2 219 31 09
Mail : denis.pousseur@gmail.com
-------------------------------------------------------

Re: Lispworks append is too slow

Yes, in general you should compile code before timing or profiling it 
otherwise time spent in the interpreter might skew the results.

But in this case -- (setf c (append a b)) -- the time spent in the 
interpreter is naff all, it's all spent messing with your cons cells.

- nick

Denis Pousseur wrote:
> You have to compile your code before using ‘time’. For instance :
>
> (defun test () (setf c (append a b)))
>
> (time (test))
>
> Best
>
> Denis
>
>
> Le 25/04/08 15:59, « [NOM] » <[ADRESSE]> a écrit :
>
>     Hello all,
>
>     Lispworks append is too slow.
>     Take a look at this code:
>
>     (defvar a (make-list 10000000))
>     (defvar b (make-list 10000000))
>     (defvar c )
>     (time (setf c (append a b)))
>
>     It's giving me this answer (and I compiled it)
>     User time = 3.468
>     System time = 0.091
>     Elapsed time = 4.027
>     Allocation = 120000096 bytes
>

Re: Lispworks append is too slow

I also haven't looked at the code and strongly second Nick's comment. Another thing to think about is that SBCL's default optimization settings may be such that it realizes that c isn't used (not in your example but in actual code like:

(defun foo ()

(let ((a (make-list 10000000))

(b (make-list 10000000))

(c nil))

(time (setf c (append a b)))

nil))

If SBCL notices c isn't used, it might be willing to decide to skip the whole append. I personally don't see how it can do allocate anything like these lists in 0.001 seconds unless something like this is happening. You might want to disassemble the functions to check that you're measuring what you think you're measuring.

On Apr 25, 2008, at 9:59 AM, Mauricio Toro wrote:

Hello all,

Lispworks append is too slow.
Take a look at this code:

(defvar a (make-list 10000000))

(defvar b (make-list 10000000))
(defvar c )
(time (setf c (append a b)))

It's giving me this answer (and I compiled it)

User time = 3.468
System time = 0.091
Elapsed time = 4.027

Allocation = 120000096 bytes

Under SBCL it takes 0,001.

I was trying to rewrite this append, keeping the
last cons in a "pointer". But, it did not work.

Any clues?

Look at the code (it update two variables, thelist and the lastcons) :

(defstruct *ghost* )
(defmacro appendE (thelist lastcons element)
   `(if (equal ,thelist nil) ; I am becoming a lisp programmer lol
   (let () (setf ,lastcons (list (make-*ghost*))) (setf ,thelist (cons ,element ,lastcons)))

   (if (typep ,lastcons '*ghost*)
   (setf (car ,lastcons) ,element)
   (let ((x (cons ,element nil))) (setf (cdr ,lastcons) x) (setf ,lastcons x))))
)

Thanks
--
Mauricio Toro Bermudez
Estudiante de Ingeniería de Sistemas
Pontificia Universidad Javeriana, Colombia

Stagiare à l'Ircam
1, place Igor-Stravinsky 75004 Paris,
France de 2008 à 2009

Gary Warren King, metabang.com

Cell: (413) 559 8738

Fax: (206) 338-4052

gwkkwg on Skype * garethsan on AIM

Re: Lispworks append is too slow

[Apologies, I meant to send this to the list, the other reply I sent  
makes no sense without it.]

If SBCL is doing this append in 1e-3 secs, then it is traversing about  
1e7 conses in that time.  That is 1e10 conses/sec.  If we assume one  
instruction per cons (it will be more) then that requires the machine  
to issue 1e10 instructions/sec.  Or about 10 billion instructions/sec.  
Since it's almost certainly more than one we're talking some multiple  
of that.

Or in other words: your figures for SBCL are not what you think they  
are.