Cfrtjryk

I'm new to Clojure and using some Project Euler problems to familiarize myself with the language's capabilities. Problem #10 asks to find the sum of all primes less than two million.

I wanted to solve this problem by building a generalized Sieve of Eratosthenes, then adding up all the primes:

(defn sieve [size]

  (-> (reduce (fn [prev i]

                (if (prev i)

                  (vec (reduce #(assoc %1 %2 false)

                               prev

                               (range (+ i i) size i)))

                  prev))

              (vec (repeat size true))

              (range 2 (-> size Math/sqrt int inc)))

      vec

      (assoc 0 false)

      (assoc 1 false)))



(time

 (let [limit 2000000

       s (sieve limit)]

   (reduce #(+ %1 (if (s %2) %2 0))

           0 (range limit))))

That works, but takes over 14 seconds when run from an already "hot" REPL. For comparison, I did a simple Java implementation:

import java.util.Arrays;

import java.lang.Math;



public class P10 {

  public static void main(String args) {

    int size = 2000000;



    boolean sieve = new boolean[size];



    Arrays.fill(sieve, true);

    sieve[0] = false;

    sieve[1] = false;



    for (int i = 2; i < (1 + Math.sqrt(size)); i++) {

      if (sieve[i]) {

        for (int j = i + i; j < size; j += i) {

          sieve[j] = false;

        }

      }

    }



    long sum = 0;

    for (int i = 0; i < size; i++) {

      if (sieve[i]) sum += (long) i;

    }



    System.out.println(sum);

  }

}

