What *warn-on-reflection* doesn’t tell you about arrays

optimization — cgrand, 6 August 2009 @ 9 h 12 min
user=> (time (let [a (make-array Object 100)] (dotimes [i 10000000] (aset a (rem i 100) nil))))
Reflection warning, NO_SOURCE_PATH:840 - call to aset can't be resolved.
"Elapsed time: 136063.015272 msecs"

With aget/aset, the index must be hinted to be an int:

user=> (time (let [a (make-array Object 100)] (dotimes [i 10000000] (aset a (int (rem i 100)) nil))))
"Elapsed time: 1064.546402 msecs"

Wow, more than 100x faster (reflection is bad) but despite the compiler doesn’t complain one can help it to choose a faster path:

user=> (time (let [a #^"[Ljava.lang.Object;" (make-array Object 100)] (dotimes [i 10000000] (aset a (int (rem i 100)) nil))))
"Elapsed time: 247.446882 msecs"

On the whole we get a 500x speed-up with only two type hints.

5 Comments »

  1. Very interesting!

    Sadly this trick doesn’t seem to work for arrays of primitives, or my syntax is wrong?

    (let [a (make-array Double/TYPE 10000)
    b #^doubles (make-array Double/TYPE 10000)]
    (time (doseq [i (range 100), j (range 100)] (aget a (int (+ i (* j 100))))))
    (time (doseq [i (range 100), j (range 100)] (aget b (int (+ i (* j 100)))))))

    Also… is there any way to get (aget a i j) to be fast – or do I have to go with a flat array and calc the offsets?

    Btw looks like a small bit of markup leaked into your code on the new site:
    “…”
    It doesn’t appear on the old site.

    Comment by Timothy Pratley — 27 September 2009 @ 12 h 58 min
  2. opps the comment ate the tags,
    they are ins tags that are leaking through.

    Comment by Timothy Pratley — 27 September 2009 @ 12 h 59 min
  3. Hmmm actually I do see a speed-up for larger samples:

    (let [a (make-array Double/TYPE 1000000)
    b #^doubles (make-array Double/TYPE 1000000)]
    (time (doseq [i (range 1000), j (range 1000)] (aget a (int (+ i (* j 100))))))
    (time (doseq [i (range 1000), j (range 1000)] (aget b (int (+ i (* j 100)))))))
    “Elapsed time: 1452.764384 msecs”
    “Elapsed time: 1118.704557 msecs”

    Comment by Timothy Pratley — 27 September 2009 @ 14 h 58 min
  4. @Timothy, I think your tests are dominated by boxed arithmetic.
    (let [a #^doubles (make-array Double/TYPE 100)]
    (time (dotimes [i 100000000] (aget a (int (rem i 100))))))
    “Elapsed time: 1806.106502 msecs”
    user=> (let [a (make-array Double/TYPE 100)]
    (time (dotimes [i 100000000] (aget a (int (rem i 100))))))
    “Elapsed time: 17794.809466 msecs”

    Note that dotimes automatically hints ‘i as an int.

    I measure this difference even for smaller arrays:
    user=> (let [a #^doubles (make-array Double/TYPE 100)]
    (time (dotimes [i 100000] (aget a (int (rem i 100))))))
    “Elapsed time: 14.871513 msecs”
    user=> (let [a (make-array Double/TYPE 100)]
    (time (dotimes [i 100000] (aget a (int (rem i 100))))))
    “Elapsed time: 30.586988 msecs”

    When I hint your code to perform primitive arithmetic, I get similar improvements:
    user=> (let [a (make-array Double/TYPE 1000000)
    b #^doubles (make-array Double/TYPE 1000000)]
    (time (doseq [i (range 1000), j (range 1000)] (aget a (int (+ (int i) (* (int j) 100))))))
    (time (doseq [i (range 1000), j (range 1000)] (aget b (int (+ (int i) (* (int j) 100)))))))
    “Elapsed time: 415.131113 msecs”
    “Elapsed time: 209.553309 msecs”

    Comment by cgrand — 28 September 2009 @ 11 h 55 min
  5. Ah, thanks!

    Comment by Timothy Pratley — 28 September 2009 @ 15 h 00 min

RSS feed for comments on this post. TrackBack URI

Leave a comment

(c) 2018 Clojure and me | powered by WordPress with Barecity