Clojure Performance For Expensive Algorithms

[Geo]

Hello,

I am cross-posting my Clojure question from StackOverflow.  I am trying to get an algorithm in Clojure to match Java speed and managed to get the performance to within one order of magnitude and wondering if more is possible. The full question is here:

http://stackoverflow.com/questions/14949705/clojure-performance-for-expensive-algorithms

Thank you.

[Andy Fingerhut]

This won't get you all of the way to Java speeds, or at least it didn't for me, but try these things:

Use:

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

The first won't speed anything up, but it will warn you about some things that are slow.

The second will use unchecked match wherever it can, meaning primitive operations on arithmetic values like longs, that will silently wrap instead of checking for overflow. Java doesn't check for overflow in primitive operations, either.

Also use aset instead of aset-int. I don't know why, but the aset-* operations are typically slower than aset, as long as the type hints on the aset arguments are good enough.

I got within 4x Java speed with those changes.

Andy

[Mark Engelberg]

Another idea: try using arrays of longs, rather than ints, since that is what Clojure prefers.

[Geo]

Thanks. The unchecked math didn't make any difference. But after I switching to aset I did indeed get to within 4x of Java. Then at the suggestion of Christophe Grand on StackOverflow I switched to .equals instead of = and that got me to ~133% of Java performance. Very close!

[Geo]

Using long-array instead of int-array seems to produce a very slight but noticeable improvement. (~2.1 sec -> ~1.8 sec) = 1.16x improvement

One other thing is that loop seems to return boxed primitives, so by wrapping the inner loop with (long ) I got another slight performance gain. (~2.5 sec -> ~2.0 sec) = ~1.25x improvement

[Geo]

One thing I don't get is that switching the type hints from

[#^"[Ljava.lang.String;" a1 #^"[Ljava.lang.String;" a2]

to [^objects a1 ^objects a2] didn't seem to have any negative impact on performance. Can anyone explain why hinting ^objects is just as good as specifying that it's an array of Strings? What are you hinting with ^objects that Clojure doesn't already know?

[Andy Fingerhut]

^objects is a Clojure synonym for ^"[Ljava.lang.Object;".  Note that there are such synonyms for only a few Java types, not everything, e.g. there is no ^strings.

What you are hinting is that a1 and a2 are Java arrays of objects.  I think this might speed up (aget a1 i) expressions, since it is known that a1 is an array of objects, but I'm not sure about that.  I believe "under the hood" in the JVM all arrays of Objects are treated the same, regardless of whether those Objects are String, Integer, java.awt.Color, etc.

Andy

[Geo]

Note that I'm not very confident that using long-array instead of int-array is a true improvement vs. just noise.

[Marko Topolnik]

The difference between String[] and Object[] is that a member of the former doesn't need a checked cast to String, but the latter does need one. In the code under consideration, however, nothing specific to String is used, so even in the Java code you can freely replace String[] with Object[] and everything still works.

If, on the other hand, you needed to invoke say substring, you'd see a small penalty due to the checked cast operation.

[Geo]

What about the call to .equals?

[Marko Topolnik]

Naturally, it's Object#equals. String's override of equals gets involved without the checked downcast.

[Geo]

Cool. Thanks for the explanation.

[Phillip Lord]

So, I was curious about this. So, you've done everything using java
arrays. What would happen if you used clojure data structures.

So I tried this instead.

(defn lcs-native
[n1 n2]
(let [n1-len (count n1)
n2-len (count n2)
prev {}
curr {}]
(loop [i 0 max-len 0 prev prev curr curr]
(if (< i n1-len)
(recur (inc i)
(loop [j 0 max-len max-len]
(if (< j n2-len)
(if (= (nth n1 i) (nth n2 j))
(let [match-len (inc (get prev j 0))]
(do
(assoc curr (inc j) match-len)
(recur (inc j) (max max-len match-len))))
(do
(assoc curr (inc j) 0)
(recur (inc j) max-len)))
max-len))
curr
prev)
max-len))))

This is slower, but interesting only by about 1/3 which is less than you
might have thought, assuming I have got the code correct.

Perhaps, then, using transients would speed things up.

(defn lcs-native-transient
[n1 n2]
(let [n1-len (count n1)
n2-len (count n2)
prev (transient {})
curr (transient {})]
(loop [i 0 max-len 0 prev prev curr curr]
(if (< i n1-len)
(recur (inc i)
(loop [j 0 max-len max-len]
(if (< j n2-len)
(if (= (nth n1 i) (nth n2 j))
(let [match-len (inc (get prev j 0))]
(do
(assoc! curr (inc j) match-len)
(recur (inc j) (max max-len match-len))))
(do
(assoc! curr (inc j) 0)
(recur (inc j) max-len)))
max-len))
curr
prev)
max-len))))


Curiously, this is a disaster, taking over about 10x longer. Not what I
was expecting at all.

Guess this doesn't shed any light on your problem at all, but just
thought it would be good to share.

Phil

[Stephen Compall]

On Feb 20, 2013 5:55 AM, "Phillip Lord" <philli...@newcastle.ac.uk> wrote:
>                      (do
>                        (assoc curr (inc j) 0)
>                        (recur (inc j) max-len)))

Here you're discarding the result of assoc, a pure function, which changes the code's nature significantly.

>                      (do
>                        (assoc! curr (inc j) 0)
>                        (recur (inc j) max-len)))

Nor is it safe to discard the result of calling assoc!; see how assoc! is used in other online examples.

--
Stephen Compall
If anyone in the MSA is online, you should watch this flythrough.

[Christophe Grand]

I updated my answer on SO, with a deftype-based one that gives me an additional 30% boost.  

--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--
On Clojure http://clj-me.cgrand.net/
Clojure Programming http://clojurebook.com
Training, Consulting & Contracting http://lambdanext.eu/

[Marko Topolnik]

Whatever the final performance achieved, the fact remains that the original Java code was much cleaner, simpler, and more comprehensible than the big ball of mud the performant Clojure version is turning into.

I have my own piece of performance-critical code that I used to maintain and improve over a timespan of many months. I finally gave in and recoded the thing in Java. It took only a couple of hours and the result was nice, clean, idiomatic Java code, with completely predictable performance characteristics, as opposed to the Clojure version where it took many hours of staring at ridiculuously counterintuitive stacktraces in VisualVM to find what to optimize and how. The amount of code is about the same at either end.

[Phillip Lord]

Ah, yes, thought it was wrong somewhere!

[Geo]

Man, this is exactly how I feel after all this tinkering! It was great for learning Clojure a bit more in depth, but in the end I am going to stick with the Java solution. Especially since it's so easy to mix Java and Clojure in the same project! I just specify :java-source-paths ["src/java"] in my project.clj and I just call that one method when I need it and the rest of the project is in Clojure. I think when performance if critical idiomatic Clojure is to just drop down to Java :)

Christophe's second function actually achieves Java speed or very close (within 5-10%), but it's ugly and there's a bit more to my algorithm which would make it even uglier if I were to go that route.

[David Nolen]

On Thu, Feb 21, 2013 at 4:55 AM, Marko Topolnik <marko.t...@gmail.com> wrote:

Whatever the final performance achieved, the fact remains that the original Java code was much cleaner, simpler, and more comprehensible than the big ball of mud the performant Clojure version is turning into.

To my eyes the deftype version is about as clean, simple, comprehensible, as the Java version. But I've been doing Clojure for a while now.

Christophe's version also has the advantage that it can pretty much compile down to efficient JavaScript via ClojureScript and probably an efficient ClojureCLR program as well. This may or may not matter to you.

David 

[David Nolen]

This thread made me realize there's quite a bit of low hanging compatibility fruit between Clojure & ClojureScript, so as of this changeset http://github.com/clojure/clojurescript/compare/4652498035...3c0fb6ef5f

We can now compile Christophe's example code in ClojureScript w/ exactly 4 minor changes. We could imagine handling these differences with feature expressions:

(deftype F [^:unsynchronized-mutable ^ints curr

            ^:unsynchronized-mutable ^ints prev]

  IFn ; <===== CHANGED

  (invoke [_ a1 a2]

    (let [^objects a1 a1

          ^objects a2 a2]

      (areduce a1 i max-len 0

               (let [m (areduce a2 j max-len max-len ; <===== CHANGED

                  (let [match-len 

                        (if (identical? (aget a1 i) (aget a2 j)) ; <===== CHANGED

                          (unchecked-inc (aget prev j))

                          0)]

                    (aset curr (unchecked-inc j) match-len) ; <===== CHANGED

                    (if (> match-len max-len)

                      match-len

                      max-len)))

              bak curr]

          (set! curr prev)

          (set! prev bak)

          m)))))

(defn my-lcs2 [^objects a1 a2]

  (let [n (inc (alength a1))

        f (F. (int-array n) (int-array n))]

    (f a1 a2)))

Running under the Google V8 JS engine I see an execution time of ~2.2 seconds using the same benchmark on the StackOverflow question. This is compared to a ~1s running time for the JVM. This is nearly within 2X of the JVM!

The pretty printed Closure advanced optimized code for the important bits:

