Primitive Queue<any T> considerations

Vitaly Davidovich vitalyd at gmail.com
Wed Nov 18 16:34:59 UTC 2015


>
> having Cell with final fields is useless here because then I have a
> constant array and not a queue.


That's the current proposal (i.e. value types can only have final fields).
Can't say I'm too happy about that, but it is what it is.

The implementation of offer(T) looks like this:
> offset = producerIndex & (array.length - 1)
> if (array[offset].mark != 0) {
>     return false;
> }
> array[offset].value = v;
> array[offset].mark = 1;
> producerIndex++;
> return true;


Given the above, this would likely need to be:

array[offset] = new Cell<>(v,1);

Due to the memory model requirements setting the mark field must be at
> least ordered. In an AtomicReferenceArray, I'd use lazySet(offset) which
> does the necessary barriers. Here, I either make mark volatile or have a
> VarHandle point to it. I'm not sure if I will be able to do this within the
> same JDK version at the moment.


Well, in this particular case you can make producerIndex++ have a
store-store fence, but I agree with the general premise.  Perhaps
VarHandle/Arrays 2.0 will provide something here, or barring that, a manual
Unsafe/Fence storeFence() type of thing would suffice.

On Wed, Nov 18, 2015 at 11:22 AM, Dávid Karnok <akarnokd at gmail.com> wrote:

