Primitive Queue<any T> considerations

[Brian Goetz]

Having null as a universal sentinel is a darn convenient thing. Having 
that taken away is going to make life harder for some data structures.  
You've already identified a few ways to do that; pick a different 
algorithm, use a side-table to indicate special conditions like empty, 
or widen the data to include enough space to stuff a boolean.  (Optional 
has this same issue; the footprint of Optional can be a single ref but 
needs an extra bit for primitives like int which use all their bit 
patterns.)

Some value types have unused bit patterns which could be pressed into 
service as sentinels, but that doesn't help us with int, long, xy-point, 
complex, tuple of ints, etc -- these all use all the bit patterns to 
encode valid values.

As Richard points out, .NET has a default(T) -- which gives you the 
all-zero bit pattern for a given type (the value to which array elements 
and fields are initialized) -- and we will have the same (currently we 
spell this T.default.)  For some situations, this might be enough of a 
sentinel and requires no extra hoop jumping (though obviously zero is a 
useful integer and so it might not be suitable.)

Our current thoughts are to support some sort of 
hand-written-specialization for specific instantiations of a 
parameterized type, possibly at both method and whole-class 
granularities.  For example, one can write an ArrayList<any T> class, 
but one might (or might not, there's room for disagreement) want 
ArrayList<boolean> to use a bit vector rather than a boolean[].  
Similarly, the literature is full of specialized algorithms for hash 
maps from int to int.

Applying this to Optional, which is similar to your situation, there 
could be a generic implementation (which used a side boolean to indicate 
presence) and a specialized implementation for Optional<ref T>, which 
omits the boolean and uses null as the sentinel.

tl;dr: we're aware of this issue and have integrated it into the 
requirements set :)

On 11/18/2015 8:27 AM, Dávid Karnok wrote:
> Hello,
>
> 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?
>