Sg.prototype.call = function(a, b, c) {

  for(var a = this, d = 0, f = 0;;) {

    if(d < b.length) {

      var h = d + 1, i;

      i = g;

      a: {

        i = 0;

        for(var k = f;;) {

          if(i < c.length) {

            var f = i + 1, p = b[d] === c[i] ? a.gb[i] + 1 : 0;

            a.cb[i + 1] = p;

            k = p > k ? p : k;

            i = f

          }else {

            i = k;

            break a

          }

        }

        i = g

      }

      d = a.cb;

      a.cb = a.gb;

      a.gb = d;

      d = h;

      f = i

    }else {

      return f

    }

  }

};

That looks like some highly optimized JS to me ;)

I think I'll stick with writing my fast code in Clojure thank you very much.

David

[Marko Topolnik]

On Thursday, February 21, 2013 10:49:42 PM UTC+1, David Nolen wrote:

On Thu, Feb 21, 2013 at 4:55 AM, Marko Topolnik <marko.t...@gmail.com> wrote:

Whatever the final performance achieved, the fact remains that the original Java code was much cleaner, simpler, and more comprehensible than the big ball of mud the performant Clojure version is turning into.

To my eyes the deftype version is about as clean, simple, comprehensible, as the Java version. But I've been doing Clojure for a while now.

My 5-year experience with Clojure (since 0.9) hasn't helped me to see it that way.

 

Christophe's version also has the advantage that it can pretty much compile down to efficient JavaScript via ClojureScript and probably an efficient ClojureCLR program as well. This may or may not matter to you.

In a Java project it clearly does not matter. In library code it quite likely could matter a lot. That is of course a subject completely separate from the discussion on the pitfalls involved in getting Clojure performance right.

Apparently even Cristophe broke quite a bit of sweat to come up with his second solution, and did also wander around searching for bottlenecks (like .equals against =). ^:unsynchronized-mutable is something I've never layed my eyes on before and I've spent quite a bit of time working on optimized Clojure, googling for any trick I could find. What is the most trivially obvious way to solve a probelm in Java takes the most obscure features of Clojure to emulate.

Finally, Cristophe's solution, as well as all other optimized Clojure code, seems to be just barely making it for the use case involved. In my code, for example, I struggle with such things as an array of Strings (received from a Java method) failing when used in amap, which needs an array of Objects. I'm sure I could come up with yet another layer of obscurity which would make this work, but, as I said, after several months of struggling I'm ready to settle for 100 lines of clean, elegant, obvious Java.

[Phillip Lord]

Marko Topolnik <marko.t...@gmail.com> writes:
>> Christophe's version also has the advantage that it can pretty much
>> compile down to efficient JavaScript via ClojureScript and probably an
>> efficient ClojureCLR program as well. This may or may not matter to you.
>>

> Apparently even Cristophe broke quite a bit of sweat to come up with his
> second solution, and did also wander around searching for bottlenecks (like
> .equals against =). ^:unsynchronized-mutable is something I've never layed
> my eyes on before and I've spent quite a bit of time working on optimized
> Clojure, googling for any trick I could find. What is the most trivially
> obvious way to solve a probelm in Java takes the most obscure features of
> Clojure to emulate.

What is interesting, though, it that it's not clear yet why this is the
case. What is clojure doing that is slow.

Phil

[Marko Topolnik]

Perhaps it's time to hit the decompiler :) AOT compile and apply javap; do the same for a comparable Java version. This will be a time-consuming and frustrating experience and it won't bring you lasting insight into performant Clojure because things will change around in the next release.

[Phillip Lord]

I'd look at it the other way around. It would be good if someone did
this, so that it would change around in the next release, and I won't
have to have any lasting insight into the performant Clojure.

I wasn't the OP, BTW, although I suspect he and I share a profession.
String matching algorithms are things I would like to work and would
like to work quickly. But I'd like not to have to code them; hence the
interest in the thread.

Phil

> --

--
Phillip Lord, Phone: +44 (0) 191 222 7827
Lecturer in Bioinformatics, Email: philli...@newcastle.ac.uk
School of Computing Science, http://homepages.cs.ncl.ac.uk/phillip.lord
Room 914 Claremont Tower, skype: russet_apples
Newcastle University, twitter: phillord
NE1 7RU

[Marko Topolnik]

That would exactly be my point, too: I want to write idiomatic Clojure and have the underlying runtime make it perform; that's what I get with Java. I don't want to twist the compiler's arm into producing the bytecode that I can get from straightforward Java code.

Incidentally, it happens that the piece of code that I have mentioned is also about heavy string matching.

[David Nolen]

On Fri, Feb 22, 2013 at 3:43 AM, Marko Topolnik <marko.t...@gmail.com> wrote:

My 5-year experience with Clojure (since 0.9) hasn't helped me to see it that way.

I've been doing Clojure for about 5 years as well. Optimizing Clojure in the early days was pretty tough stuff, and resorting to Java was pretty much necessary. Today I think Clojure does pretty well at exposing a subset of the language that is fast and no more cumbersome to write than Java (or JavaScript) when performance is key.

 

 

Christophe's version also has the advantage that it can pretty much compile down to efficient JavaScript via ClojureScript and probably an efficient ClojureCLR program as well. This may or may not matter to you.

In a Java project it clearly does not matter. In library code it quite likely could matter a lot. That is of course a subject completely separate from the discussion on the pitfalls involved in getting Clojure performance right.

Fair enough. My point was simply that Clojure implementations have a small learnable subset that performs well when performance is desired - primitives, loops, arrays, deftypes, etc regardless of host. It's unfortunate that the host, in this case the JVM, requires quite a bit of thinking about type hints and casts. I think most of the challenges around are writing fast Clojure JVM code lie here. I note these issues are not present in ClojureScript ;)

 

Apparently even Cristophe broke quite a bit of sweat to come up with his second solution, and did also wander around searching for bottlenecks (like .equals against =). ^:unsynchronized-mutable is something I've never layed my eyes on before and I've spent quite a bit of time working on optimized Clojure, googling for any trick I could find. What is the most trivially obvious way to solve a probelm in Java takes the most obscure features of Clojure to emulate.

It's right there in the docstring of deftype, but OK. 

Finally, Cristophe's solution, as well as all other optimized Clojure code, seems to be just barely making it for the use case involved. In my code, for example, I struggle with such things as an array of Strings (received from a Java method) failing when used in amap, which needs an array of Objects. I'm sure I could come up with yet another layer of obscurity which would make this work, but, as I said, after several months of struggling I'm ready to settle for 100 lines of clean, elegant, obvious Java.

Perhaps it's because I lack considerable experience with Java that I don't find it so challenging. Yes it's a bit finicky, yes it could be improved, but it still beats writing Java in my mind.

David 

[Marko Topolnik]

It's right there in the docstring of deftype, but OK. 

...followed by several sentences of big fat warnings, including that they

are present only to facilitate the building of higher
level constructs, such as Clojure's reference types, in Clojure
itself.

Other than that, you are right, it's there in the docstring :)

Fair enough. My point was simply that Clojure implementations have a small learnable subset that performs well when performance is desired - primitives, loops, arrays, deftypes, etc regardless of host. It's unfortunate that the host, in this case the JVM, requires quite a bit of thinking about type hints and casts. I think most of the challenges around are writing fast Clojure JVM code lie here. I note these issues are not present in ClojureScript ;)

OK, but does that mean that at the end of the day, optimized ClojureScript performance is head-to-head with optimized JVM Clojure in a desktop/server side application?

 

 

Finally, Cristophe's solution, as well as all other optimized Clojure code, seems to be just barely making it for the use case involved. In my code, for example, I struggle with such things as an array of Strings (received from a Java method) failing when used in amap, which needs an array of Objects. I'm sure I could come up with yet another layer of obscurity which would make this work, but, as I said, after several months of struggling I'm ready to settle for 100 lines of clean, elegant, obvious Java.

Perhaps it's because I lack considerable experience with Java that I don't find it so challenging. Yes it's a bit finicky, yes it could be improved, but it still beats writing Java in my mind.

I'll give you one specific item that I keep tripping upon: the lack of reassignable, stack-based locals. Without them I can't efficiently get more than one value out of a loop. Another item is that I can get zero primitive values out of a loop. How do you cope with those?

When on the subject, the times are getting ripe for a full-length book not about how handsome and elegant and FP-y Clojure is (we have plenty of those), but a "terrorist's handbook" on writing performant Clojure. Can you recommend any current material in that direction?

-Marko

[David Nolen]

On Fri, Feb 22, 2013 at 2:06 PM, Marko Topolnik <marko.t...@gmail.com> wrote:

Fair enough. My point was simply that Clojure implementations have a small learnable subset that performs well when performance is desired - primitives, loops, arrays, deftypes, etc regardless of host. It's unfortunate that the host, in this case the JVM, requires quite a bit of thinking about type hints and casts. I think most of the challenges around are writing fast Clojure JVM code lie here. I note these issues are not present in ClojureScript ;)

OK, but does that mean that at the end of the day, optimized ClojureScript performance is head-to-head with optimized JVM Clojure in a desktop/server side application?

I don't think we can ever really be head-to-head and performance varies between JS engines. V8 is particularly good - not surprising since it's from the same folks who worked on HotSpot.

