[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: lisp performance was Re: problems with lisp
That's why the postscript was there: it's not a very practical
example. Most people would use the mapcar solution by default if
they actually wanted to write this and I fully expected (and
confirmed myself) that the "simple" solution would run faster.
The reason for the examples was to show the tail recursive vs.
non-tail recursive versions of a function. These were probably too
simple and good compilers may have even transformed them into tail
recursive versions--I don't know enough about the compilers in
question to say. As Common Lisp doesn't even guarantee tail call
optimization as part of the standard, it probably isn't safe to
assume that all compilers will optimize non-tail recursive calls to
use constant space even when it is possible.
The danger of providing an example is that it becomes too easy to
focus on the example instead of what it is trying to illustrate.
- Russ
On Sun, Aug 31, 2003 at 01:54:04PM -0700, Peter Seibel wrote:
<snip>
> > p.s. No, I'm not looking for better ways to implement/optimize the
> > double function ;-)
>
> I had to ignore your postscript because I'm you seem to be proving the
> opposite of what you set out to. Just for grins I tried out your two
> versions plus two of my own devising in Allegro Common Lisp (a
> highly-regarded Common Lisp implementation with a native compiler) and
> SBCL a open source Common Lisp, also with a native compiler, and CLISP
> 2.30. I'm running on a dual Xeon GNU/Linux box, FWIW. Anyway, In both
> of those implementations the version you'd rather have written was
> *faster* than the version you felt like had to write for effeciency
> sake. And both were slower than two implementations that seemed to me
> even more "simple and obvious":
>
> (defun mapcar-double (list)
> (mapcar #'(lambda (x) (* 2 x)) list))
>
> (defun loop-double (list)
> (loop for x in list collect (* 2 x)))
>
> So in this case it seems that maybe the gap between "Simple Lisp" and
> "Efficient Lisp" is due to a misapprehension about what Simple Lisp
> is, or could be. Do you have some other more realistic examples of
> what "Simple Lisp" and what it had to get turned into to become
> "Efficient Lisp"? (Feel free to send them directly to me if you think
> they're off topic for this list.)
>
>
> Anyway, below are the are the various timing results from Allegro,
> SBCL, and CLISP. (The macro test-double is shown below the results;
> basically the two numbers are the length of the list and the number of
> times to call the function on it).
>
> Allegro:
>
> CL-USER(22): (test-double 10000 10000 double) ;; This is your prefered version
> Testing DOUBLE
> ; cpu time (non-gc) 14,490 msec user, 10 msec system
> ; cpu time (gc) 600 msec user, 0 msec system
> ; cpu time (total) 15,090 msec user, 10 msec system
> ; real time 15,102 msec
> ; space allocation:
> ; 100,080,015 cons cells, 104 other bytes, 282,952 static bytes
> NIL
> CL-USER(23): (test-double 10000 10000 reverse-double) ;; This is your "optimized version"
> Testing REVERSE-DOUBLE
> ; cpu time (non-gc) 19,540 msec user, 70 msec system
> ; cpu time (gc) 1,120 msec user, 0 msec system
> ; cpu time (total) 20,660 msec user, 70 msec system
> ; real time 20,737 msec
> ; space allocation:
> ; 200,080,015 cons cells, 128 other bytes, 1,083,912 static bytes
> NIL
> CL-USER(24): (test-double 10000 10000 mapcar-double)
> Testing MAPCAR-DOUBLE
> ; cpu time (non-gc) 13,620 msec user, 10 msec system
> ; cpu time (gc) 450 msec user, 0 msec system
> ; cpu time (total) 14,070 msec user, 10 msec system
> ; real time 14,074 msec
> ; space allocation:
> ; 100,080,015 cons cells, 80 other bytes, 0 static bytes
> NIL
> CL-USER(25): (test-double 10000 10000 loop-double)
> Testing LOOP-DOUBLE
> ; cpu time (non-gc) 12,080 msec user, 10 msec system
> ; cpu time (gc) 430 msec user, 0 msec system
> ; cpu time (total) 12,510 msec user, 10 msec system
> ; real time 12,520 msec
> ; space allocation:
> ; 100,090,015 cons cells, 80 other bytes, 0 static bytes
> NIL
> CL-USER(26):
>
> * (test-double 10000 10000 double)
> Testing DOUBLE
> Evaluation took:
> 17.072 seconds of real time
> 15.22 seconds of user run time
> 1.85 seconds of system run time
> [Run times include 5.19 seconds GC run time.]
> 1 page fault and
> 943424488 bytes consed.
> NIL
>
> SBCL:
>
> * (test-double 10000 10000 reverse-double)
> Testing REVERSE-DOUBLE
> Evaluation took:
> 25.013 seconds of real time
> 21.66 seconds of user run time
> 3.3 seconds of system run time
> [Run times include 5.49 seconds GC run time.]
> 0 page faults and
> 1605457608 bytes consed.
> NIL
> * (test-double 10000 10000 mapcar-double)
> Testing MAPCAR-DOUBLE
> Evaluation took:
> 14.135 seconds of real time
> 12.31 seconds of user run time
> 1.65 seconds of system run time
> [Run times include 2.77 seconds GC run time.]
> 0 page faults and
> 802806304 bytes consed.
> NIL
> * (test-double 10000 10000 loop-double)
> Testing LOOP-DOUBLE
> Evaluation took:
> 13.351 seconds of real time
> 11.67 seconds of user run time
> 1.68 seconds of system run time
> [Run times include 2.71 seconds GC run time.]
> 0 page faults and
> 802805480 bytes consed.
> NIL
> *
>
> CLISP:
>
> Testing DOUBLE
> Real time: 51.21597 sec.
> Run time: 51.21 sec.
> Space: 800000000 Bytes
> GC: 1466, GC time: 16.83 sec.
>
> Testing REVERSE-DOUBLE
> Real time: 66.582756 sec.
> Run time: 66.58 sec.
> Space: 1600000000 Bytes
> GC: 2864, GC time: 33.12 sec.
>
> Testing MAPCAR-DOUBLE
> Real time: 41.80126 sec.
> Run time: 41.8 sec.
> Space: 800000000 Bytes
> GC: 1489, GC time: 16.5 sec.
>
> Testing LOOP-DOUBLE
> Real time: 46.084793 sec.
> Run time: 46.08 sec.
> Space: 800000000 Bytes
> GC: 1467, GC time: 16.66 sec.
> NIL
>
>
> (defmacro test-double (list-length iters fn)
> `(progn
> (format *trace-output* "Testing ~a~%" ',fn)
> (let ((list (loop for i from 1 to ,list-length collect i)))
> (time (dotimes (i ,iters) (,fn list))))))
>
> -Peter
>
>
> --
> Peter Seibel peter@javamonkey.com
>
> Lisp is the red pill. -- John Fraser, comp.lang.lisp
>