Lispworks append is too slow (2)

Hello all,

The problem is that append is very slow in Lispworks and

I think that it is possible to write an efficient append

keeping the pointer of the "last cons". But, my code does

not work well, any clues how to write this efficient append?

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))))

)

---------- Forwarded message ----------
From: Mauricio Toro <mauriciotorob@gmail.com>
Date: 25 avr. 2008 15:59
Subject: Lispworks append is too slow
To: lisp-hug@lispworks.com

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

--
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 (2)

"Mauricio Toro" <mauriciotorob@gmail.com> writes:

> Hello all,
> The problem is that append is very slow in Lispworks and
> I think that it is possible to write an efficient append
> keeping the pointer of the "last cons". But, my code  does
> not work well, any clues how to write this efficient append?

You mean, you want something like:


CL-USER 33 > (defparameter *list1* (list :foo :bar))
*LIST1*

CL-USER 34 > (defparameter *list2* (list :foo2 :bar2))
*LIST2*

CL-USER 35 > (setf (rest (last *list1*)) *list2*)
(:FOO2 :BAR2)

CL-USER 38 > *list1*
(:FOO :BAR :FOO2 :BAR2)


For this, you don't need to roll your own code, you can use
the built-in destructive version of append: nconc.

And it will indeed be highly efficient for immensely large lists,
since memory allocation is the culprit when you use append here.
But you still need to think through whether these lists really
are the data structure you want!
-- 
  (espen)

Re: Lispworks append is too slow (2)

On 25 Apr 2008, at 15:38, Mauricio Toro wrote:
> The problem is that append is very slow in Lispworks

I think before drawing that conclusion you should obtain some  
meaningful measurements - see my other reply.

The tail-pointer trick is well known (see for instance http://www.tfeb.org/lisp/hax.html#COLLECTING 
, especially the MAKE-COLLECTOR function defined at the end), but it's  
a special purpose technique.  If you have large numbers of huge data  
structures which you want to append you probably should not be using  
lists.

--tim