Re: is reduce/reduced faster than loop/recur?

[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ł


On 30 April 2016 at 02:18, Timothy Baldridge  wrote:

> 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
>
> On Fri, Apr 29, 2016 at 6:06 PM, Mark Engelberg 
> wrote:
>
>> 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?
>>
>>
>> On Fri, Apr 29, 2016 at 1:14 PM, Alex Miller  wrote:
>>
>>> 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.
>>>
>>>
>>> On Friday, April 29, 2016 at 2:41:10 PM UTC-5, Camilo Roca wrote:

 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
 

 El viernes, 29 de abril de 2016, 21:17:42 (UTC+2), puzzler escribió:
>
> By "internal reduce", are you all talking about the Clojure reducers
> library, or something else?
>
> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Clojure" group.
>>> To post to this group, send email to clojure@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+unsubscr...@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+unsubscr...@googlegroups.com.
>>> For more options, visit https://groups.google.com/d/optout.
>>>
>>
>> --
>> You received this message because you are subscribed to the Google
>> Groups "Clojure" group.
>> To post to this group, send email to clojure@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+unsubscr...@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+unsubscr...@googlegroups.com.
>> For more options, visit https://groups.google.com/d/optout.
>>
>
>
>
> --
> “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)
>
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clojure@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+unsubscr...@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+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>

-- 
You received this message because you are subscribed to the 

Re: is reduce/reduced faster than loop/recur?

[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

On Fri, Apr 29, 2016 at 6:06 PM, Mark Engelberg 
wrote:

> 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?
>
>
> On Fri, Apr 29, 2016 at 1:14 PM, Alex Miller  wrote:
>
>> 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.
>>
>>
>> On Friday, April 29, 2016 at 2:41:10 PM UTC-5, Camilo Roca wrote:
>>>
>>> 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
>>> 
>>>
>>> El viernes, 29 de abril de 2016, 21:17:42 (UTC+2), puzzler escribió:

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

 --
>> You received this message because you are subscribed to the Google
>> Groups "Clojure" group.
>> To post to this group, send email to clojure@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+unsubscr...@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+unsubscr...@googlegroups.com.
>> For more options, visit https://groups.google.com/d/optout.
>>
>
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clojure@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+unsubscr...@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+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>



-- 
“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)

-- 
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@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+unsubscr...@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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: is reduce/reduced faster than loop/recur?

[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?

On Fri, Apr 29, 2016 at 1:14 PM, Alex Miller  wrote:

> 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.
>
>
> On Friday, April 29, 2016 at 2:41:10 PM UTC-5, Camilo Roca wrote:
>>
>> 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
>> 
>>
>> El viernes, 29 de abril de 2016, 21:17:42 (UTC+2), puzzler escribió:
>>>
>>> By "internal reduce", are you all talking about the Clojure reducers
>>> library, or something else?
>>>
>>> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clojure@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+unsubscr...@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+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>

-- 
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@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+unsubscr...@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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: is reduce/reduced faster than loop/recur?

[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.


On Friday, April 29, 2016 at 2:41:10 PM UTC-5, Camilo Roca wrote:
>
> 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
>  
> 
>
> El viernes, 29 de abril de 2016, 21:17:42 (UTC+2), puzzler escribió:
>>
>> By "internal reduce", are you all talking about the Clojure reducers 
>> library, or something else?
>>
>>

-- 
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@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+unsubscr...@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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: is reduce/reduced faster than loop/recur?

[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

El viernes, 29 de abril de 2016, 21:17:42 (UTC+2), puzzler escribió:
>
> By "internal reduce", are you all talking about the Clojure reducers 
> library, or something else?
>
>

-- 
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@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+unsubscr...@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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: is reduce/reduced faster than loop/recur?

[Mark Engelberg]

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

-- 
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@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+unsubscr...@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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: is reduce/reduced faster than loop/recur?

[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


On Friday, April 29, 2016 at 5:46:03 AM UTC-5, Camilo Roca wrote:
>
>
> 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?
>

-- 
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@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+unsubscr...@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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: is reduce/reduced faster than loop/recur?

[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 :/


El viernes, 29 de abril de 2016, 13:21:47 (UTC+2), Jozef Wagner escribió:
>
> 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.
>
> On Fri, Apr 29, 2016 at 12:46 PM, Camilo Roca  > wrote:
>
>>
>> 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?
>>
>> -- 
>> 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.
>>
>
>

-- 
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@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+unsubscr...@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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: is reduce/reduced faster than loop/recur?

[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.

On Fri, Apr 29, 2016 at 12:46 PM, Camilo Roca  wrote:

>
> 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?
>
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clojure@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+unsubscr...@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+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>

-- 
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@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+unsubscr...@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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

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?

-- 
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@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+unsubscr...@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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.