Path: utzoo!yunexus!geac!syntron!jtsv16!uunet!seismo!sundc!pitstop!sun!amdcad!ames!mailrus!purdue!decwrl!labrea!csli!johnson
From: johnson@csli.STANFORD.EDU (Mark Johnson)
Newsgroups: comp.lang.lisp
Subject: Re: Summing a list
Message-ID: <6143@csli.STANFORD.EDU>
Date: 26 Oct 88 21:04:50 GMT
Article-I.D.: csli.6143
References: <10794@srcsip.UUCP> <10813@srcsip.UUCP> <6135@csli.STANFORD.EDU> <29718@think.UUCP>
Reply-To: johnson@csli.UUCP (Mark Johnson)
Organization: Center for the Study of Language and Information, Stanford U.
Lines: 81

Ah, comparing alternative programs accross different machines
is always fun stuff!

I just ran your code (slightly modified as shown below) and
obtained the following results under Allegro CL on a Mac II.
Interestingly, the non-tail recursive version (as originally
provided) is faster than the tail-recursive one!  (Or have I
made an error in the coding?)

Mark Johnson

Preferred return address: johnson@csc.brown.edu

Welcome to Allegro CL Version 1.2.1!
? (setq list nil)
NIL
? (dotimes (i 1000) (push (- 1000 i) list))
NIL
? list
(1 2 3 4...
Aborted
? (length list)
1000
? (sum-test list)
(NOTHING) took 0 ticks (0.000 seconds) to run.
(EVAL-+) took 739 ticks (12.317 seconds) to run.
(DO-LOOP) took 111 ticks (1.850 seconds) to run.
(RECURSIVE) took 315 ticks (5.250 seconds) to run.
(TRECURSIVE) took 357 ticks (5.950 seconds) to run.
(RECURSIVE1) took 170 ticks (2.833 seconds) to run.
(TRECURSIVE1) took 220 ticks (3.667 seconds) to run.
(APPLY-+) took 55 ticks (0.917 seconds) to run.
(REDUCE-+) took 375 ticks (6.250 seconds) to run.
NIL
? 

(defun sum-test (list &optional (count 100))
  (macrolet ((repeat (&body body) `(dotimes (i count) do (progn .,body)))   
             (time-it (form) `(#+symbolics without-interrupts
                               #-symbolics progn                   
                               (time ,form))))
      
    (flet ((my-false (&rest x)                                  
             (declare (ignore x))
             nil))
      (flet ((nothing () (repeat (my-false list)))
             (do-loop () (repeat (let ((sum 0)) (dolist (item list) (incf sum item)) sum)))
             (recursive ()
               (labels ((recursive-call (list)
                          (if (null list) 0
                              (+ (car list) (recursive-call (cdr list))))))
                 (repeat (recursive-call list))))
             (trecursive ()
               (labels ((trecursive-call (list sum)
                          (if (null list) sum
                              (trecursive-call (cdr list) (+ (car list) sum)))))
                 (repeat (trecursive-call list 0))))
             (recursive1 () (repeat (recursive1-call list)))
             (trecursive1 () (repeat (trecursive1-call list 0)))
             (eval-+ () (repeat (eval (cons '+ list))))
             (apply-+ () (repeat (apply #'+ list)))
             (reduce-+ () (repeat (reduce #'+ list))))
        (time-it (nothing))
        (time-it (eval-+))
        (time-it (do-loop))
        (time-it (recursive))
        (time-it (trecursive))
        (time-it (recursive1))
        (time-it (trecursive1))
        (time-it (apply-+))
        (time-it (reduce-+))))))

(declare (inline recursive1-call trecursive1-call))

(defun recursive1-call (list)
  (if (null list) 0
      (+ (car list) (recursive1-call (cdr list)))))

(defun trecursive1-call (list sum)
  (if (null list) sum
      (trecursive1-call (cdr list) (+ (car list) sum))))