Unexpected performace of transducers

[Jiacai Liu]

I have read lots of articles saying transducers are faster and more efficient than normal threading form. so I create a benchmark between transducer and threading form, the result shows that transducers are slower. Is there anything I was missing?

The code and result is here:

https://gist.github.com/jiacai2050/7f3a08de9290d8810e8ef74e4dabb8e5

[Alex Miller]

Two immediate questions I would have...

You're starting from a lazy sequence, not a self-reducible collection. That's not wrong, but it's removing a key transduce/reduce power to work with reducible colls. Note that `range` *does* return a collection that can be used as either a lazy seq or a reducible collection, but using interleave will combine the lazy seq version of each range result into a lazy sequence.

Your sequence benchmark is not realizing all the results in the first benchmark, so it's doing a lot less work. By using reduce (an eager operation) in the second one, you are making them more similar.

[David Bürgin]

Jiacai –

I saw you updated the gist. Just in case it passed you by: performance
profits from the source collection being reducible. So pouring ‘dataset’
into a vector beforehand should speed up the processing quite a bit.

Also, I think the transducer version should always be faster, no matter
the size of the source collection (no threshold).


--
David

[Timothy Baldridge]

>> Also, I think the transducer version should always be faster, no matter the size of the source collection (no threshold).

It's a bit more complicated than that, mostly because transducer pipelines require about 2 allocations per step during creation. Also, most of the performance boost from transducers is due to less garbage being created, and some times the heap of the JVM is so large you'll never see much change from switching to transducers. 

Don't get me wrong, transducers are great and I often default to them over seqs, but in micro-benchmarks like this there's too much in play to always see a 100% performance boost. 

--
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+unsubscribe@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+unsubscribe@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)

[Alex Miller]

Chunked seqs are annoyingly fast. :)

[Jiacai Liu]

> Also, most of the performance boost from transducers is due to less garbage being created, and some times the heap of the JVM is so large you'll never see much change from switching to transducers.

Thanks for this tip. I seldom use transducers in my daily work, and I was convinced transducers are a better choice in whatever situation after reading some articles. But the test shows it isn't an easy choice, only when do something reducible, will transducers make more sense.

On Tuesday, November 28, 2017 at 5:07:10 AM UTC+8, tbc++ wrote:

>> Also, I think the transducer version should always be faster, no matter the size of the source collection (no threshold).

It's a bit more complicated than that, mostly because transducer pipelines require about 2 allocations per step during creation. Also, most of the performance boost from transducers is due to less garbage being created, and some times the heap of the JVM is so large you'll never see much change from switching to transducers. 

Don't get me wrong, transducers are great and I often default to them over seqs, but in micro-benchmarks like this there's too much in play to always see a 100% performance boost. 

On Mon, Nov 27, 2017 at 12:55 PM, David Bürgin <dbue...@gluet.ch> wrote:

Jiacai –

I saw you updated the gist. Just in case it passed you by: performance
profits from the source collection being reducible. So pouring ‘dataset’
into a vector beforehand should speed up the processing quite a bit.

Also, I think the transducer version should always be faster, no matter
the size of the source collection (no threshold).


--
David

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

[Alex Miller]

I would say transducers are preferable when:

1) you have reducible collections

2) you have a lot of pipelined transformations (transducers handle these in one pass with no intermediate data)

3) the number of elements is "large" (this amplifies the memory and perf savings from #2)

4) you put to produce a concrete output collection (seqs need an extra step to pour the seq into a collection; transducers can create it directly)

5) you want a reusable transformation that can be used in multiple contexts (reduction, sequence, core.async, etc)

[Jiacai Liu]

Thanks Alex. Good summary.

I think this can be added to https://clojure.org/reference/transducers

clojure+unsubscribe@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+unsubscribe@googlegroups.com.

[Renzo Borgatti]

> On 28 Nov 2017, at 02:33, Jiacai Liu <jiaca...@gmail.com> wrote:
>
> > Also, most of the performance boost from transducers is due to less garbage being created, and some times the heap of the JVM is so large you'll never see much change from switching to transducers.
>
> Thanks for this tip. I seldom use transducers in my daily work, and I was convinced transducers are a better choice in whatever situation after reading some articles. But the test shows it isn't an easy choice, only when do something reducible, will transducers make more sense.

If you're going for pure speed (such as, you have functional use cases to make the application faster) you shouldn't take them from granted. It's true that they might be faster option in many situations, but you should always benchmark it.

Missing the pure speed requirement, I'd use them as the default option, reducible or not. I prefer the flexibility they offer out of the box, the fact that I can stack up xducers as I need and then refactor/compose them out, when and if it makes sense. As a bonus, I like the fact that transducers let me turn off caching of lazy seqs (eduction) or fold a stateless chain in parallel.

IMHO, it's more flexible option to grant default use.

Renzo

[Renzo Borgatti]

> On 28 Nov 2017, at 02:54, Alex Miller <al...@puredanger.com> wrote:
>
> I would say transducers are preferable when:
>
> 1) you have reducible collections
> 2) you have a lot of pipelined transformations (transducers handle these in one pass with no intermediate data)
> 3) the number of elements is "large" (this amplifies the memory and perf savings from #2)
> 4) you put to produce a concrete output collection (seqs need an extra step to pour the seq into a collection; transducers can create it directly)
> 5) you want a reusable transformation that can be used in multiple contexts (reduction, sequence, core.async, etc)

