[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Efficiency of Y (Was: Limitation with lambda)

 From article <8811142229.AA01756@duchamps.ads.com> (Bob Riemenschneider):
> Here's a simple experiment you can perform using your favorite Scheme.
  [three definitions of a factorial function omitted: one
   iterative, one recursive, and one using the Y combinator]
>    3.	Compute the factorial of a number using each of the three procedures,
> 	timing the results.  Make the number large enough so that you can get
> 	a reasonably accurate timing.  (I found 100 worked well for MacScheme,
> 	and 1000 for T on my Sun 3.)
> I found performance of the three to be identical, leading me to believe that,
> given current Scheme compiler technology, there's no reason to avoid using Y.

I tried this using T.  When I performed the experiment as stated, I
indeed got identical times for the three definitions:
> (time (factorial-loop 100))
  virtual time = 0.36 seconds
> (time (factorial-rec 100))
  virtual time = 0.36 seconds
> (time (factorial-lfp 100))
  virtual time = 0.36 seconds

However, when I instead calculated the factorial of a small number many
times, there was a huge difference --- more than a factor of 10 ---
between the times: 

> (time (factorial-loop 10) 1000)
  virtual time = 0.18 seconds
> (time (factorial-rec 10) 1000)
  virtual time = 0.2 seconds
> (time (factorial-lfp 10) 1000)
  virtual time = 2.58 seconds

I think the benchmark, as originally stated, mostly measures the speed
of longnum arithmetic, and not the efficiency of the various contol

Mike Coffin				mike@arizona.edu
Univ. of Ariz. Dept. of Comp. Sci.	{allegra,cmcl2}!arizona!mike
Tucson, AZ  85721			(602)621-2858