Racket streams slower than custom streams?

Question

I implemented a simple and not very efficent sieve of eratosthenes. Once for the built in racket-streams, and once for self defined streams. The only known difference to me is that the built in streams are evaluating the first item on call and not on construction. When evaluating the first 1000 primes on both implementations the self defined streams are running 10-20 times as fast. Is there any explanation?

(define (integers-starting-from-stream n)
  (stream-cons n (integers-starting-from-stream (+ n 1))))

(define (stream-limit s limit)
    (when (not (= limit 0)) (stream-limit (stream-rest s) (- limit 1))))

(define x (integers-starting-from-stream 2))

(define (divisible? x y)
  (= (remainder x y) 0))

(define (sieve s)
  (stream-cons
   (stream-first s)
   (sieve (stream-filter
           (lambda (x)
             (not (divisible? x (stream-first s))))
           (stream-rest s)))))
(time (stream-limit (sieve x) 1000))

Or am i mising something that's affecting the performance?

(define-syntax-rule (s-delay exp)
  (λ() exp))

(define (s-force delayedObject)
  (delayedObject))

(define empty-s 'S-EMPTY-STREAM)

(define (s-empty? s)
  (eq? s empty-s))

(define (s-first s)
  (car s))

(define (s-rest s)
  (s-force (cdr s)))

(define-syntax-rule (s-cons a b)
  (cons a (s-delay b)))
(define (s-filter p s)
  (cond ((s-empty? s) empty-s)
        ((p (s-first s))
         (s-cons (s-first s)
                 (s-filter p (s-rest s))))
        (else (s-filter p (s-rest s)))))
;;;;;;;;;;;;;;;;;;;;
(define (divisible? x y)
  (= (remainder x y) 0))

(define (integers-starting-from n)
  (s-cons n (integers-starting-from (+ n 1))))

(define (s-limit s limit)
    (when (not (= limit 0)) (s-limit (s-rest s) (- limit 1))))

(define x (integers-starting-from 2))

(define (sieve s)
  (s-cons (s-first s) (sieve (s-filter (lambda(x) (not (divisible? x (s-first s)))) (s-rest s)))))
(time (s-limit (sieve x) 1000))

Answer 1

Here is an observation:

Using a version of integers-starting-from-stream that prints the numbers as they are generated:

(define (integers-starting-from-stream n)
  (stream-cons n
               (begin
                 (display (~a n " "))
                 (integers-starting-from-stream (+ n 1)))))

And similarly:

(define (integers-starting-from n)
  (s-cons n
          (begin (display (~a n " "))
                 (integers-starting-from (+ n 1)))))

We can test with:

(collect-garbage) (collect-garbage) (collect-garbage)
(time (stream-limit (sieve x) 10))
(collect-garbage) (collect-garbage) (collect-garbage)
(time (s-limit (s-sieve s-x) 10))

We observe that the stream-version prints the numbers from 2 to 51 where as the s-version prints the numbers from 2 to 30.

The list generated by the stream version is nearly of double size.

This is the first (and most important) reason the stream version is slower than the custom version.

The second reason the stream version is slower, is that the stream version caches the result of stream-first. Caching will be in general be faster, when the computation of the element is slow.

(define (integers-starting-from-stream n)
  (stream-cons (begin (sleep 1) n)
               (integers-starting-from-stream (+ n 1))))

and

(define (integers-starting-from n)
  (s-cons (begin (sleep 1) n)
          (integers-starting-from (+ n 1))))

And then run:

(collect-garbage) (collect-garbage) (collect-garbage)
(define x (integers-starting-from-stream 2))
(time (stream-limit x 10))
(time (stream-limit x 10))
(collect-garbage) (collect-garbage) (collect-garbage)
(define s-x (integers-starting-from 2))
(time (s-limit s-x 10))
(time (s-limit s-x 10))