Comment made by: jdevuyst
Hm. I guess the lazy sequence does lead to a lot of allocations.
Alright, I rewrote my test and ran it a few more times. I now also tested on both vectors and arrays.
Patch 1 needed a slight tweak. When coll-fold is invoked, patch 1 only specifies a fallback for type {{object}} (i.e. {{r/reduce}} is called). I had to add the same fallback for type {{array}}. (This is weird!)
So here are the results.
For vectors:
`
(let [coll (vec (repeat 100 (vec (range 100))))]
(time (dotimes [n 3000]
(->> coll
(r/mapcat identity)
(r/map inc)
(r/filter even?)
(r/fold +)))))
`
Patch 1: 205872 msecs
Patch 2: 210756 msecs
For arrays:
`
(let [coll (into-array (repeat 100 (into-array (range 100))))]
(time (dotimes [n 3000]
(->> coll
(r/mapcat identity)
(r/map inc)
(r/filter even?)
(r/fold +)))))
`
Patch 1: 123567 msecs
Patch 2: 119704 msecs
I ran my tests a few times and the results were pretty consistent. Patch 1 is faster for vectors and patch 2 is faster for arrays.
This makes sense.
In patch 1 {{reducer}} will call {{-reduce}} directly. In patch 2, {{reducer}} first calls {{r/reduce}}, which calls {{-reduce}} if the collection is a vector and {{array-reduce}} if it's an array. Hence patch 2 contains an extra function call in the case of vectors, but avoids invoking a protocol method on a native type in the case of arrays.
Using macros (or copy and paste) the extra function call can be avoided. Would that be worth trying or is it more important to keep the code clean?
--
I just realized that patch 2 is semantically slightly different from what Clojure does, although perhaps this is a bug in Clojure: https://groups.google.com/forum/#!searchin/clojure-dev/kv-reduce/clojure-dev/bEqECvbExGo/iW4B2vEUh8sJ. My suggestion to use a macro (or copy and paste) to avoid the extra function call in patch 2, could also fix this discrepancy.
