[concurrency-interest] On A Formal Definition of 'Data-Race'

oleksandr otenko oleksandr.otenko at oracle.com
Wed Apr 17 13:06:43 EDT 2013


Yes.

1. Unroll the loop.
2. Reorder non-volatile accesses to go ahead of volatile stores
3. Now all volatile stores from all iterations are one after the other
4. Multiple stores to the same location can be fused, even if they are 
volatile stores

If you want a store in every iteration, need a volatile load somewhere 
between the stores.

Alex


On 17/04/2013 18:01, Vitaly Davidovich wrote:
>
> Are you sure about fusion if shared is volatile? Maybe theoretically 
> it's possible but the analysis (and risk) the JVM would have to do to 
> make that transform is probably impractical.  Intuitively, if I mark 
> something volatile, I expect almost verbatim code to execute.
>
> By instructions, I mean loads and stores since that's what actually 
> matters for these scenarios.
>
> On Apr 17, 2013 12:55 PM, "oleksandr otenko" 
> <oleksandr.otenko at oracle.com <mailto:oleksandr.otenko at oracle.com>> wrote:
>
>     Yes, but not any instructions - only those that have temporal
>     relationship.
>
>     So, for example, in this case even if shared is volatile, then
>     volatile stores can still be moved out of the loop and fused into
>     a single volatile store.
>
>     Alex
>
>
>     On 17/04/2013 17:43, Vitaly Davidovich wrote:
>>
>>     Immediate means store is made globally visible before subsequent
>>     instructions complete/retire.
>>
>>     On Apr 17, 2013 12:26 PM, "oleksandr otenko"
>>     <oleksandr.otenko at oracle.com
>>     <mailto:oleksandr.otenko at oracle.com>> wrote:
>>
>>         What is this "immediate" anyway?
>>
>>         It is actually "before anything else in this thread that's
>>         temporal"
>>
>>         Alex
>>
>>
>>         On 17/04/2013 16:44, Vitaly Davidovich wrote:
>>>
>>>         I actually expect that the optimizer *would* do this
>>>         transformation on plain fields (provided it doesn't break
>>>         intra-thread semantics, of course) because it's a perf gain.
>>>
>>>         Don't know how much JIT can see through println as it
>>>         ultimately calls into runtime and OS functions, so I'd guess
>>>         it doesn't know enough or simply plays conservative here. 
>>>         However, Nathan's point is still valid even if example isn't
>>>         necessarily the best one. If you had "pure" java code
>>>         instead of an I/O call that took significant time to
>>>         execute, the write would be delayed.  I'm not sure why that
>>>         matters though for benign data races.  Clearly if you need
>>>         immediate visibility, you code for that specifically.
>>>
>>>         On Apr 17, 2013 11:32 AM, "Zhong Yu" <zhong.j.yu at gmail.com
>>>         <mailto:zhong.j.yu at gmail.com>> wrote:
>>>
>>>             On Wed, Apr 17, 2013 at 1:38 AM, Nathan Reynolds
>>>             <nathan.reynolds at oracle.com
>>>             <mailto:nathan.reynolds at oracle.com>> wrote:
>>>             > Couldn't JIT hoist the non-volatile writes out of the
>>>             loop?
>>>
>>>             Certainly, sorry if my statement sounds too absolute.
>>>
>>>             > For example, the following code...
>>>
>>>             But, is this a valid example? Can JMM really reorder around
>>>             System.out.println()?
>>>
>>>             > for (i = 0; i < 1_000_000_000; i++)
>>>             > {
>>>             >     System.out.println(i);
>>>             >     shared = 2 * i;
>>>             > }
>>>             >
>>>             > ... could be transformed into ...
>>>             >
>>>             > for (i = 0; i < 1_000_000_000; i++)
>>>             > {
>>>             >     System.out.println(i);
>>>             > }
>>>             >
>>>             > shared = 2 * 1_000_000_000;
>>>             >
>>>             > ... If so, then the non-volatile write may not happen
>>>             for a very long time.
>>>             >
>>>             > Nathan Reynolds | Architect | 602.333.9091
>>>             <tel:602.333.9091>
>>>             > Oracle PSR Engineering | Server Technology
>>>             > On 4/16/2013 10:27 PM, Zhong Yu wrote:
>>>             >
>>>             > On Tue, Apr 16, 2013 at 8:51 PM, thurstonn
>>>             <thurston at nomagicsoftware.com
>>>             <mailto:thurston at nomagicsoftware.com>>
>>>             > wrote:
>>>             >
>>>             > Vitaly Davidovich wrote
>>>             >
>>>             > The code works as-is.
>>>             >
>>>             > Absolutely.  volatile is not needed for correctness
>>>             >
>>>             > Vitaly Davidovich wrote
>>>             >
>>>             > Why?
>>>             >
>>>             > Well, for performance reasons given the
>>>             'undefined/indefinite' visibility of
>>>             > #hash to other threads.
>>>             > At least according to the JMM (which has nothing to
>>>             say about CPU cache
>>>             > coherency), it is *possible* that each distinct thread
>>>             that invoked
>>>             > #hashCode() *could* result in a recalculation of the hash.
>>>             >
>>>             > In practice though, application threads contain very
>>>             frequent
>>>             > synchronization actions, or other operations that
>>>             force VM to
>>>             > flush/reload. So it won't take very long for any
>>>             non-volatile write in
>>>             > one thread to become visible to other threads.
>>>             >
>>>             > Imagine a long-lived Map<String, ?>; and many threads
>>>             accessing the map's
>>>             > keyset and for some unknown reason invoking
>>>             #hashCode() on each key.
>>>             > If #hash was declared volatile, although there is no
>>>             guarantee that #hash
>>>             > would only be calculated once, it is guaranteed that
>>>             once a write to main
>>>             > memory was completed, every *subsequent* (here meaning
>>>             after the write to
>>>             >
>>>             > In JMM though, we cannot even express this guarantee.
>>>             Say we have
>>>             > threads T1...Tn, each thread Ti burns `i` seconds CPU
>>>             time first, then
>>>             > volatile-reads #hash, and if it's 0, calculates and
>>>             volatile-writes
>>>             > #hash which takes 100 ns. We can find no guarantee
>>>             from JMM that
>>>             > there's only one write; it's legal that every thread
>>>             sees 0 from the
>>>             > volatile read.
>>>             >
>>>             > Zhong Yu
>>>             >
>>>             > main memory) read no matter from which thread would
>>>             see #hash != 0 and
>>>             > therefore skip the calculation.
>>>             >
>>>             >
>>>             >
>>>             > Vitaly Davidovich wrote
>>>             >
>>>             > String is too high profile (especially
>>>             > hashing it) to do the "naive" thing.
>>>             >
>>>             > Nothing wrong with being naive; naive can be charming.
>>>             >
>>>             >
>>>             > Vitaly Davidovich wrote
>>>             >
>>>             > Also, some architectures pay a
>>>             > penalty for volatile loads and you'd incur that each time.
>>>             >
>>>             > Fair point; the JDK authors only get one shot and they
>>>             can't assume that
>>>             > volatile reads are cheap
>>>             >
>>>             >
>>>             >
>>>             >
>>>             >
>>>             > --
>>>             > View this message in context:
>>>             >
>>>             http://jsr166-concurrency.10961.n7.nabble.com/On-A-Formal-Definition-of-Data-Race-tp9408p9466.html
>>>             > Sent from the JSR166 Concurrency mailing list archive
>>>             at Nabble.com.
>>>             > _______________________________________________
>>>             > Concurrency-interest mailing list
>>>             > Concurrency-interest at cs.oswego.edu
>>>             <mailto:Concurrency-interest at cs.oswego.edu>
>>>             > http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>>             >
>>>             > _______________________________________________
>>>             > Concurrency-interest mailing list
>>>             > Concurrency-interest at cs.oswego.edu
>>>             <mailto:Concurrency-interest at cs.oswego.edu>
>>>             > http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>>             >
>>>             >
>>>             >
>>>             >
>>>             > _______________________________________________
>>>             > Concurrency-interest mailing list
>>>             > Concurrency-interest at cs.oswego.edu
>>>             <mailto:Concurrency-interest at cs.oswego.edu>
>>>             > http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>>             >
>>>             _______________________________________________
>>>             Concurrency-interest mailing list
>>>             Concurrency-interest at cs.oswego.edu
>>>             <mailto:Concurrency-interest at cs.oswego.edu>
>>>             http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>>
>>>
>>>
>>>         _______________________________________________
>>>         Concurrency-interest mailing list
>>>         Concurrency-interest at cs.oswego.edu  <mailto:Concurrency-interest at cs.oswego.edu>
>>>         http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>
>>
>>         _______________________________________________
>>         Concurrency-interest mailing list
>>         Concurrency-interest at cs.oswego.edu
>>         <mailto:Concurrency-interest at cs.oswego.edu>
>>         http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>
>
>
>     _______________________________________________
>     Concurrency-interest mailing list
>     Concurrency-interest at cs.oswego.edu
>     <mailto:Concurrency-interest at cs.oswego.edu>
>     http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20130417/6a636870/attachment-0001.html>


More information about the Concurrency-interest mailing list