What's slowing this Clojure function down?

Question

I am working on Project Euler problem 14 in Clojure. I have what I feel is a good general algorithm, and I am getting the correct result, but I am struggling to understand why my function is so slow compared to (what I believe to be) an equivalent function in Java. Here's my Clojure function to get the length of the Collatz chain from a given starting number:

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

And here's my Java function to do the same thing:

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 time the performance of 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));

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

Answer 1

You're using boxed math so numbers are constantly being boxed and unboxed. Try something like:

(set! *unchecked-math* true)
(defn collatz-length
  ^long [^long n]
  (loop [x n 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))))))