Taming multidim Arrays

interop — cgrand, 15 October 2009 @ 20 h 04 min

Utilities

(defn array? [x] (-> x class .isArray))
(defn see [x] (if (array? x) (map see x) x))

Creation

Blank and rectangular:

(see (make-array Double/TYPE 3 2))
; ((0.0 0.0) (0.0 0.0) (0.0 0.0))

From a nested collection:

(see (into-array (map (partial into-array Double/TYPE) [[1 2 3 4] [5 6]])))
; ((1.0 2.0 3.0 4.0) (5.0 6.0))

Reading

A multidim array:

(def dd (make-array Double/TYPE 1000 1000))

Naive method:

(time (dotimes [i 1000] (dotimes [j 1000] (aget dd i j))))
; "Elapsed time: 455.514388 msecs"

Step-by-step (allow inlining):

(time (dotimes [i 1000] (dotimes [j 1000] (-> dd (aget i) (aget j)))))
; "Elapsed time: 257.625829 msecs"

(Not so) Hinted step-by-step (#^doubles is ignored because of inline-expansion):

(time (dotimes [i 1000] (dotimes [j 1000] (-> #^objects dd (#^doubles aget i) (aget j)))))
; "Elapsed time: 157.095175 msecs"

Fully hinted step-by-step:

(time (dotimes [i 1000] (dotimes [j 1000] (let [#^doubles a (aget #^objects dd i)] (aget a j)))))
; "Elapsed time: 17.412548 msecs"

Let’s embody this knowledge in a nice macro:

(defmacro deep-aget
  ([hint array idx]
    `(aget ~(vary-meta array assoc :tag hint) ~idx))
  ([hint array idx & idxs]
    `(let [a# (aget ~(vary-meta array assoc :tag 'objects) ~idx)]
       (deep-aget ~hint a# ~@idxs))))

Does it work?

(time (dotimes [i 1000] (dotimes [j 1000] (deep-aget doubles dd i j))))
; "Elapsed time: 16.937279 msecs"

Updating

Naive method:

(time (dotimes [i 1000] (dotimes [j 1000] (aset dd i j 42.0))))
; "Elapsed time: 13859.404896 msecs"

Partially hinted step-by-step:

(time (dotimes [i 1000] (dotimes [j 1000] (-> #^objects dd (aget i) (aset j 42.0)))))
; "Elapsed time: 94.699536 msecs"

Fully hinted step-by-step (take 1):

(time (dotimes [i 1000] (dotimes [j 1000] (let [#^doubles a (aget #^objects dd i)] (aset a j 42.0)))))
; java.lang.IllegalArgumentException: More than one matching method found: aset

The compiler doesn’t know which aset to pick between (Object[], int, Object) and (double[], int, double) according to the hints (double[], int, Object). That’s why one needs to hint 42.0:

(time (dotimes [i 1000] (dotimes [j 1000] (let [#^doubles a (aget #^objects dd i)] (aset a j (double 42.0))))))
; "Elapsed time: 19.561983 msecs"

A nice macro to abstract away:

(defmacro deep-aset [hint array & idxsv]
  (let [hints '{doubles double ints int} ; writing a comprehensive map is left as an exercise to the reader
        [v idx & sxdi] (reverse idxsv)
        idxs (reverse sxdi)
        v (if-let [h (hints hint)] (list h v) v)
        nested-array (if (seq idxs)
                       `(deep-aget ~'objects ~array ~@idxs)
                        array)
        a-sym (with-meta (gensym "a") {:tag hint})]
      `(let [~a-sym ~nested-array]
         (aset ~a-sym ~idx ~v))))

Does it work?

(time (dotimes [i 1000] (dotimes [j 1000] (deep-aset doubles dd i j 42.0))))
; "Elapsed time: 19.439133 msecs"

(All tests run on jdk 1.6.0_14 32bit, options -server -XX:+DoEscapeAnalysis on a processor with a 6MB L2 cache.)

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