That, we try to get the performance of ClojureScript on V8 as close to Clojure on the JVM as we can without sacrificing performance on the other engines. I think we're doing OK and we're improving constantly.

 

 I'll give you one specific item that I keep tripping upon: the lack of reassignable, stack-based locals. Without them I can't efficiently get more than one value out of a loop. Another item is that I can get zero primitive values out of a loop. How do you cope with those?

Some ideas for the first point:

* atoms

* implement efficient tuple type which uses mutation for multiple value return

I suspect the second option will be pretty fast. Annoying, but that's a tradeoff with Clojure's mostly functional design.

Second point, I think 1.5.0 addresses that to some degree thanks to Christophe.

 

When on the subject, the times are getting ripe for a full-length book not about how handsome and elegant and FP-y Clojure is (we have plenty of those), but a "terrorist's handbook" on writing performant Clojure. Can you recommend any current material in that direction?

-Marko

Heh, I always point out test.benchmark - http://github.com/clojure/test.benchmark. There's some horrifying stuff in there ;)

David 

[Marko Topolnik]

On Friday, February 22, 2013 8:23:38 PM UTC+1, David Nolen wrote:

 

 I'll give you one specific item that I keep tripping upon: the lack of reassignable, stack-based locals. Without them I can't efficiently get more than one value out of a loop. Another item is that I can get zero primitive values out of a loop. How do you cope with those?

Some ideas for the first point:

* atoms

These are thread-safe and nowhere near as efficient as stack-based locals.

 

* implement efficient tuple type which uses mutation for multiple value return

Basically, this is the ^:unsynchronized-mutable that we just mentioned :) This is much better, but still it's not stack-based, so incurs the cost of allocation and GC.

 

I suspect the second option will be pretty fast. Annoying, but that's a tradeoff with Clojure's mostly functional design.

Annoying and slower than Java's locals, unfortunately. Most of the time it won't make a huge dent in the performance, but I just happen to have an inner loop that iterates between zero and three times only, zero being by far the most common case, and is entered many times from the surrounding loop. The performance drop is considerable.

 

Second point, I think 1.5.0 addresses that to some degree thanks to Christophe.

As far as I got it, it only prevents loop-recur from destroying the primitive-returning semantics of functions. Loops used within function bodies stay the same.

 

Heh, I always point out test.benchmark - http://github.com/clojure/test.benchmark. There's some horrifying stuff in there ;)

I remember you mentioning that on StackOverflow, maybe it's time for me to check it out more seriously.

[Marko Topolnik]

On Friday, February 22, 2013 8:44:30 PM UTC+1, Marko Topolnik wrote:

 

* implement efficient tuple type which uses mutation for multiple value return

Basically, this is the ^:unsynchronized-mutable that we just mentioned :) This is much better, but still it's not stack-based, so incurs the cost of allocation and GC.

Forgot to mention another hugely important factor: heap-allocated objects spell disaster for CPU cachelines. With today's architectures the difference between a cache hit and a cache miss is like the difference between catching your bus to work and having to walk instead. In our example I would have to be careful to reuse the same deftype instance for all inner loop runs, but then I'd need even more code to make sure the values are reset before entering. The result would be messy, brittle code with higher-level logic scattered between all the housekeeping constructs.

[David Nolen]

On Friday, February 22, 2013, Marko Topolnik wrote:

Annoying and slower than Java's locals, unfortunately. Most of the time it won't make a huge dent in the performance, but I just happen to have an inner loop that iterates between zero and three times only, zero being by far the most common case, and is entered many times from the surrounding loop. The performance drop is considerable.

If the loops are so small why can't you just make these be more loop bindings? 

[Marko Topolnik]

Because the number of iterations is driven by outside data. On occasion it may be more than three iterations; from the logic standpoint this is clearly a loop, it's just that the statistical distribution of iterations leans heavily towards zero and almost vanishes above three or four. 

[David Nolen]

Er re: assigning stack based locals. Forget wasting time making a tuple type, probably best to just do that with a small mutable array. This worked ok for us when porting some Java persistent data structure code to ClojureScript.

[Marko Topolnik]

On Friday, February 22, 2013 8:41:15 PM UTC+1, David Nolen wrote:

Er re: assigning stack based locals. Forget wasting time making a tuple type, probably best to just do that with a small mutable array. This worked ok for us when porting some Java persistent data structure code to ClojureScript.

Again, must reuse the same array for all inner iterations to avoid allocation, GC, and cache misses. I need two Strings and one primitive double, so I'm actually looking at two arrays. The housekeeping overhead is just too much for my taste. That's why the rewrite into Java came as such a relief :)

[David Nolen]

OK, though threading one 3 element object array into the loop with one double cast doesn't really seem that problematic or slow to me.

[David Nolen]

Oh right, sorry, you don't want to pay for boxing the double. Yeah this is the case where you'd want to go with a tuple. If this really was common in my own code I would probably write a mutable tuple macro. But I totally understand why someone else might just write the Java if they just want performance and just don't want to bother.

[Marko Topolnik]

It wouldn't be a first for me, either; I'm already accustomed to writing macros for performance. For example, unrolling writer.append loops, using "jassoc" as a Java HashMap replacement for assoc, and many similar tricks.

On this particular occasion, where the performance-critical code segment has gradually grown to over 100 lines, and where with each development iteration I had to set up profiling sessions, painstakingly work through VisualVM traces, devise hypotheses, try out solutions, etc., the point was reached where I called it a day and rewrote to Java. Not to say that having Java involved is any picnic: each change requires restarting the nREPL session, recompiling everything, reconnecting nrepl.el, reinitializing database connection and Lucene indexes, and so on. The pain is substantial but it feels like a relief nevertheless.

[Korny Sietsma]

Isn't that always the way, though? Build your program in a powerful, expressive language, then profile it, find the critical parts, and optimise them - where possible in the same language, and where that's too ugly/painful, drop down a layer to a lower level language.

I did lots of this in the late '80s - I wrote programs in C, found where they were slow, optimised the C where it was viable, and re-implemented the core bits in assembler. This was great for high performance on a single cpu architecture, but over the years CPUs got faster and CPUs changed - among other things they optimised differently, so speed tweaks for an 80386 were actually slower on a Pentium.

I tend to think clojure is in a similar position - fast enough for the vast majority of things (ymmv of course - depending on what your domain is) and if you meet a situation like this where optimising the clojure becomes too ugly, you can drop down to Java (or indeed C!) - but you lose interoperability with ClojureScript, and hopefully in time language and VM improvements will make this less necessary.

- Korny
--
Sent from my geek device... Spelling mistakes can be blamed on Google

[Mark Engelberg]

On Fri, Feb 22, 2013 at 7:47 PM, Korny Sietsma <ko...@sietsma.com> wrote:

Isn't that always the way, though? Build your program in a powerful, expressive language, then profile it, find the critical parts, and optimise them - where possible in the same language, and where that's too ugly/painful, drop down a layer to a lower level language.

I'd be curious to hear some opinions on this from the Scala community.  I have only been limited by Clojure's performance on one particular program where it was truly necessary to drop down to Java, for the most part performance has been good enough that it has been a non-issue for me.  But for those who regularly need to write high-performance code, isn't that supposed to be Scala's sweet spot?  The promise of Scala is that it allows you to do a reasonable amount of high-level functional coding while also making it convenient to write mutable, Java-like performance code using the same language with the same semantics.  If there are any members of this list who straddle the two worlds of Clojure and Scala, I'd be interested in knowing whether Scala delivers on that promise of being able to write both high-level and performant low-level code, and how much of a difference this makes in practice versus Clojure's approach of expecting the programmer to "drop down" to Java for the best performance.

[Marko Topolnik]

I tend to think clojure is in a similar position - fast enough for the vast majority of things (ymmv of course - depending on what your domain is) and if you meet a situation like this where optimising the clojure becomes too ugly, you can drop down to Java (or indeed C!)

Not quite, I'd say. In Java, and I bet it wasn't very different with C in the '80s, the most natural way to solve a problem is already the most performant, or at least within 50% of that. If you ever need to optimize, it means you are doing something very, very critical indeed, and probably involving native system resources in a way not idiomatically supported by Java's abstractions.

In Clojure this is nohwere close to being true. Idiomatic Clojure is concise, expressive, and slow. Not 50% slower; not 100% slower; more like 100 times slower. Optimized Clojure is like a completely different language. Have you ever experienced the culture shock of opening core.clj? On the other hand, have you ever studied String.java or ArrayList.java? No surprises there; just the basic Java you write every day.

On the other hand, an attitude that you are nevertheless likely to encounter on this grous is "It's not Clojure; it's you. Clojure already has all you need to achieve native performance. If that's not what you are seeing, don't blame it on Clojure". Many posters feel put down by that kind of attitude and the worst part it, it really isn't their fault.

[Marko Topolnik]

From my (admittedly limited) experience with Scala, yes, you can freely use reassignable local vars and write pretty much the same loops as in Java, but on the other hand there are many non-obvious performance pitfalls (like simply using the built-in for comprehension) and the optimized library code is a heavy mess. With Clojure, you open core.clj and stand a good chance of learning something; with Scala, you just stare in total confusion.

[David Nolen]

Lisp programmers know the value of everything and the cost of nothing ;)

[Marko Topolnik]

:)

On the other hand, the Common Lisp movement of the '80s was brimming with the can-do attitude of achieving native performance. From Steele, Gabriel, The Evolution of Lisp:

