Primitive Queue<any T> considerations

Dávid Karnok akarnokd at gmail.com
Wed Nov 18 14:59:45 UTC 2015


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


More information about the valhalla-dev mailing list