1

In which cases compiler can reorder instructions by its own will?

For example, can they be reordered in case when synchronization primitives like mutexes are involved like in the following example:

void foo()
{
  int x = 0;
  {
    std::lock_guard<std::mutex> lock(g_mutex);
    std::cout << x << std::endl;
  }
  x = 1;
}

Can this code print 1 instead of 0 at some conditions?

And will any shared variables be actually modified after calling unlock on such mutex so it's guaranteed that other threads will see the updated values of such variables instead of the probably-cached ones?

Does it apply to all well-known synchronization primitives like critical sections, mutexes etc?

Is it also guaranteed that the following code (assuming that Thread 1 will acquire the specified mutex before Thread 2) will always print 1 instead of some cached value (for example, 0):

int some_global_variable = 0;

// Thread 1
mutex.lock();
some_global_variable = 1;
mutex.unlock();

// Thread 2
mutex.lock();
std::cout << some_global_variable << std::endl;
mutex.unlock();

If so, why? Where does it stated?

FrozenHeart
  • 19,844
  • 33
  • 126
  • 242
  • 3
    This question is a little confusing, you tagged it multithreading but your example concerns the output of `cout` of a automatic variable which implies the question is really about a single threaded case. – Shafik Yaghmour Nov 11 '15 at 14:54
  • If this is really the single threaded case then this question [For { A=a; B=b; }, will “A=a” be strictly executed before “B=b”?](http://stackoverflow.com/q/25847349/1708801) covers the key details. – Shafik Yaghmour Nov 11 '15 at 14:58
  • 1
    Your question is **still** completely unclear, and now you’ve added a second, unrelated question which has a completely different answer with a completely different explanation. Really, the two code examples have got nothing to do with each other, and the word “mutex” is a big red herring here. – Konrad Rudolph Nov 11 '15 at 16:31

2 Answers2

2

No, it can't. One of the distinct features of mutex is that code reordering does not cross mutex aquisition or release.

On a side note, critical section is NOT a synchronization primitive in Posix model (on which C++ thread stuff is largely based). Instead, it is a logical term, meaning the piece of code which has to be protected.

EDIT

Answering second question.

Yes, it is guranteed that in case thread 1 aquires the mutex first the value printed will be 1. The reason for this explicit gurantee is a a combination of mutex low-level code and hardware implementation of this code. Although not stated, I would assume two pieces of code belong to two different functions (for simplicity). Note, that in this case no compiler optimizations will be at play regardless of mutexes - there are two independent functions, and compiler optimizations are local to the functions.

On a mutex level, any implementation of mutex would include a direct or indirect instruction to put a memory fence before and after mutex is aquired. Thos instrucion will instruct hardwre to fresh all it's caches and thus no cached value would be used.

SergeyA
  • 61,605
  • 5
  • 78
  • 137
  • And what about other synchronization primitives like critical sections? – FrozenHeart Nov 11 '15 at 14:44
  • 1
    Downvoters, make a habit of explaining yourself. Otherwise downvote is not helpful for anybody. – SergeyA Nov 11 '15 at 14:45
  • 2
    While the result is true, that would obviously also be the case without any locks whatsoever. Single threaded behavior without deadlocks must not be changed by any optimization (except a few exceptions) – Voo Nov 11 '15 at 14:45
  • So, it **can** be reordered if I change `mutex` in this example to critical sections? – FrozenHeart Nov 11 '15 at 14:46
  • @Voo, I agree with that. The code as asked is not very illustrative, since it has cout between two assignments. However, since I have a history of the question, I did answer in a more generic way. – SergeyA Nov 11 '15 at 14:51
  • 2
    @FrozenHeart, no. The code as written will not be reordered, since you have a an `operator << ` between two assignments. Calls of opaque functions or functions with known side-effects (and `<<` could be either of those depending on implementations) will always serve as reordering barrier. – SergeyA Nov 11 '15 at 14:52
2

In which cases compiler can reorder instructions by its own will?

In cases where the compiler is able to prove that reordering does not have side effects which are observable within the same thread.

Can this code print 1 instead of 0 at some conditions?

No.

Certainly not due to compiler reordering instructions because x is both read and written to in the same thread and changing the order so that 1 is printed would obviously be an observable side-effect.

Also not due to another thread writing to x because it is an automatic variable and you don't at any point take it's address, so its easy to prove that it can not be shared with other threads.

eerorika
  • 232,697
  • 12
  • 197
  • 326
  • Importantly, it's only forbidden to change the side effects which are observable in the same thread. Reordering that changes the effects observable from other threads is generally permitted, and requires use of atomics or synchronization to prevent. – Ben Voigt Nov 11 '15 at 15:09
  • @BenVoigt I added the important detail to my answer. – eerorika Nov 11 '15 at 15:11
  • One might want to mention the few exceptions that C++ (to the best of my knowledge really the only language that specifies these) has to the general "not observable in same thread" rule. – Voo Nov 11 '15 at 15:13
  • @user2079303 `In cases where the compiler is able to prove that reordering does not have side effects which are observable within the same thread.` but mostly I read this reordering is cause side effects on multithreading, so why still this algorithm exists ? it has potential to make side effects in multithreading. Also multi-threading is so common. – FZE Mar 22 '16 at 16:58