Re: Using transducers in a new transducing context

An optimizer (hardware or software) will not execute the program in an order that it can't prove to be sequentially consistent with the original order. What is important for us is not to specify exact ordering, it is to specify our intent unambiguously. To find the fastest ordering is optimizers

Re: Using transducers in a new transducing context

Reordering definitely matters: StepA: write to x StepB: read from x StepB: read from x StepA: write to x On Wednesday, April 12, 2017 at 7:15:09 AM UTC-5, Léo Noel wrote: > > I could have one thread that invokes a transduce step on odd seconds and >> another that invokes on even seconds. Or som

Re: Using transducers in a new transducing context

> > I could have one thread that invokes a transduce step on odd seconds and > another that invokes on even seconds. Or some external api call that tells > me to take the next step, which I do on a thread pulled from a pool. > Both strategies will fail to ensure no more than one thread at time.

Re: Using transducers in a new transducing context

> > >> Transducers should ensure stateful changes guarantee visibility. That is: >> you should not make assumptions about external memory barriers. > > > How do you enforce no more than one thread at a time without setting a > memory barrier ? > I could have one thread that invokes a transduce

Re: Using transducers in a new transducing context

Seems risky to depend on that. eduction creates an iterable for example - it has no way of preventing somebody from creating the iterator on one thread and consuming it on another. On Tue, Apr 11, 2017 at 7:32 AM, Léo Noel wrote: >> volatile! is what ensures that there's a memory barrier. > > > N

Re: Using transducers in a new transducing context

> > volatile! is what ensures that there's a memory barrier. > No. The memory barrier is set by the transducing context as a consequence of implementing the "single thread at a time" rule. Be it lock, thread isolation, agent isolation, or anything that ensures that the end of a step happens-be

Re: Using transducers in a new transducing context

The single thread at a time rule is implemented by the transducing context (transduce, into, core.async, etc). Inside of a transducer's implementation you just have to make the assumption that it's being used properly. volatile! is what ensures that there's a memory barrier. On Tue, Apr 11, 2017 a

Re: Using transducers in a new transducing context

Thank you Alex for these precisions. The JVM is pretty good at minimizing this stuff - so while you are stating > these barriers are redundant and are implying that's an issue, it would not > surprise me if the JVM is able to reduce or eliminate the impacts of that. > At the very least, it's t

Re: Using transducers in a new transducing context

Thanks for clearing all of that up Alex! Very helpful. On Monday, April 10, 2017 at 3:46:45 PM UTC-4, Alex Miller wrote: > > > > On Monday, April 10, 2017 at 2:25:48 PM UTC-5, Alexander Gunnarson wrote: >> >> I think you present a key question: what assumptions can a transducer >> make? We know t

Re: Using transducers in a new transducing context

On Monday, April 10, 2017 at 2:25:48 PM UTC-5, Alexander Gunnarson wrote: > > I think you present a key question: what assumptions can a transducer > make? We know the standard ones, but what of memory barriers? > Transducers should ensure stateful changes guarantee visibility. That is: you s

Re: Using transducers in a new transducing context

On Monday, April 10, 2017 at 1:57:10 PM UTC-5, Léo Noel wrote: > > What you said holds for reduction but not necessarily a parallel fold (see >> clojure.core.reducers/fold). >> > > Exactly, and that's why stateful transducers are explicitly forbidden in > fold and in core.async pipeline function

Re: Using transducers in a new transducing context

I think you present a key question: what assumptions can a transducer make? We know the standard ones, but what of memory barriers? Based on the current implementation, in terms of concurrency, it seems to make (inconsistent — see also `partition-by`) guarantees that sequential writes and reads

Re: Using transducers in a new transducing context

> > What you said holds for reduction but not necessarily a parallel fold (see > clojure.core.reducers/fold). > Exactly, and that's why stateful transducers are explicitly forbidden in fold and in core.async pipeline functions. This is not related to memory visibility, this is due to the fact t

