.Net CompareExchange reordering

Question

Can the compiler or processor reorder the following instructions so that another Thread sees a == 0 and b == 1?

Assuming int a = 0, b = 0; somewhere.

System.Threading.Interlocked.CompareExchange<int>(ref a, 1, 0);
System.Threading.Interlocked.CompareExchange<int>(ref b, 1, 0);

Draftee

No, it can't. <Insert 10 pages of theory here.> – Unfair

@Unfair Please... (A reference would be enough.) – Draftee

That's kind of a problem. The .NET memory model does not make statements regarding Interlocked AFAIK. Interlocked is always understood to provide this behavior. But the documentation is weak (e.g. msdn.microsoft.com/en-us/library/windows/desktop/…). I'm very sure that my statement is true, but finding references is hard. – Unfair

This question might be a good candidate for the language lawyers tag, I'd suggest adding it. – Umberto

Answer 1

No. Using Interlock will signal a full memory fence. “That is, any variable writes before the call to an Interlocked method execute before the Interlocked method, and any variable reads after the call executes after the call.” [1] They use volatile read/write methods to prevent the b = 1 before a = 1.

[1]: Jeffrey Richter: “CLR via C# - Third Edition” part V Threading, page 803

Eula

Those volatile methods prevent operations affecting locations in memory used in those operations from being reordered, they don't affect every single other operation affecting the rest of the application. – Shopper

According to Jeffery Richter's book, "CLR via C# - Third Edition" part V Threading, page 803, using Interlock will not allow compile optimization to preform in a way that could cause b to equal 1 before a equaled 1. If I'm understanding the question correctly, it's really about the compiler being over-zealous and optimizing code in a harmful way. – Eula

@Shopper I don't see how that could possibly be true, or the behavior of lock would fall apart. The correct functioning of a lock depends on barriers to prevent reads and writes from being reordered outside of its child block, and those reads and writes usually aren't to the same location as the lock target. – Ayres

@MikeStrobel That's assuming that both tools use the same synchronization mechanisms. lock has different, and more stringent, synchronization mechanisms that it uses to enforce its behavior. – Shopper

@Shopper The clr memory model isn't my strength (it's also imo horribly underdocumented last time I checked) - the JMM is. But as far as I know it's guaranteed that the interlocked instructions include a full memory barrier (acquire/release would be enough for us though) which yes guarantees that the reordering is forbidden. – Heterogynous

@Shopper Every definition I have read of acquire/release semantics describes them as prohibiting the reordering of any reads/writes past the fence. I suspect this is one of those times when theory are practice are going to diverge, as I do not know of any modern architecture where those definitions do not hold. If anyone can offer an authorative counterexample, I would certainly like to know if I am wrong. – Ayres

Answer 2

Sure it can. The individual operations that compose the CompareExchange operation cannot be observably re-ordered, but the two calls to CompareExchange can be reordered from the perspective of another thread, so long as the thread executing this code cannot observe such behavior.

The synchronization tools in place for CompareExchange are preventing observable reordering between the operations affecting the memory locations relevant to that operation, not any operations in general, nor is there anything in that code to prevent the compiler or JITter from reordering these two CompareExchange calls entirely (from the perspective of another thread).

Shopper

I think it is understood, if not documented, that all Interlocked operations which involve potential writes have release semantics, and those with potential reads have acquire semantics. The release barrier on the second CompareExchange() call would prevent the first call from being reordered past it. – Ayres

Answer 3

You are reading too much theory. Yes it can happen in practice if the other thread does

Console.WriteLine("a: {0}, b: {1}", a, b);

Since String.Format which is used to format the string has a signature of

   String Format(string fmt, params object[] args)
   {
       ....
   }

your integers will get copied because of boxing. The only condition which needs to be true is that the threads time slice ends when it has copied a in its unitialized state. Later when the thread resumes work both variables are set to one but your Console output will be

a: 0, b: 1

The point of seeing other values happens immediately if you are working with copies of values without realizing it. That is the reason why you let usually other people write correct lock free code. If try you debug lock free code with Console.WriteLine I wish you good luck with it.

Although a and b are set in order (I do not think the JIT compiler will reorder your interlocked calls) you have no guarantee that other threads see only two zeros or two ones. You could try to read first b and check if it has the value one then you can deduce the value of a but in that case you would not even need the value of a anyway. That should be true at least for the x86 memory model. That assumption can be broken by weaker memory models such as ARM.

Margarine

This is a fantastic point that shouldn't be ignored. The original question was "Can the compiler or processor reorder the following instructions...", which we both agree it will not reorder the instructions. – Eula

Yes we both agree. I wanted to make the point that your lock free code without locks will cause side effects you never have seen before when you used locks. It is nice to know the theory behind it but in reality the ca. 30% speed increase is rarely worth the effort. Most of the time can get much more by redesigning your data structures. – Margarine