Clojure performance really bad on simple loop versus Java

Question

Spoiler alert, this is problem 5 of Project Euler.

I am attempting to learn Clojure and solved problem 5, but it is a couple orders of magnitude slower (1515 ms in Java versus 169932 ms in Clojure). I even tried using type hinting, unchecked math operations, and inlining functions all for naught.

Why is my Clojure code so much slower?

Clojure code:

(set! *unchecked-math* true) (defn divides? [^long number ^long divisor] (zero? (mod number divisor)))  (defn has-all-divisors [divisors ^long num]   (if (every? (fn [i] (divides? num i)) divisors) num false))  (time (prn (some (fn [^long i] (has-all-divisors (range 2 20) i)) (iterate inc 1)))) 

Java code:

public class Problem5 {   public static void main(String[] args) {     long start = System.currentTimeMillis();     int i = 1;     while(!hasAllDivisors(i, 2, 20)) {       i++;     }     long end = System.currentTimeMillis();     System.out.println(i);     System.out.println("Elapsed time " + (end - start));   }    public static boolean hasAllDivisors(int num, int startDivisor, int stopDivisor) {     for(int divisor=startDivisor; divisor<=stopDivisor; divisor++) {       if(!divides(num, divisor)) return false;     }     return true;   }    public static boolean divides(int num, int divisor) {     return num % divisor == 0;   } } 

Answer 1

Some performance problems:

• The (range 2 20) call is creating a new lazy list of numbers for every increment of i. This is expensive, and is causing lots of unnecessary GC.
• You are doing a lot of boxing by passing through function calls. Even the (iterate inc 1) is doing boxing / unboxing at every increment.
• You are traversing a sequence of divisors. This is slower than a straight iterative loop
• mod is actually not a very well optimised function in Clojure at present. You are much better off using rem

You can solve the first problem by using a let statement to define the range just once:

(time (let [rng (range 2 20)]   (prn (some (fn [^long i] (has-all-divisors rng i)) (iterate inc 1))))) => "Elapsed time: 48863.801522 msecs" 

You can solve the second problem with loop/recur:

(time (let [rng (range 2 20)            f (fn [^long i] (has-all-divisors rng i))]        (prn (loop [i 1]                (if (f i)                 i                 (recur (inc i))))))) => "Elapsed time: 32757.594957 msecs" 

You can solve the third problem by using an iterative loop over the possible divisors:

(defn has-all-divisors [^long num]   (loop [d (long 2)]     (if (zero? (mod num d))       (if (>= d 20) true (recur (inc d)))       false)))   (time (prn (loop [i (long 1)] (if (has-all-divisors i) i (recur (inc i))))))  => "Elapsed time: 13369.525651 msecs" 

You can solve the final problem using rem

(defn has-all-divisors [^long num]   (loop [d (long 2)]     (if (== 0 (rem num d))       (if (>= d 20) true (recur (inc d)))       false)))   (time (prn (loop [i (long 1)] (if (has-all-divisors i) i (recur (inc i)))))) => "Elapsed time: 2423.195407 msecs" 

As you can see, it is now competitive with the Java version.

In general, you can usually make Clojure almost as fast as Java with a bit of effort. The main tricks are usually:

• Avoid lazy functional features. They are nice, but add some overhead which can be problematic in low-level computation-intensive code.
• Use primitive / unchecked maths
• Use loop/recur rather than sequences
• Ensure you are not doing any reflection on Java objects (i.e. (set! *warn-on-reflection* true) and eliminate all warnings you find)

Answer 2

I have not been able to reproduce the 1500 ms performance. The Clojure code seems actually twice as fast as the Java version after compilation to uberjar.

Now timing Java version     232792560 "Elapsed time: 4385.205 msecs"  Now timing Clojure version     232792560 "Elapsed time: 2511.916 msecs" 

I put the java class in resources/HasAllDivisors.java

public class HasAllDivisors {      public static long findMinimumWithAllDivisors() {         long i = 1;         while(!hasAllDivisors(i,2,20)) i++;         return i;     }      public static boolean hasAllDivisors(long num, int startDivisor, int stopDivisor) {         for(int divisor = startDivisor; divisor <= stopDivisor; divisor++) {             if(num % divisor > 0) return false;         }         return true;     }      public static void main(String[] args){         long start = System.currentTimeMillis();         long i = findMinimumWithAllDivisors();         long end = System.currentTimeMillis();         System.out.println(i);         System.out.println("Elapsed time " + (end - start));     }  } 

And in Clojure

(time (prn (HasAllDivisors/findMinimumWithAllDivisors)))  (println "Now timing Clojure version") (time     (prn         (loop [i (long 1)]             (if (has-all-divisors i)                 i                 (recur (inc i)))))) 

Even on the command line the java class is not reproducing the fast speed.

$ time java HasAllDivisors   232792560 Elapsed time 4398  real   0m4.563s user   0m4.597s sys    0m0.029s