5

Can anyone explain why the time jumps by an order of magnitude simply by wrapping this in a function?

user> (time (loop [n 0 t 0] (if (= n 10000000) t (recur (inc n) (+ t n))))) "Elapsed time: 29.312145 msecs" 49999995000000 user> (defn tl [r] (loop [n 0 t 0] (if (= n r) t (recur (inc n) (+ t n))))) #<Var@54dd6004: #object[user$eval3462$tl__3463 0x7d8ba46 "user$eval3462$tl__3463@7d8ba46"]> user> (time (tl 10000000)) "Elapsed time: 507.333844 msecs" 49999995000000

I'm curious how a simply iteration like this can be made much faster. For example, a similar iterative loop in C++ takes less than 1 ms in Release mode, or about 20 ms in Debug mode on the same system as this Clojure code.

Improve this question

1 Answer 1

Reset to default
9

This happens because in second case passed argument is being boxed. Add type hint to fix this:

user> (defn tl [^long r] (loop [n 0 t 0] (if (= n r) t (recur (inc n) (+ t n))))) user> (time (tl 10000000)) "Elapsed time: 20.268396 msecs" 49999995000000

UPD:

1, 2) In the first case you operate with java primitives, that's why it's so fast. ^Integer won't work here, because it's type hint for boxed type java.lang.Integer (that's why it's capitalized). ^long is type hint exactly for java long primitive. For function parameters you may do only ^long and ^double primitive type hints (others are not supported besides of these you may do type hints for all kinds of primitive arrays, like ^floats, ^bytes etc.).

3) Since passed argument is boxed this forces generic aritmethics for all operations. In other words, every + and inc operation will create new object on heap (in case of primitives, they will remain on stack).

UPD 2:

As an alternative to type hinting you may explicitly convert passed argument to primitive before the loop:

user> (defn tl [r] (let [r (long r)] (loop [n 0 t 0] (if (= n r) t (recur (inc n) (+ t n)))))) user> (time (tl 10000000)) "Elapsed time: 18.907161 msecs" 49999995000000
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

two followups: I had tried this with ^Integer with no difference; why is long necessary for an arg of ten million? and 2) why is long lower-case but ^Integer must be capitalized or won't compile? 3) since the arg is only passed once, at function call, this "unboxing" one time only is enough to cause such a huge time increase?
@johnbakers I'll extend my answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.