Primitive Queue<any T> considerations

Vitaly Davidovich vitalyd at gmail.com
Wed Nov 18 15:28:13 UTC 2015


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


More information about the valhalla-dev mailing list