[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: lisp performance was Re: problems with lisp
On Thu, Aug 28, 2003 at 11:24:46PM +0100, Russ Ross wrote:
> 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. Lisp isn't the only one guilty of
> this (OCaml is the same, as are almost all languages) but this is
> just an example to illustrate a point: modern languages let us be
> artists, abstractors, and aestheticians some of the time, but they
> still force us to be human compilers all too often.
Well, just as a data point, then, with CMU CL (18e, as packaged by
Peter van Eynde, for Debian):
(defun double (lst)
(labels ((f (n accum)
(if (endp n)
accum
(f (cdr n) (cons (* 2 (car n)) accum)))))
(reverse (f lst nil))))
(defun double-2 (lst)
(if (endp lst)
nil
(cons (* 2 (car lst)) (double (cdr lst)))))
(defun o-double (lst)
(declare (optimize (speed 3) (compilation-speed 0) (debug 0)))
(labels ((f (n accum)
(if (endp n)
accum
(f (cdr n) (cons (* 2 (car n)) accum)))))
(reverse (f lst nil))))
(defun o-double-2 (lst)
(declare (optimize (speed 3) (compilation-speed 0) (debug 0)))
(if (endp lst)
nil
(cons (* 2 (car lst)) (double (cdr lst)))))
(defparameter *apa* (loop repeat 1000
collect
(random (* 100 most-positive-fixnum))))
(defparameter *bepa* (loop repeat (* 1000 1000)
collect
(random (* 100 most-positive-fixnum))))
* (time (prog1 nil (double *apa*)))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 0.0 seconds of real time
; 0.0 seconds of user run time
; 0.0 seconds of system run time
; 475,696 CPU cycles
; 1 page fault and
; 31,896 bytes consed.
;
NIL
* (time (prog1 nil (double-2 *apa*)))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 0.0 seconds of real time
; 0.0 seconds of user run time
; 0.0 seconds of system run time
; 472,247 CPU cycles
; 0 page faults and
; 31,888 bytes consed.
;
NIL
* (time (prog1 nil (double *bepa*)))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 4.96 seconds of real time
; 2.17 seconds of user run time
; 0.23 seconds of system run time
; 6,472,984,798 CPU cycles
; [Run times include 2.0 seconds GC run time]
; 0 page faults and
; 31,889,520 bytes consed.
;
NIL
* (time (prog1 nil (double-2 *bepa*)))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 1.3 seconds of real time
; 1.13 seconds of user run time
; 0.11 seconds of system run time
; 1,683,858,574 CPU cycles
; [Run times include 0.84 seconds GC run time]
; 0 page faults and
; 31,889,560 bytes consed.
;
NIL
* (time (prog1 nil (o-double *apa*)))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 0.0 seconds of real time
; 0.0 seconds of user run time
; 0.0 seconds of system run time
; 484,820 CPU cycles
; 0 page faults and
; 31,896 bytes consed.
;
NIL
* (time (prog1 nil (o-double-2 *apa*)))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 0.0 seconds of real time
; 0.0 seconds of user run time
; 0.0 seconds of system run time
; 463,580 CPU cycles
; 0 page faults and
; 31,888 bytes consed.
;
NIL
* (time (prog1 nil (o-double *bepa*)))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 2.02 seconds of real time
; 0.96 seconds of user run time
; 0.4 seconds of system run time
; 2,623,532,407 CPU cycles
; [Run times include 0.97 seconds GC run time]
; 0 page faults and
; 31,886,224 bytes consed.
;
NIL
* (time (prog1 nil (o-double-2 *bepa*)))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 1.58 seconds of real time
; 1.43 seconds of user run time
; 0.06 seconds of system run time
; 2,054,434,395 CPU cycles
; [Run times include 1.09 seconds GC run time]
; 0 page faults and
; 31,889,544 bytes consed.
;
NIL
*
Rather slim differences, in my book. On the other hand; Python is a
quite good compiler, and it doesn't have much to do with the language
per se. If I have misunderstood your argument, please forgive me for
wasting time (and computrons).
(The timings were run an AMD Duron 1300 with 256 Mio memory.)
Regards,
'mr
--
[Emacs] is written in Lisp, which is the only computer language that is
beautiful. -- Neal Stephenson, _In the Beginning was the Command Line_