[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
followup to tail recursion code

To: slug@ai.sri.com
Subject: followup to tail recursion code
From: robinson%pravda@gatech.edu (Stephen M. Robinson)
Date: Fri, 9 Nov 1990 13:12:24 -0500
I played around with Rich Cohen's recent tail recursion optimization
code using "time" to get a quick idea of the difference such
optimization can make. Here are the results.

(P.S. Should the DefOptimizer be put *after* the other defs in the file
to avoid problems with the compiler trying to use an incomplete
optimizer while compiling the rest of the file? Or, am I missing
something?) 

This is one of Cohen's test funcs. I ran it looking for the last member
of a list of 10000 items.

(defun D,#TD1PsT[Begin using 006 escapes](1 0 (NIL 0) (NIL :BOLD NIL) "CPTFONTCB")My-Member 0(X L)
   (if (null L)
       NIL
       (if (eql X (car L))
	   L
	   (My-Member X (cdr L))))
   )

"*list*" was created by
(setq *list*
  (loop for a from 1 to 10000 collect a in b finally (return b)))

First, my-member compiled without tail recursion optimization

  (loop for a from 1 to 5 do (time (my-member 10000 *list*)))
Evaluation of (MY-MEMBER 10000 *LIST*) took 0.432555 seconds of elapsed time including:
  0.008 seconds processing sequence breaks,
  0.067 seconds in the storage system (including 0.000 seconds waiting for pages):
    0.067 seconds processing 197 page faults including 0 fetches,
    0.000 seconds in creating and destroying pages, and
    0.000 seconds in miscellaneous storage system tasks.
Evaluation of (MY-MEMBER 10000 *LIST*) took 0.402645 seconds of elapsed time including:
  0.005 seconds processing sequence breaks,
  0.042 seconds in the storage system (including 0.000 seconds waiting for pages):
    0.042 seconds processing 138 page faults including 0 fetches,
    0.000 seconds in creating and destroying pages, and
    0.000 seconds in miscellaneous storage system tasks.
Evaluation of (MY-MEMBER 10000 *LIST*) took 0.398398 seconds of elapsed time including:
  0.005 seconds processing sequence breaks,
  0.045 seconds in the storage system (including 0.000 seconds waiting for pages):
    0.045 seconds processing 130 page faults including 0 fetches,
    0.000 seconds in creating and destroying pages, and
    0.000 seconds in miscellaneous storage system tasks.
Evaluation of (MY-MEMBER 10000 *LIST*) took 0.452039 seconds of elapsed time including:
  0.007 seconds processing sequence breaks,
  0.099 seconds in the storage system (including 0.000 seconds waiting for pages):
    0.099 seconds processing 307 page faults including 0 fetches,
    0.000 seconds in creating and destroying pages, and
    0.000 seconds in miscellaneous storage system tasks.
Evaluation of (MY-MEMBER 10000 *LIST*) took 0.447140 seconds of elapsed time including:
  0.006 seconds processing sequence breaks,
  0.094 seconds in the storage system (including 0.000 seconds waiting for pages):
    0.094 seconds processing 293 page faults including 0 fetches,
    0.000 seconds in creating and destroying pages, and
    0.000 seconds in miscellaneous storage system tasks.

My-member compiled with optimization on:

  (loop for a from 1 to 5 do (time (my-member 10000 *list*)))
Evaluation of (MY-MEMBER 10000 *LIST*) took 0.081867 seconds of elapsed time including:
  0.002 seconds processing sequence breaks,
  0.001 seconds in the storage system (including 0.000 seconds waiting for pages):
    0.001 seconds processing 4 page faults including 0 fetches,
    0.000 seconds in creating and destroying pages, and
    0.000 seconds in miscellaneous storage system tasks.
Evaluation of (MY-MEMBER 10000 *LIST*) took 0.074971 seconds of elapsed time including:
  0.002 seconds processing sequence breaks,
  0.000 seconds in the storage system (including 0.000 seconds waiting for pages):
    0.000 seconds processing 0 page faults including 0 fetches,
    0.000 seconds in creating and destroying pages, and
    0.000 seconds in miscellaneous storage system tasks.
Evaluation of (MY-MEMBER 10000 *LIST*) took 0.074971 seconds of elapsed time including:
  0.002 seconds processing sequence breaks,
  0.000 seconds in the storage system (including 0.000 seconds waiting for pages):
    0.000 seconds processing 0 page faults including 0 fetches,
    0.000 seconds in creating and destroying pages, and
    0.000 seconds in miscellaneous storage system tasks.
Evaluation of (MY-MEMBER 10000 *LIST*) took 0.074719 seconds of elapsed time including:
  0.001 seconds processing sequence breaks,
  0.000 seconds in the storage system (including 0.000 seconds waiting for pages):
    0.000 seconds processing 0 page faults including 0 fetches,
    0.000 seconds in creating and destroying pages, and
    0.000 seconds in miscellaneous storage system tasks.
Evaluation of (MY-MEMBER 10000 *LIST*) took 0.076016 seconds of elapsed time including:
  0.000 seconds processing sequence breaks,
  0.000 seconds in the storage system (including 0.000 seconds waiting for pages):
    0.000 seconds processing 0 page faults including 0 fetches,
    0.000 seconds in creating and destroying pages, and
    0.000 seconds in miscellaneous storage system tasks.

Using a loop for comparison (compiled defun):
(defun 1my-loop-member 0(x l)
  (loop for i in l if (eql x i) return i finally (return nil))
  )

  (loop for a from 1 to 5 do (time (my-loop-member 10000 *list*)))
Evaluation of (MY-LOOP-MEMBER 10000 *LIST*) took 0.084687 seconds of elapsed time including:
  0.001 seconds processing sequence breaks,
  0.000 seconds in the storage system (including 0.000 seconds waiting for pages):
    0.000 seconds processing 4 page faults including 0 fetches,
    0.000 seconds in creating and destroying pages, and
    0.000 seconds in miscellaneous storage system tasks.
Evaluation of (MY-LOOP-MEMBER 10000 *LIST*) took 0.090015 seconds of elapsed time including:
  0.002 seconds processing sequence breaks,
  0.000 seconds in the storage system (including 0.000 seconds waiting for pages):
    0.000 seconds processing 0 page faults including 0 fetches,
    0.000 seconds in creating and destroying pages, and
    0.000 seconds in miscellaneous storage system tasks.
Evaluation of (MY-LOOP-MEMBER 10000 *LIST*) took 0.085557 seconds of elapsed time including:
  0.001 seconds processing sequence breaks,
  0.000 seconds in the storage system (including 0.000 seconds waiting for pages):
    0.000 seconds processing 0 page faults including 0 fetches,
    0.000 seconds in creating and destroying pages, and
    0.000 seconds in miscellaneous storage system tasks.
Evaluation of (MY-LOOP-MEMBER 10000 *LIST*) took 0.099583 seconds of elapsed time including:
  0.002 seconds processing sequence breaks,
  0.001 seconds in the storage system (including 0.000 seconds waiting for pages):
    0.001 seconds processing 2 page faults including 0 fetches,
    0.000 seconds in creating and destroying pages, and
    0.000 seconds in miscellaneous storage system tasks.
Evaluation of (MY-LOOP-MEMBER 10000 *LIST*) took 0.085144 seconds of elapsed time including:
  0.001 seconds processing sequence breaks,
  0.000 seconds in the storage system (including 0.000 seconds waiting for pages):
    0.000 seconds processing 0 page faults including 0 fetches,
    0.000 seconds in creating and destroying pages, and
    0.000 seconds in miscellaneous storage system tasks.
Follow-Ups:
- Re: followup to tail recursion code
  - From: HI.COHEN@MCC.COM (Rich Cohen)
Prev by Date: Tail recursion
Next by Date: Fast Graphics on 3653
Previous by thread: UX400s.
Next by thread: Re: followup to tail recursion code
Index(es):
- Date
- Thread