对于 { A=a; B=b; }，"A=a" 在"B=b"之前严格执行吗？

Question

假设变量A、B、a和b都是不同的，并且它们的地址也都不同。对于以下代码：

A = a;
B = b;

C 和 C++ 标准是否明确要求在执行 A=a 之前必须严格执行 B=b？假设 A、B、a 和 b 的地址都不同，编译器是否允许交换两个语句的执行顺序以进行某些优化？

如果 C 和 C++ 的答案不同，请同时告知。

编辑：问题的背景是，在棋盘游戏 AI 设计中，人们使用 无锁共享哈希表 进行优化，如果没有添加 volatile 限制，其正确性强烈依赖于执行顺序。

- ACcreator

---

即使编译器保证按照那个顺序生成代码，CPU仍会进行乱序执行。 - KitsuneYMG

不仅编译器可以这么做，CPU、内存控制器、缓存等也可以这么做。 - David Schwartz

任何时候进行多线程编程都会完全进入另一个维度。即使代码按顺序执行，如果没有进一步的控制，在另一个处理器上观察，执行顺序也不会保证是顺序的。如果你想做类似于共享哈希表的事情，你需要花费很多时间研究同步问题。 - Hot Licks

是的，这是可能的，取决于使用的特定缓存一致性协议。例如，x86提供比Itanium更强的保证。在多线程中，您还需要关注撕裂和推测写入。 - Ben Voigt

@ACcreator：使用内存栅栏。这比临界区更便宜，但仍确保缓存以正确顺序同步。 - Ben Voigt

Answer 1

这两个标准允许按照任意顺序执行指令，只要不会改变可观察的行为。这被称为“as-if”规则:

• “as-if”规则到底是什么?
• http://en.cppreference.com/w/cpp/language/as_if

需要注意的是，正如评论中所指出的那样，“可观察的行为”是指具有定义行为的程序的可观察行为。如果你的程序存在未定义行为，则编译器无需推理该行为。

- David Heffernan

---

如果它们不影响程序的可观察行为（即被完全优化掉），那么这两个操作都不能执行。 - M.M

值得一提的是，只有变量是易失性的时候，访问或修改变量才算作“可观察行为”。 - Mike Seymour

@DavidHeffernan：是的，我应该更加精确，抱歉。我的意思是“访问或修改基本类型变量”。当然，用户定义的操作可能会有可观察的行为。 - Mike Seymour

在这种情况下，我认为值得强调（如G_G所暗示的），“好像”要求是具有定义行为的程序的可观察行为不会改变。提问者不应认为这个答案意味着任何指令顺序的更改都保证不会改变他的无锁哈希表的行为。实际上，如果他正在询问此问题，那么该代码包含数据竞争，因此其行为未被定义，并且由于优化、调度意外等原因，其行为可能会发生变化。 - Steve Jessop

@Cornstalks 在 as-if 规则下不执行复制省略；有特定的文本定义了复制省略。 - M.M

Answer 2

编译器只需要模拟程序的可观察行为，因此如果重新排序不违反该原则，则允许这样做。假设行为是明确定义的，如果您的程序包含未定义行为，例如数据竞争，那么程序的行为将是不可预测的，并且需要使用某种形式的同步来保护关键部分。 一个有用的参考 一篇有趣的文章涵盖了这个问题编译时内存排序，它说：

内存重新排序的基本规则被编译器开发者和CPU供应商普遍遵循，可以概括为：

不得修改单线程程序的行为。

一个例子 该文章提供了一个简单的程序，我们可以在其中看到这种重新排序：

int A, B;  // Note: static storage duration so initialized to zero

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

在更高的优化级别下，B = 0 在 A = B + 1 之前执行，我们可以使用 godbolt 来复现这个结果，而使用 -O3 时会产生以下结果（see it live）：

movl    $0, B(%rip) #, B
addl    $1, %eax    #, D.1624

为什么？

