[racket] Why is this slow?

Jordan,

I'm new to Racket, so I do not fully understand your implementation of
the sieve-of-eratosthenes. So I can't comment one why it is slow. But
I have a faster version, and maybe some differences will stand out to
investigate.

I did notice that your when your implementation of the sieve was
running, the little GC icon was always atleast flashing and sometimes
solid. Lots of intermediate results being created that need GCed? If
you compare my faster implementation of the sieve below, it has far
fewer arithmetic operations and fewer intermediate results.

My version is pretty close to what I would have done in r5rs
scheme. But I don't have the scheme library functions memorized and
used the Racket documentation to find appropriate Racket functions,
which may or may not have been in r5rs.

    #lang racket

    (define (soe n)
      (define sqrt-n (inexact->exact (ceiling(sqrt n))))

      (define primes (build-vector (add1 n) (λ (_) _)))
      (vector-copy! primes 0 (vector #f #f))

      (define (cross-off-multiples prime)
        (define (cross-off-multiples-iter not-prime)
          (if (<= not-prime n)
              [begin
                (vector-set! primes not-prime #f)
                (cross-off-multiples-iter (+ not-prime prime))]
              (visit-candidates (add1 prime))))
        (cross-off-multiples-iter (expt prime 2)))

      (define (visit-candidates  prime-candidate)
        (cond [(> prime-candidate sqrt-n) primes]
              [(not (vector-ref primes prime-candidate)) (visit-candidates
(add1 prime-candidate))]
              [(vector-ref primes prime-candidate) (cross-off-multiples
prime-candidate)]))
      (filter (λ (_) _) (vector->list (visit-candidates 2))))

I placed the two versions you gave and my version in the same
definitions file. Within the Dr Racket IDE, ran the definitions and
then:

    > (define n (inexact->exact 2e6))
    > (time (apply + (filter prime? (range 2 n))))
    cpu time: 9788 real time: 9974 gc time: 1851
    142913828922
    > (time (apply + (soe n)))
    cpu time: 1049 real time: 1065 gc time: 311
    142913828922
    > (time (apply + (sieve-of-eratosthenes n)))
    cpu time: 266955 real time: 274532 gc time: 218362
    142913828922

Machine Info:
    Model Name:              Mac Pro
    Model Identifier:        MacPro4,1
    Processor Name:          Quad-Core Intel Xeon
    Processor Speed:         2.66 GHz
    Number of Processors:    1
    Total Number of Cores:   4
    L2 Cache (per Core):     256 KB
    L3 Cache:                8 MB
    Memory:                  6 GB

    System Version:          OS X 10.8.3 (12D78)
    Kernel Version:          Darwin 12.3.0
    Boot Volume:             Macintosh SSD
    Boot Mode:               Normal
    Secure Virtual Memory:   Enabled

    DrRacket version         5.3.3
    Memory Limit             4096MB

Hoping there is a clue above.

-- Shannon