Why is this seemingly basic clojure function so slow?

Question

I'm new to clojure, and as quick practice I wrote a function that is supposed to go through the Fibonacci sequence until it exceeds 999999999 1 billion times (does some extra math too but not very important). I've written something that does the same in Java, and while I understand that by nature Clojure is slower than Java, the java program took 35 seconds to complete while the Clojure one took 27 minutes, which I found very surprising (considering nodejs was able to complete it in about 8 minutes). I compiled the class with the repl and ran it with this Java command java -cp `clj -Spath` fib. Really unsure was to why this was so slow.

(defn fib
  []
  (def iter (atom (long 0)))
  (def tester (atom (long 0)))
  (dotimes [n 1000000000]
    (loop [prev (long 0)
           curr (long 1)]
      (when (<= prev 999999999)
        (swap! iter inc)
        (if (even? @iter)
          (swap! tester + prev)
          (swap! tester - prev))
        (recur curr (+ prev curr)))))
  (println (str "Done in: "  @iter " Test: " @tester))
)

Here is my Java method for reference

    public static void main(String[] args) {
        long iteration = 0;
        int test = 0;
        for (int n = 0; n < 1000000000; n++) {
            int x = 0, y = 1;
            while (true) {
                iteration += 1;
                if (iteration % 2 == 0) {
                    test += x;
                }
                else {
                    test -=x;
                }
                int i = x + y;
                x = y;
                y = i;
                if (x > 999999999) { break; }
            }
        }
        System.out.println("iter: " + iteration + " " + test);
    }

Answer 1

As others have noted, a straightforward translation of the Java code to Clojure runs rather slowly. However, if we write a Fibonacci number generator which takes advantage of Clojure's strengths we can get something which is short and does its job more idiomatically.

To start, let's say we want a function which will computed the n'th number of the Fibonacci sequence (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...). To do that we could use:

