Primitive Queue<any T> considerations

[Vitaly Davidovich]

>
> To be clear, I don't want to use nullable primitive long, this is what
> Long is for


Why would you want to use Long if you have Nullable<long> available? That
doesn't make sense given your counting of cache misses.

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



has to be changed to



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


The usage pattern ought to become:

Optional<T> v = queue.poll();
// use Optional API to work with v



On Wed, Nov 18, 2015 at 3:38 PM, Dávid Karnok <akarnokd at gmail.com> wrote:

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