I found a simple, worthwhile improvement for a CPU bound
implementation of the Sieve of Eratosthenes in Clojure and thought I'd
share it. Also attached are a few metrics and code for the curious.
So I'm using Clojure to solve some of the problems on Project Euler.
I'd solved some of them before with other languages, but not in new
lazy/immutable way Clojure is encouraging me to think.
Anyways, my Sieve of Eratosthenes was too slow. It took about three
minutes on a 2GHz Intel Core Duo MacBook Pro to find the primes lesser
than 100,000. The blame's on me here -- I'm trying to do it the
immutable/lazy/??? way rather than the big mutable array way. Patience
is appreciated as I am still low on the learning curve.
I enabled local jmx monitoring and attached JConsole to the Clojure
1.0 process. Almost all the time was spent in garbage collection. JMap
showed scary things like this:
================================================================
New Generation (Eden + 1 Survivor Space):
capacity = 589824 (0.5625MB)
used = 524288 (0.5MB)
free = 65536 (0.0625MB)
88.88888888888889% used
Eden Space:
capacity = 524288 (0.5MB)
used = 524288 (0.5MB)
free = 0 (0.0MB)
100.0% used
>From Space:
capacity = 65536 (0.0625MB)
used = 0 (0.0MB)
free = 65536 (0.0625MB)
0.0% used
To Space:
capacity = 65536 (0.0625MB)
used = 65536 (0.0625MB)
free = 0 (0.0MB)
100.0% used
[...]
================================================================
So the young spaces are both a.) small and b.) full. Much to my
surprise enabling parallel garbage collection of the young space was
the biggest win:
1.0 = official release
1.1a = compiled from git 2009-07-27
* clojure version, jvm flags, seconds to find primes <= 100,000
1.0, (default), 230
1.1a, (default), 190
1.1a, -XX:NewRatio=2 -Xmx128m, 148
1.1a, -XX:+UseParallelGC, 51
1.1a, -XX:NewRatio=2 -Xmx128m -XX:+UseParallelGC, 49
So it looks like my code makes Clojure generate a lot of young
objects... I tried to stick to the immutable/lazy approach... all
suggestions would be very welcome -- don't spare the corrections
please!
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defn subsequent-multiples [val]
(fn [candidate]
(or (not= 0 (mod candidate val))
(= val candidate))))
(defn build-sieve-slow [ceiling]
(loop [primes ()
field (range 2 (+ 1 ceiling))]
(let [cur (first field)
remnants (filter (subsequent-multiples cur) field)]
(if (> cur (/ ceiling 2))
(concat primes remnants)
(recur
(concat primes (list (first remnants)))
(rest remnants))))))
(time (apply + (build-sieve-slow 100000)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
