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

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:它为编译器和硬件提供了更多空间来利用as-if规则,不要求它保留原始源的所有行为,只保留单个线程本身的结果.

将外部可观察(来自其他线程)的加载/存储排序作为优化必须保留的内容,使编译器有很多空间将事物合并到更少的操作中.对于硬件来说,延迟商店是最重要的,但对于编译器来说,各种重新排序都有帮助.

(有关它为何对编译器有帮助的部分,请参见部分内容)

为什么它有助于硬件

硬件重新排序早期存储以及CPU内部的后续加载(StoreLoad重新排序)对于无序执行至关重要.(见下文).

其他类型的重新排序(例如StoreStore重新排序,这是您的问题的主题)并不是必不可少的,只有StoreLoad重新排序才能构建高性能CPU,而不是其他三种.(主要的例子是标签:x86,其中每个商店都是一个发布商店,每个负载都是一个获取负载.有关更多详细信息,请参阅x86标签wiki.)

有些人,比如Linus Torvalds,认为与其他商店重新排序商店对硬件的帮助不大,因为硬件已经必须跟踪商店订购以支持单个线程的无序执行.(单个线程总是运行,好像它自己的所有存储/加载按程序顺序发生.)如果你很好奇,请参阅realworldtech上该线程中的其他帖子.和/或如果你发现Linus的侮辱和明智的技术争论很有趣:P

对于Java,问题在于,存在硬件不提供这些排序保证的架构. 弱内存排序是RISC ISA的常见功能,如ARM,PowerPC和MIPS.(但不是SPARC-TSO).设计决策背后的原因与我所链接的真实世界的线程中的争论相同:使硬件更简单,并让软件在需要时请求订购.

因此,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>为共享变量获得一些排序保证. 这是错误的,因为优化是基于语言内存模型的as-if规则而不是目标硬件发生的.

更多技术硬件说明:

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

将存储提交到缓存后,对于在其他核心上运行的线程(通过缓存一致性协议),它变得全局可见.那时,将它回滚为时已晚(另一个核心可能已经获得了该值的副本).因此,只有知道商店不会出错,并且在它之前没有任何指令,它才会发生.并且商店的数据准备就绪.并且在之前的某个时刻没有分支错误预测,等等.即我们需要在退出商店指令之前排除所有错误推测的情况.

如果没有StoreLoad重新排序,每个加载都必须等待所有先前的存储退出(即完全执行完毕,将数据提交到缓存),然后才能从缓存中读取值以供稍后依赖于加载值的指令使用.(加载将值从缓存复制到寄存器中的时刻是其他线程全局可见的时刻.)

由于您无法知道其他内核上发生了什么,我认为硬件不会通过推测它不是问题来隐藏启动负载的延迟,然后在事后检测到误推测.(并将其视为分支错误预测:抛弃所有依赖于该负载的工作,并重新发布它.)核心可能能够允许来自处于独占或修改状态的缓存行的推测性早期加载,因为它们不能出现在其他核心.(如果在推测加载之前退出最后一个商店之前,如果来自另一个CPU的缓存一致性请求来自另一个CPU,则检测错误推测.)无论如何,这显然是其他任何事情都不需要的大量复杂性.

请注意,我甚至没有提到商店的缓存缺失.这会将商店的延迟从几个周期增加到数百个周期.

实际CPU的工作原理(允许StoreLoad重新排序时):

在我的答案中,我将一些链接作为计算机体系结构简介的一部分包含了一些链接,这些部分是针对英特尔Sandybridge系列CPU中管道的优化程序.如果你发现这很难理解,这可能会有所帮助,或者更令人困惑.

CPU 通过在存储队列中缓冲它们来避免商店的WAR和WAW管道危险,直到存储指令准备好退出.来自同一核心的负载必须检查存储队列(以保留单个线程的按顺序执行的外观,否则在加载最近可能存储的任何内容之前,您需要内存屏障指令!).存储队列对其他线程不可见; 只有在存储指令退出时,存储才会变为全局可见,但只要它们执行,负载就会全局可见.(并且可以使用预先提取到缓存中的值).

另请参阅维基百科关于经典RISC管道的文章.

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

由于加载在执行时变为全局可见,因此强制执行LoadLoad排序可能需要在缓存中未命中的加载后延迟加载.当然,实际上CPU会推测性地执行以下负载,并且如果发生则检测存储器顺序错误推测.这对于良好的性能几乎是必不可少的:无序执行的很大一部分好处是继续做有用的工作,隐藏缓存未命中的延迟.

Linus的一个论点是,弱排序的CPU需要多线程代码才能使用大量的内存屏障指令,因此对于多线程代码来说,它们需要便宜而不要太糟糕.只有在硬件跟踪加载和存储的依赖性排序时才有可能.

但是如果你有依赖关系的硬件跟踪,你可以让硬件一直强制执行,因此软件不必运行尽可能多的屏障指令.如果你有硬件支持来减少障碍,为什么不在每个加载/存储上隐含它们,就像x86那样.

他的另一个主要论点是内存排序很难,也是bug的主要来源.在硬件中实现一次就比每个必须正确完成的软件项目更好.(这个论点只有在没有巨大性能开销的硬件中才有效.)

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

性能更好,因为数据存在于寄存器中.

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