I agree with the above Alex, although I think that is the kind of checklist I'd look at if performance optimizations is my primary goal. In any other case, I'd reach for transducers as the default. There are then several corner cases to understand, but that's true for normal sequential processing too.

Renzo

[Matan]

Hi, 

As this thread seems to have been going down this path, I am joining it after having spent some time fiddling the source code of some clojure.core transducers and familiarizing with how to create, compose and use transducers in transducing processes. By the way I think the reference could be more explicit about the relationship between transducers, transducing processes and contexts for applying transducers (as is, IMO a lot of ambiguity arises, causing a lot of confusion in getting started). So, it was noted earlier in this thread by Alex Miller:

You're starting from a lazy sequence, not a self-reducible collection. That's not wrong, but it's removing a key transduce/reduce power to work with reducible colls.

I think that's also the case with applying any transducer to a file input (?!) and I am therefore wondering about:

1. I didn't fully grasp the difference between self-reducible collections v.s. other ones (in this context, and in general).
   Can you please delineate?
   
   
2. Roughly how much performance lag do we get when not working a transduction from a (self) reducible collection, and moreso why exactly? 
   
   
3. Should we typically choose a different vehicle for stream processing from large files, over using transducers? My current use case is stream-processing from large files.

Thanks in advance for your reply,

Matan

[Didier]

| I didn't fully grasp the difference between self-reducible collections v.s. other ones (in this context, and in general). Can you please delineate?

I think this means that collections which implement CollReduce have an implementation of reduce which is faster than just calling first and next on them. Transducers will use this implementation when available. This is one of the biggest speedup of transducers over seq, which always use first and next to iterate. That said, if the collection does not offer a faster CollReduce implementation, it will fallback to using first and next, and thus won't be faster than sequences.

| Roughly how much performance lag do we get when not working a transduction from a (self) reducible collection, and moreso why exactly?

I covered why above, but I do not know how much performance lag there is. It would depend on the concrete collection and how faster its CollReduce implementation is over using first and next.

| Should we typically choose a different vehicle for stream processing from large files, over using transducers? My current use case is stream-processing from large files.

I think as a stream, you won't benefit from CollReduce, but I'm not sure. I don't think you can really reduce over the stream faster than first and next. That said, you might benefit from loop fusion if your operations can be fused.

Disclaimer: I only vaguely know what I'm talking about, you probably want a more expert opinion.

[Alex Miller]

On Saturday, December 16, 2017 at 2:39:14 PM UTC-6, Matan wrote:

Hi, 

As this thread seems to have been going down this path, I am joining it after having spent some time fiddling the source code of some clojure.core transducers and familiarizing with how to create, compose and use transducers in transducing processes. By the way I think the reference could be more explicit about the relationship between transducers, transducing processes and contexts for applying transducers (as is, IMO a lot of ambiguity arises, causing a lot of confusion in getting started). So, it was noted earlier in this thread by Alex Miller:

You're starting from a lazy sequence, not a self-reducible collection. That's not wrong, but it's removing a key transduce/reduce power to work with reducible colls.

I think that's also the case with applying any transducer to a file input (?!) and I am therefore wondering about:

1. I didn't fully grasp the difference between self-reducible collections v.s. other ones (in this context, and in general).
   Can you please delineate?
   

I'm referring primarily to collections that implement their own reduce() method (like vectors and lists) vs seqs.

1. Roughly how much performance lag do we get when not working a transduction from a (self) reducible collection, and moreso why exactly? 
   

Vectors and lists are concrete, have all their own data available, and can directly iterate through the data in a tight loop. Seqs must be realized and this entails object creation, synchronization, and object destruction overhead per element (or for chunked seqs, per chunk). 

Some collections can be iterated like a seq OR reduce themselves (vectors, lists, seqs on arrays, and the collection produced by range, cycle, repeat, and iterate).

1. Should we typically choose a different vehicle for stream processing from large files, over using transducers? My current use case is stream-processing from large files.
   

Stream processing is just another means of producing values. The question is really in how you represent the stream. Seqs have some inherent overhead. Presumably you don't want to read the entire stream and put it in a collection. The trick then is to create an object that is reducible, not a seq, and reads the stream. Probably the easiest way is to use something Iterable that can provide an iterator over the stream. The CollReduce protocol is extended to Iterable so this is already built in. Then reduce/transduce over the iterable.

An eduction combines a reducible collection and a transformation (transducer) into a collection that delays its execution until the point where you reduce it (this has some of the same utility as a lazy sequence in delaying execution). 

How exactly you want to iterate over reading the stream depends on what you're doing (Java provides streams, readers, and channels for a variety of different use cases). In any case you want to have an Iterator implementation (hasNext() and next()) that can provide the "next" item. Things like Apache Commons IOUtils can give you line iterators over a reader for example. 

[Gary Verhaegen]

The iota library implements a reducible object on top of files. It may be worth trying out for your use-case.

--

[Matan Safriel]

Thanks Gary, Alex, Didier, I learned a lot from your replies.

As per iota, I assume we're talking about this library of course.

clojure+unsubscribe@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+unsubscribe@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 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+unsubscribe@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 a topic in the Google Groups "Clojure" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/clojure/JjiYPEMQK4s/unsubscribe.
To unsubscribe from this group and all its topics, send an email to clojure+unsubscribe@googlegroups.com.

[Gary Verhaegen]

Yes.

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.