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' responsibility.
On Wednesday, April 12, 2017 at 5:34:32 PM UTC+2, Seth Verrinder wrote: > > 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 [email protected] Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to [email protected] 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 [email protected]. For more options, visit https://groups.google.com/d/optout.
