[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_