Instruction Re-Ordering

Question

I have a question about legal instruction re-ordering in C#/.NET.

Let's start with this example. We have this method defined in some class, where _a, _b, and _c are fields.

int _a;
int _b;
int _c;
void Foo()
{
   _a = 1; // Write 1
   _b = 1; // Write 2
   _c = 1; // Write 3
}

And our calling environment would look something like this.

//memory operations
ClassInstance.Foo();
//memory operations

I'm wondering what kind of legal instruction re-orderings are possible when this method call gets inlined vs a function call. More specifically, I'm wondering if/when is it legal to re-order memory operations within Foo(), with memory operations outside of it (from our previous example, the //memory operations).

Also, does a function call(no inline), in a sense, "generate memory barriers". As in, memory operations that happen before or after the function call cannot be re-ordered with memory operations within the function call.

If so, would it still have this "memory barrier" behavior when it gets inlined by the compiler?

Are you asking what known bugs are there in the compiler that might *get* you here? — johnb003, Mar 15 '14 at 06:29
Maybe it's just me, but it seems crazy to me that you're so concerned about low level memory optimizations in a managed memory environment. — johnb003, Mar 15 '14 at 06:30
@johnb003. No, not compiler bugs. The compiler performs many optimizations during compilation and runtime, such as inlining function calls, re-ordering memory operations, hoisting reads out of loops, etc. I'm also fairly interested in the topic. Learning the concepts in the managed environment will still transfer over to when I make the move to C++, I'd just need to familiarize myself with new memory models. — user2738477, Mar 15 '14 at 06:34
and as such, should not introduce side effects in simple code like this, unless there's a serious bug. — johnb003, Mar 15 '14 at 06:35
Well in a single threaded scenario it wouldn't, but as soon as you're in a multi threaded scenario, the instruction re-ordering may or may not alter behaviour. — user2738477, Mar 15 '14 at 06:42
@user2738477 No, it would not. Memory barriers happen in .NET only in well defined places, either implicit (lock statement, for example) or explicit (there is a memory barrier class actually). You need them, YOU put them in. — TomTom, Mar 15 '14 at 06:47

score 6 · Accepted Answer · edited Jun 20 '20 at 09:12

The C# Language Specification can help answer this. The section on Execution Order has this to say:

3.10 Execution order

Execution of a C# program proceeds such that the side effects of each executing thread are preserved at critical execution points. ....The execution environment is free to change the order of execution of a C# program, subject to the following constraints:

Data dependence is preserved within a thread of execution. That is, the value of each variable is computed as if all statements in the thread were executed in original program order.

Initialization ordering rules are preserved (§10.5.4 and §10.5.5).

The ordering of side effects is preserved with respect to volatile reads and writes (§10.5.3).

(there is more that I've left out; the spec is quite readable so I suggest taking a look if you really want to get into the gritty details).

Essentially, the rules can be thought of as "the jitter may rearrange the execution order as long as the difference is not observable by the executing thread". But, other threads may observe the differences. In a post by Eric Lippert on the Coverity blog, he says:

...the CPU may as an optimization choose to [rearrange execution order] provided that doing so is not detectable by the current thread. But that fact could be observed by another thread...

So, if the order of operations is important for other threads as well as the current thread, then you'll need to create a "critical execution point"; the easiest way to do this is probably to surround the statements with a lock.

Thanks for the shout-out. I'll be following that blog post up with one on ways that reordering of virtual reads and writes can mess up program invariants, in about two weeks, — Eric Lippert, Mar 16 '14 at 01:02
The link to Eric Lippert's post appears broken. Looks like it's here (https://ericlippert.com/2014/03/12/can-i-skip-the-lock-when-reading-an-integer/) but the links on that page seem broken too. Has something been discontinued? — bornfromanegg, Jul 03 '17 at 08:59
@bornfromanegg Coverity was purchased by Synopsys and it seems they didn't keep the blog working. That's too bad, it had a lot of good information. I updated the link to point to the Internet Archive copy. — Stephen Jennings, Jul 06 '17 at 17:03

score 3 · Answer 2 · edited May 23 '17 at 10:29

When discussing instruction reordering keep in mind that there are usually two (or more) threads in play. The Execution Order clause in the specification is basically the formal definition of the intuitive idea that a thread should perceive side-effects in the same order as specified by the programmer. Applications would have non-deterministic behavior without it.

The real crux of the topic is how other threads perceive the side-effects. This is where that 3rd point about volatile reads and writes comes into play. It just so happens that all writes (in all versions of the .NET Framework that I am aware of) have release-fence semantics.

I like to use an arrow notation to help visualize the constraints placed on instruction reordering optimizations. I use an ↑ arrow to indicate a release-fence and a ↓ arrow to indicate an acquire-fence. Nothing is allowed to float down past an ↑ arrow or up past an ↓ arrow. Think of the arrow head as pushing everything away. Using this arrow notation and assuming writes still have release-fence semantics then your code would look like this.

void Foo()
{
   ↑
   _a = 1; // Write 1
   ↑
   _b = 1; // Write 2
   ↑
   _c = 1; // Write 3
}

Hopefully it is now easier to see that any of the writes is not allowed to float down past another one because an arrow blocks its movement. What this means is that other threads will, in fact, perceive these writes in the same order as they occurred in the thread executing Foo.

I describe other ways instructions can get reordered in questions here, here, here, here, and especially here.

Could you please give some details/sources on "It just so happens that all writes (in all versions of the .NET Framework that I am aware of) have release-fence semantics"? It's a powerful statement for a mixture of architectures. — Sergey.quixoticaxis.Ivanov, Feb 02 '17 at 12:50
@Sergey.quixoticaxis.Ivanov Section 3.10 Execution Order in [C# Language Specification Version 5.0](https://www.microsoft.com/en-us/download/confirmation.aspx?id=7029) - _"Execution of a C# program proceeds such that the side effects of each executing thread are preserved at critical execution points. A side effect is defined as a read or write of a volatile field, **a write to a non-volatile variable,** a write to an external resource, and the throwing of an exception."_, emphasis mine. — laika, Apr 30 '18 at 10:02

Instruction Re-Ordering

2 Answers2