[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: lisp performance was Re: problems with lisp
- To: address@hidden
- Subject: Re: lisp performance was Re: problems with lisp
- From: Peter Seibel <address@hidden>
- Date: 31 Aug 2003 13:54:04 -0700
- Sender: address@hidden
- User-agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.3
[Sorry for the late followup on this--I tried to post this through
gmane a few days ago and that didn't work. Hopefully this goes through.]
Russ Ross <rgr22@cl.cam.ac.uk> writes:
> In this particular case, type declarations are not allowed by the
> contest rules:
>
> http://www.ravenbrook.com/doc/2003/05/28/contest/
>
> Using a bytecode lisp interpreter (clisp) and a compiler that isn't
> reputed to be all that great (gcl) undoubtedly affected the results.
> The bytecode version of the OCaml code takes about 4x longer to run
> than the native code version.
>
> I don't wish to drag out the discussion of lisp performance, as that
> was only one part of the point I was trying to make originally.
> Matthias kindly volunteered to do the PLT Scheme comparison which
> provided some interesting results. I appreciate those who have
> offered to help me tune my lisp code, but that example was just
> meant to be an anecdote comparing the efforts of a relative novice
> in both languages using the main idioms common to those languages
> (heavy recursion over list structures).
I'm not sure that "heavy recursion over list structures" is a fair
characterization of a natural Common Lisp idiom. (Scheme maybe, but I
won't speak for the Schemers).
> Getting a significant performance boost through heavy tuning would
> just support my complaint that the natural and simple way to do
> something often comes with a performance penalty. I think a useful
> design goal for languages would be to make sure that the clean,
> simple way of coding a given algorithm is also the efficient way.
That seems like a good goal. And I too have struggled to understand
the mapping between Simple Lisp and Effecient Lisp. It does sometimes
seem to be a bit of a black art. However I'm not sure the example you
show here is compelling:
> Wouldn't it be great if we didn't have to use reverse-append or
> reverse-map to get tail recursion because the compiler could
> recognize the pattern and optimize this into a tail recursive
> function? Perhaps the runtime could be smart enough to notice that
> you were using map on a really long list (with no dependency between
> elements) and convert it to (reverse (reverse-map)) for you? I'd
> love to never have to write something like:
>
> (defun double (lst)
> (labels ((f (n accum)
> (if (endp n)
> accum
> (f (cdr n) (cons (* 2 (car n)) accum)))))
> (reverse (f lst nil))))
>
> when what I really mean is:
>
> (defun double (lst)
> (if (endp lst)
> nil
> (cons (* 2 (car lst)) (double (cdr lst)))))
>
> just for the sake of efficiency.
> 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