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 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. You > need something to prevent overlapping, e.g when a long step is running and > you get a request to start the next one. > > > While this is a good reference, it's also 13 years old and the JMM has >> been updated since then. A much better reference explaining the semantics >> and constraints is: > > https://shipilev.net/blog/2014/jmm-pragmatics/ > > In particular, even if there is a memory barrier, there are some >> reorderings allowed if the transducer state is not volatile that may be >> surprising. Making it volatile adds a critical edge in the total program >> order. > > I'm saying that the logical ordering of steps is irrelevant wrt how a >> multi-threaded program can be optimized/reordered under the JMM. > > > Thank you for the reference. Very enlightening (esp. part III > <https://shipilev.net/blog/2014/jmm-pragmatics/#_part_iii_sc_drf>). > I understand reordering is a thing. Does ordering really matter ? What > matters to us is that each step is able to see the changes made the step > before. That is, we need to ensure memory visibility across steps. This is > all what we need to be sure that the JVM won't run the program in an order > that doesn't yield the same result as what we expect. > In a degenerate case, we'll put volatile on every variable, ensuring that > the running program is totally ordered and totally unoptimizable. Is this > what we want ? > > > happens-before across threads requires a volatile or lock, but I don't see >> how the use of one is guaranteed by this logical ordering. >> > > Volatiles and locks are means to an end. The end is memory visibility, and > the happens-before partial ordering is what is of interest to us, > application developers, to reason about this end. The happens-before rules > have not changed since jsr-133 (source > <http://download.java.net/java/jdk9/docs/api/java/util/concurrent/package-summary.html#MemoryVisibility>) > > : > * Each action in a thread happens-before every action in that thread that > comes later in the program's order. > * An unlock (synchronized block or method exit) of a monitor > happens-before every subsequent lock (synchronized block or method entry) > of that same monitor. And because the happens-before relation is > transitive, all actions of a thread prior to unlocking happen-before all > actions subsequent to any thread locking that monitor. > * A write to a volatile field happens-before every subsequent read of that > same field. Writes and reads of volatile fields have similar memory > consistency effects as entering and exiting monitors, but do not entail > mutual exclusion locking. > * A call to start on a thread happens-before any action in the started > thread. > * All actions in a thread happen-before any other thread successfully > returns from a join on that thread. > > Here is an example of a multithreaded transducing context that doesn't use > locks nor volatiles (inspired from the official documentation for agents > <https://clojure.org/reference/agents>) : > > (def xf (comp (partition-all 64) cat)) > > (defn ! [f & args] (apply f args) f) > > (defn run [m n] > (let [p (promise) > f (reduce (fn [f _] (partial send (agent f) (xf !))) > #(when (zero? %) (deliver p nil)) (range m))] > (doseq [i (reverse (range n))] (f i)) > (f) > @p)) > > (run 1000 1000) > > > The unsynchronized ArrayList in partition-all will be accessed by multiple > threads, and I can still be confident about visibility, because agents > ensure a happens-before ordering between each message. This behaviour is > actually delegated to the backing Executor, which may or may not use locks. > Locks are really an implementation detail, what is important is > happens-before guarantees. > > > 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. >> > > Iterators are unsynchronized and mutable, like many classes in the Java > standard library. You know they're unsafe and need to treat them as such. > This leads to a more general debate on mutability. Objects generally fall > in 3 categories : > 1. Immutable objects aka values. They're the default in Clojure and that's > great because they can be exposed safely and they're so easy to reason > about. > 2. Thread-safe mutable objects. Includes core reference types, core.async > channels. They're useful to model identity, they can be exposed safely but > sparingly as they tend to complect the system in the large. > 3. Unsafe mutable objects. Includes transients, Iterator, > InputStream/OutputStream. They exist for performance or legacy reasons. > They need extra care when used in multithreaded contexts and they should > not be exposed as-is. > > Clearly, reducing functions produced by stateful transducers are of the > third type. You need to care if you're designing a transducing context, but > most of the time you don't because : > - when you design a stateful transducer, you can write your code as if it > were single-threaded because it will be run in a context that cares about > concurrency for you > - once your ugly mutable state is encapsulated in a transducer, it's a > value. Instead of handling a mutable process, you handle a recipe for > making a mutable process, it's immutable and it's good. > > Once again, I don't understand what's wrong with that. > > Java, beeing mutable by default, has refrained to clutter its standard > library with volatiles and locks. Instead, most classes are unsynchronized, > optimized for single-threading. When synchronization is needed, we rely on > a limited set of concurrency primitives. What's wrong with this approach ? > > > > On Tuesday, April 11, 2017 at 5:24:38 PM UTC+2, Alex Miller wrote: >> >> >>>> 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 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. I'm >> sure I could come up with others. >> >> >>> For the JMM, no more than one thread at a time means exactly that return >>> of step n will *happen-before* the call to step n+1. >>> >> >> happens-before across threads requires a volatile or lock, but I don't >> see how the use of one is guaranteed by this logical ordering. >> >> This implies that what was visible to the thread performing step n will >>> be visible to the thread performing the step n+1, including all memory >>> writes performed during step n inside stateful transducers. >>> >> >> Only if there is a volatile or lock forcing that visibility. >> >> >>> https://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html >>> <https://www.google.com/url?q=https%3A%2F%2Fwww.cs.umd.edu%2F~pugh%2Fjava%2FmemoryModel%2Fjsr-133-faq.html&sa=D&sntz=1&usg=AFQjCNFrKhTVAobPzLvc5FHLhtsUgQ5YTg> >>> >>> Still no need for extra synchronization. >>> >> >> While this is a good reference, it's also 13 years old and the JMM has >> been updated since then. A much better reference explaining the semantics >> and constraints is: >> >> https://shipilev.net/blog/2014/jmm-pragmatics/ >> >> In particular, even if there is a memory barrier, there are some >> reorderings allowed if the transducer state is not volatile that may be >> surprising. Making it volatile adds a critical edge in the total program >> order. >> >> You're conflating the stateful values inside the transducer with the >>>> state returned by and passed into a transducer. That's a linkage that does >>>> not necessarily exist. >>>> >>> >>> What do you mean ? How could a function return a value without having >>> executed its body ? >>> >> >> I'm saying that the logical ordering of steps is irrelevant wrt how a >> multi-threaded program can be optimized/reordered under the JMM. >> >> -- 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.
