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.http://clojure.com/blog/2012/05/08/reducers-a-library-and-mo...
EDIT: and my response is just a little redundant now
It was a pretty transparent change.
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...
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.
See for instance, the "some" implementation: https://github.com/clojure/clojure/blob/c6756a8bab137128c811...
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)
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.