Re: in general: arrays vs lists (blah blah)

On Mon, Sep 25, 2006 at 08:40:16AM -0700, Andrew Wolven wrote:
> Can anyone tell me why traversing down a list:
> (+ (car s) (cadr s))
> 
> is so much faster than using arrays?
> (+ (aref s i) (aref s (1+ i)))

If you understand List Structure, you'll realize that lists are
constructed "recursively" so to speak:

  a list is either NIL or (CONS elem shorter-list)

So (list 1.0 2.0 3.0) is really:

  (cons 1.0 (cons 2.0 (cons 3.0 nil)))

Hence writing structurally recursive programs on lists is both fast and
easy.  Not to mention Allegro CL has some clever implementational tricks
for dealing with conses and NIL quickly.

However, I suspect that if you annotate the array example with the
correct type and optimization declarations, it will speed up quite a
bit.

> Here is my test program:
> (in-package :user)

^ not a real package btw

> cl-user(24):  (test)
> scoot-array:
> ; cpu time (non-gc) 798 msec user, 15 msec system
> ; cpu time (gc)     265 msec user, 0 msec system
> ; cpu time (total)  1,063 msec user, 15 msec system
> ; real time  1,437 msec
> ; space allocation:
> ;  1 cons cell, 384,000,000 other bytes, 0 static
> bytes

Look at this space allocation.  I believe that Allegro must be boxing
the floats before applying Generic Arithmetic.  That can be corrected
with type declarations.

> scoot-list:
> ; cpu time (non-gc) 219 msec user, 0 msec system
> ; cpu time (gc)     0 msec user, 0 msec system
> ; cpu time (total)  219 msec user, 0 msec system
> ; real time  219 msec
> ; space allocation:
> ;  0 cons cells, 0 other bytes, 0 static bytes

Admittedly, I don't know why Allegro doesn't box in this case, but
perhaps it's because it is clever with cons cells.

-- 
;; Matthew Danish -- user: mrd domain: cmu.edu
;; OpenPGP public key: C24B6010 on keyring.debian.org