内存重新排序如何帮助处理器和编译器？

Question

我研究了Java内存模型，看到了重新排序的问题。一个简单的例子：

boolean first = false;
boolean second = false;

void setValues() {
    first = true;
    second = true;
}

void checkValues() {
    while(!second);
    assert first;
}

重新排序是非常不可预测和奇怪的。此外，它会破坏抽象。我想处理器架构一定有很好的理由去做一些对程序员来说如此不方便的事情。这些原因是什么？

有很多关于如何处理重新排序的信息，但我找不到任何关于为什么需要它的信息。无论在哪里，人们都会说“这是因为某些性能优势”。例如，将＜code＞第二个＜code＞存储在＜code＞第一个＜code＞之前有哪些性能优势？

你能推荐一些关于这方面的文章、论文或书籍，或者自己解释一下吗？

Answer 1

在现代处理器芯片上，处理器通常可以比从主存储器中获取快一个数量级（或更多）的寄存器到寄存器操作。命中L1或L2缓存的操作比主存储器快，比寄存器到寄存器慢。另一个需要注意的是，现代处理器芯片通常使用管道，允许同时执行不同指令的不同部分。

考虑到这一点，操作的重新排序通常是为了避免流水线（快）必须等待主存上的操作（慢）完成的情况：

>

Davide的例子说明了完全避免内存读取和写入的重新排序。（至少，这是他的意图。实际上，重新排序是在本机指令级别完成的，而不是源代码或字节码级别。）

在其他情况下，您可能会发现执行a=a 1和b=b 1的指令被交错；例如。

1) load a -> r1
2) load b -> r2
3) r1 + 1 -> r3
4) r2 + 1 -> r4
5) save r3 -> a
6) save r4 -> b

在管道架构中，这可能允许2)和3)同时发生，4)和5)同时发生，等等。

最后要注意的是，现代处理器芯片/指令集尽可能避免从主存储器读取和写入主存储器。事实上，写入指令写入L1或L2缓存是常见的，并延迟（慢）写入主存，直到刷新缓存行。这会导致另一种“内存异常”……在不同的内核上运行的单独线程看不到内存更新，因为相应的写操作尚未刷新。

如上所述，Java内存模型旨在允许编译器/处理器优化多线程应用程序的性能。当保证一个线程看到另一个线程所做的内存更改时，这一点很清楚。在没有可见性保证的情况下，允许编译器/处理器重新排序等。这种重新排序会对整体性能产生很大影响。

Answer 2

想象一下，有以下代码：

a = 1;
b = 1;
a = a + 1;   // Not present in the register
b = b + 1;   // Not present in the register
a = a + 1;   // Not present in the register
b = b + 1;   // Not present in the register
// Here both a and b has value 3

使用内存重新排序的可能优化是：

a = 1;
a = a + 1;   // Already in the register
a = a + 1;   // Already in the register
b = 1;
b = b + 1;   // Already in the register
b = b + 1;   // Already in the register
// Here both a and b has value 3

性能更好，因为数据出现在寄存器中。

请注意，有许多不同级别的优化，但这将让您了解为什么重新排序可以提高性能。

Answer 3

TL;DR：它为编译器和硬件提供了更多的空间来利用as-if规则，因为它不需要它保留原始源代码的所有行为，只需要单个线程本身的结果。

优化必须保留加载/存储的外部可观察（从其他线程）顺序，这为编译器提供了大量空间，可以将内容合并到更少的操作中。对于硬件来说，延迟存储是一个大问题，但对于编译器来说，各种重新排序都有帮助。

（有关为什么它有助于编译器的部分，请参阅部分内容）

硬件重新排序早期存储，在 CPU 内部加载较晚（StoreLoad 重新排序）对于无序执行至关重要。（见下文）。

其他类型的重新排序（例如StoreStore重新排序，这是您问题的主题）不是必需的，并且高性能CPU可以仅通过StoreLoad重新排序构建，而不是其他三种。（主要的例子是tag：x86，其中每个商店都是一个发布商店，每个负载都是一个获取负载。有关更多详细信息，请参阅 x86 标记 wiki。

有些人，如Linus Torvalds，认为用其他存储重新排序存储对硬件没有太大帮助，因为硬件已经必须跟踪存储排序以支持单个线程的无序执行。(单个线程总是运行，就好像它自己的所有存储/加载都按照程序顺序发生一样。)如果你好奇的话，可以看看realworldtech上的其他帖子。和/或如果你觉得莱纳斯的侮辱和明智的技术争论的组合很有趣:P

