Primitive Queue<any T> considerations

[Brian Goetz]

On 11/18/2015 3:16 PM, Vitaly Davidovich wrote:
>
> Right, I was talking about case where atomicity is explicitly 
> requested.  I understand JVM can pick, I'm curious on where it would 
> get a lock from.  I'm also unclear how boxing helps since the data has 
> to be unpacked atomically anyway.
>

The lock used would be invisible to the calling code.  Lots of degrees 
of freedom for the VM here, of course.  If transactional memory ever 
starts working well enough, that's an option as well.

Converting an array of big values to an array of boxes (transparently) 
is one of the options the VM has regardless of atomicity requirements.  
For big values, passing them by value is expensive anyway, and the VM 
has the right to silently box and pass a reference instead if it thinks 
this will be faster (this will be invisible to the user.)  An array of 
boxes has the nice property in that references are small enough that 
atomicity is free. So one way to get atomicity for an array of 1000-bit 
values is to use an array of references to boxed values.  Again, VM's 
choice.

> Using David's example, say he wanted to have queue of nullable longs, 
> which internally he'd store as Optional<long>.  But how does he 
> specify in his generic class definition that when sizeof (Optional<T>) 
> > word size that he'd like atomic access? This goes back to 
> specialization selection, but has size constraint.
>

Nullability is orthogonal to atomicity.  If he wants nullability, he 
wraps his values with Optional<T>.  (For refs, Optional<T> will 
hopefully be the same size as a ref, so it isn't a problem to do this 
across the board.)

For atomicity, you don't switch on size, you just ask for it.  If the 
values are small, atomicity will be free or cheap anyway.


> sent from my phone
>
> On Nov 18, 2015 3:07 PM, "Brian Goetz" <brian.goetz at oracle.com 
> <mailto:brian.goetz at oracle.com>> wrote:
>
>     If the value is "too big" and no atomicity has been requested (via
>     use-site volatile indication, declaration-site indication, etc),
>     then tearing is possible.  If atomicity is requested, the VM is
>     free to pick the most efficient means to transparently achieve
>     this, whether this be atomic load/store, seq lock, spin lock, Java
>     lock, boxing, etc.
>
>     On 11/18/2015 3:01 PM, Vitaly Davidovich wrote:
>>     This is good to hear Brian.
>>
>>         So the answer is not "reads and writes need to be atomic",
>>         but instead "there should be a way to ask for atomic
>>         reads/writes." The current front-runner here builds on an
>>         existing story -- using volatile to make longs/double fields
>>         atomic.  We can easily extend this to values. 
>>
>>
>>     Just to spitball this a bit, if the value type is larger than max
>>     atomic transfer unit on the machine, what's the thinking? I
>>     suppose you'd need some locking, but where would it get a lock
>>     for this? Would a synthetic one be generated automatically (javac
>>     or JVM)?
>>
>>     On Wed, Nov 18, 2015 at 2:56 PM, Brian Goetz
>>     <brian.goetz at oracle.com <mailto:brian.goetz at oracle.com>> wrote:
>>
>>
>>>         If value types are final, that means the array-store and
>>>         array-load have to be atomic in some way for fast-flow to
>>>         work, i.e., mark has to be written last and read first in
>>>         the structured array.
>>>
>>
>>         That would be putting it too strongly.
>>
>>         Your concern is structure tearing.  If thread A writes a
>>         value to an array element (or a field) and thread B reads it,
>>         you are concerned that the reader see some consistent value
>>         that was put there by a single write in the past (even if
>>         stale.)
>>
>>         Obviously for "small enough" values, this isn't an issue, but
>>         small enough is pretty small (64 bits on today's hardware).  
>>         Also note that the JLS / JVMS have allowed tearing of longs
>>         and doubles since day one, unless they are declared volatile.
>>
>>         Note that the bad outcome -- tearing -- /only happens in the
>>         presence of a data race/.  So the question is, what should we
>>         do to protect the too-clever (and too-unclever) folks from
>>         their own mistakes?  The answer is certainly not to make all
>>         value reads and writes atomics -- this would be burdening all
>>         of the users who follow the rules with a crippling
>>         performance penalty (and it is really bad for
>>         larger-than-64-bit values) for the sake of the few who are
>>         living on the edge.
>>
>>         So the answer is not "reads and writes need to be atomic",
>>         but instead "there should be a way to ask for atomic
>>         reads/writes."  The current front-runner here builds on an
>>         existing story -- using volatile to make longs/double fields
>>         atomic.  We can easily extend this to values.
>>
>>         That leaves two cases uncovered:
>>          - What about arrays -- there is currently no means to
>>         declare an array with volatile (or final) elements.  This is
>>         being explored now.
>>          - What about classes that are intrinsically
>>         security-sensitive, and could not tolerate tearing in any
>>         case?  For this case, we are considering a declaration-site
>>         indication that a value is "unbreakable".
>>
>>         Summary:
>>          - Tearing is going to be a risk when accessing shared
>>         mutable state via a data race.
>>          - There will be use-site and likely also declaration-site
>>         tools to opt into atomicity, with a cost.
>>
>>
>>
>