Making my Clojure map function implementation faster

Question

I've been experimenting with Clojure lately. I tried writing my own map function (two actually) and timed them against the built in function. However, my map functions are way way slower than the built in one. I wanted to know how I could make my implementation faster. It should give me some insights into performance tuning Clojure algorithms I write. The first function (my-map) does recursion with recur. The second version (my-map-loop) uses loop/recur which was much faster than simply using recur.

(defn my-map
    ([func lst] (my-map func lst []))
    ([func lst acc]
        (if (empty? lst)
            acc
            (recur func (rest lst) (conj acc (func (first lst)))))))

(defn my-map-loop
    ([func lst]
        (loop [acc []
                     inner-lst lst]
            (if (empty? inner-lst)
                acc
                (recur (conj acc (func (first inner-lst))) (rest inner-lst))
                ))))

(let [rng (range 1 10000)]
    (time (map #(* % %) rng))
    (time (my-map #(* % %) rng))
    (time (my-map-loop #(* % %) rng)))

These are the results I got -

"Elapsed time: 0.084496 msecs"
"Elapsed time: 14.132217 msecs"
"Elapsed time: 7.324682 mess"

Update

After resueman pointed out that I was timing things incorrectly, I changed the functions to:

(let [rng (range 1 10000)]
  (time (doall (map #(* % %) rng)))
  (time (doall (my-map #(* % %) rng)))
  (time (doall (my-map-loop #(* % %) rng)))
  nil)

These are the new results:

"Elapsed time: 9.563343 msecs"
"Elapsed time: 12.320779 msecs"
"Elapsed time: 5.608647 mess"

"Elapsed time: 11.103316 msecs"
"Elapsed time: 18.307635 msecs"
"Elapsed time: 5.86644 mess"

"Elapsed time: 10.276658 msecs"
"Elapsed time: 10.288517 msecs"
"Elapsed time: 6.19183 mess"

"Elapsed time: 9.277224 msecs"
"Elapsed time: 13.070076 msecs"
"Elapsed time: 6.830464 mess"

Looks like my second implementation is fastest of the bunch. Anyways, I would still like to know if there are ways to optimize it further.

Beware using time to benchmark on the JVM. JIT warmup can have a significant impact on results. time can provide a first-order approximation, but it's best to use a proper benchmarking framework like Criterium (linked to in one of the answers) if you really care about accuracy. — Nathan Davis
– Nathan Davis, Commented Sep 4, 2015 at 18:30

cgrand · Accepted Answer · 2015-09-07 06:54:22Z

0

There are many things that could be leveraged to have a faster map: transients (for your accumulator), chunked seqs (for the source but only make sense when you want a lazy output), reducible collections (for the source again) and getting more familiar with the core functions (there's is a mapv).

You should also consider using Criterium instead of time if only for the fact that it checks whether your JVM optimizations are capped (which is the default with lein).

=> (let [rng (range 1 10000)]
       (quick-bench (my-map-loop #(* % %) rng))
       (quick-bench (into [] (map #(* % %)) rng)) ; leveraging reducible collections and transients 
       (quick-bench (mapv #(* % %) rng))) ; existing core fn

(output elided to keep only the means)
             Execution time mean : 776,364755 µs
             Execution time mean : 409,737852 µs
             Execution time mean : 456,071295 µs

It is interesting to note that mapv is no faster than (into [] (map #(* % %)) rng) that is a generic way of optimizing these kinds of computations.

edited Sep 7, 2015 at 6:54

answered Sep 4, 2015 at 7:03

cgrand

7,95930 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

amalloy Over a year ago

I don't get the replacement of #(* % %) with just *. You're not removing indirections, you're removing multiplications! (* x) is just x, for any x.

cgrand Over a year ago

@amalloy thanks for spotting this glaring oversight. I edited my reply accordingly.

Collectives™ on Stack Overflow

Making my Clojure map function implementation faster

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related