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);

.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?

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