<div dir="ltr">Hi: beware that timing inside DrRacket can be very misleading (DrRacket is doing lots of stuff). See:<div><br></div><div>  <a href="http://docs.racket-lang.org/guide/performance.html?q=performance">http://docs.racket-lang.org/guide/performance.html?q=performance</a></div>
<div><br></div><div style>for more details.</div><div style><br></div><div style>Robby</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, Apr 24, 2013 at 4:38 AM, Shannon Severance <span dir="ltr">&lt;<a href="mailto:srs@s53.me" target="_blank">srs@s53.me</a>&gt;</span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Jordan,<br>
<br>
I&#39;m new to Racket, so I do not fully understand your implementation of<br>
the sieve-of-eratosthenes. So I can&#39;t comment one why it is slow. But<br>
I have a faster version, and maybe some differences will stand out to<br>
investigate.<br>
<br>
I did notice that your when your implementation of the sieve was<br>
running, the little GC icon was always atleast flashing and sometimes<br>
solid. Lots of intermediate results being created that need GCed? If<br>
you compare my faster implementation of the sieve below, it has far<br>
fewer arithmetic operations and fewer intermediate results.<br>
<br>
My version is pretty close to what I would have done in r5rs<br>
scheme. But I don&#39;t have the scheme library functions memorized and<br>
used the Racket documentation to find appropriate Racket functions,<br>
which may or may not have been in r5rs.<br>
<br>
    #lang racket<br>
<br>
    (define (soe n)<br>
      (define sqrt-n (inexact-&gt;exact (ceiling(sqrt n))))<br>
<br>
      (define primes (build-vector (add1 n) (λ (_) _)))<br>
      (vector-copy! primes 0 (vector #f #f))<br>
<br>
      (define (cross-off-multiples prime)<br>
        (define (cross-off-multiples-iter not-prime)<br>
          (if (&lt;= not-prime n)<br>
              [begin<br>
                (vector-set! primes not-prime #f)<br>
                (cross-off-multiples-iter (+ not-prime prime))]<br>
              (visit-candidates (add1 prime))))<br>
        (cross-off-multiples-iter (expt prime 2)))<br>
<br>
      (define (visit-candidates  prime-candidate)<br>
        (cond [(&gt; prime-candidate sqrt-n) primes]<br>
              [(not (vector-ref primes prime-candidate)) (visit-candidates<br>
(add1 prime-candidate))]<br>
              [(vector-ref primes prime-candidate) (cross-off-multiples<br>
prime-candidate)]))<br>
      (filter (λ (_) _) (vector-&gt;list (visit-candidates 2))))<br>
<br>
I placed the two versions you gave and my version in the same<br>
definitions file. Within the Dr Racket IDE, ran the definitions and<br>
then:<br>
<br>
    &gt; (define n (inexact-&gt;exact 2e6))<br>
    &gt; (time (apply + (filter prime? (range 2 n))))<br>
    cpu time: 9788 real time: 9974 gc time: 1851<br>
    142913828922<br>
    &gt; (time (apply + (soe n)))<br>
    cpu time: 1049 real time: 1065 gc time: 311<br>
    142913828922<br>
    &gt; (time (apply + (sieve-of-eratosthenes n)))<br>
    cpu time: 266955 real time: 274532 gc time: 218362<br>
    142913828922<br>
<br>
Machine Info:<br>
    Model Name:              Mac Pro<br>
    Model Identifier:        MacPro4,1<br>
    Processor Name:          Quad-Core Intel Xeon<br>
    Processor Speed:         2.66 GHz<br>
    Number of Processors:    1<br>
    Total Number of Cores:   4<br>
    L2 Cache (per Core):     256 KB<br>
    L3 Cache:                8 MB<br>
    Memory:                  6 GB<br>
<br>
    System Version:          OS X 10.8.3 (12D78)<br>
    Kernel Version:          Darwin 12.3.0<br>
    Boot Volume:             Macintosh SSD<br>
    Boot Mode:               Normal<br>
    Secure Virtual Memory:   Enabled<br>
<br>
    DrRacket version         5.3.3<br>
    Memory Limit             4096MB<br>
<br>
Hoping there is a clue above.<br>
<span class="HOEnZb"><font color="#888888"><br>
-- Shannon<br>
</font></span><div class="HOEnZb"><div class="h5"><br>
<br>
<br>
____________________<br>
  Racket Users list:<br>
  <a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/users</a><br>
</div></div></blockquote></div><br></div>