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

Question

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

boolean first = false;
boolean second = false;

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

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

重新排序非常不可预测且很奇怪。另外，它破坏了抽象。我想处理器架构必须有充分的理由来做一些对程序员来说很不方便的事情。 那是什么原因

关于如何处理重新排序有很多信息，但是我找不到有关 为什么
需要重新排序的任何信息。人们到处都只说“这是因为有一些性能优势”。例如，在存储second之前有什么性能好处first？

您可以推荐一些有关此的文章，论文或书，还是自己解释一下？

Answer 1

TL; DR ：它使编译器和硬件的更多的空间利用的 作为，如果 通过不要求它保留原始源的所有行为，只有单个线程本身的结果规则。

通过优化可以保留从外部观察（从其他线程）的装载/存储顺序，这是优化必须保留的东西，这为编译器提供了很大的空间来将内容合并为更少的操作。对于硬件而言，延迟存储是最大的问题，但是对于编译器而言，各种重新排序都可以提供帮助。

（请参阅半途部分，以了解它为何有助于编译器的部分）

为什么它有助于硬件

硬件对CPU内部的较早存储和较晚的负载进行重新排序（StoreLoadreordering）对于无序执行至关重要。（见下文）。

其他类型的重新排序（例如，StoreStore重新排序，这是您要考虑的问题）不是必需的，并且仅通过StoreLoad重新排序就可以构建高性能CPU，而其他三种则不能。（最主要的示例是tag：x86，其中每个商店都是一个发行商店，每个负载都是一个Acquisition-load。有关更多详细信息，请参见x86标签Wiki。）

像Linus
Torvalds这样的人认为，与其他商店重新排序商店对硬件没有多大帮助，因为硬件已经必须跟踪商店排序以支持单个线程的无序执行。（一个线程总是像它自己的所有存储/加载都按照程序顺序运行一样运行。）如果您感到好奇，请在realworldtech上查看该线程中的其他帖子。和/或，如果您发现Linus的侮辱与明智的技术论点相结合，则很有趣：P

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

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

Java的强大内存模型将使ARM（和其他ISA）上的高效JVM成为不可能。证明不需要障碍是几乎不可能的，这需要对全球程序有一定了解的AI。（这超出了普通优化器的功能）。

为什么它可以帮助编译器

（另请参阅Jeff Preshing在C ++编译时重新排序方面的精彩博客文章。当您将JIT编译包括在本机代码中作为过程的一部分时，这基本上适用于Java。）

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

例如，在像Davide这样的例子中：

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

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

不需要其他线程能够观察中间状态。因此，编译器可以c.a = 2; c.b = 2;在Java编译时或将字节码JIT编译为机器代码时将其编译为。

对于一种方法，从另一种方法多次调用某些东西通常是很常见的。没有这个规则，c.a += 4只有在编译器可以证明没有其他线程可以观察到差异的情况下，才有可能将其变为现实。

C ++程序员有时会误以为，由于他们正在为x86进行编译，因此他们不需要std::atomic<int>为共享变量获得一些顺序保证。
这是错误的，因为优化是基于语言内存模型的假设规则而不是目标硬件进行的。

为什么StoreLoad重新排序有助于提高性能：

将存储提交到高速缓存后，该存储将对其他内核上运行的线程（通过高速缓存一致性协议）全局可见。到那时，将其回滚为时已晚（另一个核心可能已经获得了该值的副本）。因此，只有在确定存储不会出错并且之前没有任何指令的情况下，它才会发生。商店的数据已准备就绪。而且，在某个时候还没有分支错误的预测，等等。也就是说，我们需要排除所有错误推测的情况，然后才能撤消存储指令。

如果没有对StoreLoad进行重新排序，则每个加载都必须等待所有先前的存储退出（即，完全完成执行，将数据提交到缓存中），然后才能从缓存中读取一个值，以供以后的指令使用（取决于加载的值）。（加载将值从缓存复制到寄存器的时刻是其他线程全局可见的时刻。）

由于您不知道其他内核发生了什么，因此我认为硬件无法通过推测这不是问题，然后在事后发现错误推测来掩盖启动负载中的延迟。（然后将其视为分支的错误预测：丢弃所有依赖于该负载的工作，然后重新发出。）内核可能能够允许处于独占或已修改状态的高速缓存行进行推测性的早期负载，因为它们不能存在于其他内核中。（检测错误推测，是否在推测负载之前退出最后一个存储之前，是否从另一个CPU发出了对该缓存行的缓存一致性请求。）无论如何，这显然是大量的复杂性，而其他任何事情都不需要。

请注意，我什至没有提到商店的缓存缺失。这将存储的等待时间从几个周期增加到数百个周期。

实际CPU的工作方式（允许StoreLoad重新排序时）：

在我的答案的早期部分中，我引入了一些链接作为计算机体系结构简介的一部分，该部分是[针对英特尔Sandybridge系列CPU的管道优化程序的。如果您发现这很难遵循，那可能会有所帮助，或者更加令人困惑。

CPU
通过将它们缓冲在存储队列中直到存储指令准备退出，从而避免了存储区的WAR和WAW管道危害。从同一个内核进行的加载必须检查存储队列（以保留单个线程按顺序执行的外观，否则在加载最近存储的任何内容之前，您需要内存屏障指令）。存储队列对于其他线程是不可见的。存储仅在存储指令退出时才变为全局可见，但是加载在执行后立即变为全局可见。（并且可以在此之前使用预取到缓存中的值）。

另请参阅Wikipedia上有关经典RISC管道的文章。

因此，商店可能会无序执行，但它们只会在商店队列中重新排序。由于必须退出指令以支持精确的异常，因此让硬件强制执行StoreStore排序似乎并没有多大好处。

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

Linus的论据之一是，顺序较弱的CPU需要多线程代码才能使用大量内存屏障指令，因此，为了不吸引多线程代码，它们必须便宜。仅当您具有跟踪负载和存储的依赖关系顺序的硬件时，这才有可能。

但是，如果您具有对依赖项的硬件跟踪，则可以一直让硬件强制执行排序，因此软件不必运行那么多的屏障指令。如果您有硬件支持来降低障碍，为什么不像x86一样在每个加载/存储中都隐式设置它们。

他的另一个主要论点是内存排序是HARD，并且是bug的主要来源。在硬件中一次完成正确的操作比每个必须正确执行的软件项目都好。（此参数之所以有效，是因为它可以在没有巨大性能开销的情况下在硬件中使用。）