Brool brool (n.) : a low roar; a deep murmur or humming

aset is Faster Than aset-int

 |  performance array clojure coding

Clojure isn’t the fastest functional lanuage – that title seems to go to Haskell these days, at least for the stuff that I do – but it nonetheless is usually fast enough. It’s a dynamic language, so is perhaps cursed to be somewhat slower always, but nonetheless for the things that I do, it seems to be about 2-4x slower than Ocaml/Haskell and substantially faster than Python.

Nonetheless, I ran into a situation where it seemed to be 100x slower than Java because of an erroneous assumption on my part. After stripping out and profiling and removing everything extraneous, it finally came down to array access. Ignoring the uselessness of this snippet for a while, the issue is how to translate something like the following code:

int v[] = new int[1000];
java.util.Arrays.fill(v, 0);
for (int i = 0; i < 100000; i++)
    for (int ix = 0; ix < 1000; ix++) {

… which runs in about 350ms on my Macbook. My pass at the Clojure equivalent, with the type hinting:

;; this is 100x slower than the equivalent in Java
(defn useless-array-manipulation []
  (let [v (int-array 1000)]
    (java.util.Arrays/fill v 0)
    (dotimes [_ (int 100000)]
      (dotimes [ix (int 1000)]
        (aset-int v ix (unchecked-add (int 1) (aget v ix)))
        (aset-int v ix (unchecked-subtract (int 1) (aget v ix)))))))

… which takes about 40692ms – more than 100x slower. What the hell? After many hours of Googling, I finally discovered from the comments on this blog post that aset-int is slower than aset, which I don’t recall seeing anywhere else. Does it really make a difference?

;; much faster
(defn useless-array-manipulation []
  (let [v (int-array 1000)]
    (java.util.Arrays/fill v 0)
    (dotimes [_ (int 100000)]
      (dotimes [ix (int 1000)]>
        (aset v ix (unchecked-add (aget v ix) (int 1)))
        (aset v ix (unchecked-subtract (aget v ix) (int 1)))))))

… runs in about 1000ms, or about 3x slower than the Java variant, and is definitely something that I can live with. I had been assuming that aset-int was of course faster because it was more specific, but in fact (aset v ix (int val)) is much faster than (aset-int v ix val).


Comments are moderated whenever I remember that I have a blog.

Jan Rychter | 2013-06-12 08:42:48
Just stumbled upon this. Note that you don't need to do the fill(), as Java guarantees that your array will be initialized with zeroes: "Each class variable, instance variable, or array component is initialized with a default value when it is created (§15.9, §15.10) [...] For type int, the default value is zero, that is, 0." Also, my measurements show that if you need to zero an array repeatedly in a loop, it is faster to actually create it than call java.util.Arrays/fill (even taking the increased GC pressure into account).
Add a comment