对于Java，问题在于，存在硬件不提供这些排序保证的体系结构。弱内存排序是RISC ISA（如ARM、PowerPC和MIPS）的一个常见特征。（但不是SPARC-TSO）。设计决策背后的原因与我链接的realworldtech线程中讨论的原因相同：使硬件更简单，并让软件在需要时请求订购。

因此，Java的架构师没有太多选择：为内存模型比Java标准弱的体系结构实现JVM需要在每个存储之后执行存储屏障指令，在每次加载之前执行加载屏障。（除非JVM的JIT编译器可以证明没有其他线程可以引用该变量。）一直运行屏障指令是很慢的。

Java的强大内存模型将使ARM（和其他ISA）上的高效JVM变得不可能。证明不需要障碍几乎是不可能的，需要人工智能水平的全球程序理解。（这远远超出了普通优化器的功能）。

（另请参阅杰夫·普莱斯兴关于C编译时重新排序的优秀博客文章。这基本上适用于Java，当您将JIT编译作为过程的一部分包含在本机代码中时。）

保持Java和C/C内存模型较弱的另一个原因是允许更多的优化。由于（弱内存模型）允许其他线程以任何顺序观察我们的存储和加载，因此即使代码涉及存储到内存，也允许进行主动转换。

例如，在大卫的例子中:

c.a = 1;
c.b = 1;
c.a++;
c.b++;

// same observable effects as the much simpler
c.a = 2;
c.b = 2;

不要求其他线程能够观察中间状态。所以编译器可以将其编译成＜code＞c。a=2；c、 b=2，无论是在Java编译时还是在字节码被JIT编译为机器代码时。

对于一个方法来说，从另一个方法多次调用递增的内容是很常见的。如果没有此规则，将其转换为＜code＞c。只有当编译器能够证明没有其他线程能够观察到差异时，才会出现a=4。

C程序员有时会错误地认为，既然他们正在为x86编译，他们就不需要std::atomic

将存储提交到缓存中后，它对在其他内核上运行的线程（通过缓存一致性协议）变得全局可见。此时，回滚它为时已晚（另一个核心可能已经获得了该值的副本）。因此，在确定商店不会出错之前，它不会发生，并且之前的任何指示也不会发生（即在从无序后端退休或之后）。而且，在之前的某个时刻没有分支错误预测，等等，也就是说，在我们将存储指令提交到L1d缓存之前，我们需要排除所有错误推测的情况。（这就是为什么我们有一个存储缓冲区）

如果没有StoreLoad重新排序，每个加载都必须等待所有前面的存储退出（即完全完成执行，已知的非推测性）并实际将数据提交到缓存，然后它们才能从缓存中读取值以供以后的指令使用依赖于加载的值。（加载将值从缓存复制到寄存器中的时刻是它作为加载和存储在该内存位置上的一致性顺序的一部分“发生”的关键时间。）

通常，在相应的存储指令从无序后端退出后，CPU将存储从存储缓冲区提交到L1d缓存（ReOrder buffer=ROB）。存储缓冲区中可以有一定数量的“分级”存储，因此这将执行与缓存未命中存储分离。但你可以放弃这项福利，将L1d作为退休的一部分。（存储的执行仍将通过将地址数据写入存储缓冲区来工作，因此它可能是推测性的，发生在数据准备就绪时。存储缓冲区将这种推测保持为核心私有。）

如果没有StoreLoad重新排序，加载将无法执行，直到所有早期的存储都提交到缓存。这将是内存并行的巨大障碍。即每个加载都像x86lford，耗尽无序的后端，并且像mford等待存储缓冲区清空，因为我们建议提交将在退休时发生，而不是之后。包括等待任何早期的缓存未命中加载或存储，以及等待CPU咀嚼所有依赖链，因此它倾向于序列化事物，而不是让CPU重叠循环的独立迭代或其他长dep链。

现代x86 CPUs在其他(缓存未命中)加载之前进行推测性早期加载，如果它们检测到它们的缓存行副本从加载实际发生时到体系结构允许时没有保持有效，则可能会采取内存顺序误推测管道nuke。在这种情况下，它们会丢弃ROB内容，回滚到一致的退休状态，并再次开始执行。(这通常只发生在另一个内核正在修改高速缓存行时，但如果它错误地预测加载不会重新加载存储，也会发生这种情况。)(当然真正的x86可以在存储之前自由地重新排序加载。)

如果不允许StoreLoad重新排序，CPU仍然可以推测性地执行加载，但可能仍然必须比普通CPU更早提交存储。负载推测可以在退役后跟踪存储缓冲区中的存储。

