Primitive Queue<any T> considerations

[Vitaly Davidovich]

>
> If value types are to be final, that's fine as long as assignment works,
> however, the purpose of the fast-flow algorithm to use the cell itself so
> there is only one cache miss. Even if producerIndex has release semantics,
> I have to read producerIndex in poll() for acquire semantics before reading
> the cell which now may yield two cache misses.


Yes, agreed.

If value types are final, that means the array-store and array-load have to
> be atomic in some way for fast-flow to work, i.e., mark has to be written
> last and read first in the structured array


Yes, this is a tough one I think (i.e. cannot write arbitrary sized value
types atomically).  In .NET, this is simply not allowed, e.g. you cannot do
atomic operations on a DateTime, even though it happens to be 8 bytes.  In
those cases, people fallback to using the underlying primitive (long, in
this case) and convert to the value type on the fly.  This isn't too bad
since it becomes an internal implementation detail only.  If you cannot
encode the required state into the widest atomic unit, then you're SOL
unfortunately.

(In addition, not sure where or how Gil Tene's ObjectLayout would fit in
> because that proposal allows field mutation but forbids whole cell
> assignment.)


Not sure either.  I know Volker Simonis from SAP was prototyping JIT
support for this, but no clue where this proposal is headed, if anywhere.

On Wed, Nov 18, 2015 at 12:00 PM, Dávid Karnok <akarnokd at gmail.com> wrote:

> Thanks Brian & Vitaly.
>
> Just a few final remarks and I'll consider my question answered.
>
> If value types are to be final, that's fine as long as assignment works,
> however, the purpose of the fast-flow algorithm to use the cell itself so
> there is only one cache miss. Even if producerIndex has release semantics,
> I have to read producerIndex in poll() for acquire semantics before reading
> the cell which now may yield two cache misses.
>
> If value types are final, that means the array-store and array-load have
> to be atomic in some way for fast-flow to work, i.e., mark has to be
> written last and read first in the structured array.
>
> (In addition, not sure where or how Gil Tene's ObjectLayout would fit in
> because that proposal allows field mutation but forbids whole cell
> assignment.)
>
> 2015-11-18 17:43 GMT+01:00 Vitaly Davidovich <vitalyd at gmail.com>:
>
>> 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.
>>
>>
>> Being able to specialize ArrayList<boolean> as bit vector, ala
>> std::vector<bool> in C++, would be great.  The more general feature of
>> being able to specialize internals is exciting to hear, assuming that comes
>> to fruition.
>>
>> 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.
>>
>>
>> Yes, this would be great as well; Rust does this type of thing, for
>> example.
>>
>> On Wed, Nov 18, 2015 at 11:26 AM, Brian Goetz <brian.goetz at oracle.com>
>> wrote:
>>
>>> 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?
>>>>
>>>>
>>>
>>
>
>
> --
> Best regards,
> David Karnok
>