[racket] Why is this slow?

Hi: beware that timing inside DrRacket can be very misleading (DrRacket is
doing lots of stuff). See:

  http://docs.racket-lang.org/guide/performance.html?q=performance

for more details.

Robby


On Wed, Apr 24, 2013 at 4:38 AM, Shannon Severance <srs at s53.me> wrote:

> 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
>
>
>
> ____________________
>   Racket Users list:
>   http://lists.racket-lang.org/users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20130424/7329ba1c/attachment.html>