因此，真正的限制是负载在早期商店提交之前无法停用。这些存储区在停用后仍可以保留在存储缓冲区中（变为非推测）。这在具有巨大ROB和大型存储缓冲区的现代CPU上听起来并不那么糟糕，但对于按顺序排列的CPU或设计内存模型时存在的CPU中更适度的无序执行功能来说，这将是一场灾难。

即使拥有巨大的乱序执行功能，它也会引入更多的猜测，或者更大的猜测时间窗口，CPU可能需要对管道进行核打击（丢弃ROB）。在大的ROB/乱序状态下，这可能会损失大量工作。在访问共享内存的并行代码中，这可能会很糟糕。（包括错误共享，其中两个变量恰好在同一缓存行中）。对此的处罚已经相当严重，即使在当前x86 CPU上只加载也会发生。（即使在其他不需要负载排序的ISA上也不是很好，但缓存行乒乓仍然是个问题）。

缓存未命中存储无法有效隐藏。如果您的代码没有进行很多存储，那么缓存中未命中的代码可能会在存储缓冲区中等待数百个延迟周期，从DRAM中获取行。（或者，如果行在另一个内核中脏了，并且其他内核正在争读或写它，则通过读换所有权获得独占所有权。）如果正在执行的代码中没有太多存储，则在存储提交之前，它可能会在存储之前获得数百条指令，包括来来往往的多次加载。但是，如果在存储提交之前，所有这些稍后的加载都不能从ROB中退出，那么它将阻止新的潜在独立指令进入无序后端，并在延迟期间被调度到执行单元。

(不过，大多数代码都会进行大量的存储，存储缓冲区会很快填满。除了在允许存储存储重新排序的弱排序isa上，因此在缓存未命中存储时，不会对稍后命中缓存的存储造成瓶颈。)

（我在意识到x86 CPU会提前进行推测性加载后重写了上面的部分，并可以将其应用于假设的StoreLoad规则以及x86的实际LoadLoad排序规则。（通过存储转发对存储缓冲区进行程序排序）。本节中的一些内容现在可能与此重复。）

我在回答“为英特尔 Sandybridge 系列 CPU 中的管道取消优化程序”的回答的早期部分，包括了一些链接，作为计算机体系结构简短介绍的一部分。这可能会有所帮助，或者更令人困惑，如果你发现这很难遵循。

CPU 通过在商店队列中缓冲 CPU 和 WAW 管道，直到商店指令准备好停用，从而避免商店的 WAR 和 WAW 管道危险。来自同一内核的加载必须检查存储队列（以保持单个线程的顺序执行的外观，否则在加载最近可能存储的任何内容之前，您需要内存屏障指令！存储队列对其他线程不可见;仅当存储指令停用时，存储才会变为全局可见，但加载一旦执行就会变为全局可见。（并且可以使用在此之前预取到缓存中的值）。

另请参阅我写的这个答案，解释了存储缓冲区以及它们如何将执行与缓存未命中存储提交解耦，并允许存储的推测执行。维基百科关于经典RISC管道的文章也为更简单的CPU提供了一些东西。存储缓冲区本质上会创建StoreLoad重新排序（以及存储转发，以便核心可以在全局可见之前看到自己的存储，假设核心可以进行存储转发而不是停顿。）

因此，对于商店来说，无序执行是可能的，但它们只在商店队列中重新排序。由于指令必须停用才能支持精确的异常，因此让硬件强制执行StoreStore订购似乎根本没有多大好处。

由于加载在执行时全局可见，因此强制加载加载顺序可能需要在缓存中丢失加载后延迟加载。当然，在现实中，CPU会推测性地执行以下负载，并在发生内存顺序错误推测时检测到。这对于良好的性能几乎是必不可少的：无序执行的很大一部分好处是继续做有用的工作，隐藏缓存未命中的延迟。

Linus的一个论点是，弱有序CPU需要多线程代码来使用大量的内存屏障指令，因此它们需要便宜，以便多线程代码不会出错。只有当您有硬件跟踪加载和存储的依赖顺序时，这才是可能的。

但是，如果你有硬件跟踪依赖性，你可以让硬件一直强制排序，这样软件就不必运行那么多屏障指令。如果您有硬件支持来降低屏障的成本，为什么不像x86那样，在每次加载/存储时都将其隐式化呢？

他的另一个主要论点是，内存排序很难，也是bug的主要来源。在硬件上一次就把它做好，比每一个软件项目都要把它做好要好。（这个论点之所以有效，是因为它可以在硬件中实现，而不会产生巨大的性能开销。）