31

Spoiler alert, this is problem 5 of Project Euler.

I am attempting to learn Clojure and solved problem 5, but it is a couple orders of magnitude slower (1515 ms in Java versus 169932 ms in Clojure). I even tried using type hinting, unchecked math operations, and inlining functions all for naught.

Why is my Clojure code so much slower?

Clojure code:

(set! *unchecked-math* true)
(defn divides? [^long number ^long divisor] (zero? (mod number divisor)))

(defn has-all-divisors [divisors ^long num]
  (if (every? (fn [i] (divides? num i)) divisors) num false))

(time (prn (some (fn [^long i] (has-all-divisors (range 2 20) i)) (iterate inc 1))))

Java code:

public class Problem5 {
  public static void main(String[] args) {
    long start = System.currentTimeMillis();
    int i = 1;
    while(!hasAllDivisors(i, 2, 20)) {
      i++;
    }
    long end = System.currentTimeMillis();
    System.out.println(i);
    System.out.println("Elapsed time " + (end - start));
  }

  public static boolean hasAllDivisors(int num, int startDivisor, int stopDivisor) {
    for(int divisor=startDivisor; divisor<=stopDivisor; divisor++) {
      if(!divides(num, divisor)) return false;
    }
    return true;
  }

  public static boolean divides(int num, int divisor) {
    return num % divisor == 0;
  }
}
Improve this question
4
  • 1
    Your java code goes to 2-18 whereas the Clojure code goes to 2-20. Commented Jan 2, 2013 at 11:43
  • Sorry, I've fixed it. I had mistakenly pasted the wrong version of the code but the timings were accurate for both going up to 20. Commented Jan 4, 2013 at 5:08
  • System.currentTimeMillis() as benchmark? this is not serious. look at shipilev.net/talks/devoxx-Nov2013-benchmarking.pdf Commented Jan 13, 2016 at 17:46
  • I appreciate your sentiment @Puh. But I think its perfectly reasonable to find writing the naively equivalent code in Java and then in Clojure and finding Clojure to be 10x slower. My test harness sucks, it's a really small micro-benchmark, the JIT probably hasn't even fired up, but who cares. 10X is crazy. If I'm trying to learn the language and a perf issue this obvious pops up, I want to know why, even if my methods aren't scientific and are motivated by unnecessary or eager optimization. Commented Jan 13, 2016 at 22:28

3 Answers 3

Reset to default
56

Some performance problems:

  • The (range 2 20) call is creating a new lazy list of numbers for every increment of i. This is expensive, and is causing lots of unnecessary GC.
  • You are doing a lot of boxing by passing through function calls. Even the (iterate inc 1) is doing boxing / unboxing at every increment.
  • You are traversing a sequence of divisors. This is slower than a straight iterative loop
  • mod is actually not a very well optimised function in Clojure at present. You are much better off using rem

You can solve the first problem by using a let statement to define the range just once:

(time (let [rng (range 2 20)]
  (prn (some (fn [^long i] (has-all-divisors rng i)) (iterate inc 1)))))
=> "Elapsed time: 48863.801522 msecs"

You can solve the second problem with loop/recur:

(time (let [rng (range 2 20)
           f (fn [^long i] (has-all-divisors rng i))]
       (prn (loop [i 1] 
              (if (f i)
                i
                (recur (inc i)))))))
=> "Elapsed time: 32757.594957 msecs"

You can solve the third problem by using an iterative loop over the possible divisors:

(defn has-all-divisors [^long num]
  (loop [d (long 2)]
    (if (zero? (mod num d))
      (if (>= d 20) true (recur (inc d)))
      false)))

 (time (prn (loop [i (long 1)] (if (has-all-divisors i) i (recur (inc i))))))
 => "Elapsed time: 13369.525651 msecs"

You can solve the final problem using rem

(defn has-all-divisors [^long num]
  (loop [d (long 2)]
    (if (== 0 (rem num d))
      (if (>= d 20) true (recur (inc d)))
      false)))

 (time (prn (loop [i (long 1)] (if (has-all-divisors i) i (recur (inc i))))))
=> "Elapsed time: 2423.195407 msecs"

As you can see, it is now competitive with the Java version.

In general, you can usually make Clojure almost as fast as Java with a bit of effort. The main tricks are usually:

  • Avoid lazy functional features. They are nice, but add some overhead which can be problematic in low-level computation-intensive code.
  • Use primitive / unchecked maths
  • Use loop/recur rather than sequences
  • Ensure you are not doing any reflection on Java objects (i.e. (set! *warn-on-reflection* true) and eliminate all warnings you find)
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