(defn fib [n]
  (loop [a   1
         b   0
         cnt n]
    (if (= cnt 1)
      a
      (recur (+' a b) a (dec cnt)))))

which iteratively recomputes the "next" Fibonacci value until it gets to the one which is desired.

Given this function we can develop one which creates a collection of the Fibonacci sequence values by mapping this function across a range of index values:

(defn fib-seq [n]
  (map #(fib %) (range 1 (inc n))))

But this is of course a stunningly inefficient way of computing a sequence of Fibonacci values, since for each value we have to compute all of the preceding values and then we only save the last one. If we want a more efficient way to compute the entire sequence we can loop through the possibilities and gather the results in a collection:

(defn fib-seq [n]
  (loop [curr   1
         prev   0
         c      '(1)]
    (if (= n (count c))
      (reverse c)
      (let [new-curr  (+' curr prev)]
        (recur new-curr curr (cons new-curr c))))))

This gives us a reasonably efficient way to collect the values of the Fibonacci sequence. For your test of a billion loops through (fib 45) (the 45th term of the sequence being the first one which exceeds 999,999,999) I used:

(time (dotimes [n 1000000000](fib-seq 45)))

which completed in 17.5 seconds on my hardware and OS (Windows 10, dual-processor Intel i5 @ 2.6 GHz).

Answer 2

One thing a lot of newcomers to Clojure don't realize is that Clojure is a higher-level language by default. That means it will force you into implementations that will handle overflow on arithmetic, will treat numbers as objects you can extend, will prevent you from mutating any variable, will force you to have thread-safe code, and will push you towards functional solutions that rely on recursion for looping.

It also doesn't force you to type everything by default, which is also convenient not to have to care to think about the type of everything and making sure all your types are compatible, like that your vector contains only Integers for example, Clojure doesn't care, letting you put Integers and Longs in it.

All this stuff is great for writing fast-enough correct, evolvable, and maintainable applications, but it is not so great for high-performance algorithms.

That means by default Clojure is optimized for implementing applications and not for implementing high-performance algorithms.

Unfortunately, it seems most people that "try" a new language, and thus newcomers to Clojure will tend to first use the language to try and implement high-performance algorithms. This is an obvious mismatch in what Clojure defaults to be good at, and lots of newcomers are immediately faced with the added friction Clojure causes here. Clojure assumed you were going to implement an app, not some high-performance one billion N sized Fibonacci-like algorithm.

But don't lose hope, Clojure can also be used to implement high-performance algorithms, but it isn't the default, so you generally need to be a more experienced Clojure developer to know how to do so, as it is less obvious.

Here's your algorithm in Clojure, which performs as fast as your Java implementation, it's a recursive re-write of your exact Java code:

(ns playground
  (:gen-class)
  (:require [fastmath.core :as fm]))

(defn -main []
  (loop [n (long 0) iteration (long 0) test (long 0)]
    (if (fm/< n 1000000000)
      (let [^longs inner
            (loop [x (long 0) y (long 1) iteration iteration test test]
              (let [iteration (fm/inc iteration)
                    test (if (fm/== (fm/mod iteration 2) 0) (fm/+ test x) (fm/- test x))
                    i (fm/+ x y)
                    x y
                    y i]
                (if (fm/> x 999999999)
                  (doto (long-array 2) (aset 0 iteration) (aset 1 test))
                  (recur x y iteration test))))]
        (recur (fm/inc n) (aget inner 0) (aget inner 1)))
      (str "iter: " iteration " " test))))

(println (time (-main)))

"Elapsed time: 47370.544514 msecs"
;;=> iter: 45000000000 0

Using deps:

:deps {generateme/fastmath {:mvn/version "2.1.8"}}

As you can see, on my laptop, it completes in ~47 seconds. I also ran your Java version on my laptop to compare on my exact hardware, and for Java I got: 46947.343671 ms.

So on my laptop, you can see the Clojure and the Java are basically just as fast each, both clocking in at around 47 seconds.

The difference is that in Java, the style of programming is always conductive to implementing high-performance algorithms. You can directly use primitive types and primitive arithmetic, no boxing, no overflow checks, mutable variables with no synchronization or atomicity or volatility protections, etc.

Few things were thus required to get similar performance in Clojure:

1. Use primitive types
2. Use primitive math
3. Avoid the use of higher-level managed mutable containers like atom

And obviously, we needed to run the same algorithm too, so similar implementation. I wasn't trying to compare if another algorithm exists that can be faster for the same problem, but how to implement the same algo in Clojure so it runs just as fast.

In order to do primitive types in Clojure, you have to know that you are only allowed to do so inside local contexts using let and loop, and all function call will undo the primitive type, unless they too are typed to primitive long or double (the only supported primitive types that can cross function boundaries in Clojure).

That's the first thing I did then, just re-write your same loops using Clojure's loop/recur and declare the same variables as you did, but using let shadowing instead, so we don't need a managed mutable container.

Finally, I made use of Fastmath, a library that provides a lot of primitive versions of arithmetic functions so that we can do primitive math. Clojure core has some of its own, but it doesn't have mod for example, so I needed to pull in Fastmath.

That's it.

Generally, this is what you need to know, keep to primitive types, keep to primitive math (using fastmath), type hint to avoid reflection, leverage let shadowing, keep to primitive arrays, and you'll get Clojure high-performance implementations.

There's a good set of info about it here: https://clojure.org/reference/java_interop#primitives

One last thing, the philosophy of Clojure is that it is meant to implement fast-enough correct, evolvable and maintainable apps that can scale. That's why the language is the way it is. While you can, as I've shown, implement high-performance algos, Clojure's philosophy is also not to re-invent a syntax for things that Java already is great at. Clojure can use Java, so for algorithms that need very imperative, mutable, primitive logic, it would expect you'd just fallback to Java to write this as a static method, and then just use it from Clojure. Or it thinks you'll even delegate to something more performant than even Java, and use BLAS, or a GPU to perform super-fast matrix math, or something of that sort. That's why it doesn't bother to provide its own imperative constructs, or raw memory access and all that, since it doesn't think it do anything better than the hosts it runs over.

Answer 3

If you are a beginner at programming, I suggest you always assume your code is wrong before assuming the language/lib/framework/platform is wrong.

Take a look at Fibonacci sequence various implementations in Java and Clojure, you may learn something.

Answer 4

Your code might seem like a "basic function", but there are two main problems:

• You used atom. Atom isn't variable as you know it from Java, but it's construct for managing synchronous state, free of race conditions. So reset! and swap! are atomic operations and they're slow. Look at this example:

(let [counter (atom 0)]
  (dotimes [x 1000]
    (-> (Thread. (fn [] (swap! counter inc)))
        .start))
  (Thread/sleep 2000)
  @counter)
=> 1000

1000 threads is started, value of counter is 1000x increased, result is 1000, no surprise. But compare that with volatile!, which isn't thread-safe:

(let [counter (volatile! 0)]
  (dotimes [x 1000]
    (-> (Thread. (fn [] (vswap! counter inc)))
        .start))
  (Thread/sleep 2000)
  @counter)
=> 989

See also Clojure Reference about Atoms.

• Unless you really need atoms and volatiles, you shouldn't use them. Usage of loop is also discouraged, because there is usually some better function, which does exactly what you want. You tried to literally rewrite your Java function into Clojure. Clojure requires different approach to problems and your code definitelly isn't idiomatic. I suggest you to not rewrite Java code to Clojure line by line, but find some easy problems and learn how to solve them in Clojure way, without atom, volatile! and loop.

By the way, there is memoize, which can be useful in examples like yours.