Clojure micro benchmark

September 29, 2010 at 7:15 pm | Posted in Clojure, Programming | 6 Comments

First a disclaimer: benchmarking software is difficult. Furthermore, micro-benchmarks hardly ever make sense, unless you have identified that particular piece of code as a performance bottleneck. Following Donald Knuth’s famous quote: “premature optimization is the root of all evil”. Having said this, I also know that tinkering with a few lines of code and trying different versions can be a lot of fun. So that is exactly what I did when I needed some Clojure code that calculates the sum of squares of two sequences.

The algorithm itself is straightforward: it iterates through all the values of the two sequences, calculates the square of the difference for each value pair, and sums them. A perfect algorithm for a map/reduce implementation.

The first version sumsqr1 uses an anonymous function (#(* % %)) to calculate the square root. The advantage is that the subtraction y from x is only done once. The downside might be potential function call overhead.

(defn sumsqr1 [s1 s2]
  (reduce + (map (fn [x y] (#(* % %) (- x y))) s1 s2)))

The next version uses a very straightforward implementation to take the square of the difference between x and y. I was expecting this one to be the fastest.

(defn sumsqr2 [s1 s2]
  (reduce + (map (fn [x y] (* (- x y) (- x y))) s1 s2)))

And finally an implementation (sumsqr3) that uses the Java pow function.

(defn sumsqr3 [s1 s2]
  (reduce + (map (fn [x y] (Math/pow (- x y) 2)) s1 s2)))

Strictly speaking this last function is not the same as the first two ones, since it returns a floating point number, while the other two return integers. To execute my benchmark I called the three versions repeatedly like this:

(time (dotimes [_ 1e6] (sumsqr1 (range 10) (range 1 11))))

I executed all three versions in the REPL, using Clojure 1.1, 1.2 and 1.3 Alpha 1. Results are shown in the next graph:

Clojure micro benchmark

As you can see the sumsqr1 version is the fastest. Next is the version that uses Math.pow. The differences in execution time aren’t spectacular (about 10 %). What is more interesting to conclude is that in this particular micro benchmark, Clojure 1.2 is about 10 % faster than Clojure 1.1 and that Clojure 1.3 Alpha 1 is already 10 % faster than release 1.2. The developers are doing some great work here!

About these ads

6 Comments »

RSS feed for comments on this post. TrackBack URI

  1. Hi Maurits,

    Any clue how it comes that the algorithm that you expected to be the fastest, is actually the slowest?

    Best regards,

    Arnaud

    • Not yet. I will have to look at the generated byte code (next blog!) to see what the compiler generates.

  2. What happens if you type-hint the solution? (http://clojure.org/java_interop#Java%20Interop-Type%20Hints)

    • Hi Martin, thanks for the suggestion. I will give it a try and update the blog with the results.

  3. Why didn’t you try the obvious solution?

    (defn sumsqr4 [s1 s2]
      (reduce + (map #(let [z (- %1 %2)] (* z z)) s1 s2)))
    

    Did you have a look at criterium for benchmarking?

    • Hi Meikel. Good question. Main reason I guess is that I was mostly curious about how an anonymous function impacts performance. In hindsight I probably didn’t think of your solution since in functional programming I somehow tend to avoid introducing new variables. I will update the blog with the results of your suggestion. Thanks!

      I haven’t looked at criterium yet.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com. | The Pool Theme.
Entries and comments feeds.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: