深入探索并发编程系列(六)-编译期间内存乱序

写在最前：掌握并发编程非常困难，除了多读书、多写代码、多调试、多和朋友讨论，别无他法。

在众多资料中，preshing这个博客质量很高，经过和作者邮件沟通获得授权后，我们着手翻译了他的一系列文章并加上注释，构成了“深入探索并发编程系列”。翻译，力求精准又易懂；注释，力求全面又有益，希望对大家理解这个系列有所帮助，也希望可以为社区做点贡献。

在写完C/C++代码之后与CPU执行之前，代码会根据一定规则在与内存的交互过程中发生乱序。内存执行顺序的变化在编译器(编译期间)和cpu(运行期间)中都会发生，其目的都是为了让代码运行的更快。

编译器开发者和cpu厂商都遵守着内存乱序的基本原则，简单归纳如下：

不能改变单线程程序的行为

这条原则带来的影响就是，写单线程代码的程序员都忽视了内存乱序的影响。在多线程编程中，由于互斥量，信号量和事件都在设计的时候都阻止了它们调用点中的内存乱序，内存乱序的影响同样被忽视了。只有当使用无锁(lock-free)^注1技术时–内存在线程间共享而没有任何的互斥量-内存乱序的效果才会显露无疑.

要提醒你的是，在多核平台下写lock-free的代码而不发生内存乱序也是有可能的。就像我在无锁编程介绍中提到的那样，可以利用顺序一致类型来达到目的(比如java中的volatile变量或C++11原子类型)，这样做的后果是有可能会牺牲一些性能。我不去详细谈论这些细节。在这篇文章中，集中关注编译器对常规，非顺序一致类型的内存乱序情况。

编译器指令乱序

就像你了解的那样,编译器的工作就是将人们可读的源代码转化为CPU可读的机器码。在转换过程中，编译器是可以非常自由的改变其中行为的。

其中一个例子就是可以让指令乱序-再次说明，仅仅在单线程程序的行为不会改变的这一基本原则下才有效。
这种指令乱序现象主要发生在编译器优化开启的情况下。看看下面的函数

int A, B;

void foo()
{
    A = B + 1;
    B = 0;
}

如果使用GCC 4.6.1编译这个函数而没有开启编译器优化选项时，会产生以下机器代码，使用-s选项可以看到其中的汇编代码。对变量B的写操作恰好发生在对变量A写操作之后，这和源代码中的行为是一致的。

$ gcc -S -masm=intel foo.c
$ cat foo.s
        ...
        mov     eax, DWORD PTR _B  (redo this at home...)
        add     eax, 1
        mov     DWORD PTR _A, eax
        mov     DWORD PTR _B, 0
        ...

当使用-o2开启编译器优化选项时，结果是这样的：

$ gcc -O2 -S -masm=intel foo.c
$ cat foo.s
        ...
        mov     eax, DWORD PTR B
        mov     DWORD PTR B, 0
        add     eax, 1
        mov     DWORD PTR A, eax
        ...

这时，编译器就有选择的余地了，内存会发生乱序，在写变量A之前会先写变量B。有什么理由不这么做呢？这时内存乱序的基本规则并没有被打破。对于一个单线程程序来说，并不会发觉其中的差异^注2。

另一方面，在写lock-free代码时,这种编译器导致的乱序行为会引起一些问题。下面是一个经常被引用的例子，共享标志用来指示一些其它的共享数据被published了：

int Value;
int IsPublished = 0;
 
void sendValue(int x)
{
    Value = x;
    IsPublished = 1;
}

想象一下当编译器在对Value进行写操作之前，先写IsPublished变量发生乱序会是什么情况。即使是在单处理器程序中，我们也会遇到一个问题：操作系统以抢占式方式调度某个线程在两次写操作之间运行，这时让其它线程以为Value变量已经更新过了，而实际上并没有。

当然，编译器可能并不会将那些操作乱序，产生的机器代码在任何的多核CPU中（比如x86/x64)或者在任何CPU类型的单核处理器中，都会像lock-free方式一样工作，这个属于强内存模型
如果正好就在那样的环境中工作，只能说我们是幸运的。毫无疑问，识别共享变量的内存乱序一定要多练习，并且要确保内存执行顺序能正确实施，如你所愿。

显式Compiler Barriers

阻止编译器级别的内存乱序最简单方式就是使用一种比较特殊的直接方法，称作compiler barrier. 我已经在前面的文章中介绍了GCC的compiler barrier. 在Microsoft Visual C++中，_ReadWriteBarrier充当同样的角色。

int A, B;

void foo()
{
    A = B + 1;
    asm volatile("" ::: "memory");
    B = 0;
}

这样修改之后，我们可以开启编译器优化，内存的写指令会保证你想要的执行顺序

$ gcc -O2 -S -masm=intel foo.c
$ cat foo.s
        ...
        mov     eax, DWORD PTR _B
        add     eax, 1
        mov     DWORD PTR _A, eax
        mov     DWORD PTR _B, 0
        ...

类似的，如果我们想保证sendMessage例子的正确性，并且只关心单核处理器系统，那么这里也需要引入compiler barrier. 不仅sending操作需要compiler barrier来阻止写操作乱序，接收端在读操作之间同样需要。

#define COMPILER_BARRIER() asm volatile("" ::: "memory")

int Value;
int IsPublished = 0;

void sendValue(int x)
{
    Value = x;
    COMPILER_BARRIER();          // prevent reordering of stores
    IsPublished = 1;
}

int tryRecvValue()
{
    if (IsPublished)
    {
        COMPILER_BARRIER();      // prevent reordering of loads
        return Value;
    }
    return -1;  // or some other value to mean not yet received
}

就像我提到的那样，compiler barrier在单核处理器中已经足够能用来阻止内存乱序了。但现在已经是2012年了，更常见的是多核处理器。如果我们要保证交互在多处理器环境中依然能保证想要的执行顺序，并且能适用任意的CPU架构，仅仅compiler barrier是不够的。这时我们需要一个CPU fence指令，或者在运行时能执行充当memory barrier的操作^注3。我会在下面文章中介绍更多这方面的内容.

Linux内核的预处理器宏(比如smb_rmb)可以充当CPU fence指令，这些宏在单核处理器系统中编译时被降级为简单的 compiler barriers^注4.

隐式Compiler Barrier

也有其它的方法来阻止编译器乱序。当然，上面提到的CPU fence指令就能直接作为compiler barriers. 下面是PowerPC系统中CPU fence指令的例子，它在GCC中被定义为一个宏：

1	#define RELEASE_FENCE() asm volatile("lwsync" ::: "memory")

我们可以在代码中任意位置放置RELEASE_FENSE,来阻止处理器乱序以及编译器乱序。举个例子，在多处理器环境下，它可以让sendValue函数变得更加安全。

void sendValue(int x)
{
    Value = x;
    RELEASE_FENCE();
    IsPublished = 1;
}

在新的C++11原子库标准中，如果一个原子操作不是使用std::memory_order_relaxed这种内存序选项^注5，那么它也可以作为一个compiler barrier

int Value;
std::atomic<int> IsPublished(0);

void sendValue(int x)
{
    Value = x;
    // <-- reordering is prevented here!
    IsPublished.store(1, std::memory_order_release);
}

和你想的那样，每个包含compiler barrier的函数自身都可以作为一个compiler barrier，这个函数也可以是内联的。(然而，微软的文档中表明Visual C++ 编译器的早期版本并不是那么回事)

void doSomeStuff(Foo* foo)
{
    foo->bar = 5;
    sendValue(123);       // prevents reordering of neighboring assignments
    foo->bar2 = foo->bar;
}

实际上，大多数的函数调用不管它们自身是否包含compiler barrier,都可以充当compiler barrier. 这里排除那些内联函数^注6，用pure属性声明的函数^注7，以及开启了link-time code generation编译链接选项的情况^注8。除了上述这些情况，由于编译器并不清楚函数的副作用，对一个外部函数的调用比compiler barrier还要强。编译器必须要放弃那些对此函数可见的内存上的任何假设。

当你能考虑到这些的时候，就可以高枕无忧了。在上面的代码中，假设sendValue函数在一个外部库里实现。编译器是怎么知道sendValue不依赖于foo->bar的值呢？它又是如何知道sendValue不会在内存中修改foo->bar呢？它并不知道。因此，为了遵守内存执行顺序的基本原则，编译器不能对sendValue函数的外部调用做任何乱序操作。类似地，它必须在调用结束后在内存中读取foo->bar的新值，而不是假设它仍然是5，尽管这时已经开启了优化选项。

$ gcc -O2 -S -masm=intel dosomestuff.c
$ cat dosomestuff.s
        ...
        mov    ebx, DWORD PTR [esp+32]
        mov    DWORD PTR [ebx], 5            // Store 5 to foo->bar
        mov    DWORD PTR [esp], 123
        call    sendValue                     // Call sendValue
        mov    eax, DWORD PTR [ebx]          // Load fresh value from foo->bar
        mov    DWORD PTR [ebx+4], eax
        ...

可以看到，尽管当编译器必须从内存中重新读取数据的时候，阻止编译器指令乱序的例子也有很多。我相信这些隐藏的规则构成了人们长期认为C语言中的volatile数据类型对正确编写多线程代码来说并不是必要的原因之一^注9。

横空出现的写操作

指令乱序让无锁编程变得tricky?在C++11标准化之前，并没有技术上的规则来阻止编译器做tricky的优化. 具体来说，在没有任何写操作的情况下，编译器会很自由的引入写操作。下面是个非常简单的例子，也是受到Hans Boehm一些文章中例子的启发。

int A, B;

void foo()
{
    if (A)
        B++;
}

尽管在实际中这看起来不太现实，没有任何东西能阻止编译器在检查变量A之前将变量B传递给寄存器，结果会生成下面的机器码：

void foo()
{
    register int r = B;    // Promote B to a register before checking A.
    if (A)
        r++;
    B = r;          // Surprise! A new memory store where there previously was none.
}

再强调一次，这时内存执行顺序的基本原则仍然遵守了。一个单线程程序可能对此一无所知。但在多线程环境下，尽管在变量A是0的时候，我们的函数却错误地消除了线程对变量B并发的修改，这和原始的代码情况不同^注10。尽管我们已经用C/C++写多线程和无锁代码几十年了，这种晦涩但在技术上可行的情况也就是人们说C++不支持线程的一部分原因。

我不知道现实中是否有人成为这种横空出现的写操作的受害者。可能是因为我们倾向编写的无锁代码的类型（比较固定），以至于并没有太多的优化机会来适应这种模式。我觉得当我看到编译器产生这种代码变换时，我会去找相应的方法来避免其所带来的影响.如果这些发生在你身上，可以在评论中让我看到。

在任何的情况下，新的C++11 标准明确的说明了编译器会引入数据竞争的情况。细节可以在最近的C++11 手稿的1.10.22章节中找到

Compiler transformations that introduce assignments to a potentially shared memory location that would not be modified by the abstract machine are generally precluded by this standard.

为什么有编译器乱序

就像我在文章开头提到的那样，编译器会像处理器一样以同样的原因-性能优化-来修改内存执行顺序。这种优化是现代CPU复杂性的直接产物。

当CPU最多只有几十万个晶体管的时候，我有点怀疑编译器在80年代早期就已经做了很多指令乱序的工作。我这个说法可能有点惊世骇俗。那时候并没有太多关于编译器乱序的观点。从那时起，根据摩尔定律，CPU的设计者将晶体管的数目成10000倍的增长，那些晶体管设计了许多trick,比如流水线，内存预取，ILP以及最近的多核。这些特征的结果就是，我们可以看到程序中指令的执行顺序在性能上能产生很大的差异。

Intel在1993年发布的首个Pentium处理器，其所谓的U和V管道，是我记得的第一个人们经常说起关于管道和指令乱序的处理器。最近，当我在Visual Studio上开始涉及X86汇编代码时。我对其中极少数的指令乱序情况感到非常惊讶。另一方面，我在Playstation 3平台上写SPU汇编代码时，发现编译器非常高效^注11。这只是一些有趣的经历，并不能反应其他人的情况，当然也不影响我们在lock-free的代码中保证内存执行顺序的手段和方法^注12。

译者注

注1：lock free虽然翻译为无锁，但是它并不是“没有锁”的意思，“没有锁”在英文里一般是lockless。lock free考察的是若干个线程组成的系统，不管如何，总能保证至少有一个线程能make progress，因此保证系统，从整体上看，是make progress的。这样的系统或者算法实现就是lock free的。

注2：假设A、B的初始值都是0，那么对于单线程程序而言，foo执行完A的的值为1，B的值为0。保证这点的情况下，编译器可以随意优化。这里重要的是影响和效果。

注3：很多时候我们把barrier分为两种：compiler级别和cpu级别。compiler级别的memory barrier只阻止编译器乱序，不影响CPU乱序，不对CPU乱序执行进行约束；而CPU级别的memory barrier则束缚了编译器和cpu两者的乱序。

注4：在linux里，barrier()是编译器级别的memory barrier；smp_wb()是cpu级别的memory barrier。

