[racket] Why is this slow?

From: Gary Baumgartner (gfb at cs.toronto.edu)
Date: Wed Apr 24 05:17:28 EDT 2013

The `range` function produces a list, which is a big overhead for each time
 the inner loop executes. There's a big improvement changing the inner loop
 sequence clause to just [p n]. There's a bit more improvement making that
 [p (in-range n)], which is recognized statically at expansion time by the
 `for` loop to  produce better code. See:

  http://docs.racket-lang.org/guide/for.html#(part._for-performance)

Filtering the final list during building is also an improvement:

  (for/list ([i (range 2 n)]
             #:when (vector-ref A i))
    i)

And let's make it more consistent with the comment style, and consistent
 with the above changes. This appears to speed it up even more, although
 I didn't investigate where exactly the big win(s) were:


#lang racket

;; Input: an integer n > 1
(define (sieve-of-eratosthenes n)
  ;; Let A be an array of Boolean values, indexed by integers 2 to n,
  ;; initially all set to true.

  ;; for i = 2, 3, 4, ..., √n :
  ;;   when A[i] is true:
  ;;     for j = i², i²+i, i²+2i, ..., n:
  ;;       A[j] := false
  (define A (make-vector n #t))
  (for ([i (in-range 2 (sqrt n))]
        #:when (vector-ref A i))
    (for ([j (in-range (sqr i) n i)])
      (vector-set! A j #f)))

  ;; Now all i such that A[i] is true are prime.
  (for/list ([i (in-range 2 n)]
             #:when (vector-ref A i))
    i))

(time (apply + (sieve-of-eratosthenes 2000000)))


Posted on the users mailing list.