The Interlocked on the Edge of Forever

William Stacey [C# MVP] wrote:

> So are you saying the JIT can reorder these two lines:
> int a = x;
> int b = y;
>
> Like so:
> int b = y;
> int a = x;

Yes, if x and y are not volatile locations. The language of the spec is
that reads and writes to volatile locations are the only observable side
effects of memory access; memory accesses may be arbitrarily reordered
if they aren't volatile. For example, if the value of y has been loaded
to a register because it was used somewhere before the line 'int a =
x;', then the value of y used in the line 'int b = y;' may predate the
actual in-memory value of x, because the value may be used from the
register, rather than freshly loading it from memory. So, volatile can
inhibit these kinds of optimizations (avoiding redundant loads).

There's more to it than that, volatile reads have acquire semantics,
volatile writes release semantics. That has stronger guarantees than
just inhibiting optimization, as it affects e.g. write buffer reordering
in some processors.

-- Barry

--
http://barrkel.blogspot.com/

William Stacey [C# MVP] <william.stacey> wrote:
> So are you saying the JIT can reorder these two lines:
> int a = x;
> int b = y;
>
> Like so:
> int b = y;
> int a = x;

Exactly, so long as there aren't any memory barriers in the way. Memory
barriers (which include operations with volatile locations) stop the
JIT from moving memory operations beyond the barrier.

It's unfortunate that the CLI spec isn't nearly as clear as it might be
about all this, but Vance Morrison wrote a great MSDN article about the
..NET 2.0 model (which is stricter than the CLI spec):
http://msdn.microsoft.com/msdnmag/is.../MemoryModels/

--
Jon Skeet - <skeet@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

William Stacey [C# MVP] <william.stacey> wrote:
> So are you saying the JIT can reorder these two lines:
> int a = x;
> int b = y;
>
> Like so:
> int b = y;
> int a = x;

Exactly, so long as there aren't any memory barriers in the way. Memory
barriers (which include operations with volatile locations) stop the
JIT from moving memory operations beyond the barrier.

It's unfortunate that the CLI spec isn't nearly as clear as it might be
about all this, but Vance Morrison wrote a great MSDN article about the
..NET 2.0 model (which is stricter than the CLI spec):
http://msdn.microsoft.com/msdnmag/is.../MemoryModels/

--
Jon Skeet - <skeet@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

Here is some more food for the party:
http://msdn2.microsoft.com/en-us/library/ms686355.aspx

Here he states the compiler will not re-order volatile variable access,
However these operations still *could be re-ordered by the processor. In
fact, he shows correcting this issue with an Interlocked operation. This
article also state that Interlocked functions *ensure appropriat barriers
for memory ordering. So (at least for this example) it would seem
Interlocked provides as good or better symatics as the volatile example (and
also prevents CPU re-order). However, I am not sure any this matters for
this example, as in both cases you still have the race issue. R1 can read
x, then W1 writes x and y, then R1 reads y - or various combinations of
same. So some form of critical section around both x and y would seem to be
the proper behavior, unless we don't care about x or y in respect to each
other (i.e. simple counters that are not treated as a set).

--
William Stacey [C# MVP]
PCR concurrency library: www.codeplex.com/pcr
PSH Scripts Project www.codeplex.com/psobject


"Jon Skeet [C# MVP]" <skeet@pobox.com> wrote in message
news:MPG.20a8e1115b0c872180@msnews.microsoft.com.. .
| William Stacey [C# MVP] <william.stacey> wrote:
| > So are you saying the JIT can reorder these two lines:
| > int a = x;
| > int b = y;
| >
| > Like so:
| > int b = y;
| > int a = x;
|
| Exactly, so long as there aren't any memory barriers in the way. Memory
| barriers (which include operations with volatile locations) stop the
| JIT from moving memory operations beyond the barrier.
|
| It's unfortunate that the CLI spec isn't nearly as clear as it might be
| about all this, but Vance Morrison wrote a great MSDN article about the
| .NET 2.0 model (which is stricter than the CLI spec):
| http://msdn.microsoft.com/msdnmag/is.../MemoryModels/
|
| --
| Jon Skeet - <skeet@pobox.com>
| http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
| If replying to the group, please do not mail me too

Here is some more food for the party:
http://msdn2.microsoft.com/en-us/library/ms686355.aspx

Here he states the compiler will not re-order volatile variable access,
However these operations still *could be re-ordered by the processor. In
fact, he shows correcting this issue with an Interlocked operation. This
article also state that Interlocked functions *ensure appropriat barriers
for memory ordering. So (at least for this example) it would seem
Interlocked provides as good or better symatics as the volatile example (and
also prevents CPU re-order). However, I am not sure any this matters for
this example, as in both cases you still have the race issue. R1 can read
x, then W1 writes x and y, then R1 reads y - or various combinations of
same. So some form of critical section around both x and y would seem to be
the proper behavior, unless we don't care about x or y in respect to each
other (i.e. simple counters that are not treated as a set).

--
William Stacey [C# MVP]
PCR concurrency library: www.codeplex.com/pcr
PSH Scripts Project www.codeplex.com/psobject


"Jon Skeet [C# MVP]" <skeet@pobox.com> wrote in message
news:MPG.20a8e1115b0c872180@msnews.microsoft.com.. .
| William Stacey [C# MVP] <william.stacey> wrote:
| > So are you saying the JIT can reorder these two lines:
| > int a = x;
| > int b = y;
| >
| > Like so:
| > int b = y;
| > int a = x;
|
| Exactly, so long as there aren't any memory barriers in the way. Memory
| barriers (which include operations with volatile locations) stop the
| JIT from moving memory operations beyond the barrier.
|
| It's unfortunate that the CLI spec isn't nearly as clear as it might be
| about all this, but Vance Morrison wrote a great MSDN article about the
| .NET 2.0 model (which is stricter than the CLI spec):
| http://msdn.microsoft.com/msdnmag/is.../MemoryModels/
|
| --
| Jon Skeet - <skeet@pobox.com>
| http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
| If replying to the group, please do not mail me too

William Stacey [C# MVP] wrote:

> Here is some more food for the party:
> http://msdn2.microsoft.com/en-us/library/ms686355.aspx
>
> Here he states the compiler will not re-order volatile variable access,
> However these operations still *could be re-ordered by the processor.

Volatile read has acquire semantics. Loads won't move before an acquire,
similarly, writes won't move after a release. These should be
implemented by CPU instructions, as explained in the article you linked
to, and aren't restricted to just compiler optimizations. This means
that volatile read on .NET is sufficient, because the CPU won't reorder
such that the second load moves before the first load, because of the
acquire semantics (aka read fence).

> In
> fact, he shows correcting this issue with an Interlocked operation. This
> article also state that Interlocked functions *ensure appropriat barriers
> for memory ordering.

The have full fence semantics (except the Interlocked*Acquire and
Interlocked*Release).

> So (at least for this example) it would seem
> Interlocked provides as good or better symatics as the volatile example (and
> also prevents CPU re-order).

Volatile also prevents CPU re-order, but asymmetrically: read causes
acquire, write causes release. The write side release means that e.g.
"publishing" a new instance to a static volatile variable won't have a
problem such that some fields in the instance aren't fully retired
before other threads could read the instance reference - writes won't
move ahead of the release / write fence.

-- Barry

--
http://barrkel.blogspot.com/

William Stacey [C# MVP] wrote:

> Here is some more food for the party:
> http://msdn2.microsoft.com/en-us/library/ms686355.aspx
>
> Here he states the compiler will not re-order volatile variable access,
> However these operations still *could be re-ordered by the processor.

Volatile read has acquire semantics. Loads won't move before an acquire,
similarly, writes won't move after a release. These should be
implemented by CPU instructions, as explained in the article you linked
to, and aren't restricted to just compiler optimizations. This means
that volatile read on .NET is sufficient, because the CPU won't reorder
such that the second load moves before the first load, because of the
acquire semantics (aka read fence).

> In
> fact, he shows correcting this issue with an Interlocked operation. This
> article also state that Interlocked functions *ensure appropriat barriers
> for memory ordering.

The have full fence semantics (except the Interlocked*Acquire and
Interlocked*Release).

> So (at least for this example) it would seem
> Interlocked provides as good or better symatics as the volatile example (and
> also prevents CPU re-order).

Volatile also prevents CPU re-order, but asymmetrically: read causes
acquire, write causes release. The write side release means that e.g.
"publishing" a new instance to a static volatile variable won't have a
problem such that some fields in the instance aren't fully retired
before other threads could read the instance reference - writes won't
move ahead of the release / write fence.

-- Barry

--
http://barrkel.blogspot.com/

"Barry Kelly" <barry.j.kelly> wrote

> There's more to it than that, volatile reads have acquire semantics,
> volatile writes release semantics. That has stronger guarantees than
> just inhibiting optimization, as it affects e.g. write buffer reordering
> in some processors.

I see that in CLI spec, but have you actually verified it? It is not
what I would expect and not what I have seen.

Oddly, I see that the Jitter even removes dead loads altogher.

Anyway, given the rationale in the CLI spec (hardware
register access), I don't see how this could possibly work in
a reasonably cheap way for the P4 memory model.

-hg

"Barry Kelly" <barry.j.kelly> wrote

> There's more to it than that, volatile reads have acquire semantics,
> volatile writes release semantics. That has stronger guarantees than
> just inhibiting optimization, as it affects e.g. write buffer reordering
> in some processors.

I see that in CLI spec, but have you actually verified it? It is not
what I would expect and not what I have seen.

Oddly, I see that the Jitter even removes dead loads altogher.

Anyway, given the rationale in the CLI spec (hardware
register access), I don't see how this could possibly work in
a reasonably cheap way for the P4 memory model.

-hg

William Stacey [C# MVP] <william.stacey> wrote:
> Here is some more food for the party:
> http://msdn2.microsoft.com/en-us/library/ms686355.aspx
>
> Here he states the compiler will not re-order volatile variable access,
> However these operations still *could be re-ordered by the processor.

Hmm. That sounds like it's a broken implementation then. Basically, if
the .NET CLR executes code in a way which violates the spec, the
implementation is flawed. If the processor could reorder things, the
CLR should make sure that that is invisible to the user, beyond what is
possible within the CLI spec.

I'd be interested to hear Joe Duffy's opinion on that part of the
article.

> In fact, he shows correcting this issue with an Interlocked operation. This
> article also state that Interlocked functions *ensure appropriat barriers
> for memory ordering. So (at least for this example) it would seem
> Interlocked provides as good or better symatics as the volatile example (and
> also prevents CPU re-order).

No - because only the thread which *calls* the Interlocked method knows
that interlocked is involved, whereas with volatile both the reading
thread *and* the writing thread know to use memory barriers. Of course,
if you use Interlocked in both threads, to both read *and* write the
value, then everything will be okay.

> However, I am not sure any this matters for
> this example, as in both cases you still have the race issue. R1 can read
> x, then W1 writes x and y, then R1 reads y - or various combinations of
> same. So some form of critical section around both x and y would seem to be
> the proper behavior, unless we don't care about x or y in respect to each
> other (i.e. simple counters that are not treated as a set).

If we care about atomicity, there needs to be some kind of locking.
If we only care that the change to y is seen after the change to x
(i.e. you can't see x=0, y=1) then volatile will do the job but I don't
believe that changing the variable with Interlocked and then reading it
directly in another thread is guaranteed to work.

--
Jon Skeet - <skeet@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too