很多朋友们可能一直存在一个疑问：在linux下，在单处理器(Uniprocessor)环境中，这里的cpu级别的memory barrier退化为编译器级别的memory barrier，仅仅束缚编译器的乱序能力，却不影响cpu，那么仅仅使用compiler barrier是否足够？

这是因为根据文档，

SMP memory barriers are reduced to compiler barriers on uniprocessor compiled systems because it is assumed that a CPU will appear to be self-consistent, and will order overlapping accesses correctly with respect to itself.

也就是说，在linux下，对单核处理器有两个前置条件：

1，单核不具有多核处理中存在的cache coherence问题。

2，在单核cpu上乱序执行指令的线程在被调度出去发生上下文切换时，会把乱序的指令流水撤销或者提交。

因此，单核单线程、单核多线程都不需要担心cpu乱序执行问题。

注5：C++11引入的feature。在C++11中，除了上面例子用到的std::memory_order_release之外，还有如下的内存序选项：

memory_order_relaxed,
memory_order_consume,
memory_order_acquire,
memory_order_release,
memory_order_acq_rel,
memory_order_seq_cst

关于它们的语义和用法，请继续关注我们的深入探索并发编程系列，或者参考《C++ Concurrency In Action》这本书

注6：gcc提供了必须inline和必须不inline的feature，很有意思。

void attribute ((noinline)) foo()
{
…
}

void attribute ((always_inline)) foo()
{
…
}

注7：指在gcc中，加了pure attribute的函数：

void attribute ((pure)) foo()
{
…
}

根据gcc文档，pure属性是用来修饰这样的函数：该函数除了返回一些值之外，不会产生其他作用和影响；并且它的返回值只依赖于它的输入参数和一些全局变量，比如说strlen和memcmp.

因此，对于这类函数，gcc就可以施展手脚，优化一番了。比如说，

int attribute ((pure)) strlen(char *p)
{
…
}

那么假如你写了这样的代码：

char *p = "abc";
for (int i = 0; i < strlen(p); i++) {
  //do sth
}

那么gcc可以将它优化为：

char *p = "abc";
int tmp = strlen(p);
for (int i = 0; i < tmp; i++) {
  //do sth
}

注8：Link-time Code Generation，一般简写为LTCG，主要针对不同编译单元(compilation unit)间的函数定义和调用进行优化。更多细节除了编译器官方文档外，可以参考这里和这里。

注9：C/C++中的volatile常常被人错误使用，很多朋友错误以为它和Java中的volatile一样。其实不然。

在C/C++中的volatile，有两个重要特点：

1，它不提供任何的防止乱序的功能。

2，它不保证是原子的。

也就是说，以下操作不一定是原子的：

1	volatile int64_t a = 12345671234567;

不考虑具体的、特定的平台和环境，以下操作是未定义行为：

volatile int is_ready = 0;
int info = 0;
void thread_A
{
  while(is_ready == 0)
  {
  }
  //use info;
}
void thread_B
{
  info = 123;
  is_ready = 1;
}

当线程A发现is_ready不等于0而退出循环时，不能保证线程B已经执行了info=123，因为volatile不提供memory ordering保证，线程B里的两条语句可能被CPU乱序执行(顺便一说，在Intel X86体系结构下，这两条语句不会被CPU乱序执行)。

正确的做法建立happens-before关系。更多细节，敬请继续关注我们的深入探索并发编程系列。

注10：在多线程环境下，本来是要对B进行并发修改的，优化后却变成了对局部寄存器变量的修改，显然是不符合预期的。

注11：原文为really went to town，这里的意思是说，和前面的x86中的极少数乱序相比，在Playstation 3下可以看到大量的乱序情况。

注12：本文的重点是编译器的乱序；关于更多CPU乱序的细节和内容，请参考上一篇文章。

Acknowledgement

本文由 Diting0x 与睡眼惺忪的小叶先森共同完成，在原文的基础上添加了许多精华注释，帮助大家理解。

感谢好友小伙伴-小伙伴儿与skyline09_ 阅读了初稿，并给出宝贵的意见。

原文： http://preshing.com/20120625/memory-ordering-at-compile-time/

本文遵守Attribution-NonCommercial-NoDerivatives 4.0 International License (CC BY-NC-ND 4.0)
仅为学习使用，未经博主同意，请勿转载
本系列文章已经获得了原作者preshing的授权。版权归原作者和本网站共同所有