> Let's assume I have a value type named cell:
>
> valuetype Cell<any T> {
>    public T value;
>    public int mark;
> }
>
> and a power-of-2 array of cells:
>
> Cell<any T>[] array;
>
>
> having Cell with final fields is useless here because then I have a
> constant array and not a queue.
>
> This array forms the basis of my bounded, single-producer single-consumer
> queue.
>
> The implementation of offer(T) looks like this:
>
> offset = producerIndex & (array.length - 1)
> if (array[offset].mark != 0) {
>     return false;
> }
> array[offset].value = v;
> array[offset].mark = 1;
> producerIndex++;
>
> return true;
>
> Due to the memory model requirements setting the mark field must be at
> least ordered. In an AtomicReferenceArray, I'd use lazySet(offset) which
> does the necessary barriers. Here, I either make mark volatile or have a
> VarHandle point to it. I'm not sure if I will be able to do this within the
> same JDK version at the moment.
>
> Since poll() can no longer return null to indicate emptiness, I need a new
> API method with the following definition to make it type-agnostic:
>
> boolean poll(Consumer<? super T> consumer);
>
> which calls the consumer with the available value and returns true or
> returns false if the queue is empty.
>
> SpscArrayPrimitiveQueue shouldn't encounter null because it gets only
> instantiated when the SpscArrayAnyQueue instantiation is replaced by it.
> This happens when the programmer explicitly declares the type parameter to
> be a primitive. From then on, he/she can't use nulls with Queue<int>
> because the compiler forbids it.
>
> Somehow I doubt it will be possible to dispatch on the kind of T at
> runtime from within Java:
>
> <any T> AnyQueue<T> createQueue() {
>    if (T instanceof class) {
>       return (AnyQueue<T>)new SpscArrayRefQueue<(class)T>();
>    } else
>    if (T instanceof valuetype) {
>       return (AnyQueue<T>)new SpscArrayPrimitiveQueue<(valuetype)T>();
>    }
>    throw new IllegalArgumentException();
> }
>
>
> 2015-11-18 16:28 GMT+01:00 Vitaly Davidovich <vitalyd at gmail.com>:
>
>>  However, I'm not sure if it will be possible
>>> to do lazySet on either the value or the mark word
>>
>>
>> why not? because value types must have final fields?
>>
>> q can have an SpscArrayPrimitiveQueue<int> implementation returned if T
>>> turns out to be int or SpscArrayRefQueue<T> for ref types?
>>
>>
>> how would your SpscArrayPrimitiveQueue<int> handle null values?
>>
>> On Wed, Nov 18, 2015 at 9:59 AM, Dávid Karnok <akarnokd at gmail.com> wrote:
>>
>>> I'm not sure about the default null-indicator because every time a queue
>>> is
>>> needed in our library, that can serve a source with unique choice of a
>>> default-null value. It is unlikely the users of the library want or can
>>> specify that all the time.
>>>
>>> Of course, I can define a value type Cell<any T> where a mark word is
>>> packed with the actual value. However, I'm not sure if it will be
>>> possible
>>> to do lazySet on either the value or the mark word because volatile write
>>> adds quite an overhead to an Spsc queue. The second problem is alignment
>>> in
>>> Cell because Java doesn't have smaller than int size atomics (unlike C#),
>>> i.e., Cell<short> should be aligned in a way the mark word is properly
>>> accessible on all platforms.
>>>
>>> Even if the poll() problem is solved by a new Queue interface (AnyQueue),
>>> this common implementation I believe is still puts to much burden on a
>>> reference-typed instance.
>>>
>>> My question is, will there be some infrastructure (at runtime?) that
>>> let's
>>> a library customize what
>>>
>>> AnyQueue<T> q = new SpscArrayAnyQueue<>();
>>>
>>> q can have an SpscArrayPrimitiveQueue<int> implementation returned if T
>>> turns out to be int or SpscArrayRefQueue<T> for ref types?
>>>
>>>
>>>
>>> 2015-11-18 15:24 GMT+01:00 Richard Warburton <
>>> richard.warburton at gmail.com>:
>>>
>>> > Hi,
>>> >
>>> > We are using the SpscArrayQueue (extends Queue<T>) from JCTools quite
>>> often
>>> > > in our library which exploits null as an indicator if the queue is
>>> full
>>> > or
>>> > > not. However, this won't work in case of a Queue<any T> because for
>>> > > primitives, zero is a valid value.
>>> > >
>>> > > I see two options:
>>> > >
>>> > >   - use wider primitive and atomics-acessible types: byte -> int,
>>> char ->
>>> > > int, short -> int, int -> long, float -> long, double -> 2 slots
>>> long and
>>> > > long -> 2 slots of long
>>> > >   - don't use fast-flow and go back to producer-consumer index
>>> > comparison.
>>> > >
>>> > > In either case, the internals and the usage have to be changed
>>> > drastically,
>>> > > i.e., switch to AtomicLongArray, how to indicate the queue is
>>> actually
>>> > > empty when calling poll(), etc. Perhaps a new queue interface is
>>> > necessary
>>> > > where poll returns a boolean indicator and calls a Consumer if the
>>> data
>>> > is
>>> > > there.
>>> > >
>>> > > The examples I saw regarding valhalla showed List<any T> where I'd
>>> guess
>>> > > the internals of the ArrayList can be altered in a straightforward
>>> manner
>>> > > but I don't see how this could happen if the algorithm itself has to
>>> > change
>>> > > based on what primitive T is.
>>> > >
>>> > > What are the plans for supporting such kind of specializations?
>>> >
>>> >
>>> > As Vitaly says you can have a value type that represents
>>> presence/absence
>>> > in your backing array.
>>> >
>>> > Another option is having a "missing" value. This is the approach that
>>> I use
>>> > when writing/using primitive collections. There always seems to be a
>>> number
>>> > value that you can using to represent a missing element whenever I've
>>> used
>>> > primitive specialized collections. That missing value can be used where
>>> > null is used for reference types.
>>> >
>>> > .NET has a "default(T)" construct where default some value is
>>> constructed
>>> > for a type, eg 0 for primitives, null for references which can used as
>>> a
>>> > missing value or as a way to initialise backing arrays.
>>> >
>>> > regards,
>>> >
>>> >   Richard Warburton
>>> >
>>> >   http://insightfullogic.com
>>> >   @RichardWarburto <http://twitter.com/richardwarburto>
>>> >
>>>
>>>
>>>
>>> --
>>> Best regards,
>>> David Karnok
>>>
>>
>>
>
>
> --
> Best regards,
> David Karnok
>


More information about the valhalla-dev mailing list