Primitive Queue<any T> considerations

[Vitaly Davidovich]

Do a poll if you'd like :) Bottom line is that (reasonable) people will not
complain if (a) the JVM behavior is predictable and (b) it does what the
programmer requested.  Given the topic is value types, and one of the big
issues they help with is avoiding the heap, people *will* complain if
that's subverted behind the scenes.  For once, don't make the JVM think it
knows better :).

On Wed, Nov 18, 2015 at 3:45 PM, Brian Goetz <brian.goetz at oracle.com> wrote:

> 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>
> 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> 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>
>>> 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.
>>>>
>>>>
>>>>
>>>
>>>
>>
>
>