News for hackers. Stuff that matters.
Re:Clojure Tradeoffs by fiatmoney on Wednesday June 26, 2013 @12:45AM (#5944251)
I'll give a real tradeoff - persistent datastructures are much less efficient to iterate through, since they usually involve a) returning "mutated" copies at each iteration (not as bad as it sounds due to structural sharing, but much more expensive than incrementing an index) and b) lots of pointer following & manipulation.

Also, the STM has an interesting intersection with garbage collection depending on your access patterns. Returning modified copies & throwing away references to the old one, rather than mutating, can increase pressure on the GC since you end up with more transient objects. Especially if you're "mutating" objects that all end up living in the tenured generation.

Re:Clojure Tradeoffs by aphyr on Wednesday June 26, 2013 @02:05AM (#5944438)
persistent datastructures are much less efficient to iterate through

As far as Clojure iteration is concerned, Vectors (immutable, persistent) are actually faster than ArrayLists (mutable, unsynchronized). Criterium reports:

  (let [v (vec (range 10000))] (bench (reduce + v)))
  
  Evaluation count : 95340 in 60 samples of 1589 calls.
               Execution time mean : 642.508722 µs
      Execution time std-deviation : 5.452816 µs
     Execution time lower quantile : 636.188082 µs ( 2.5%)
     Execution time upper quantile : 658.023220 µs (97.5%)

  (let [a (java.util.ArrayList. (range 10000))]
    (bench (reduce + a)))

  Evaluation count : 77640 in 60 samples of 1294 calls.
               Execution time mean : 739.523157 µs
      Execution time std-deviation : 6.064187 µs
     Execution time lower quantile : 730.818794 µs ( 2.5%)
     Execution time upper quantile : 751.968107 µs (97.5%)
Amusingly, using iterators directly instead of reduce speeds up ArrayLists (since there's no need to go through seq, I think), and slows down Vectors to the same speed:

  (defn iterator-sum
    [^java.util.Iterator i]
    (loop [sum 0]
      (if (.hasNext i)
        (recur (+ sum (.next i)))
        sum)))
  
  (defn iterable-sum
    [^Iterable i]
    (iterator-sum (.iterator i)))
  
  (let [v (vec (range 10000))]
    (bench (iterable-sum v))))
  Execution time mean : 682.147166 µs

  (let [a (java.util.ArrayList. (range 10000))]
    (bench (iterable-sum a))))
  Execution time mean : 683.351808 µs
After conferring with ztellman, I suspect this is due to Clojure's InternalReduce avoiding extra iterator allocations over vectors, since it can recur f directly over the internal array at each leaf node.
Re:Clojure Tradeoffs by prospero on Wednesday June 26, 2013 @02:29AM (#5944477)
For those of you playing along at home, this is because of Clojure's reducers framework [1]. If we were to extend 'clojure.core.protocols.CollReduce' to ArrayList, we'd get similar performance, but the important point is that efficient iteration across immutable collections is very much possible.

http://clojure.com/blog/2012/05/08/reducers-a-library-and-mo...

EDIT: and my response is just a little redundant now

Re:Clojure Tradeoffs by dragandj on Wednesday June 26, 2013 @04:41AM (#5944817)
Are you sure? Reducers framework has its own version of major functions (map, reduce, etc.) and has to be called explicitly by use or require. Last time I checked, in version 1.5, if you just call normal reduce, it does not use reducers framework.
Re:Clojure Tradeoffs by gtrak on Wednesday June 26, 2013 @10:01AM (#5946055)
there were changes to the core data structures in order to support reducers, namely the addition of polymorphic reduction by the collection. See: https://github.com/clojure/clojure/commit/5b281880571573c591...

It was a pretty transparent change.

Re:Clojure Tradeoffs by gtrak on Wednesday June 26, 2013 @01:01AM (#5944290)
Yes, having to understand the details and implications of clojure's compilation was definitely painful, but the implementing code is accessible. There's always going to be some performance bottlenecks, I guess I'm more concerned with how hard are they to identify and overcome than they might have been having coded stuff up in pure java from the start? Or, once you're committed to a design, say refs and STM, and you hit such a problem, is it difficult to change course?
Re:Clojure Tradeoffs by kleiba on Wednesday June 26, 2013 @01:07AM (#5944307)
Why does the iteration have to return copies? Can it not just return the object itself? Or are you talking about return-by-value versus return-by-reference (Java does the latter)?
Re:Clojure Tradeoffs by tel on Wednesday June 26, 2013 @01:14AM (#5944329)
Immutability means that if you're "modifying" the structure you must actually be "making a new copy with a small change". Structural sharing means that usually only the small change itself gets new allocation, but it's still more pointer-chasing than a continuous memory map.

Lots of algorithms don't work with this kind of copying semantics, but you have all of Purely Functional Data Structures [1] to help.

[1] http://www.amazon.com/Purely-Functional-Structures-Chris-Oka...

Re:Clojure Tradeoffs by kleiba on Wednesday June 26, 2013 @01:46AM (#5944400)
Fair enough, but I wasn't talking about modification, I asked about iteration.
Re:Clojure Tradeoffs by cgag on Wednesday June 26, 2013 @02:04AM (#5944435)
Just iterating doesn't make any copies. Replace iterating over with modifying.

Efficient immmutable data structures are easily one of Clojure best features. Easiest trade off ever (though the actual hit to performance isn't that bad) imo.

Re:Clojure Tradeoffs by dragandj on Wednesday June 26, 2013 @04:44AM (#5944830)
Not only that, but you can also make a persistent structure locally transient for the duration of the (modifying) iteration, so in lots of cases you do not have to pay the persistence penalty.
Re:Clojure Tradeoffs by tel on Wednesday June 26, 2013 @02:35AM (#5944499)
Oh, true—I jumped his point
Re:Clojure Tradeoffs by aphyr on Wednesday June 26, 2013 @02:09AM (#5944447)
It doesn't. I suspect the parent was thinking of mutation.
Re:Clojure Tradeoffs by fiatmoney on Wednesday June 26, 2013 @12:51PM (#5947226)
I should clarify: "iteration" is a bit of a fuzzy concept in Clojure that encompasses things like "for", "reduce", "some", "map", etc., some of which have differing implementations under the hood. If you're leveraging InternalReduce you're likely to be pretty darn efficient, especially because under the hood it's allowed to multithread with Java fork/join (which you would have to implement much more verbosely if you wanted to use it with an ArrayList). But in a lot of cases, you scan through a collection by taking the first element, then the first of the rest (which is generated by returning a "modified" copy of the original collection), etc.

See for instance, the "some" implementation: https://github.com/clojure/clojure/blob/c6756a8bab137128c811...

Re:Clojure Tradeoffs by masklinn on Wednesday June 26, 2013 @04:04AM (#5944739)
> I'll give a real tradeoff - persistent datastructures are much less efficient to iterate through

Pretty sure you mean "mutation", because none of your criticisms makes sense for iteration of persistent datastructures in general (the former one makes no sense at all, the latter one may make sense in tree-based persistent datastructures which will have higher constant factors due to pointer chasing)

Re:Clojure Tradeoffs by Mikeb85 on Wednesday June 26, 2013 @08:57AM (#5945679)
If you're constantly returning and saving modified immutable data structures you're doing it wrong. Clojure has mutable data, you use them when you need them, and don't use them when you don't.