Path: utzoo!yunexus!geac!syntron!jtsv16!uunet!seismo!sundc!pitstop!sun!amdcad!ames!think!barmar
From: barmar@think.COM (Barry Margolin)
Newsgroups: comp.lang.lisp
Subject: Re: Summing a list
Message-ID: <29718@think.UUCP>
Date: 26 Oct 88 16:23:16 GMT
Article-I.D.: think.29718
References: <10794@srcsip.UUCP> <10813@srcsip.UUCP> <6135@csli.STANFORD.EDU>
Sender: news@think.UUCP
Reply-To: barmar@kulla.think.com.UUCP (Barry Margolin)
Organization: Thinking Machines Corporation, Cambridge, MA
Lines: 60


I decided to time all the various methods that have been discussed.  I
tried them on a Symbolics 3640 running Genera 7.2 and a Sun 3/280
running Lucid CL 2.0.3.  I used the default OPTIMIZE parameters.

Here is the function I used for the tests:

(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))))
	     (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 (apply-+))
	(time-it (reduce-+))))))

The argument I gave was a list of the integers from 1 to 1000.

NOTHING is there just as a control, to show the function call
overhead.  This overhead turned out to be negligible on both systems.

On the Symbolics the fastest method was APPLY-+, followed closely by
DO-LOOP.  REDUCE-+ and RECURSIVE took five and six times as long as
APPLY-+, respectively, and EVAL-+ took more than twice as long as
RECURSIVE, and consed a great deal.

In Lucid the fastest method was DO-LOOP.  RECURSIVE took a little less
than twice as long, APPLY-+ took over 8 times as long, and REDUCE-+
took twice as long as APPLY-+.  EVAL-+ was between APPLY-+ and
REDUCE-+.  GCs took place during EVAL-+ and REDUCE-+ all the times I
tried, so the GC time is being factored into these results.  The times
I am comparing are the "User cpu time".

So, if these two are representative implementations, and performance
is an issue, the best way to sum a list is to write your own loop.  In
my opinion, the clearest version is the one using APPLY, or perhaps
the one using REDUCE (APPLY has been around much longer, so I'm
generally more comfortable with it).

Barry Margolin
Thinking Machines Corp.

barmar@think.com
{uunet,harvard}!think!barmar