Clojure, Faster

Re:Clojure, Faster by patrec on Friday January 08, 2021 @04:58PM (#25691064)

This reads a bit like "why you shouldn't use clojure" to me. I'd expect to leave some performance on the table when writing idiomatic code in a dynamic language with immutable datatypes, but a function that's already specialized to arrays, as the name indicates, taking 3 orders of magnitude too much time? 1-10 microseconds to say "get me the length of this java array, and BTW this is a java array"? What on earth is going on there?

Edit: So I just ran the author's (alength (long-array 5)) (with the indirection to foil type inference) and got 10µs mean execution time in criterium. By contrast here's some roughly equivalent python:

   In [5]: a = array.array('l', [5])                                                                                                                                                                         
   In [6]: timeit len(a)                                                                                                                                                                                     
   32.9 ns ± 0.105 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

More or less exactly the same with a plain python list. So clojure's type specialized function manages to be 300 times slower than the generic version in freaking *python*. In fairness "count" is better if still terrible (4x slower than python).

[ Parent | on HN ]

Re:Clojure, Faster by aphyr on Friday January 08, 2021 @05:27PM (#25691353)

In short: it's slow because there isn't just one kind of Java array, and if you don't say which one you mean, Clojure has to do reflection to figure it out.

Inside the JVM, there are several different types of arrays: bytes, floats, objects, etc. Clojure.lang.RT includes methods for getting the length of all of these types--for instance, here's the method for the length of arrays of longs:

https://github.com/clojure/clojure/blob/master/src/jvm/cloju...

The clojure.core/alength function calls clojure.lang.RT/alength, but that callsite is polymorphic: the Clojure compiler doesn't know which of the RT functions to emit a call for, because it needs the type signature. If the type is unavailable at compile time, the Clojure compiler emits reflective code which inspects the type of the reference, determines which specific clojure.lang.RT/alength implementation to dispatch to, then executes that call dynamically. That's the slow part!

https://github.com/clojure/clojure/blob/clojure-1.10.1/src/c...

Just like the article says, if you include a type hint, the compiler can emit an invokestatic call directly to, say, clojure.lang.RT.alength(long[]), and skip all the reflection.

[ Parent | on HN ]

Re:Clojure, Faster by patrec on Friday January 08, 2021 @06:35PM (#25692228)

> In short: it's slow because there isn't just one kind of Java array, and if you don't say which one you mean, Clojure has to do reflection to figure it out.

But it can't need any less reflection than "count" needs, and "count" is 100x faster. Surely whatever alength is doing in the non-type hinted case can't be... ideal?

> If the type is unavailable at compile time, the Clojure compiler emits reflective code which inspects the type of the reference, determines which specific clojure.lang.RT/alength implementation to dispatch to, then executes that call dynamically. That's the slow part!

But where do all those clock cycles go? Doing runtime type inspection and then dispatching to one of 9 static functions based on that doesn't feel like it ought to be anywhere near that terrible (especially in a JIT'ed language).

[ Parent | on HN ]

Re:Clojure, Faster by patrec on Friday January 08, 2021 @06:49PM (#25692600)

Just to illustrate, some pretend-analogous run time type-inspect based dispatch code in python (a language not known for its blazing speed) is still much, much faster than this:

   In [3]: timeit a = [1];  a.__len__() if type(a) is list else len(a)                                                                                                                                       
   126 ns ± 0.615 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

[ Parent | on HN ]

Re:Clojure, Faster by aphyr on Friday January 08, 2021 @05:40PM (#25691466)

So clojure's type specialized function manages to be 300 times slower than the generic version in freaking python. In fairness "count" is better if still terrible (4x slower than python).

Er, to be clear, Clojure's `alength` is a generic function--you're not measuring type-specialized behavior. The type-specialized `alength` call clocks in at around ~4 ns/call, as the article notes.

[ Parent | on HN ]

Re:Clojure, Faster by patrec on Friday January 08, 2021 @06:07PM (#25691693)

Well, it's generic in the type of the array element, but it's not generic in that it only works with Java arrays not arbitrary sequences. In particular it's clearly less generic than count (in clojure) or len (in python).

And it is not at all obvious to someone not intimately familiar with the JVM/Clojure that the element type would in any way matter for working out the length of an array. Indeed as far as I'm aware the OpenJVM memory representation for arrays has a length field at the same offset that's independent of the array element type, correct?

So that alength (in the typical case) is in fact 300x slower than len in python and 100x than count in clojure does not seem something that would be intuitively obvious to most people (including clojure programers).

[ Parent | on HN ]

Re:Clojure, Faster by gameswithgo on Friday January 08, 2021 @05:44PM (#25691502)

It is really nice when the easy way is also the fast way. I have a pet peeve about this for languages that have “iterators”. they should be fast! like rust and c++ and java streams manage to make then. then you don’t have to worry about this stuff.

[ Parent | on HN ]

Re:Clojure, Faster by fulafel on Monday January 11, 2021 @02:25AM (#25725788)

The Clojure functional equivalent, approximately, of iterators is the ISeq interface, and lazy sequences etc that work with it. It's fast. You just don't have to deal with iterators manually.

[ Parent | on HN ]

Re:Clojure, Faster by brundolf on Friday January 08, 2021 @06:04PM (#25691668)

You wouldn't want to use iterators to compute the length of a collection, even in a language where they're fast. That turns a constant-time operation into a linear-time operation

[ Parent | on HN ]

Re:Clojure, Faster by patrec on Saturday January 09, 2021 @07:12AM (#25699715)

Not true, with two random access iterators in C++ for example you can compute the distance between them, and thus the the length of an array (e.g. a.end() - a.begin()) and it will be constant time.

[ Parent | on HN ]

Re:Clojure, Faster by brundolf on Sunday January 10, 2021 @12:09PM (#25716757)

I guess I'm not familiar enough with C++'s iterators. In most languages I'm familiar with, an iterator is an abstract concept that only knows how to get the next item and (sometimes) tell whether or not it's finished.

[ Parent | on HN ]