Sebastian Oberhoff Sebastian Oberhoff -4 years ago 104
Java Question

Why does Clojure spend so much time on clojure.lang.Iterate.first?

I'm quite fond of the story about Frank Nelson Cole, who in 1903 demonstrated the prime factorization of 2^67 - 1 in a famous "lecture without words". These days the factorization can be readily found using the following naive algorithm:

(def mersenne67 (dec (expt 2 67)))

(->> (iterate inc 2)
(filter #(zero? (rem mersenne67 %)))
(first))


However I've noticed that this Clojure code takes roughly twice as long as the equivalent Java or Kotlin code. (~40 vs ~20 seconds on my machine)

Here's the Java I compared it to:

public static BigInteger mersenne() {
BigInteger mersenne67 =
BigInteger.valueOf(2).pow(67).subtract(BigInteger.ONE);

return Stream.iterate(BigInteger.valueOf(2), (x -> x.add(BigInteger.ONE)))
.filter(x -> mersenne67.remainder(x).equals(BigInteger.ZERO))
.findFirst()
.get();
}


Rewriting the Clojure code on a lower level made no difference:

(def mersenne67 (-> (BigInteger/valueOf 2)
(.pow (BigInteger/valueOf 67))
(.subtract BigInteger/ONE)))

(->> (iterate #(.add ^BigInteger % BigInteger/ONE) (BigInteger/valueOf 2))
(filter #(= BigInteger/ZERO (.remainder ^BigInteger mersenne67 %)))
(first))


After profiling the code with the VisualVM the primary suspect seems to be
clojure.lang.Iterate.first()
which accounts almost exactly for the difference in how long these functions run. Java's equivalent
java.util.stream.ReferencePipeline.findFirst()
runs for only a fraction as long (~22 vs ~2 seconds).
This leads to my question: How does Java (and Kotlin) get away with spending so much less time on this task?

Answer Source

Your problem is that you're inefficiently iterating through your iterate. This is why you're seeing first up top at your profiling. This is, of course a result of all the core functions of clojure working with lots and lots of different data structures.

The best way to avoid this is to use reduce, which gives the object itself the task to call the function in a loop.

So this is about 2x as fast:

(reduce
      (fn [_ x]
        (when (identical? BigInteger/ZERO (.remainder ^BigInteger mersenne67 x))
          (reduced x)))
      nil
      (iterate #(.add ^BigInteger % BigInteger/ONE) (BigInteger/valueOf 2)))
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download