CODEWITHSUNDEEP
performanceclojurefunctional-programming
Lordking
Lordking

Reputation: 1413

Making my Clojure map function implementation faster

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.

Upvotes: 2

Views: 825

Answers (1)

cgrand
cgrand

Reputation: 7949

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.

Upvotes: 0

Related Questions