Primitive Queue<any T> considerations

[Dávid Karnok]

To be clear, I don't want to use nullable primitive long, this is what Long
is for. My problem is that the j.u.Queue.poll() relies on the ability to
return null indicating an empty queue which when primitivized is likely to
return zero which is also a valid value.

A similar issue happens with JDBC's getInt() method which may return zero
and one has to call wasNull() to find out if it was a valid zero or a null
really.

With ref-based queue, I can forbid using null as a value but it would be
over restrictive to forbid zero in offer().

This means that for Spsc, the usage pattern of

T v = queue.poll();
if (v != null) { ... }

has to be changed to

if (!queue.isEmpty()) {
    T v = queue.poll();
    ...
}

Which incurs 2 cache misses with fast-flow and 3 with the marked variant.

Note however that this pattern doesn't work for MPMC as another consumer
may take the value between isEmpty and poll.

The bottom line is that my SPSC queue requires a different API to tell
apart emptyness and having a value "atomically" and the ability to chose
this implementation in an <any T> situation.


2015-11-18 21:16 GMT+01:00 Vitaly Davidovich <vitalyd at gmail.com>:

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


-- 
Best regards,
David Karnok