4 ms·
persistent datastructures are much less efficient to iterate through As far as Clojure iteration is concerned, Vectors (immutable, persistent) are actually fas
by aphyr 13y ago
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.
- prospero 13y agoFor 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-model-for-collection-processing.html http://clojure.com/blog/2012/05/08/reducers-a-library-and-mo... EDIT: and my response is just a little redundant now
- dragandj 13y agoAre 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.
- gtrak 13y agothere 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/5b281880571573c5917781de932ce4789f18daec https://github.com/clojure/clojure/commit/5b281880571573c591... It was a pretty transparent change.