Primitive Queue<any T> considerations

Brian Goetz brian.goetz at oracle.com
Wed Nov 18 20:36:50 UTC 2015


In this respect, large values offer nothing new over longs and doubles.  
In the presence of a data race, tearing and reordering is possible.  
Reads and writes of values have the same JMM characteristics as any 
other read or write.

Note that while values are in part about getting flatter data layouts, 
we do not plan to offer anything in the way of fine-grained layout 
control, such as allowing for explicit alignment requirements.  (Though 
other efforts, such as Project Panama, may have something to offer here).

On 11/18/2015 3:25 PM, Dávid Karnok wrote:
> In my queue case, I'm not worried about payload tearing but rather memory
> reordering around the mark field. The analogy is the classical concurrency
> quiz question:
>
> Thread A:
>
> a = 42;
> b = 1;
>
> Thread B:
>
> if (b == 1)
>     println(a);
>
>
> If b is volatile or is accessed with Unsafe.getVolatile and putOrdered then
> it doesn't matter how large a is or in what order a's structure is updated
> as long as it stops and flushes when b is set to 1.
>
> If the valuetype is immutable and assignment is memcopy then b can't be
> part of that structure and has to be a separate array of int at least (if
> no byte-atomics). The two arrays can now be anywhere in memory and if one
> wants to avoid false sharing, the memory usage increases as well. On a
> sidenote, without knowing the size of a, it's hard to pad the array to
> avoid false sharing between adjacent elements.
>
>
> 2015-11-18 20:57 GMT+01:00 Vitaly Davidovich <vitalyd at gmail.com>:
>
>> FWIW, CLR explicitly states that value type assignments larger than machine
>> word size are not atomic.  Or rather, it guarantees that any value type of
>> size <= machine word will be atomic (modulo someone playing around with
>> struct layout manually).  As far as I know, there's never been much fuss
>> about this stipulation.
>>
>> On Wed, Nov 18, 2015 at 2:15 PM, Timo Kinnunen <timo.kinnunen at gmail.com>
>> wrote:
>>
>>> Hi,
>>>
>>>
>>>
>>> That’s a good question. How would arbitrary-sized values be assigned into
>>> an array without any other thread observing the value halfway between two
>>> states with its invariants not holding?
>>>
>>>
>>>
>>> As is mentioned in the JLS in 17.6: “One consideration for
>> implementations
>>> of the Java Virtual Machine is that every field and array element is
>>> considered distinct; updates to one field or element must not interact
>> with
>>> reads or updates of any other field or element.” This probably has to be
>>> weakened in the same way as non-atomic reads/writes of long.
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> Sent from Mail <http://go.microsoft.com/fwlink/?LinkId=550986> for
>>> Windows 10
>>>
>>>
>>>
>>>
>>>
>>>
>>> *From: *Vitaly Davidovich
>>> *Sent: *Wednesday, November 18, 2015 19:56
>>> *To: *MacGregor, Duncan (GE Energy Management)
>>> *Cc: *valhalla-dev at openjdk.java.net
>>> *Subject: *Re: Primitive Queue considerations
>>>
>>>
>>>
>>>
>>>
>>> As discussed upthread, how would that operation be atomic for arbitrarily
>>>
>>> sized value types?
>>>
>>>
>>>
>>> On Wed, Nov 18, 2015 at 1:53 PM, MacGregor, Duncan (GE Energy
>> Management) <
>>> duncan.macgregor at ge.com> wrote:
>>>
>>>
>>>
>>>> On 18/11/2015, 16:22, "valhalla-dev on behalf of Dávid Karnok"
>>>> <valhalla-dev-bounces at openjdk.java.net on behalf of akarnokd at gmail.com
>>>
>>>> wrote:
>>>>> Let's assume I have a value type named cell:
>>>>> valuetype Cell<any T> {
>>>>>    public T value;
>>>>>    public int mark;
>>>>> }
>>>>> and a power-of-2 array of cells:
>>>>> Cell<any T>[] array;
>>>>> having Cell with final fields is useless here because then I have a
>>>>> constant array and not a queue.
>>>> Maybe I¹m not following you here but the fact fields on a Cell are
>> final
>>>> does not stop you from replacing one Cell in array with a new Cell,
>> just
>>>> as you can replace individual ints in an array of ints.
>>>> So you offset method would be more like
>>>> offset = producerIndex & (array.length - 1)
>>>> if (array[offset].mark != 0) {
>>>>      return false;
>>>> }
>>>> array[offset] = Cell(value, 1);
>>>> producerIndex++;
>>>> return true;
>>>> And that operation on the array will be guaranteed to be atomic (though
>>>> probably needs a compare and swap in case another thread is trying to
>> do
>>>> the same thing).
>>>> Duncan.
>>>
>>>
>>>
>>>
>
>



More information about the valhalla-dev mailing list