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))

Ake

I assume you are running the compiled code. I've played a little with it and while your implementation skips memoization and lazy car I get only 5 times slower if I add it. My best guess is that JIT manages to constant fold the local code and perhaps not so good when it's in its own module. You might be interested in how to look at what the jit has done – Christinchristina

@Ake Can you post a ready-to-run example, so we can try the benchmark our-selves? – Scarab

@Scarab They should be ready to run, you just jave to add #lang racket at the top. – Ake

I cannot offer any solution or answer but I can confirm that the Racket stream implementation of the Sieve of Eratosthenes is painfully, unacceptably, slow! The algorithm you use is pretty standard (see e.g. SICP); comparing it e.g. to MIT-Scheme it is about 100x slower when finding the 500th prime! 3 minutes on an i7? Really? Comparing it to Clojure it will simply cause despair. Something seriously awry, I think. Not usable as it is. But perhaps we're all missing something obvious... – Subway

It's not just the speed, either. Space demands are ridiculous too. Had to take the memory limit to 4096 MB just to be able to calculate the 500th prime (3581). I will look into it at some stage but as it stands it is not really fit for purpose. – Subway

Apparently, this is a well-known issue, going back many years. See, for instance, lists.racket-lang.org/users/archive/2011-March/044656.html I do not know if this has been addressed yet, it should have been, but if not, if you want to work through SICP with Racket, you'll have to make your own stream-conser. – Subway

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))

Scarab

Do you have any explantion, why the stream list would be twice, for larger values even mor than twice the size? And if I understand correctly you are saying that the stream caches the values, but it would be faster if not? – Ake

@Ake Caching has both extra code that needs executing and it has increased memory usage. The benefit is when you do stream-rest the previously calculated step would be cached and thus the code run second time around is one if and a binding eval. However you never access the stream parts more than once so the caching in this case have no benefits. – Christinchristina

@alex Not besides the difference between always evaluating the first element versus delaying the first element. Experiment with integers-starting-from-stream and stream-limit and see if you can get them to produce lists of the same length. – Scarab