Clojure consecutive function call and memoization

Question

I go through the "Clojure programming" book by Chas Emerick, Brian Carper and Christophe Grand.

At the part about memoization, I noticed significantly decreased time elapsed for the second (and other) calls of function without even using memoization.

Sure, using memoization decreased time by order of magnitude, but I'm interested, if Clojure perform something like memoization internally.

Here is the code:

(defn prime? 
  [n]
  (cond
    (== 1 n) false
    (== 2 n) true
    (even? n) false
    :else (->> (range 3 (inc (Math/sqrt n)) 2)
               (filter #(zero? (rem n %)))
               empty?)))


(def n 123)

(time (prime? n))
(time (prime? n))

(let [m-prime? (memoize prime?)]
  (time (m-prime? n))
  (time (m-prime? n)))

And the output:

"Elapsed time: 0.235977 msecs"
"Elapsed time: 0.054549 msecs"
"Elapsed time: 0.045127 msecs"
"Elapsed time: 0.003814 msecs"

So, why the second call is almost 5 times faster, than the first one?

I think you missed JIT. I think that first performance increasing is JIT's work. — fl00r
– fl00r, Commented Dec 3, 2015 at 22:00
OK, maybe, someone can suggest good intro reading about how Clojure compiles to Java bytecode? — Oleksii M
– Oleksii M, Commented Dec 4, 2015 at 10:56

Krzysztof Kaczmarek · Accepted Answer · 2015-12-04 02:15:31Z

2

Internaly each clojure functions are represented by jvm classes - first call is longer because classloader have to load class.

as previous answer says - it's not JIT for sure, as JIT for most optimisation has a certain threshold - can be changed using XX:CompileThreshold - default value is set to 10000 - this is one of the reasons why jvm has to be warm up before benchmarking.

keep in mind that memoization is just cache. And the function have to be "pure" to work it correctly - it'd extremely hard for compiler to guess which function can be potentially automatically memoized.

answered Dec 4, 2015 at 2:15

Krzysztof Kaczmarek

3184 silver badges12 bronze badges

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

1 Comment

BillRobertson42 Over a year ago

The class is loaded when the function is read, not the first time it's called. Run your repl with the -verbose:class option and you can see that.

BillRobertson42 · Accepted Answer · 2015-12-04 13:54:57Z

2

The first time you call any Clojure function it's slower. I think Clojure delays some internal linkage or setup until a function is called.

It might be JIT, but I don't think so. That would kick in when the function is defined.

Memoization is not a panacea. If what you're calling is not really really slow, then it can actually be slower than just executing the original code. For example, I when I wrote the tournament pairing algorithm , I experimented with memoization on a function that was called repeatedly and always returned the same result, and it slowed the matching algorithm down significantly. It was 2-3 times as slow with memoization than without.

edited Dec 4, 2015 at 13:54

answered Dec 4, 2015 at 0:56

BillRobertson42

12.9k4 gold badges44 silver badges62 bronze badges

1 Comment

Davyzhu Over a year ago

Yah, I have once profiled an inappropriate memoization, it took a lot of time vectorizing, hashing, and cache searching the arg-list that even exceeds a bare computation.

Collectives™ on Stack Overflow

Clojure consecutive function call and memoization

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related