News for hackers. Stuff that matters.
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.