Which runs in about 0.7 seconds from the command line. (Incidentally, my Java experience isn't very deep either--does that include JVM startup?)

So I thought maybe the problem with the "pure" (?) Clojure version is the creation/reliance on Clojure's vectors. So my idea was to rework the Clojure version to use Java's mutable array:

(defn sieve [size]

  (-> (let [ar (to-array (repeat size true))]

        (dorun (map (fn [i]

                      (when (aget ar i)

                        (dorun (map (fn [j] (aset ar j false))

                                    (range (+ i i) size i)))))

                    (range 2 (-> size Math/sqrt int inc))))

        ar)

      vec

      (assoc 0 false)

      (assoc 1 false)))

But that takes more than 3.5 seconds.

At this point, I'm not so interested in implementing fancy things like bit-packing, I'm just trying to reach performance parity with the "traditional" Java implementation. What am i doing "wrong" in my Clojure that makes it "non-competitive" with the Java version?

Also, any other tips/hints/criticisms regarding Clojure style?

I won't comment on the Java bit because I don't write Java very often. I agree with the other answer though that sqrt should only be called once. Computing the sqrt of a number is relatively expensive.

First, for Clojure, a baseline on my computer:

(defn sieve [size]

    (-> (reduce (fn [prev i]

                  (if (prev i)

                    (vec (reduce #(assoc %1 %2 false)

                                 prev

                                 (range (+ i i) size i)))

                    prev))

                (vec (repeat size true))

                (range 2 (-> size Math/sqrt int inc)))

        vec

        (assoc 0 false)

        (assoc 1 false)))



(defn main 

  (time

    (let [limit 2000000

          s (sieve limit)]

      (reduce #(+ %1 (if (s %2) %2 0))

              0 (range limit)))))



; From REPL

(main)

"Elapsed time: 2274.584779 msecs"

=> 142913828922

I should note that I'm on a crappy M3 Surface Pro 4; not a power machine by a stretch of any definition. If this is taking 14 seconds, you must have something else going on. That's far too long.

I actually prefer wrapping threading calls in parenthesis, even if they aren't required. I'd write lines such as (-> size Math/sqrt int inc) as (-> size (Math/sqrt) (int) (inc)). I find it helps differentiating between the form being a plain function call, and the threading of a value. The only time I omit them is when I'm golfing.

Your nested reduction is a lot going on in only a few lines. I would definitely break the inner reduction off into its own function, give it a descriptive name, and call it in the outer reduction.

(defn calc [size i prev] ; Although give it a better name

  (vec (reduce #(assoc %1 %2 false)

               prev

               (range (+ i i) size i))))



(defn sieve [size]

    (-> (reduce (fn [prev i]

                  (if (prev i)

                    (calc size i prev)

                    prev))

                (vec (repeat size true))

                (range 2 (-> size Math/sqrt int inc)))

        vec

        (assoc 0 false)

        (assoc 1 false)))

I like breaking functions up. Having giant functions forces you to consider a large amount of data and interactions at once. If you split a part off into its own function and ensure that it's pure, you know that no code in that function can manipulate any data that you haven't explicitly given it as a parameter. That's one less bit of the code to need to look at when debugging.

For your second bit, interestingly, it performed the same for me:

(main) ; Using your arrays version

"Elapsed time: 2106.530431 msecs"

=> 142913828922

You're making a critical error though when dealing with arrays in Clojure: don't use aset unless you have to. aset works on Objects, not primitives, as its documentation notes:

Sets the value at the index/indices. Works on Java arrays of
reference types. Returns val.

Using aset forces your bools to be boxed into a Boolean, which is pricey when done over and over. aset has multiple overloads for primitive types that should be used instead. I'd switch to aset-boolean, and create the array using boolean-array instead:

(defn sieve2 [size]

  (-> (let [ar (boolean-array (repeat size true))]

        (dorun (map (fn [i]

                      (when (aget ar i)

                        (dorun (map (fn [j] (aset-boolean ar j false))

                                    (range (+ i i) size i)))))

                    (range 2 (-> size Math/sqrt int inc))))

        ar)

      vec

      (assoc 0 false)

      (assoc 1 false)))



(defn main 

  (time

    (let [limit 2000000

          s (sieve2 limit)]

      (reduce #(+ %1 (if (s %2) %2 0))

              0 (range limit)))))



(main)

"Elapsed time: 759.412393 msecs"

=> 142913828922

A little better. I'll also note though that use of (dorun (map is usually a code smell. You're better off just using mapv which is strict. Using laziness when you don't need it can be costly. maping isn't the right tool here for the job anyways. Use map when you want to transform a list. Use doseq when you want to carry out side effects over a list. Think of it as Java's enhanced for-loop. I'm also using doseq's :when clause to replace the use of the when macro:

(defn sieve2 [size]

  (let [ar (boolean-array (repeat size true))]

    (doseq [i (range 2 (-> size (Math/sqrt) (int) (inc)))

            :when (aget ar i)] ; Replacing the call to when

      (doseq [j (range (+ i i) size i)]

        (aset-boolean ar j false)))



    (-> ar

        (vec)

        (assoc 0 false)

        (assoc 1 false))))



(main)

"Elapsed time: 577.607879 msecs"

=> 142913828922

Still not great, but better.

Just for a laugh comparison, here's a implementation of Eratosthenes' Sieve I wrote back in April:

(defn sieve-primes [n]

  (loop [p 2 ; First prime

         marked #{} ; Found composites

         primes ]

    (let [mults (->> n

                     (range p)

                     (map #(* p %))

                     (take-while #(< % n)))



          next-p (->> p

                      (inc)

                      (iterate inc)

                      (remove marked)

                      (first))



          new-primes (conj primes p)]



      (if (>= next-p n)

        new-primes

        (recur next-p (into marked mults) new-primes)))))



(time

  (apply + (sieve-primes 2000000)))

"Elapsed time: 8719.010487 msecs"

=> 142913828922

Ouch! I don't think I tried very hard to get it lower though. That was the first time I had ever written the sieve in any language, and was happy with just having a working implementation at the time. It is pretty though, even if it's slow.

Clojure is really not a performance-oriented language though. Yes, you can add all sorts of optimizations to make good use of all cores and limit intermediate lists when doing transformations, but it generally won't perform as well as other languages. It's generally even slower than Java of all languages in my experience. I write Clojure because it's fun to write and produces nice looking code, not because it produces fast code.

0.7 seconds for your Java implementation is too slow. We can speed that up (putting even more pressure on Closure):

• Compute the sqrt once.


• treat 2 as a special case


• start at 3, start eliminations at $i^2$, and increment by 2i

Eg)

int limit = 1 + (int) Math.sqrt(size);

for (int i = 3; i < limit); i += 2) {

  if (sieve[i]) {

    for (int j = i*i; j < size; j += 2*i) {

      sieve[j] = false;

    }

  }

}



long sum = 2;

for (int i = 3; i < size; i += 2) {

  if (sieve[i]) sum += (long) i;

}