Cons versus Append function

[Costinbos77]

Hi gents .

 

Working around with some big lists of coordinates , I just came across the following :

 

; p i [x y z]

(repeat n
...
 (setq l (cons p1 (cons p2 (cons p3 l))) )
...
)

 

And I said why in this way and not as below :

; p i [x y z]

(repeat n
...
 (setq l (append (list p1 p2 p3) l) )
...
)

 

The result is the same , but the APPEND function takes far more time .

 

(defun c:Test (/ c i l p te ts x y z)
 (princ "\n   Test  :  V  :  7 . 09 . 2024  ;")
 (setq c (if (= (getString "\n   Test  TYPE  :  Any  =  APPEND  ;   <  Enter  =  CONS  >  :  ") "") T nil)
       ts (getVar "cDate")  x 35363738.123456789  y 53545556.123456789  z 2567.123456789  i 0  l nil)
 (repeat 5000 (setq x (+ x 1)  y (+ y 1)  z (+ z 1)  p (list x y z)  i (1+ i) )
  (if c (setq l (cons p (cons p (cons p l))) ) (setq l (append (list p p p) l)) ) ; if
 ) ; r
 (setq te (getVar "cDate")  ti (RtoS (* (- te ts) 10e6) 2 16) )
 (princ (strcat "\n   " (if c "CONS" "APPEND") "  :  i = " (itoA i)  "  ;  Time  = " ti "  ;")) (princ)
) ; c:Test

   ;    CONS  :  i = 5000  ;  Time  = 0.000000000000000  ;
   ;    APPEND  :  i = 5000  ;  Time  = 40.00961780548095  ;

 

Do you have the same big difference , or my computer is broken ?

 

Regards ,

[Lee Mac]

Since AutoLISP lists are stored as singly-linked lists in memory (whereby each element is a pair consisting of a value (car) and a pointer to the next pair (cdr), with the last pair containing a null pointer), using cons to push an item onto a list is a very efficient operation, as a new cons pair can simply point to the previous head of the list. Whereas, to append an element to the end of the list, the interpreter must traverse the entire linked list and point the last element to the newly appended element.

 

As such, the performance of cons will not be impacted by the list length, whereas the performance of append will worsen by a factor of the list length.

[Costinbos77]

Thank you very much for your detailed explanation . Now I, t is very clear .

 

I was thinking CONS needs to push / move all the existing elements back down to create space for the new one , in which case is time-consuming.

 

Regards ,

Edited September 7 by Costinbos77

[Lee Mac]

No - unlike an array (which is stored in contiguous memory), a linked list merely needs to update the pointers between successive elements.

Edited September 7 by Lee Mac

[dexus]

I knew cons was faster, but didn't know why. Interesting stuff Lee!

 

How about vl-list*, do you know, does it work the same as cons?

It seems to be the same speed when adding a single item and even quicker that chaining cons when adding multiple items.