[racket] generator performance (again)

From: Patrick Useldinger (uselpa.list at gmail.com)
Date: Sun Oct 7 13:34:44 EDT 2012

Hi,

following up on my earlier thread (sep 16th) on the same subject, I 
tried to compare some solutions generating fibonacci series in a lazy 
way: via a closure, via generators and using delay/force.

The results are correct for all methods:

fibo-clos : 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 
4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229
fibo-gen1 : 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 
4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229
fibo-gen2 : 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 
4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229
fibo-delay: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 
4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229

but the execution times vary vastly:

fibo-clos : cpu time: 5892 real time: 6133 gc time: 725
fibo-gen1 : cpu time: 14592 real time: 15176 gc time: 1713
fibo-gen2 : cpu time: 3 real time: 2 gc time: 0
fibo-delay: cpu time: 14245 real time: 14479 gc time: 8545

The funny thing is the difference between fibo-gen1 (the slowest) and 
fibo-gen2 (the fastest by a huge margin). The code is virtually the 
same, the only difference being that fibo-gen1 uses (in-producer) to 
call the generator, and fibo-gen2 calls it directly:

(define fibo-gen
   (generator ()
     (let loop ((n-1 0) (n 1))
       (yield n-1)
       (loop n (+ n-1 n)))))

(define (run-fibo-gen1 count verbose)
   (printf "fibo-gen1 : ")
   (for ( [i (in-range count)]
          [f (in-producer fibo-gen #f)])
     (when verbose (printf "~a " f)))
   (when verbose (printf "\n")))

(define (run-fibo-gen2 count verbose)
   (printf "fibo-gen2 : ")
   (for ( [i (in-range count)] )
     (when verbose (printf "~a " (fibo-gen))))
   (when verbose (printf "\n")))

Is this to be expected?

Full code:

#!/usr/bin/env racket
#lang racket

; generate a lazy fibonacci sequence
; ----------------------------------

; --- closure

(define (fibo-clos)
   (let ((n-1 0) (n 1))
     (lambda ()
       (let ((res n-1) (next (+ n-1 n)))
         (set! n-1 n)
         (set! n next)
         res))))

(define (run-fibo-clos count verbose)
   (printf "fibo-clos : ")
   (for ( [i (in-range count)]
          [f (in-producer (fibo-clos) #f)])
     (when verbose (printf "~a " f)))
   (when verbose (printf "\n")))

; --- generator

(require racket/generator)

(define fibo-gen
   (generator ()
     (let loop ((n-1 0) (n 1))
       (yield n-1)
       (loop n (+ n-1 n)))))

(define (run-fibo-gen1 count verbose)
   (printf "fibo-gen1 : ")
   (for ( [i (in-range count)]
          [f (in-producer fibo-gen #f)])
     (when verbose (printf "~a " f)))
   (when verbose (printf "\n")))

(define (run-fibo-gen2 count verbose)
   (printf "fibo-gen2 : ")
   (for ( [i (in-range count)] )
     (when verbose (printf "~a " (fibo-gen))))
   (when verbose (printf "\n")))

; --- delay

(define (fibo-delay)
   (delay
     (let loop ((n-1 0) (n 1))
       (values n-1 (delay (loop n (+ n-1 n)))))))

(define (run-fibo-delay count verbose)
   (printf "fibo-delay: ")
   (let loop ((i 1) (fibo-delay (fibo-delay)))
     (let-values ([(fibo-delay-val fibo-delay) (force fibo-delay)])
       (when verbose (printf "~a " fibo-delay-val))
       (when (< i count) (loop (add1 i) fibo-delay))))
   (when verbose (printf "\n")))

; --- main

(define (main args)
   (let* ([count (string->number (vector-ref args 0))]
          [type (vector-ref args 1)]
          [algo (vector-ref args 2)])
     (cond
       ((string=? algo "clos")
        (if (string=? type "r")
            (run-fibo-clos count #t)
            (time (run-fibo-clos count #f))))
       ((string=? algo "gen1")
        (if (string=? type "r")
            (run-fibo-gen1 count #t)
            (time (run-fibo-gen1 count #f))))
       ((string=? algo "gen2")
        (if (string=? type "r")
            (run-fibo-gen2 count #t)
            (time (run-fibo-gen2 count #f))))
       ((string=? algo "delay")
        (if (string=? type "r")
            (run-fibo-delay count #t)
            (time (run-fibo-delay count #f))))
        (else
          (displayln algo)))))

(main (current-command-line-arguments))

Posted on the users mailing list.