Why is nested loop/recur slow in Clojure?

Question

A single loop/recur in Clojure executes as fast as it's Java for loop equivalent

Clojure Version:

(defn singel-loop [i-count]
  (loop [i 0]
    (if (= i i-count)
      i
      (recur (inc i)))))

(time (loop-test 100101))
"Elapsed time: 0.8857 msecs"

Java Version:

long s = System.currentTimeMillis();
for (i = 0; i < 100000; i++) {
}
System.out.println("Time: " + (System.currentTimeMillis() - s));

Time: ~1ms

However, if you add an inner loop/recur the performance absolutely falls off of a cliff!

Clojure:

(defn double-loop [i-count j-count]
  (loop [i 0]
    (loop [j 0]
      (if (= j j-count)
        j
        (recur (inc j))))
      (if (= i i-count)
        i
        (recur (inc i)))))

(time (double-loop 100000 100000))
"Elapsed time: 70673.9189 msecs"

Java Version:

long s = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    for (int j = 0; j < 100000; j++) {
    }
}
System.out.println((System.currentTimeMillis() - s));

Time: ~3ms

Why does the performance of the Clojure version tank to a comical degree whereas the Java version stays constant?

Answer 1

I think this is primarily due to the Java code being more open to optimization.

According to here:

An infinite loop with an empty body consumes CPU cycles but does nothing. Optimizing compilers and just-in-time systems (JITs) are permitted to (perhaps unexpectedly) remove such a loop. Consequently, programs must not include infinite loops with empty bodies.

Although, I can't validate such a claim. The code here also doesn't involve infinite loops, but empty loops regardless of the exit condition are equally useless. If anything, a finite loop seems like a more plausible optimization target since at least an infinite loop has a potential purpose (to block indefinitely).

A better comparison then would be to try to eliminate any such optimization. I chose to use System.out.flush since println can be quite expensive and inconsistent, and I don't thing anything directly affecting System.out. would be optimized out.

Here are the results:

(defn double-loop [i-count j-count]
  (loop [i 0]
    (loop [j 0]
      (if (= j j-count)
        j
        (do
          (.flush System/out)
          (recur (inc j)))))

    (if (= i i-count)
      i

      (recur (inc i)))))

(time (double-loop 1000 10000))  ; "Elapsed time: 1194.718969 msecs"

---

public class HelloWorld {

     public static void main(String []args){
        long s = System.currentTimeMillis();
        for (int i = 0; i < 1000; i++) {
            for (int j = 0; j < 10000; j++) {
                System.out.flush();
            }
        }

        System.out.println((System.currentTimeMillis() - s));  // 1097
     }
}

1194.718969 ms vs 1097 ms

So, it seems, potentially, to be a failure of Clojure to compile into easily optimization code.

Things to note:

• I did these tests on Tutorials Point, not a real environment. IntelliJ has been completely unusable for me since the last update, and I honestly didn't feel like setting up a project for Clojure and fiddling with javac for Java.

• Why these exact numbers? Because I'm running in a poor environment, and I don't want the website throttling me or doing anything similar. For whatever reason with the Clojure test, 10000x10000 hung indefinitely (or at least out-did my patience). I had to drop it to 10000x1000 so it would finish.

• As I noted in the comments on the question, this is still an awful way to benchmark languages that run on the JVM as this case shows nicely. See here for why. I use Criterium for Clojure. It's excellent. It runs the code for you before tests to warm everything up, and tries to handle things like garbage collection.

Answer 2

You made it do 100,000 times as much work, and it now takes 100,000 times longer. This is not very surprising, and I wouldn't call it "falling off a cliff". You might ask why the Java version takes only 3 times as long to do 100,000 times as much work, but at that point it's not really a question about how loop/recur in general performs. Instead it's more a question of what miracle the JIT can pull off with the Java code.

Answer 3

It should raise red flags for you if, as an earlier answer mentioned, a Java nested loop version that appears from the source code that it should require 10,000 times more time than the non-nested loop, only takes 3 times more time (~ 3 msec for the Java nested loop, vs. ~1 msec for the non-nested loop). I do not know why that is happening, but a couple of possibilities are:

(a) the JVM JIT compilation hasn't kicked in yet for your shorter version, so all or a large fraction of the time is spent interpreting byte code, or executing a less-optimized version of JIT machine code, compared to the nested loop version

(b) the JVM JIT is somehow determining that your loops do not need to be run, because there is no return value, so the same effect occurs whether the loops are run or not. In general, I would recommend doing at least a little bit of computation in each inner loop (e.g. adding two numbers, e.g. to a running total), and have a return value that depends upon this computation occurring.

I have created Clojure and Java versions with similar running times here that you can look at, and recorded the measurement results I obtained using the Criterium library, which runs the same code many times for it to "warm up" the JIT first, and then measures it many more times after that, reporting results based only on the post-warmup executions.

Java code: https://github.com/jafingerhut/leeuwenhoek/blob/master/src/leeuwenhoek/java/JavaLoops.java

Clojure code: https://github.com/jafingerhut/leeuwenhoek/blob/master/src/leeuwenhoek/clojure_loops.clj

Measurement code for both, with results in comments: https://github.com/jafingerhut/leeuwenhoek/blob/master/src/leeuwenhoek/measure_loops.clj