[plt-scheme] recursion and efficiency?!

Manfred Lotz wrote:

>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
> 
> Hi folks,
> I'm a newbie to both scheme and to the paradigm of functional
> programming.
> 
> I built three versions of fact:

...

> I assumed fact2 and fact3 being superior from a timing perspective.
> However fact1 is the fastest.
> 
> (fact1 20000)
> 	cpu time: 2046 real time: 2202 gc time: 996
> 	2,31s user 0,05s system 92% cpu 2,544 total
> 
> (fact2 20000)
> 	cpu time: 6287 real time: 7194 gc time: 5199
> 	6,52s user 0,07s system 87% cpu 7,528 total
> 
> (fact3 20000)
> 	cpu time: 5677 real time: 6128 gc time: 4711
> 	5,95s user 0,04s system 92% cpu 6,453 total

There are at least two problems.

The first is that (fact 20000) is *very* large number. That means
that the majority of the running  time is spent by the bignum
calculations. This means that the thing you want to measure (i.e.
the costs of function application) is lost in the noise.

The second problem is that the first call (fact1 2000) can generate
garbage, which is first collected when the second call (fact2 2000)
is run. This is a bit unfair.

> Can anybody explain to me why the recursive version is the fastest?

Probably due to the second problem.


For comparison I changed the factorials into sums and
initiated a garbage collection before each timing.

;; recursion
(define (sum1 n)
   (cond ((= n 0) 0)
         (else
          (+ n (sum1 (- n 1))))))

;; tail recursion from n to 1
(define (sum2 n)
   (define (iterate n acc)
     (if (<= n 1)
         acc
         (iterate (- n 1)
                  (+ n acc))))
   (iterate n 1))

;; tail recursion from 1 to n
(define (sum3 n)
   (define (iterate i acc)
     (if (> i n)
         acc
         (iterate (+ i 1)
                  (+ i acc))))
   (iterate 1 0))

(define n 1000000)
(collect-garbage)
(time (sum1 n))
(collect-garbage)
(time (sum2 n))
(collect-garbage)
(time (sum3 n))


On my machine I got these results:

cpu time: 40398 real time: 85433 gc time: 4827
500000500000
cpu time: 2514 real time: 4186 gc time: 0
500000500000
cpu time: 2584 real time: 3435 gc time: 0
500000500000


Observe that the two tail recursive solutions doesn't trigger
a garbage collection.


As a side note: Calculating factorials are also a bad way
to benchmark bignum libraries, since the most common uses
bignums in programs are bignums just greater than fixnums.



-- 
Jens Axel Søgaard