in general: arrays vs lists (blah blah)

Andrew Wolven <[email protected]> Mon, 25 Sep 2006 08:40:16 -0700 (PDT)
Newsgroups gmane.lisp.allegro
Message-ID <[email protected]>
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)))

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

(defun make-test-list ()
  (list 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0))

(defparameter test-array
    (make-array 9 :element-type 'double-float
:initial-contents (make-test-list)))

(defparameter test-list (make-test-list))

(defun scoot-array ()
  (loop for i from 0 to 7
      do (+ (aref test-array i) (aref test-array (1+
i)))))

(defun scoot-list ()
  (scoot-list* test-list))

(defun scoot-list* (list)
  (if (null (cdr list))
      :done
    (progn
      (+ (car list) (cadr list))
      (scoot-list* (cdr list)))))

(defun test ()
  (format t "~&scoot-array:")
  (time
   (loop for j from 1 to 1000000
       do (scoot-array)))
  (format t "~&scoot-list:")
  (time
   (loop for j from 1 to 1000000
       do (scoot-list))))

here is some output:

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

The reason I am asking is because I have an algorithm
to do cubic splines (based on my professors notes)
which consists of loading two matrices, getting the
inverse of one, multiplying them together and using
the resulting array (derivatives) to generate the
coefficients of the polynomial functions.

If I am going to show this to people who do not know
lisp, I want to make the code as straight-forward as
possible, so that they can see the algorithm in the
code and follow along.
However, at the same time I want a fast function! 
Possibly one that demonstrates recursion.

I know this is a repeat of my last posts, but I worked
most everything out on paper this time and find the
matrix version the simplest and most generalized.

AKW