Primitive Queue<any T> considerations

[Dávid Karnok]

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



-- 
Best regards,
David Karnok