Summary isn’t always the fastest way to transform or iterate over a collection. Especially if: 1. Primitive math is involved or 2. Multiple accumulators are needed or 3. Multiple sequences are involved. reduce Intro Iterating over a sequence can be done with many functions in Clojure. There is , , , and many more. Usually if none of the standard sequence transforming functions fit, developers tend to fall back to and more seldom to a manual . These latter two are very flexible since you can do any transformation you’d like map filter keep mapcat reduce loop Reduce to single value Ignore (filter) some values Map some values Add more values All at the same time. also has a (deserved) reputation of being very fast since each collection itself will run it’s own optimized reducing code. reduce Problem In this article I will be treating 2 problems: Reducing into multiple valuesSuch as:- - count all positive, count all odd number calculate the sum and the product of all numbers in a collection (iterating once) Iterating over multiple sequences at the same time.Such as:- calculate the transpose of the vectors - select all values from the one vector given another vector In the examples I’ll be using vectors since that’s the most common data type to be used when you care about performance. Let’s start with problem #1: To keep the code simple we’ll count the number of odd and even values of 10 million numbers: 229ms Using Criterium and a properly configured JVM this runs in about 229ms. For comparison: A simple runs in about 82ms. So almost 3x slower just because we have two accumulators instead of one. (reduce (fn [s _] (inc s)) 0 xs) Can we do better? Let’s try a manual simple : loop 148ms This runs in about 148ms. Why is it so much faster? Multiple reasons: We’re not destructing and constructing a new vector on every iteration. We’re doing primitive math inside the loop. However for such a simple comparison it’s still much slower than the baseline of 82ms. even? — odd? Internally, a vector is made up of chunks of Java arrays of length 32. A call to returns a sequential view on the part of the vector (a ). So this generates a new object on every iteration just to throw it away at the next iteration of the loop. This mean we’re generating garbage which the JVM needs to collect. next ChunkedSeq loop Obviously, iterating over this array of the vector would be fastest. This is exactly what does internally. Can we somehow get access to this raw array and write our own loop? Many functions and macros do know about chunked sequences and this is the reason that is pretty fast on vectors. reduce map Another candidate is which iterates over the chunked buffer (Run a to see how). Let’s use some tricks to speed things up: doseq (macroexpand '(doseq [x xs] “abc”)) 109ms This runs in about 109ms. Better! But now we left our nice immutable realm and the code is quite ugly. Also, this approach only works with a limited set of accumulators. What if we wanted to accumulate into another vector or a persistent map? It’s inflexible. Another even uglier version is to use arrays and mutate them: 73ms This runs in about 73ms. Pretty fast, but als pretty ugly, error prone and inflexible if we wanted to accumulate values other than numbers. A forgotten approach Let’s finally introduce the construct that this article is all about: Using . Most language have some kind of iterators, the Java ones are pretty simple, they only consist of two methods on their interface: and . Let’s use it: Iterator it.hasNext() it.next() 70ms This runs in about 70ms. It’s only a tiny bit faster than using the mutable array approach but we’re much more flexible: We can accumulate any values we’d like to! The iterator is very fast, since it produces very little garbage in each iteration and has fast implementations for most data structures. The check only does an index comparison and the call only an index lookup for . it.hasNext() it.next() PersistenVector Side note: I wrote a macro which manually iterates over the chunked buffer, similarly to but also accumulates odd/even within the loop. It only ran about 7% faster (down to ~65ms). I won’t show it here since it’s much less flexible and only works for vector and makes assumptions about the internals of chunked sequences. doseq A macro is born Let’s write a macro to make life easier: We can now rewrite the above nicely: Same as above but using the new macro. Note: Telling to gives us nice syntax highlighting. Cursive treat the [loop-it](https://cursive-ide.com/userguide/macros.html) like a [for](https://cursive-ide.com/userguide/macros.html) Let’s now go to our second problem: Iterating over multiple sequences. For this we’ll consider the problem of transposing two vectors. I.e: Given and we create as the output. Not too many function in can deal with multiple input sequences: As far as I can tell only , , , , , and can. So if you need to iterate over multiple collection you to use these limited set of functions. [a b c] [0 1 2] [[a 0] [b 1] [c 2]] clojure.core map mapv pmap sequence interleave lazy-cat mapcat have Instead, using iterators we can easily do this: 20ms This runs in about 20ms for two vectors with 1 million elements. Using runs in about 85ms. So over 4x faster when using iterators. Of course, it’s slightly unfair since we’re not providing a function to call here. Doing so only slows down the function by about 1–2% however. (mapv vector xs xs) f Side note: If you really need this to be fast you can use also use arrays to get this down to 10ms: There are many applications for . We can also use it to create a faster function (not lazy obviously): loop-it interleave 26ms This runs in about 26ms whereas runs in about 64ms. A nice speedup. (doall (interleave xs xs)) Of course I hear you say: is much more flexible: It can take a number of sequences: map variable Heck, it can even properly deal with infinite sequences: Can we achieve the same with ? Not in its current state: It requires you — at compile time — to give it the sequences you want to iterate over. For a variable number of sequences we can use a trick (copied from ): Transform a variable number of iterators into a single iterator. The new iterator returns a collection for each call to . We call this a . Since the class in is private we have to rewrite it: loop-it clojure.core it.next() multi iterator clojure.core Just like it uses native arrays for speed. However, one problem remains: It cannot deal with infinite number of sequences since it is eager. So let’s create another lazy one: clojure.lang.MultiIterator Now can be an infinite sequence. colls Let’s actually see how we can use it: It’s a start. But before benchmarking, let’s combine and unroll some more to come up with a really fast : mapv Note: I also change the macro to call instead of . loop-it ensure-iter clojure.lang.RT/iter Let’s benchmark: ( vector xs xs xs xs) mapv For 1 million elements this runs in about 1.28 seconds. Our new iteration based implementation runs this in only 147ms. Almost a 9x speedup and the implementation is pretty readable. Other applications Let’s write a : really fast take-nth This runs in 52ms for where has 10 million elements. runs in 273ms and runs in 290ms. (take-nth-vec 5 xs-large) xs-large (into [] (take-nth 5) xs-large) (doall (take-nth 5 xs-large)) 2. Partition your sequence into two sets: , : all-truthy-values all-falsy-values This runs in about 176ms for the based implementation and 291ms for based implementation. And IMO the loop is more readable. loop-it reduce : This is how many other programming languages define . Side note partition 3. Compute the sum of a collection. From top to bottom: 177ms, 130ms, 59ms Clojurescript All this is also possible in Clojurescript. Creating an iter is done with , only a change to is a little trickier. iter ensure-iter Dreams An is pretty simple: and . A really nice feature would an improved iterator that also allows us to say “give me the rest of the sequence right now”. Something like . This could allow us to speed up things like which currently isn’t possible with iterators. One notable idea is to speed up which isn’t all that fast. It currently iterates over the given sequence multiple times. See my for ideas. If an Iterator had a it could be used right there. Iterator it.hasNext() it.next() it.restSeq() nthrest apply clojurescript ticket it.restSeq() Conclusion Don’t forget about in clojure. They can often be worth it. Use them if you need to: Iterators Accumulate multiple values Want to do primitive math Want to iterate over multiple sequences at the same time As always: If performance matters: Benchmark. There are times when using an Iterator is not faster. For instance, an eager implementation was slower with a nested implementation (but faster using for the inner loop). mapcatv loop-it reduce All code is at: https://github.com/rauhs/clj-bench Note: Since is really small you should just copy it. There is no clojars library. loop-it