编译器为什么要重新排序呢？文章解释说，这正是处理器这样做的原因，因为体系结构的复杂性：

正如我在开头提到的那样，编译器修改内存交互顺序的原因与处理器这样做的原因完全相同——性能优化。这些优化是现代CPU复杂性的直接结果。

标准

在C++草案标准中，这在第1.9节“程序执行”中有所涵盖，其中写道（以后重点突出）：

本国际标准中的语义描述定义了一个参数化的不确定的抽象机。本国际标准对符合规范的实现的结构没有要求。特别是，它们不需要复制或模拟抽象机的结构。相反，符合规范的实现需要模拟（仅）抽象机的可观察行为，如下所述。⁵

脚注5告诉我们这也被称为as-if规则：

这个规定有时被称为“似乎”规则，因为实现可以自由地忽略此国际标准的任何要求，只要从程序的可观察行为可以确定，结果就好像遵守了该要求一样。例如，如果一个实际的实现可以推断出一个表达式的值未被使用且不会产生影响程序可观测行为的副作用，那么它不需要评估该表达式的一部分。草案C99和草案C11标准在“程序执行”章节中涵盖了这一点，尽管我们必须去索引中查看它在C标准中也被称为“似乎”规则。

这篇文章关于无锁编程的介绍很好地涵盖了这个主题，对于提问者关于无锁共享哈希表实现的问题，这一部分可能是最相关的：

内存排序

如流程图所示，在进行无锁编程的时候，特别是在多核或任何对称多处理器环境下，并且您的环境没有保证顺序一致性，您必须考虑如何防止内存重排序。

在当今的架构中，用于强制正确内存排序的工具通常分为三类，可以同时防止编译器重排序和处理器重排序：

• 一个轻量级的同步或屏障指令，我将在未来的文章中讨论它；
• 一个完整的内存屏障指令，我已经之前演示过了；
• 提供获取或释放语义的内存操作。

获取语义可以防止程序顺序后续的内存重排序操作，而释放语义可以防止程序顺序前面的内存重排序操作。这些语义特别适用于生产者/消费者关系的情况，其中一个线程发布一些信息，另一个线程读取它。我也会在未来的文章中更详细地讨论这个问题。

- Shafik Yaghmour

---

这让我想知道，为什么GCC asm生成的是addl $1, %eax而不是incl %eax？即使针对a++，它也只会生成a += 1...不过ICC的行为符合预期。 - user719662

@vaxquis 对我来说不太清楚，似乎是一种尝试优化的形式，可能取决于gcc所做出的假设。 - Shafik Yaghmour

Answer 3

如果指令之间没有依赖关系，它们可能会无序执行，即使最终结果不受影响。在调试以更高优化级别编译的代码时，您可以观察到这一点。

- Mohit Jain

Answer 4

由于A = a;和B = b;在数据依赖方面是独立的，因此这并不重要。如果先前指令的输出/结果影响后续指令的输入，则顺序很重要，否则不重要。这通常是严格的顺序执行。

- Dr. Debasish Jana

Answer 5

我的理解是，根据C++标准，这是必需的；但是，如果您试图在多线程控制中使用它，则在此情况下不起作用，因为没有任何东西可以保证寄存器以正确顺序写入内存。

正如您的编辑所示，您正尝试在完全无法工作的地方使用它。

- Joshua

Answer 6

如果您这样做，可能会对您有兴趣:

{ A=a, B=b; /*etc*/ }

请注意在分号位置的逗号。

然后，C++规范和任何确认的编译器都必须保证执行顺序，因为逗号运算符的操作数始终从左到右进行评估。这确实可以用于防止优化器通过重新排序来破坏您的线程同步。逗号有效地成为一个障碍，跨越该障碍不允许重新排序。

- Matthew Faithfulll

---

除了逗号运算符的使用有问题之外，这并没有解决原帖编辑的问题。 - Shafik Yaghmour