Re: Using transducers in a new transducing context

Yes, that makes sense that you can't make that assumption. You'd have to create something like what I was discussing above: (defn map-indexed-transducer-base [f box-mutable inc-mutable] (fn [rf] (let [i (box-mutable -1)] (fn ([] (rf)) ([result] (rf result)) ([r

Re: Using transducers in a new transducing context

On Monday, April 10, 2017 at 11:48:41 AM UTC-5, Alexander Gunnarson wrote: > > Léo, I definitely agree that you can use unsynchronized mutable stateful > transducers *as long as you can guarantee they'll be used only in > single-threaded contexts. * > Transducers included in core cannot make th

Re: Using transducers in a new transducing context

The problem is at a lower level. The memory model of the JVM doesn't guarantee that changes to an unsynchronized non-volatile reference are visible to other threads. Transducers don't have to worry about concurrency but they do have to worry about visibility of changes across different threads. On

Re: Using transducers in a new transducing context

Léo, I definitely agree that you can use unsynchronized mutable stateful transducers *as long as you can guarantee they'll be used only in single-threaded contexts. *We were talking up above on which version of synchronization is appropriate for which context. With core.async, if you're using a

Re: Using transducers in a new transducing context

> > On Monday, April 10, 2017 at 12:39:37 PM UTC-4, Alex Miller wrote: Oh, you still need r/folder, sorry! Something like: > > (r/fold + (r/folder v (map inc))) > Ah, okay, glad to know I wasn't going crazy :) Thanks! On Monday, April 10, 2017 at 12:39:37 PM UTC-4, Alex Miller wrote: > > > >

Re: Using transducers in a new transducing context

On Sunday, April 9, 2017 at 9:44:00 PM UTC-5, Alexander Gunnarson wrote: > > > As an aside about the stateful `take` transducer, Tesser uses the > equivalent of one but skirts the issue by not guaranteeing that the first n > items of the collection will be returned, but rather, n items of the

Re: Using transducers in a new transducing context

I don't agree with your conclusions. :) A transducing process could apply each step of the transduce using a thread from a pool and also not use a memory barrier - in that scenario visibility across threads would not be ensured. These kinds of failures are inherently difficult to reproduce unl

Re: Using transducers in a new transducing context

What you said holds for reduction but not necessarily a parallel fold (see clojure.core.reducers/fold). On Monday, April 10, 2017 at 9:37:29 AM UTC-4, Léo Noel wrote: > > This topic is of high interest to me as it is at the core of my current > works. I had a similar questioning a while ago >

Re: Using transducers in a new transducing context

This topic is of high interest to me as it is at the core of my current works. I had a similar questioning a while ago and I have to say I'm even more confused with this : While transducing processes may provide locking to cover the

Re: Using transducers in a new transducing context

Thanks so much for your input Alex! It was a very helpful confirmation of the key conclusions arrived at in this thread, and I appreciate the additional elaborations you gave, especially the insight you passed on about the stateful transducers using `ArrayList`. I'm glad that I wasn't the only

Re: Using transducers in a new transducing context

Hey all, just catching up on this thread after the weekend. Rich and I discussed the thread safety aspects of transducers last fall and the intention is that transducers are expected to only be used in a single thread at a time, but that thread can change throughout the life of the transducing

Re: Using transducers in a new transducing context

I do have one last question for you on the topic. I'm thinking of using the below function within a core.async context — specifically within a `go` block: (defn reduce-indexed [f init xs] (reduce (let [i (mutable-long -1)] (fn [ret x] (f ret (mutable-swap! i inc) x))) in

Re: Using transducers in a new transducing context

You make a very good point. I had been under the misimpression that you could make an `r/folder` out of any thread-safe transducer like so, and it would work out of the box: (defn broken-reducers-map-indexed [f coll] (r/folder coll (map-indexed-transducer-concurrently-multi-threaded f))) and

Re: Using transducers in a new transducing context

In your example transducer, the problem is with the `result` parameter. The specification of transducers is that the result of `(rf result x)` should be fed into the next call to `rf`. In other words: (-> result (rf x1) (rf x2) (rf x3))` trying to do that in a parallel context is next to impossible

Re: Using transducers in a new transducing context

That makes sense about them not being designed for that use case. I would add, though, that transducers could certainly be used in a parallel context *if* the current transducer implementations were abstracted such that you could pass internal state generator and modifier functions and use the

Re: Using transducers in a new transducing context

Transducers were never designed to work in parallel context. So I'd define any behavior that arises from using the same transducers in multiple threads *at the same time*, as undefined behavior. On Sun, Apr 9, 2017 at 4:39 PM, Alexander Gunnarson < alexandergunnar...@gmail.com> wrote: > I should

Re: Using transducers in a new transducing context

I should add that, as Timothy pointed out, if multiple threads mutate and read the value but only one ever does so at a time, as is the case in `core.async`, then a volatile is sufficient. My preliminary conclusions above about volatiles apply only to concurrent mutation via e.g. `fold` or the

Re: Using transducers in a new transducing context

It looks that way to me too, Seth, though I'd have to comb over the details of the locks implemented there to give a reasoned opinion of my own. But yes, if that's the case, the volatile isn't adding anything. Anyway, I'm not trying to poke holes in the current implementation of transducers — o

Re: Using transducers in a new transducing context

I'll defer to Timothy on the particulars of core.async but it looks like [1] the transducer in channel is protected by a lock. If that's the case volatile isn't adding anything in terms memory barriers. 1: https://github.com/clojure/core.async/blob/master/src/main/clojure/clojure/core/async/imp

Re: Using transducers in a new transducing context

Thanks so much for your well-considered reply, Timothy! That makes sense about volatiles being used in e.g. core.async or core.reducers contexts where the reducing function that closes over the mutable value of the stateful transducer is called in different threads. Why, then, are unsynchronized

Re: Using transducers in a new transducing context

My guess is that partition-all and partition use non-volatile references because none of the built-in stuff will return control back to the caller at a finer resolution than output value (AFAIK). That's why take needs volatile but partition-all doesn't (because for take the state persists betwe

Re: Using transducers in a new transducing context

The volatile! is needed for the case where a transducer is only used by one thread at a time, but the thread executing the transducer may change from one call to the next. This happens fairly often with core.async. If you used a non-atomic, non-volatile mutable field, the JVM would be free to perfo

Re: Using transducers in a new transducing context

EDIT: Transducers are actually not safe in `fold` contexts as I thought: (let [f (fn [i x] (println (str "i " i " " (Thread/currentThread))) (flush) x) r-map-indexed #(r/folder %2 (map-indexed %1))] (->> [6 7 8 9 10] (r-map-indexed f) (r/fold 1 (fn ([] (vector)) ([x] x) ([a

Re: Using transducers in a new transducing context

I was wondering the same thing, shintotomoe. This thread talks about it as well. I think it's safe to assume that since `ArrayList` uses unsynchronized mutability internally (a quick review of the GrepCode entry for `ArrayList` confi

Re: Using transducers in a new transducing context

Thank you for the superfast response. I take it implementing your own transducing process is not something you would usually do unless you have a unique use case (my own use case being already implemented by chan taking a transducer). Still, I was wondering about the use of ArrayList in partiti

Re: Using transducers in a new transducing context

Core.async already has pipeline, pipeline-blocking and pipeline-async. In addition you can use a transducer inside a channel. Use those instead. Timothy On Thu, Jan 1, 2015 at 6:55 PM, shintotomoe wrote: > I was wondering how to apply a transducer inside a go process. What I've > so far is the

Using transducers in a new transducing context

I was wondering how to apply a transducer inside a go process. What I've so far is the following (defn pipe-xform [in-ch out-ch xform] (let [tr (let [tr (xform (fn ([result] result) ([result input] (conj! result input] (f