is reduce/reduced faster than loop/recur?

[Camilo Roca]

I have been hearing a lot of Clojure's use of an internalReduce protocol, which seems to speed up things when using reduce.
Now the thing is that a lot of people also claim that tail-call-recursion is also pretty fast, which lets me wondering:

- if I could replace a loop/recur with an equivalent reduce/reduced approach, do I see performance gains?

Obviously the immediate answer is just "benchmark it", but so far I haven't found an stable solution to this question. The benchmark seems to go sometimes for loop/recur and some others for reduce/reduced. I also know that when doing primitive math, loop/recur performs better than reduce/reduced, but I was wondering in which cases (regardless of idiomatic or nor) would a reduce approach be preferred over a loop/recur?

Any thoughts on this?

[Jozef Wagner]

There are many ways on how you can improve the performance of loop/recur, and most of them depends on the type of a thing you are iterating through. With reducers (and transducers), the iteration part is decoupled from the reduction part, so they offer a mechanism that chooses the optimal iteration strategy for the collection that is passed in.

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Camilo Roca]

hey Jozef,

would you mind sharing a blog post or piece of documentation where I can learn about those strategies? The only one that I know so far is the local primitives for fast arithmetic, but besides from that I haven't heard of any ther optimization for loop/recur strategy :/

[Alex Miller]

Both loop/recur and reduction/transduce via IReduce are similar in doing looping without consuming stack, building up an accumulated value, and not allocating memory. reduce/transduce always take an input collection - if that collection can be traversed via internal reduction or sequential iteration, then I would favor using reduce over loop/recur. 

Take for example a vector, which is possibly the most interesting case with the most options. In a loop/recur how are you going to walk through the vector's elements? The most obvious way is to using the sequential functions like first/next/rest. Importantly, rest is going to give you a sequence over the vector, not the vector itself, which will incur extra cost. That said, the vector sequence is really fast - as much of the time it's just walking through an internal array node bumping an index. Or you might do indexed lookups into the vector ala nth. Your "iteration" has less overhead but on each index you must re-traverse the nodes of the vector.

Compare to a vector doing internal reduce - this is effectively an internal iteration that walks through the nodes of the vector data structure, evaluating the reduction function on each item it finds. There is no seq overhead and no re-traversal.

It's hard for me to say which of these is fastest without benchmarking a particular case, and it will matter a lot how many things are in the vector (as that affects the cost of lookup by index). My suspicion is that usually the cost for any of these is dominated by the function being applied per element, not by the iteration method.

loop/recur is beneficial in cases where the iteration is not based on traversing a collection (could be incrementing a counter, evaluating a function, iterating an external resource, etc), or traverses multiple collections in parallel, or any other "not sequentially traversing a collection" use case. Additionally, loop/recur is the only way in Clojure to get a loop that retains long or double primitives throughout the loop so for hot math loops you should definitely prefer loop/recur.

Alex

[Mark Engelberg]

By "internal reduce", are you all talking about the Clojure reducers library, or something else?

[Camilo Roca]

puzzler,
No, Clojure actually has quite a lot of protocols for reducing "things". But they are so many that I got lost in which does what and how, so I wanted a clarification on the subject.

Alex miller, excellent answer already gave me some overview of the topic.

Here is a link to Clojure's protocols for reduce: https://github.com/clojure/clojure/blob/master/src/clj/clojure/core/protocols.clj

[Alex Miller]

The main internal protocol is really CollReduce for collections that can reduce themselves.  InternalReduce is for concrete seq implementations that can reduce themselves.

For cases where you are creating new things, you can also plug in a little more easily by implementing the IReduceInit (reduce with an init value) or IReduce (extends IReduceInit for the case where an init value is not supplied) Java interfaces. I would generally prefer these if you are creating a new thing.

[Mark Engelberg]

So you're saying that this is an optimization that is automatically called when you invoke Clojure's standard reduce function on something like a vector?

[Timothy Baldridge]

Yes, and it happens for most collections. Vectors, maps, etc. There's even a fast path for reduce-kv on maps that doesn't create key value entry objects. 

Timothy

--

“One of the main causes of the fall of the Roman Empire was that–lacking zero–they had no way to indicate successful termination of their C programs.”
(Robert Firth)

[Michał Marczyk]

And just to add a pointer in case anybody's interested in opting in to this behaviour in a custom type, it's possible to do so by implementing clojure.core.protocols/IKVReduce (data.avl does this) or clojure.lang.IKVReduce (the iface implemented by built-in maps; clojure.core provides implementation of clojure.core.protocols/IKVReduce targeting clojure.lang.IKVReduce). Of course then it is the responsibility of that custom implementation to implement reduce-kv's semantics correctly.

Cheers,

Michał