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

On Mon, Sep 25, 2006 at 08:40:16AM -0700, Andrew Wolven wrote:
> (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))))
> 

Also I neglected to mention that your example is precarious because the
compiler is free to delete the calls to + in either case.  They do not
effect the state of the world nor do their return values get used.  This
could be the reason that Allegro is showing no boxing for the list
example.

I recommend collecting the result and returning it.

(defun scoot-list* (list result)
  (cond ((null (rest list))
         result)
        (t
         (scoot-list* (rest list)
                      (+ result (first list) (second list))))))

(defun scoot-list (list) (scoot-list* list 0))

;; Note that the above defn, like yours, contains a "tail-call" which
;; technically is turned into a simple "goto" by the compiler, rather
;; than generating a new call frame.  This is a common technique, when
;; writing structurally recursive programs that technically are
;; iterative in nature.  However, this optimization, while performed by
;; every CL compiler I know, is not a requirement.

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