the two strongest voices—Steele and Gabriel—were feeling their oats over their ability to write a powerful compiler to foil the complexities of Common Lisp. One often heard them, and later Moon, remark that a “sufficiently smart compiler” could solve a particular problem. Pretty soon the core group was quoting this “SSC” argument regularly.

[nicola...@gmail.com]

On Fri, Feb 22, 2013 at 8:01 PM, Marko Topolnik <marko.t...@gmail.com> wrote:

Forgot to mention another hugely important factor: heap-allocated objects spell disaster for CPU cachelines. With today's architectures the difference between a cache hit and a cache miss is like the difference between catching your bus to work and having to walk instead. In our example I would have to be careful to reuse the same deftype instance for all inner loop runs, but then I'd need even more code to make sure the values are reset before entering. The result would be messy, brittle code with higher-level logic scattered between all the housekeeping constructs.

 Wouldn't the object be stack allocated by escape analysis?

[Marko Topolnik]

Stack analysis is quite a brittle mechanism, as far as I'm aware of. As soon as you pass the object to any method, even if private, the object will not be stack-allocated. The way Clojure code is typically written, and the way it is compiled, some method call will almost certainly get involved.

[Geo]

Just wanted to say I am getting a lot out of this discussion.

[Leif]

This may be slightly off topic, but your "longest contiguous common subsequence" problem sounds like the "longest common substring" problem.  Your code uses the dynamic programming solution, which is O(M*N), but there are O(M+N) algorithms that might be faster depending on the length and "alphabet" of your input sequences.

On Monday, February 18, 2013 11:16:51 PM UTC-5, Geo wrote:

Hello,

I am cross-posting my Clojure question from StackOverflow.  I am trying to get an algorithm in Clojure to match Java speed and managed to get the performance to within one order of magnitude and wondering if more is possible. The full question is here:

http://stackoverflow.com/questions/14949705/clojure-performance-for-expensive-algorithms

Thank you.

[Geo]

It is in fact the longest common substring problem, but applied to words in a text rather than characters in a string, hence the algorithm operates on arrays of strings. I am aware of the O(M+N) algorithm, but it involves suffix trees with which I am unfamiliar and don't want to spend the time investigating right now. The DP solution works today and I want to focus on other parts of the project :)

Also the size of the alphabet in this case is the set of all words in a particular language, most commonly English. I am not sure what the implications of that are for the performance of the suffix tree algo.

[bernardH]

On Thursday, February 21, 2013 10:27:11 PM UTC+1, Geo wrote:

Man, this is exactly how I feel after all this tinkering! It was great for learning Clojure a bit more in depth, but in the end I am going to stick with the Java solution. Especially since it's so easy to mix Java and Clojure in the same project! I just specify :java-source-paths ["src/java"] in my project.clj and I just call that one method when I need it and the rest of the project is in Clojure. I think when performance if critical idiomatic Clojure is to just drop down to Java :)

Christophe's second function actually achieves Java speed or very close (within 5-10%), but it's ugly and there's a bit more to my algorithm which would make it even uglier if I were to go that route.

There would be no point in me to argue with you whether Chrispohe's version really is "ugly" or not for you, but I'd like to rephrase it as "hard on the eye". Because I find this "performance oriented Clojure" vs Java fits quiet well in the "easy" vs "simple" mindeset.[*]. Adding Java code in a Clojure project is certainly easy if you happen to already know the language, while no amount of prior experience in idiomatic Clojure will help you in writing perfomance oriented Clojure as it can be a completely new idiom. But I do believe that the resulting code (as a whole, not just the small performance critical bit of code) is simpler with two idioms in one language than with two languages.

