What slows down this feature of Clojure?

Question

I am working on a Project Euler 14 issue in Clojure. I have what I consider a good algorithm, and I get the correct result, but I try to understand why my function is so slow compared to (as I consider) an equivalent function in Java. Here's my Clojure function to get the Collatz chain length from a given start number:

(defn collatz-length [n] (loop [xn acc 1] (if (= 1 x) acc (recur (if (even? x) (/ x 2) (inc (* 3 x))) (inc acc))))) 

And here, my Java function does the same:

 public static int collatzLength(long x) { int count = 0; while (x > 1) { if ((x % 2) == 0) { x = x / 2; } else { x = (x * 3) + 1; } count++; } return count; } 

To perform these functions, I used the following Clojure code:

 (time (dorun (map collatz-length (range 1 1000000)))) 

And the following Java code:

 long starttime = System.currentTimeMillis(); int[] nums = new int[1000000]; for (int i = 0; i < 1000000; i++) { nums[i] = collatzLength(i+1); } System.out.println("Total time (ms) : " + (System.currentTimeMillis() - starttime)); 

Java code runs at 304 ms on my machine, but Clojure code takes 4220 ms . What causes this bottleneck and how can I improve the performance of my Clojure code?

Answer 1

You use math in a box, so numbers are constantly put in a box and unpacked. Try something like:

 (set! *unchecked-math* true) (defn collatz-length ^long [^long n] (loop [xn acc 1] (if (= 1 x) acc (recur (if (zero? (rem x 2)) (quot x 2) (inc (* 3 x))) (inc acc))))) (time (dorun (loop [i 1] (when (< i 1000000) (collatz-length i) (recur (inc i)))))) 

Answer 2

Based on Alex's answer, can you speed up the process by adding an even? (this function does not support unboxed integers):

 (defn collatz-length ^long [^long n] (loop [xn acc 1] (if (= 1 x) acc (recur (if (zero? (bit-and x 1)) (quot x 2) (inc (* 3 x))) (inc acc))))) 

For reference, https://www.refheap.com/cfd421430653cf786177f3cfe is the bytecode created by your java method (changed to using long instead of int ) and the bytecode created by my clojure function. They look very, very similar, with the exception of the opening stanza, in which the clojure version copies the input argument n to x, where the java version simply overwrites the existing n.