2

tl;dr : why is the code bellow so slow?

I try to optimize following piece of code for speed; it's purpose is to transform one array (size n=1000) to another (same size) while doing n^2 operations, details of the transformation are not important now.

Since I try to get as much speed as possible, I'm using Java primitives wherever I can; still, what I got is typically around 70ms per one 'transform' call. When re-written to Java, average call takes < 2ms.

1) wow, Java is fast

2) wow, Clojure is slow

3) can you explain to me, why this is so? Naively, I'd expect Clojure to produce a code bytecode, that should be pretty close to Java's, why is this not so?

4) I'm not 100% sure how to use those ^ints hints, maybe I got it wrong?

(defn transform [^ints src]
  (let [res ^ints (make-array Integer/TYPE 1000)]
    (loop [x (int 0)]
      (if (= 1000 x) res
        (do
          (aset res x (areduce src i ret (int 0) 
            (+ ret (* (mod x 2) (mod i 3) (aget src i)))))
          (recur (inc x)))))))

(let [arr (into-array Integer/TYPE (range 1000))]
  (doseq [_ (range 20)]
      (println (time (transform arr)))
  ))

1 Answer 1

16

Something like this should be much closer:

(set! *warn-on-reflection* true)
(set! *unchecked-math* :warn-on-boxed)

(defn inner ^long [^ints src ^long x]
  (let [len (alength src)]
    (loop [i 0 acc 0]
      (if (< i len)
        (recur (inc i) (+ acc (* (rem x 2) (rem i 3) (aget src i))))
        acc))))

(defn transform [^ints src]
  (let [res ^ints (int-array 1000)]
    (loop [x 0]
      (if (= 1000 x) 
        res
          (do
            (aset res x (inner src x))
            (recur (inc x)))))))

(defn bench []
  (let [arr (int-array (range 1000))]
    (doseq [_ (range 20)]
      (println (time (transform arr))))))

The top settings are useful to detect errors. The :warn-on-boxed one is new in Clojure 1.7 (currently in beta1, not quite out yet) but is particularly useful here.

Some important things I changed:

  • I replaced areduce - the problem with areduce is that it doesn't know about the primitive type of your arrays. By writing your own inner loop, you can leverage the hints. It may be possible to hint the body of areduce to get that to work but I tend to prefer explicit loops when doing primitive math.
  • I'm using ^long hints where needed because Clojure only supports primitive long param/return, not int. The correct primitive conversions will be inserted as needed. There are functions to get primitive int overflow semantics if those are needed.
  • rem can go to primitive ops where mod cannot. I think the semantics are the same here for what you're doing. This was the source of most of the boxing.
  • I'm using int-array instead of the other ways you were making arrays. I think this is the best way for what you're doing.

You could possibly combine the two loops into one and improve the performance some more.

1
  • Thank you, now it runs in less than 4ms, which is epic! Apr 17, 2015 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.