Primitive Queue<any T> considerations

[Brian Goetz]

Your sense of "what people are not going to complain about" is woefully 
optimistic :)

On 11/18/2015 3:38 PM, Vitaly Davidovich wrote:
>
>     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. 
>
>
> I know we discussed this automatic boxing before, and I still think 
> it's a bad idea to do this behind the user's back.  A large point of 
> value types is they do not touch the heap, and thus do not contribute 
> to any subsequent GC pauses. If I had a large struct, I may be just 
> fine having a slower copy operation percolating through the stack.  
> This is like escape analysis, nobody that's avoiding GC is actually 
> relying on it because of this "VM's choice" aspect.  I urge you to 
> reconsider this automatic boxing aspect.  Nobody is going to complain 
> that the JVM is not automatically boxing their large struct, but 
> someone will complain if there's heap allocation behind the scenes.
>
>     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.
>
>
> Well, if there's going to be a way to request just atomicity (and not 
> ordering as well), which will nop if size is atomic natively, then 
> great.  Otherwise, I'd hate for there to be *any* performance penalty 
> if the size is <= word size.
>
> On Wed, Nov 18, 2015 at 3:24 PM, Brian Goetz <brian.goetz at oracle.com 
> <mailto:brian.goetz at oracle.com>> wrote:
>
>
>     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.
>>>
>>>
>>>
>>
>
>