I need to say I find this a bit sad. It seems to suggest that one must sacrifice functional features for performance. If one has to write C-style code to get performance, then the compiler needs work doesn't it ?
Maybe it is a bit sad, but it is also a fact of life: higher level languages features often come with cost/overhead that you must pay for. I'm sure more clever work could be done on the compiler but you can't change the fact that a lazy data structure will always have more overhead than an equivalent non-lazy one, for example.
Another thing to point out is the fact that with Clojure you have a choice: if the performance is not a problem, then you can write your code using lazy sequences and all the high-level features you like, making your code more readable and possibly much more compact. If, however, you need the performance, then you can always go the other way and still get good results...
Noob question: Aren't lazy functions supposed to reduce time by only evaluating when needed?
This might reduce some computation, but it also creates extra function calls and creates objects, and if you end up executing all the results anyways, it doesn't help at all.
|
1

I have not been able to reproduce the 1500 ms performance. The Clojure code seems actually twice as fast as the Java version after compilation to uberjar. 

Now timing Java version
    232792560
"Elapsed time: 4385.205 msecs"

Now timing Clojure version
    232792560
"Elapsed time: 2511.916 msecs"

I put the java class in resources/HasAllDivisors.java

public class HasAllDivisors {

    public static long findMinimumWithAllDivisors() {
        long i = 1;
        while(!hasAllDivisors(i,2,20)) i++;
        return i;
    }

    public static boolean hasAllDivisors(long num, int startDivisor, int stopDivisor) {
        for(int divisor = startDivisor; divisor <= stopDivisor; divisor++) {
            if(num % divisor > 0) return false;
        }
        return true;
    }

    public static void main(String[] args){
        long start = System.currentTimeMillis();
        long i = findMinimumWithAllDivisors();
        long end = System.currentTimeMillis();
        System.out.println(i);
        System.out.println("Elapsed time " + (end - start));
    }

}

And in Clojure

(time (prn (HasAllDivisors/findMinimumWithAllDivisors)))

(println "Now timing Clojure version")
(time
    (prn
        (loop [i (long 1)]
            (if (has-all-divisors i)
                i
                (recur (inc i))))))

Even on the command line the java class is not reproducing the fast speed.

$ time java HasAllDivisors
  232792560
Elapsed time 4398

real   0m4.563s
user   0m4.597s
sys    0m0.029s
Improve this answer

2 Comments

I wasn't using jarred code at all. Perhaps also you are using a newer version of clojure where perf has gotten better? Always good to hear things are heading in a better direction.
Thought I would add another data point. Running your Java code in a standalone JAR file (without Clojure) returns almost instantaneously (372ms) on my machine whereas the optimized Clojure uberjar (1.8 or 1.9) code in mikera's post takes ~2300ms. OPs original functional code with mikera's first fix (range defined once) yields a much slower 24390ms. All results from 2017 MBP.
0

I know this is an old question, but I've been running into similar things. It looks like the statement from the OP, that Clojure is much worse than Java on simple loops, is true. I went through the process in this thread, starting with OP's code and then adding the performance improvements. At the end of it all, the java code runs in around 300 ms and the optimized Clojure code runs in 3000 ms. Creating an uberjar with lein gets the Clojure code down to 2500 ms.

Since we know the answer that the given code spits out, I used that to have the Clojure code merely loop the number of times without doing the mod/rem calculations. It simply goes through the loops.

(def target 232792560)

(defn has-all-divisors [divisors ^long num]
    (loop [d (long 2)]
        (if (< d 20) (recur (inc d)))))

(time (let [rng (range 2 20)
            f (fn [^long i] (has-all-divisors (range 2 20) i)) ]
    (prn (loop [i 1] 
            (if (< i target)
                (do (f i) (recur (inc i))))))))

The resulting times are roughly the same as doing the calculations, i.e. 3000 ms. So, it's taking Clojure that long simply to walk through that many loops.

Improve this answer

5 Comments

Having not actually run your code, one immediate thing is you aren't using your "rng" variable.
No, it's not true. Clojure is not worse than Java on simple loops, it's that you aren't doing a simple loop. You are doing recursion. That means function calls and stack frame creations. If you actually look at the bytecode generated, you'll see that the Clojure version has something like three times as many function calls. The way this is usually solved in a Lisp is to support tail call optimization, and then tail call elimination. What that means is recursive calls in tail position get converted to loops, and have equivalent performance. Java won't have this until Project Loom is complete
The only way to loop in Clojure is with loop/recur, so yes, Clojure is worse than Java when implementing an algorithm that is a simple loop. I've implemented this in other Lisps (chicken, racket, and common lisp) and they all have the same issue so TCO isn't enough to equal native loop performance.
It's not a simple loop in Clojure, that's my point. A fair comparison would be to have Java do recursion the way Clojure is doing. As far as other lisps, how do you know the issue is with loop performance? Have you tried simply doing a high number of recursions using any other algorithm for comparison?
No, that's not a fair comparison. That's artificially slowing Java down to Clojure's level. The algorithm is to loop over a series of numbers until a solution is found. If you have Clojure code that can do that as efficiently as Java, I'd honestly love to see it. I haven't been able to and, so far, neither has anybody else. Re: other Lisps, you don't need another algorithm. Straight recursion on this one is worse than TCO. TCO still isn't as good as loops in iterative languages. For other algos, racket, CL, etc can be comparable to C. Not with tight loops, though.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.