FWIW, I, for one, am really glad that Clojure allows us to select precisely which nice tools we want (have to) throw away (persistent data structures, dynamic typing, synchronized) when the need arises. Reminds me of the "don't pay for what you don't use" motto of C++ except done right (i.e. the other way around, because you don't want to pay wrt simplicity rather than performance, cf. "premature optimization…")

Cheers,

Bernard

[*] https://www.youtube.com/watch?v=rI8tNMsozo0

[Geo]

Well I'll just say that my opinion on this matter is not well formed at the moment since this is the first time I have encountered this issue. For now I've stuck with the Java algorithm so I can move on with my project, but I do plan to revisit this at some point. In fact, it may be important for my project to keep it all Clojure.

At the moment I don't find the Clojure solution simple, but again this may simply be to lack of exposure. Have you written a lot of performance optimized Clojure?

[Marko Topolnik]

On Sunday, February 24, 2013 2:50:01 PM UTC+1, bernardH wrote:

FWIW, I, for one, am really glad that Clojure allows us to select precisely which nice tools we want (have to) throw away (persistent data structures, dynamic typing, synchronized) when the need arises. Reminds me of the "don't pay for what you don't use" motto of C++ except done right (i.e. the other way around, because you don't want to pay wrt simplicity rather than performance, cf. "premature optimization…")

Don't you think that the real goal is to have performant idiomatic code? That was certainly the aim of the Common Lisp community of the '80s and, from what I hear, idiomatic Haskell is a performance devil as well. Static typing isn't just about type safety, after all; it's also about performance. When the compiler knows everything about your code, it has a much easier time producing killer machine code.

[Marko Topolnik]

On Sunday, February 24, 2013 4:27:34 PM UTC+1, Geo wrote:

At the moment I don't find the Clojure solution simple, but again this may simply be to lack of exposure. Have you written a lot of performance optimized Clojure?

Yes, that's the catch, isn't it? If we had to write Clojure in the performant idiom all the time, Clojure wouldn't exactly be an appealing language. So, by definition almost, happy Clojure users are inexperienced in writing performant Clojure. There is also something about diminishing returns here: you need to learn a lot of minute particularities just to be able to write that one key function.

[Michael Gardner]

On Feb 24, 2013, at 10:46 , Marko Topolnik <marko.t...@gmail.com> wrote:

> from what I hear, idiomatic Haskell is a performance devil as well

Does this mean very good, or very bad?

On a related note, is there currently any way to get the Clojure compiler to tell you where boxing is occurring, like *warn-on-reflection* does for reflection?

[Andy Fingerhut]

For both Common Lisp and Haskell, the most straightforward code you would typically write for many problems allocates more memory than code specifically written to avoid allocating memory, and if other things are equal (which they often aren't), code that allocates less memory can be faster.

At least for Common Lisp, it can often generate faster code with appropriate type declarations, especially for arithmetic.

Take a look at any of the Common Lisp or Haskell submissions to the Computer Language Benchmarks Game web site, and you will see some programs that are nowhere near what people typically write in those languages, and certainly not what people would write if they weren't concerned with squeezing out the last drop of performance.  Lots of mutable data structures in both, and lots of type declarations in Common Lisp.

    Common Lisp (SBCL) vs Java   http://benchmarksgame.alioth.debian.org/u64q/lisp.php

    Haskell vs. Java   http://benchmarksgame.alioth.debian.org/u64q/haskell.php

Then again, even for C and Java programs on that site, people will do some pretty amazing tricks they wouldn't normally do in those languages, either, e.g. performing I/O in parallel with computation, even when it makes the computation code more complex to give the correct answer.

For Clojure, I'd recommend doing the same thing I'd recommend in just about any language: write the code that occurs to you first to get it correct.  If it is fast enough for your purposes, whatever those are, you are done.  If not, use a profiler to see where most of the time is spent, and then start working on optimizations in the same language if they are worth your time to do so.  If they get too difficult in the original language, dropping down to a lower-level language (e.g. Java, C, assembler) is often a choice you can make, depending upon your deployment restrictions.

Andy

[Marko Topolnik]

Take a look at any of the Common Lisp or Haskell submissions to the Computer Language Benchmarks Game web site, and you will see some programs that are nowhere near what people typically write in those languages, and certainly not what people would write if they weren't concerned with squeezing out the last drop of performance.  Lots of mutable data structures in both, and lots of type declarations in Common Lisp.

Can you really get mutability in Haskell? I thought that was impossible; hence the notorious State monad.

 

Then again, even for C and Java programs on that site, people will do some pretty amazing tricks they wouldn't normally do in those languages, either, e.g. performing I/O in parallel with computation, even when it makes the computation code more complex to give the correct answer.

Yes, I've already got frustrated with that site several times. For example, Scala beats Java by a wide margin on some benchmarks. Turns out it's because it uses JNI to solve the problem with the C bignum library. What relevance could that have?

For Clojure, I'd recommend doing the same thing I'd recommend in just about any language: write the code that occurs to you first to get it correct.  If it is fast enough for your purposes, whatever those are, you are done.  If not, use a profiler to see where most of the time is spent, and then start working on optimizations in the same language if they are worth your time to do so.  If they get too difficult in the original language, dropping down to a lower-level language (e.g. Java, C, assembler) is often a choice you can make, depending upon your deployment restrictions.

The important consideration is, just how many times the idiomatic code is slower? In my book it is a worthwhile goal to improve from 100x slower to 10x slower, even if that outcome still means it's quite a bit slower.

[Marko Topolnik]

> from what I hear, idiomatic Haskell is a performance devil as well

Does this mean very good, or very bad?

It means the same as in "speed devil" :)

 

On a related note, is there currently any way to get the Clojure compiler to tell you where boxing is occurring, like *warn-on-reflection* does for reflection?

It already does that by default, but only for loop bindings. This makes sense because outside tight loops boxing really can't hurt. The performance hit of one box-unbox roundtrip is (my guesstimate) on the order of 10 primitive arithmetic operations. A reflective call is on the order of 1000 ops.

[Andy Fingerhut]

On Feb 24, 2013, at 9:33 AM, Marko Topolnik wrote:

Take a look at any of the Common Lisp or Haskell submissions to the Computer Language Benchmarks Game web site, and you will see some programs that are nowhere near what people typically write in those languages, and certainly not what people would write if they weren't concerned with squeezing out the last drop of performance.  Lots of mutable data structures in both, and lots of type declarations in Common Lisp.

Can you really get mutability in Haskell? I thought that was impossible; hence the notorious State monad.

I'm no Haskell expert, but it doesn't take much Googling to give strong evidence that the answer is "yes, you can get mutability in Haskell".  Search through this Haskell program on the Benchmarks Game site for occurrences of the string "unsafe".

    http://benchmarksgame.alioth.debian.org/u64q/program.php?test=fannkuchredux&lang=ghc&id=4

Then check out the description of those operations on this web page:

    http://hackage.haskell.org/packages/archive/array/0.3.0.2/doc/html/Data-Array-MArray.html

Similarly look for occurrences of "unsafe" in the other fastest Haskell programs.  I found about 4 out of 10 of them use such operations.

Then again, even for C and Java programs on that site, people will do some pretty amazing tricks they wouldn't normally do in those languages, either, e.g. performing I/O in parallel with computation, even when it makes the computation code more complex to give the correct answer.

Yes, I've already got frustrated with that site several times. For example, Scala beats Java by a wide margin on some benchmarks. Turns out it's because it uses JNI to solve the problem with the C bignum library. What relevance could that have?

So ignore the results for pidigits, which is likely the one you saw that uses the libgmp library.  Many people who dismiss the Benchmarks Game site point that out, and I agree: the pidigits benchmark doesn't tell you much, other than whether the program uses the libgmp library or not.

Instead look at the results for other programs that don't pull those tricks, or ignore the site entirely.  If you worry that some people hastily draw the wrong conclusions from the results on that site, such people are being insufficiently critical in their interpretation of the data.

For Clojure, I'd recommend doing the same thing I'd recommend in just about any language: write the code that occurs to you first to get it correct.  If it is fast enough for your purposes, whatever those are, you are done.  If not, use a profiler to see where most of the time is spent, and then start working on optimizations in the same language if they are worth your time to do so.  If they get too difficult in the original language, dropping down to a lower-level language (e.g. Java, C, assembler) is often a choice you can make, depending upon your deployment restrictions.

The important consideration is, just how many times the idiomatic code is slower? In my book it is a worthwhile goal to improve from 100x slower to 10x slower, even if that outcome still means it's quite a bit slower.

In my experience writing Clojure programs for the Benchmarks Game, getting within 10x is fairly easy, and doesn't require much knowledge other than eliminating Clojure reflection, and using a decent algorithm that doesn't throw in an extra factor of N by accident.  It often helps to use mutable Java arrays and Clojure loops, too.

Getting better than 3x of a Java program that pulls out all the optimization tricks is tougher in Clojure.  If you're in that situation, I'd say use Java and simplify your life.

Andy

[Mark Engelberg]

On Sun, Feb 24, 2013 at 5:50 AM, bernardH <un.compte....@gmail.com> wrote:

FWIW, I, for one, am really glad that Clojure allows us to select precisely which nice tools we want (have to) throw away (persistent data structures, dynamic typing, synchronized) when the need arises. Reminds me of the "don't pay for what you don't use" motto of C++ except done right (i.e. the other way around, because you don't want to pay wrt simplicity rather than performance, cf. "premature optimization…")

I think this notion that Clojure lets you select exactly what performance tools you want to pay for when the need arises overlooks one important point -- in Clojure it is not obvious what tools you need to employ to solve a given performance problem.

As I mentioned before, I'm generally happy with Clojure's performance, but the few times I've had performance problems, I ended up rewriting the code at least three different ways in order to try to find the magic combination that would boost performance.  Similarly, every snippet of well-tuned optimized code posted on this list has generally been iteratively tuned by several performance experts, often through a process of educated guesswork and trial and error.  On two of my own performance-bottleneck occasions, I went through a major rewrite to use defrecords rather than hash maps, only to find that it *hurt* my performance.  If a reasonably expert Clojure programmer can't make good predictions about whether a given rewrite will help or hurt performance, that's something that must be taken account in any discussion about how well Clojure lends itself to optimization.

I also think it's not entirely true that Clojure lets you easily choose "what nice features you want to throw away" in pursuit of performance.  In one algorithm involving massive pointer manipulation in a tight loop, even after much experimentation, I was never able to figure out how to jettison enough of Clojure's mutation straitjackets to get anywhere close to Java performance.  I had no choice but to drop down to Java for that algorithm.

Fortunately, dropping down to Java is relatively painless.  But I still wonder whether there might be some benefit to having a "low-level DSL" within Clojure, a mode that lets you choose to write your code in a way where the semantics are closer to the underlying platform.  I haven't used Clojurescript much, but I get the impression that Clojurescript is already a step in that direction, with a simpler story regarding how mutation, arrays, and primitives are translated to the underlying platform, arguably making it easier to get good performance when you need it. 

[Marko Topolnik]

I'm no Haskell expert, but it doesn't take much Googling to give strong evidence that the answer is "yes, you can get mutability in Haskell".  Search through this Haskell program on the Benchmarks Game site for occurrences of the string "unsafe".

I see; quite disgusting :)

 

In my experience writing Clojure programs for the Benchmarks Game, getting within 10x is fairly easy, and doesn't require much knowledge other than eliminating Clojure reflection, and using a decent algorithm that doesn't throw in an extra factor of N by accident.  It often helps to use mutable Java arrays and Clojure loops, too. 

The default Clojure idiom is lazy seqs and higher-order functions. That's what I have in mind when I say 100x slower. Loops, and especially arrays, are a clear sign of optimization; they never come as the most natural way to express a solution.

In languages such as Java there is just one idiom: the performant one. That's why idiomatic Java performs well. In languages such as Clojure, the most expressive idiom, the one the language is appreciated for, is a level of abstraction or two above the performant idiom, so the interesting question becomes, how much performance can be engineered into that level of abstraction. The question of the absolute performance ceiling achievable within the language is also of interest, but only secondary.

Now, my issue with a site such as the Benchmarks Game is that it will never give a fair representation of that concern, and I bet it is exactly this that most visitors of the site come looking for. That is what I meant when I said that Haskell is quite performant: I've heard idiomatic Haskell performs well. I really couldn't care less how it performs with those unsafe monstrosities. Those features are, and should be, reserved for the language's entrails, like the implementation of the IO monad.

[Marko Topolnik]

On Sunday, February 24, 2013 9:15:45 PM UTC+1, puzzler wrote:

As I mentioned before, I'm generally happy with Clojure's performance, but the few times I've had performance problems, I ended up rewriting the code at least three different ways in order to try to find the magic combination that would boost performance.

Lately I've leaned towards going full monty the first time out: stop guessing and optimize everything past the entry point to the critical section. It sounds like more work up front, but in the end it's the "smart" approach that results in more total effort.

 

Fortunately, dropping down to Java is relatively painless.  But I still wonder whether there might be some benefit to having a "low-level DSL" within Clojure, a mode that lets you choose to write your code in a way where the semantics are closer to the underlying platform.

Just one feature would make a huge difference: reassignable locals.

 

I haven't used Clojurescript much, but I get the impression that Clojurescript is already a step in that direction, with a simpler story regarding how mutation, arrays, and primitives are translated to the underlying platform, arguably making it easier to get good performance when you need it.

The gap between Clojure and JavaScript is far less than Java because both are dynamic. I think that plays a big part in why ClojureScript can be more transparent.

 

[Marek Srank]

This might be better in the future by utilizing 'invokedynamic' present since Java 7. See discussion here: https://groups.google.com/d/topic/clojure/1mr0m-9XLoo/discussion

Marek

 

[Ben Mabey]

Yeah, I wish the Benchmarks allowed for idiomatic submissions and finely tuned submissions.  That would allow you to get some sort of an idea how performant the dominant idiom is.  Along those lines this older post did an interesting analysis on the benchmark solutions where it explored the tension that exists between expressiveness and performance across the various languages:

http://blog.gmarceau.qc.ca/2009/05/speed-size-and-dependability-of.html

[Aria Haghighi]

I have a solution (gist here https://gist.github.com/aria42/5026109, key bits pasted below). It's pretty short (15 lines) and readable (I think) and only 50% slower than the Java version on my machine (averaging over 25 runs of your benchmark function). 

Generally, I've found it's really easy when you just translate Java code like this into Clojure, the Clojure will read worse than the original Java; to boot it will also be  slower! And not to be insulting, but I think the other Clojure solutions I saw in this thread seem to have this property. You usually have to pull out some abstraction in order to regain on the readability and concentrate on performance there. Here, I think it's a macro you'll probably use all over the place, arr-max, which will find the largest value of an expression looping over an array's index and values. Then lcs is just nested uses of arr-max that I think is pretty reasonable. The thing which clutters the remaining code are the prev/cur swapping which I don't have a slick way of handling.   

(defmacro arr-max 
  "return maximum value of `expr` over the indices
   and values of array `arr`, where `idx-symb` and `val-symb`
   are bound to index and values of `arr`"
  [arr idx-symb val-symb expr]
  `(let [arr# ~arr
         n# (alength arr#)]
     (loop [~idx-symb 0 max-val# java.lang.Long/MIN_VALUE]
       (if (= ~idx-symb n#)
         max-val#
         (let [~val-symb (aget arr# ~idx-symb)
               val# ~expr]
           (recur (inc ~idx-symb)
                  (if (> val# max-val#)
                    val# max-val#)))))))
 
(defn lcs [^objects a1 ^objects a2]
  (let [prev-ref (atom (long-array (inc (alength a2))))        
        cur-ref (atom (long-array (inc (alength a2))))]
    (arr-max a1 i v1
       (let [^longs prev @prev-ref
             ^longs cur @cur-ref
             max-len (arr-max a2 j v2
                         (let [match-len (if (.equals v1 v2)
                                           (inc (aget prev j))
                                           0)]
                           (aset cur (inc j) match-len)
                           match-len))]
         (reset! prev-ref cur)
         (reset! cur-ref prev)
         (long max-len)))))
 

[Isaac Gouy]

On Sunday, February 24, 2013 9:33:52 AM UTC-8, Marko Topolnik wrote:

For example, Scala beats Java by a wide margin on some benchmarks. Turns out it's because it uses JNI to solve the problem with the C bignum library.

Turns out the benchmarks game website shows both Scala programs and Java programs that use GMP via JNI --


http://benchmarksgame.alioth.debian.org/u32/program.php?test=pidigits&lang=java&id=2

http://benchmarksgame.alioth.debian.org/u32/program.php?test=pidigits&lang=scala&id=4

[Isaac Gouy]

On Sunday, February 24, 2013 1:45:33 PM UTC-8, Ben Mabey wrote:

Yeah, I wish the Benchmarks allowed for idiomatic submissions and finely tuned submissions.

So you wish the benchmarks game website would show, for example, both pi-digits programs that use BigInteger and pi-digits programs that use the highly optimised GMP library?

http://benchmarksgame.alioth.debian.org/u32/program.php?test=pidigits&lang=java&id=1

http://benchmarksgame.alioth.debian.org/u32/program.php?test=pidigits&lang=java&id=2


 

Along those lines this older post did an interesting analysis on the benchmark solutions where it explored the tension that exists between expressiveness and performance across the various languages:

http://blog.gmarceau.qc.ca/2009/05/speed-size-and-dependability-of.html

Where do you think Guillaume Marceau took the data from?

http://benchmarksgame.alioth.debian.org/u32/code-used-time-used-shapes.php

[Geo]

This is pretty neat. Thanks!

Yeah the swapping of prev and curr seems to be a stumbling block.

[bernardH]

Hi,

Nice solution, but don't we need to distinguish between the array types ? (cf. inline comment below )

Cheers,

B.

On Monday, February 25, 2013 12:08:39 AM UTC+1, Aria Haghighi wrote:

[…] Here, I think it's a macro you'll probably use all over the place, arr-max, which will find the largest value of an expression looping over an array's index and values. Then lcs is just nested uses of arr-max that I think is pretty reasonable. The thing which clutters the remaining code are the prev/cur swapping which I don't have a slick way of handling.   

(defmacro arr-max 
  "return maximum value of `expr` over the indices
   and values of array `arr`, where `idx-symb` and `val-symb`
   are bound to index and values of `arr`"
  [arr idx-symb val-symb expr]
  `(let [arr# ~arr
         n# (alength arr#)]
     (loop [~idx-symb 0 max-val# java.lang.Long/MIN_VALUE]

Shouldn't we select java.lang.Double/NEGATIVE_INFINITY for arrays of Doubles ?

[Marko Topolnik]

This is a great analysis, thanks for the link; shame it's so old.

[Ben Mabey]

As Issac pointed out, here are some very recent graphs (including Clojure):

http://benchmarksgame.alioth.debian.org/u32/code-used-time-used-shapes.php

--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Marko Topolnik]

I see; didn't notice that one. Again, only the fastest entries are shown. It appears that the same is the case with Marceau's graphs; he just didn't state that explicitly.

Things don't look very rosy for Clojure: it turns out to be about as verbose as Java and significantly slower (this confirms my experience; slightly slower than regular Java code, significantly slower than highly optimized Java). If idiomatic Clojure was used, it would move it to the left and upwards; Clojure would hang out with JRuby.

Anyway, it would be really great to see such a comparison chart, but only with idiomatic code involved. This way I don't have a clue what to make of Haskell, for example.

[Andy Fingerhut]

I've got a github repo with submissions for the Benchmarks Game web site for Java and Clojure, with several different Clojure programs for most problems:

    https://github.com/jafingerhut/clojure-benchmarks

If people would like to submit what they consider idiomatic Clojure programs for any of these problems, feel free to send them to me, and I can include them, not only in the repo but also in some benchmark results that I am planning to publish at the link below some day when I have them ready, under "whole program benchmarks":

    http://jafingerhut.github.com/clojure-benchmarks-results/Clojure-benchmarks.html

If you do submit a program, I'd ask you to consider submitting a version that you wrote first and got working correctly, before even looking at any kinds of optimizations at all, as well as one you consider to be a mild optimization pass over that first version, and yet still "idiomatic".

Andy

[Jules]

Clojure code should in principle be possible to execute very fast when using the same data structures. Clojure is much better behaved than languages like Ruby and Javascript from a compiler perspective. See for example the Stalin scheme compiler. It runs well written Scheme at almost C speed (sometimes even faster), without type annotations.

[David Nolen]

On Tue, Feb 26, 2013 at 3:50 PM, Marko Topolnik <marko.t...@gmail.com> wrote:

Things don't look very rosy for Clojure: it turns out to be about as verbose as Java and significantly slower (this confirms my experience; slightly slower than regular Java code, significantly slower than highly optimized Java). If idiomatic Clojure was used, it would move it to the left and upwards; Clojure would hang out with JRuby.

Hang out with JRuby? Seriously?

http://benchmarksgame.alioth.debian.org/u64q/benchmark.php?test=all&lang=clojure&lang2=jruby

Having written two test.benchmark entries which compare quite favorably to Java, I think the current crop of Alioth benchmarks could use a bit of improvement both in terms of code quality and performance. There's no reason that every single Clojure Alioth benchmark should not be near competitive with the corresponding Java Alioth benchmark in terms of time, memory, and code size except for lack of community interest.

Probably because none of these things will ever reveal Clojure performance for non-trivial applications.

It's much more convincing for example when Prismatic engineers say they can happily achieve Java performance without verbosity.

http://blog.getprismatic.com/blog/2012/4/5/software-engineering-at-prismatic.html

David

[Softaddicts]

I you attempt to mimic Java or C in some narrow linear
compute bound algorithm, I agree that the resulting code is quite ugly, not idiomatic
on top of having performance issues.

Lucky for us not all the problems are bounded like this.

I have been following this thread from the beginning and I cannot understand
why people are hammering at performance issues we were tackling using
machine code directly in the 80s or by carefully inspecting compiler generated
code (by Fortran, C, ...) to avoid costly instructions. We would thunk down
to machine code when required.

There are no wins on all fronts at the same time. We are happy here to get
wall clock performance boosts without added complexity
because the nature of our business domain allows us to parallelize processing.

Why insist on getting Clojure to be at par with languages that may offer a performance
boost on narrow problems at the expense of making parallel processing and code
in general more complex everywhere else ?

I do not say that these benchmarks are futile, write idiomatic code, use available
optimizations (type hints and cie) and start the baseline from there to improve the
compiler.

Improvements to the compiler will benefit everyone. Improvements to reach
similar perf levels with these benchmarks by twisting the code are pretty narrow goals
and not many can benefit from it.

100% cpu usage in the whole lifetime of your app ?
Without db or file persistence ? Without network I/O s ? All of which induce latencies ?

It's similar to me to weater simulations. These days they have enough data to
predict weather with a great accuracy... three days after the fact.
Why ? They have a compute bound problem that they cannot address other than
sequentialy in some critical steps and too much data to process if they want to improve
the accuracy of their simulations.

Using Clojure in these critical steps would be futile until new parallel algorithms
appear. Parallel algorithms to some of their performance problems do not exist
yet. The maths to do so have not been invented yet. Oups...

If anyone uses these benchmarks as their main criteria to choose a language
without considering first their problem domain, well they need to get their brain fixed.

I considered my domain problem before embracing Clojure and pushed back the
performance issues later because I knew I could always cheat with parallel processing
and lower the source code burden by getting more expressivenes.

The gains are in the sum of all parts not in a single narrowly defined one.


Luc P.

> I see; didn't notice that one. Again, only the fastest entries are shown.
> It appears that the same is the case with Marceau's graphs; he just didn't
> state that explicitly.
>
> Things don't look very rosy for Clojure: it turns out to be about as
> verbose as Java and significantly slower (this confirms my experience;

> slightly slower than *regular* Java code, significantly slower than highly

> optimized Java). If idiomatic Clojure was used, it would move it to the
> left and upwards; Clojure would hang out with JRuby.
>
> Anyway, it would be really great to see such a comparison chart, but only
> with idiomatic code involved. This way I don't have a clue what to make of
> Haskell, for example.
>
>
> On Tuesday, February 26, 2013 6:30:55 PM UTC+1, Ben Mabey wrote:
> >
> > As Issac pointed out, here are some very recent graphs (including
> > Clojure):
> >
> > http://benchmarksgame.alioth.debian.org/u32/code-used-time-used-shapes.php
> >
> > On 2/26/13 2:35 AM, Marko Topolnik wrote:
> >
> > This is a great analysis, thanks for the link; shame it's so old.
> >
> > On Sunday, February 24, 2013 10:45:33 PM UTC+1, Ben Mabey wrote:
> >>
> >>
> >> Yeah, I wish the Benchmarks allowed for idiomatic submissions and finely
> >> tuned submissions. That would allow you to get some sort of an idea how
> >> performant the dominant idiom is. Along those lines this older post did an
> >> interesting analysis on the benchmark solutions where it explored the
> >> tension that exists between expressiveness and performance across the
> >> various languages:
> >>
> >> http://blog.gmarceau.qc.ca/2009/05/speed-size-and-dependability-of.html
> >>
> >>
> >>
> >> --
> > --
> > You received this message because you are subscribed to the Google
> > Groups "Clojure" group.

> > To post to this group, send email to clo...@googlegroups.com <javascript:>

> > Note that posts from new members are moderated - please be patient with
> > your first post.
> > To unsubscribe from this group, send email to

> > clojure+u...@googlegroups.com <javascript:>

> > For more options, visit this group at
> > http://groups.google.com/group/clojure?hl=en
> > ---
> > You received this message because you are subscribed to the Google Groups
> > "Clojure" group.
> > To unsubscribe from this group and stop receiving emails from it, send an

> > email to clojure+u...@googlegroups.com <javascript:>.

> > For more options, visit https://groups.google.com/groups/opt_out.
> >
> >
> >
> >
> >
>
> --
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
> ---
> You received this message because you are subscribed to the Google Groups "Clojure" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to clojure+u...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>

--
Softaddicts<lprefo...@softaddicts.ca> sent by ibisMail from my ipad!

[Isaac Gouy]

On Tuesday, February 26, 2013 12:50:17 PM UTC-8, Marko Topolnik wrote:

Again, only the fastest entries are shown.

True, except for the special-case included to show that programs can be made slower (and sometimes more concise) -- the shortest C++ programs.

If idiomatic Clojure was used...

The problem, of course, is that: the code one-person considers to be idiomatic; another person considers to be idiotic, naïve.

[Marko Topolnik]

On Wednesday, February 27, 2013 12:53:14 AM UTC+1, Luc wrote:

Why insist on getting Clojure to be at par with languages that may offer a performance
boost on narrow problems at the expense of making parallel processing and code
in general more complex everywhere else ?

This doesn't represent anyone's view as expressed in this thread. The goal is better (not best) performance without compromising the good features that make Clojure a joy that it is. The goal is to let people enjoy the nice features in as much of the codebase as possible.

[Marko Topolnik]

On Wednesday, February 27, 2013 5:19:20 AM UTC+1, Isaac Gouy wrote:

If idiomatic Clojure was used...

The problem, of course, is that: the code one-person considers to be idiomatic; another person considers to be idiotic, naïve.

 

Not really. Take Stuart Halloway's opening example in the section entitled Why Clojure?

(defn blank? [s] (every? #(Character/isWhitespace %) s))

Have you ever wondered about its performance? Here you go:

user> (time (dotimes [_ 10000] (blank? "                                             ")))

"Elapsed time: 3887.578 msecs"

Now imagine Stuart's first concern was demonstrating performant Clojure:

(defn blank? [^String s]

  (if (or (nil? s) (= (.length s) 0))

    true

    (loop [i 0]

      (if (< i (.length s))

        (if (Character/isWhitespace (.charAt s i))

          (recur (inc i))

          false)

        true))))

user> (time (dotimes [_ 10000] (blank2? "                                             ")))

"Elapsed time: 4.884 msecs"

Yes, it's eight hundred times faster. But, would anyone care for that? Why bother learning yet another JVM language, with open parens awkwardly transposed and an inconvenient loop-recur construct? This is clearly not idiomatic Clojure and that is not a subjective appraisal.

-Marko

[Marko Topolnik]

(defn blank? [s] (every? #(Character/isWhitespace %) s))

Have you ever wondered about its performance? Here you go:

user> (time (dotimes [_ 10000] (blank? "                                             ")))

"Elapsed time: 3887.578 msecs"

To give a more complete picture, this version

(defn blank? [s] (every? #(Character/isWhitespace ^char %) s)) 

is only six times slower than the expanded version, and keeping an eye on reflection warnings is not such a drag. So, if it could be demonstrated that in general the properly type-hinted, but otherwise idiomatic Clojure is not more than 10 times slower than idiomatic Java, I'd consider that at least a good starting point.

-Marko

[Christophe Grand]

Now that reduce can be short-circuited, redifining every?, some and al on top of it would yield some interesting gains:

(defn revery? [pred coll]

  (reduce (fn [t x]

            (if (pred x)

              t

              (reduced false))) true coll))

(defn rblank? [s] (revery? #(Character/isWhitespace ^char %) s))

(defn blank? [s] (every? #(Character/isWhitespace ^char %) s)) 

=> (dotimes [_ 10]

     (time (dotimes [_ 100000] (blank? "                                             "))))

"Elapsed time: 515.371 msecs"

"Elapsed time: 500.408 msecs"

"Elapsed time: 507.646 msecs"

"Elapsed time: 644.074 msecs"

"Elapsed time: 529.717 msecs"

"Elapsed time: 482.813 msecs"

"Elapsed time: 557.563 msecs"

"Elapsed time: 486.573 msecs"

"Elapsed time: 493.636 msecs"

"Elapsed time: 481.357 msecs"

nil

=> (dotimes [_ 10]

     (time (dotimes [_ 100000] (rblank? "                                             "))))

"Elapsed time: 227.692 msecs"

"Elapsed time: 99.937 msecs"

"Elapsed time: 95.922 msecs"

"Elapsed time: 91.193 msecs"

"Elapsed time: 90.794 msecs"

"Elapsed time: 94.765 msecs"

"Elapsed time: 89.842 msecs"

"Elapsed time: 120.551 msecs"

"Elapsed time: 90.843 msecs"

"Elapsed time: 93.523 msecs"

nil

Christophe

[Marko Topolnik]

On Wednesday, February 27, 2013 10:59:33 AM UTC+1, Christophe Grand wrote:

Now that reduce can be short-circuited, redifining every?, some and al on top of it would yield some interesting gains:

(defn revery? [pred coll]

  (reduce (fn [t x]

            (if (pred x)

              t

              (reduced false))) true coll))

(defn rblank? [s] (revery? #(Character/isWhitespace ^char %) s))

(defn blank? [s] (every? #(Character/isWhitespace ^char %) s)) 

Christophe

These are very interesting results because they show that the current, supposedly "optimized" implementation involving recur is apparently 5x slower than plain reduce (the short-circuiting aspect doesn't play a role in this example).

-Marko

[Meikel Brandmeyer (kotarak)]

Hi,

the recur is not for optimisation but for short-circuiting so that every? kind of works like and. Stoppable reduce allows now to exploit the internal reduce for strings while still keeping the short-circuiting of every?.

Kind regards

Meikel

[Christophe Grand]

Indeed not in this example (all chars are blank and the string is short): but you need short-circuiting to replace seq-based every? by reduce-based every?.

reduce is special-cased for Strings (well for StringSeq to be precise). I wouldn't call optimized the seq-idiomatic version which allocates one Cons at each iteration step.

Using reduce allows (potentially) to avoid the seq allocations (and reducers allow that on a whole transformation pipeline, without having to (manually) merge everything in the reducing fn).

Having a short-circuiting reduce allows for reduce-idiomatic versions of functions that would have been too eager otherwise. 

--
On Clojure http://clj-me.cgrand.net/
Clojure Programming http://clojurebook.com
Training, Consulting & Contracting http://lambdanext.eu/

[Softaddicts]

Well then lets stop trying to twist the code further. Commenting that Clojure "looses"
in these benchmarks or is pushed in the same backyard than ruby is counter productive.

What I have seen so far is pulling toward extreme contorsions to achieve
better performance at the expense of code readability.

Chritophe's example is how much far I would go while tuning the code to get more
speed out of it.

Beyond this let's open the hood and look at the internals then...


Luc

> On Wednesday, February 27, 2013 12:53:14 AM UTC+1, Luc wrote:
>
> >
> > Why insist on getting Clojure to be at par with languages that may offer a
> > performance
> > boost on narrow problems at the expense of making parallel processing and
> > code
> > in general more complex everywhere else ?
> >
>
> This doesn't represent anyone's view as expressed in this thread. The goal

> is *better* (not *best*) performance *without* compromising the good

> features that make Clojure a joy that it is. The goal is to let people
> enjoy the nice features in as much of the codebase as possible.
>

[Marko Topolnik]

In your specific case, where you want every last inch of performance, it is acceptable that you will need to use the optimized idiom. However, if your overall code did anything else besides banging hard against your algorithm, a performance say 5 times worse than Java may soon become acceptable. In my case, for example, I managed to get the time low enough to be drowned out by index reading times inside Lucene. If I could have achieved that without involving arrays, loops, and defrecords, I wouldn't have a reason to complain.

[Marko Topolnik]

On Wednesday, February 27, 2013 12:48:13 AM UTC+1, David Nolen wrote:

Hang out with JRuby? Seriously?

http://benchmarksgame.alioth.debian.org/u64q/benchmark.php?test=all&lang=clojure&lang2=jruby

Well, all the code-size bars are above the baseline :) Let's see how it fares when they disappear or go below it.

 

Probably because none of these things will ever reveal Clojure performance for non-trivial applications.

Overall the performance is great, in my experience, due to low-ceremony architecture of the whole app. Clojure is great at reducing incidental complexity and this is relevant to more than just code aesthetics. Most of the time performance is not about computing power, anyway; that shouldn't say that computing performance is irrelevant. A great language ("the right thing") is strong at all fronts.

 

-Marko

[Softaddicts]

I disagree with your last statement. If you look backward, you will find that most
languages were created with one or two strong influential ideas at the start.

Many of them died of not being extendable to meet new concepts
(Snobol, Algol, Simula, APL, ...)

It did not prevent many of them to be successfull in terms of popularity for a number of
years or decades (Fortran, Cobol, Pascal, Basic, C/C++ are in the top ranks here).

They were not strong on all fronts on the contrary. Just look at Cobol...
but there are a few hundred millions of Cobol code lines out there driving your bank
account. We are even hearing about Cobol rejuvenation from IBM.

They were a form of compromise. Clojure will not escape this route. Using the JVM
is a compromise. You rely on the JVM and not bare metal. This cuts you out
from certain forms of optimizations while on the other hand you are isolated
from the bare metal and get access to a richer ecosystem.

Relying on JavaScript is even a bigger compromise (no threads, no control over
the container, ...) but it gets you everywhere.

There's no magic. You cannot win on all fronts.

Luc P.

> --
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
> ---
> You received this message because you are subscribed to the Google Groups "Clojure" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to clojure+u...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>

[Isaac Gouy]

On Wednesday, February 27, 2013 1:13:10 AM UTC-8, Marko Topolnik wrote:

On Wednesday, February 27, 2013 5:19:20 AM UTC+1, Isaac Gouy wrote:

If idiomatic Clojure was used...

The problem, of course, is that: the code one-person considers to be idiomatic; another person considers to be idiotic, naïve.

 

Not really. Take Stuart Halloway's opening example in the section entitled Why Clojure?

(defn blank? [s] (every? #(Character/isWhitespace %) s))

Have you ever wondered about its performance?

No. Why would I wonder about the performance of a one line code snippet that was written without concern for performance?

[Marko Topolnik]

On Wednesday, February 27, 2013 5:17:16 PM UTC+1, Luc wrote:

There's no magic. You cannot win on all fronts.

You defeatist, you :) I'm just trying to represent the enthusiastic perspective where "if it could be better, it must be better". In many respects Clojure already embodies exactly that attitude, that's why we all love it. Maybe some people here feel defensive about the criticism of Clojure's performance from those who have nowhere near the complete picture; that can't be helped, I guess, it's the inescapable nature of such public communication. Still, the complacent tone that often comes out rubs me the wrong way.

Don't get me wrong; over the years I have progressed from being in love with Clojure towards it becoming my home sweet home; in your home you take all great things for granted and spend time worrying about those little details that could be made better.

-Marko

[Marko Topolnik]

On Wednesday, February 27, 2013 5:59:25 PM UTC+1, Isaac Gouy wrote:

(defn blank? [s] (every? #(Character/isWhitespace %) s))

Have you ever wondered about its performance?

No. Why would I wonder about the performance of a one line code snippet that was written without concern for performance?

So is that piece of code, by your classification, "idiotic, naïve"? 

[Timothy Baldridge]

Luc makes a good point. And that's one thing that I love about Clojure. It is possible to have (more or less) the same language on different platforms with different trade-offs, with little effort. Just look at the three examples we have now: 

Clojure - Pretty awesome performance + interop with all of JVM. Tradeoff: JVM and the fact of having to install a runtime, etc. 

ClojureScript - Runs anywhere JS is supported these days. Tradeoff: Single-threaded, source-to-source compilation. Whole program optimization for best performance. 

ClojureCLR - Runs on .NET. Better interop with Windows. Tradeoff: Performance (compared to JVM). 


If we extend this analogy to Stalin Lisp (as mentioned above) we get the following:

Stalin - Almost magical performance numbers. Tradeoff: whole program optimizations. Once a binary is compiled, you can't extend that code with more lisp code without re-compilation. And the compilation speed isn't anything to boast about (from what I've heard). 

Timothy Baldridge

-Marko

--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--
“One of the main causes of the fall of the Roman Empire was that–lacking zero–they had no way to indicate successful termination of their C programs.”
(Robert Firth)

[Timothy Baldridge]

And by "with little effort" I mean "with little effort compared to porting other languages to different platforms". 

Given 8 hour work days a single man can hack out Clojure on almost any platform in a few months. That's quite impressive considering how hard it would be to do the same for Ruby/Python/PHP, etc. 

Timothy

[Andy Fingerhut]

I think that Isaac's point in which he used those adjectives is that reasonable people can disagree what the most idiomatic code is for solving a problem that takes over 20 lines of code (and often even if it takes fewer lines of code than that).  When you throw unreasonable people into the mix, the disagreements can only increase.

If you wanted to create a collection of idiomatic Clojure programs for solving a particular set of problems, e.g. the Benchmarks Game problems, as soon as more than one person submitted a program and/or reviewed a program, there could arise arguments over which ones are idiomatic and which are not.

If one person is maintaining the collection, they can make judgement calls on this, and/or keep multiple different submissions around to solve the same problem as all equally idiomatic, even though they use different code constructs to do it.

Andy

[Marko Topolnik]

On Wednesday, February 27, 2013 6:28:03 PM UTC+1, Andy Fingerhut wrote:

If you wanted to create a collection of idiomatic Clojure programs for solving a particular set of problems, e.g. the Benchmarks Game problems, as soon as more than one person submitted a program and/or reviewed a program, there could arise arguments over which ones are idiomatic and which are not.

If one person is maintaining the collection, they can make judgement calls on this, and/or keep multiple different submissions around to solve the same problem as all equally idiomatic, even though they use different code constructs to do it.

 

There is much truth in this; however, I bet that all those programs could in fact be considered idomatic from a wider perspective. One guy prefers (reduce...assoc) where another prefers (into {}...map...) and that's OK. However, if someone comes along with (let [m (HashMap.)] (loop []...(recur (.put m ...))) claiming that is in fact idomatic, he's just being unreasonable---by everyone's agreement. Yes, in the final analysis there will always be a fine dividing line over which everyone involved will love to disagree, but that's a lesser concern.

-Marko

[Isaac Gouy]

On Wednesday, February 27, 2013 9:48:15 AM UTC-8, Marko Topolnik wrote:

However, if someone comes along with (let [m (HashMap.)] (loop []...(recur (.put m ...))) claiming that is in fact idomatic, he's just being unreasonable---by everyone's agreement.

You don't think there are fast-code idioms?

[Ben Mabey]

Because that one line of code is representative of the majority of clojure functions (i.e. idiomatic clojure using core functions against seqs).

-Ben

[Jon Seltzer]

I beg to differ. You can't separate an assessment of idiomaticity
from the specific problem domain. *That* is true no matter what the
language.

On Feb 27, 9:48 am, Marko Topolnik <marko.topol...@gmail.com> wrote:
> On Wednesday, February 27, 2013 6:28:03 PM UTC+1, Andy Fingerhut wrote:
>
> If you wanted to create a collection of idiomatic Clojure programs for
>
> > solving a particular set of problems, e.g. the Benchmarks Game problems, as
> > soon as more than one person submitted a program and/or reviewed a program,
> > there could arise arguments over which ones are idiomatic and which are not.
>
> > If one person is maintaining the collection, they can make judgement calls
> > on this, and/or keep multiple different submissions around to solve the
> > same problem as all equally idiomatic, even though they use different code
> > constructs to do it.
>
> There is much truth in this; however, I bet that all those programs could

> in fact be considered idomatic from a wider perspective. One guy prefers *
> (reduce...assoc)* where another prefers *(into {}...map...)* and that's OK.
> However, if someone comes along with *(let [m (HashMap.)] (loop []...(recur
> (.put m ...)))* claiming that is in fact idomatic, he's just being

[Geo]

I didn't know reduce could be short circuited! I assume from the code below this is done calling the function reduced? Is this in Clojure 1.5 only and is where is this documented?

[Marko Topolnik]

It's in the official API documentation. Yes, it's new with Clojure 1.5.

[Isaac Gouy]

Is that one line of code representative of the majority of Closure programs?

Perhaps function composition has implications for program performance.