Resources on optimizing Clojure code

[Dan Kefford]

Hello fellow clojurians...

I've been using Clojure now fairly regularly for the past two months
solving problems on Project Euler. I've been fairly successful solving
them but there are times where the performance of my code either
stinks (the answer may come back in 5-10 minutes) or not at all even
though I have effectively solved the problem (the code is correct and
will return the answer for n < 1000 but for n < 10^8... forget about
it.)

My question is: are there any materials out there on how to optimize
performance of Clojure code? There doesn't seem to be a lot out there.

Thanks in advance,

dan kefford

[Alan]

Usually it's more about the algorithm than the language. Java can
generally do things faster than clojure, simply because it has fewer
layers, but the speedup is a linear factor. If the java solution for
1000 elements takes 5ms and your clojure code takes even a second,
it's likely that clojure isn't to blame. Maybe you could post one of
your solutions, or simply compare it to a java solution yourself?

[David Andrews]

Yes, on the handful of Project Euler exercises I've attempted, my
algorithm choice was frequently the source of poor performance.

Are you familiar with the clojure-euler wiki at http://clojure-euler.wikispaces.com/
? After I do an Euler exercise I compare my code and runtime with
other Clojure submissions, and learn a lot from other people's code.

[Dan Kefford]

Sorry for the delayed response.

OK... here's an example; my solution to problem 187:

(defn divides? [n d]
(zero? (rem n d))
)

(declare prime? prime-seq)

(defn prime? [n]
(if (< n 2)
false
(every? #(not (divides? n %)) (take-while #(<= (* % %) n) prime-
seq)))
)

(def prime? (memoize prime?))

(def prime-seq
(lazy-seq (concat '(2 3 5 7)
(filter #(prime? %) (map #(+ (* 2 %) 7) (iterate inc 1)))))
)

(defn factorize [n]
(loop [test-primes prime-seq
tmp n
retval '()]
(if (= 1 tmp)
retval
(if (prime? tmp)
(concat retval (list tmp))
(let [p (first test-primes)]
(if (divides? tmp p)
(recur test-primes (quot tmp p) (concat retval (list p)))
(recur (rest test-primes) tmp retval))))))
)

(defn twice-composite? [n]
(= 2 (count (factorize n)))
)

(count (filter twice-composite? (range 1 30)))

This appears to be correct, since I get the answer 10 for this one
case. However, trying to run for n<10^6 takes 6-11 seconds, and for
10^7 at least three minutes, so running for 10^8 is like going to take
on the order of hours.

I know that my prime number generator is nowhere near optimal, and I
know that in order to efficiently solve a lot of the Euler problems,
you cannot simply brute force them; you need to choose your algorithm
wisely.

Anyway... any suggestions would be greatly appreciated.

dan kefford

[Mark Engelberg]

Your Clojure implementation of your particular approach is reasonable,
but you need a cleverer approach. I'll send you a hint offline.

[Dan Kefford]

One idea that I had was to inline the factoring logic into twice-
composite. Who cares about the factors? We just want to know if there
are two or not:

(defn twice-composite? [n]
(loop [ps prime-seq
tmp n
p-count 0]
(if (< 2 p-count)
false
(if (= 1 tmp)
(= 2 p-count)
(let [p (first ps)]
(if (divides? tmp p)
(recur ps (quot tmp p) (inc p-count))
(recur (rest ps) tmp p-count))))))
)

But this lead to even slower code.

[Mark Engelberg]

All the time spent factoring is wasted. You can *construct* and/or
count the semiprimes far more efficiently than your method of
factoring each number one a time in order to filter the semiprimes
from the entire range of numbers up to 10^8. Your approach is
fundamentally slow; this has nothing to do with Clojure.

I sent you more hints privately.

[Leif Walsh]

If you want to do this, you can do it simpler, without the loop and temp var:

(defn twice-composite? [n]
(->> (take-while #(< % n) prime-seq)
(every #(or (divides? (* 2 %) n)
(not (divides? % n))))

but this is not what you want. See the hints I sent you off the list.

> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en

--
Cheers,
Leif

[Ken Wesson]

If you're looking to generate all the numbers with exactly two prime
factors (counting multiplicity), I have clojure code that generates
the ones up to 10^8 in under two minutes:

com.example.sbox=> (time (count (semiprimes-to 100000000)))
"Elapsed time: 106157.33292 msecs"
41803068

It's single-threaded code running on a 2.5GHz machine, so I didn't
achieve this through massive parallelism or running it on a Cray or
anything. :)

If anyone wants more details or the code itself I can post it or email it.

[cej38]

It is wonderful that people are so willing to help with a specific
problem, and I encourage you to continue doing so, but I don't think
anyone has answered the real question. Is there material out there
that describes some of the mechanisms, tools, ideas, etc. that will
allow the average clojure user to optimize their code. Yes, Yes, a
good implementation is key, but you need to know the best practices in
order to develop that implementation.

Not that I have done this myself (yet!) but there are some that argue
that reimplementing certain time critical components as macros will
greatly speed up the code. See the link below:
http://www.bestinclass.dk/index.clj/2010/03/functional-fluid-dynamics-in-clojure.html

Optimization is a topic that I would like to see more on.

[Gary Poster]

On Nov 4, 2010, at 1:32 PM, cej38 wrote:

> It is wonderful that people are so willing to help with a specific
> problem, and I encourage you to continue doing so, but I don't think
> anyone has answered the real question. Is there material out there
> that describes some of the mechanisms, tools, ideas, etc. that will
> allow the average clojure user to optimize their code.

Chapter 12 of Joy of Clojure is about performance (type hints, transience, chunked sequences, memoization, coercion).

Arguably much of the book is also about what you describe broadly, since it is trying to teach and encourage efficient, idiomatic Clojure usage generally, AIUI.

Gary