Primitive Queue<any T> considerations
brian.goetz at oracle.com
Wed Nov 18 16:26:03 UTC 2015
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
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:
> 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
> 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?
More information about the valhalla-dev