Fork me on GitHub
#core-async
<
2015-07-30
>
jcf09:07:40

@meow: Criterium is the most commonly recommended library for benchmarking Clojure code. https://github.com/hugoduncan/criterium

meow11:07:45

@jcf: cool, thanks simple_smile

meow12:07:28

In the interest of just doing some very basic timing of these functions to get a rough feel for the performance difference between composing transducers vs. my initial naive implementation I did the following:

(defn consume [max ch]
  (dorun (repeatedly max #(<!! ch))))

(comment
  (time (consume 2000 (chan-of-primes)))
  (time (consume 2000 (chan-of-primes-x)))
  )

meow12:07:02

Anyone interested in the performance of transducers should check it out.

meow13:07:40

I created a wiki page for this stuff if anyone would like to help with it: https://github.com/clojure/core.async/wiki/Sieve-of-Eratosthenes

meow14:07:58

Unfortunately, the better version of the code is causing a stack overflow for me when it gets to about 7000 primes.

meow14:07:24

And I can't see the cause of the problem. 😞

erik_price15:07:50

1. on every iteration, you’re creating a new function that is the composition of all previous iterations’ transducers. 2. at some point, when the function is actually executed, it becomes a giant call stack, which can overflow

erik_price15:07:32

at least, that’s what it looks like – i didn’t test this code or anything

meow15:07:48

@erik_price: aha, thank you! simple_smile

meow15:07:13

I've read all of the @stuartsierra blog posts in that series and I think they are awesome. Didn't realize that I was creating this problem using comp.

meow15:07:51

So now the question is how to comp transducers in a recursive loop without blowing the stack...

rauh15:07:29

@meow: I'd probably use dotimes for this. That shouldn't blow your stack. I don't think it's a problem with comp but with repeatedly

erik_price15:07:21

rauh: why do you say that? by the 7000th iteration, cur-xf looks like (filter #(not= 0 (mod (filter #(not= 0 (mod (filter #(not= 0 (mod (filter #(not= 0 (mod (filter #(not= 0 (mod (…) prime))) prime))) prime))) prime))) prime)))

meow15:07:37

@rauh: I'm not sure about repeatedly being a problem, but you might know better than me. But I do think comp is a problem.

erik_price15:07:48

(not exactly, but effectively – there is actually an additional anonymous function introduced between each of those recursions)

meow15:07:02

@erik_price: I'm thinking that maybe it would be better to change the transducer to not be a comp but instead make use of a collection of all the previous primes to do its filtering.

meow15:07:38

these primes are effectively getting embedded into the comp as it is now

meow15:07:59

so instead we could turn them into raw data and simplify the xform

rauh15:07:20

Oh I didn't even see the comp in the loop. I understand now

meow15:07:05

@rauh: yeah, I didn't even realize I was creating such a problem

meow15:07:27

good lesson to learn

meow18:07:02

Major revisions to the wiki page - thanks to all who provided feedback: https://github.com/clojure/core.async/wiki/Sieve-of-Eratosthenes

meow18:07:57

;tl-dr; I went with an approach based on (every? #(not= 0 (mod n %)) knowm-primes))

rauh19:07:02

@meow: Nice. I personally would create a transducer that you could potentially reuse. For instance by solving the more general problem.

rauh19:07:18

Let me explain: I'd create a filter-divisible-previous transducer that takes a sequence of anything that can filter all elements that are somehow divisble by the previously seen elements

rauh19:07:14

Thus, you can use them with core.async or really anything. Also you don't have to feed in 2,3,4... but you also do 2,5,8,11,... and get interesting results

rauh19:07:24

Based on distinct:

rauh19:07:14

Then we can do:

meow19:07:26

@rauh: very cool. I need to take a break but will look at this more closely later. simple_smile

meow19:07:06

@rauh: is volatile! supported in cljs?

meow19:07:18

I'm learning something new here with volatiles...

rauh19:07:28

it's just a variable in cljs

meow19:07:49

ok, the docs just mentioned the java stuff

rauh19:07:57

The implementation looks scary but it's literally one form changed from the distinct from core

meow22:07:19

@rauh: is there an appropriate shorter name than filter-divisible-previous?

rauh22:07:12

@meow: Good question, the filter part can be cut since distinct also doesnt use it.

rauh22:07:01

maybe mod0-none?

meow22:07:29

I was also thinking of something along the lines of factor/factorize but between not being a mathematician and not fully groking the transducer code I'm at a loss right now...

rauh22:07:42

@meow: Dive into transducers and make sure you understand partition-by implementation. After that, everything about transducers is easy simple_smile

meow22:07:10

It's not immediately apparent how to change chan-of-primes to use your transducer and it's been a long day, but I'm hoping a flash of insight comes my way because I have a sense that what you are suggesting is very clever. simple_smile

meow22:07:21

I know nothing about partition-by and am quite new to transducers but this little Game of Primes has been a good learning experience.

rauh22:07:39

That's the most important step. I'm sure you've learned tons of stuff with your core.async implementations. simple_smile

meow22:07:49

I did look at the source for distinct so I understand where your code is coming from.

rauh22:07:34

Yes, as soon as I get something stateful I immediately go to partition-by or distinct. 90% of the time I can just use those with some adjustments

meow22:07:07

11 weeks - that's how long I've been using Clojure

rauh22:07:22

Stick with us simple_smile

meow22:07:49

You're stuck with me - I'm not going anywhere simple_smile

meow22:07:00

so if the transducer has state, it won't make sense for the chan-of-primes function to also have that same state, right?

meow22:07:16

I'm just sort of thinking out loud before I quite for dinner.

meow22:07:32

so this won't just be a drop in replacement

meow22:07:49

to do that would be suboptimal

meow22:07:33

instead the transducer should have the same lifespan as the chan-of-primes function so it can accumulate state on its own

meow22:07:11

is that anywhere near to the truth? or am I going off on a tangent?