Primitive Queue<any T> considerations

Wed Nov 18 16:22:39 UTC 2015

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