相关疑难解决方法(0)

这是一段看似非常特殊的C++代码.出于某种奇怪的原因,奇迹般地对数据进行排序使得代码几乎快了六倍.

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster.
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c) …

问题如标题所述:将方法/属性标记为虚拟的性能影响是什么？

注意 - 我假设虚拟方法在常见情况下不会过载; 我通常会在这里使用基类.

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

boolean first = false;
boolean second = false;

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

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

重新排序是非常不可预测和奇怪的.此外,它破坏了抽象.我认为处理器架构必须有充分的理由去做一些对程序员来说太不方便的事情. 这些原因是什么？

有很多关于如何处理重新排序的信息,但我找不到任何关于它为什么需要的信息.在任何地方,人们只会说"这是因为一些性能优势".例如,second之前存储的性能优势是first什么？

您能推荐一些关于此的文章,论文或书籍,或者自己解释一下吗？

考虑以下x86-64程序集:

inner:
   ...
   ret

outer:
.top:
   call inner
   dec  rdi
   jnz  .top
   ret

该函数outer只是重复call地对函数inner(其主体未显示) - 它可能是空的.

内部的一系列call指令outer和相应的ret指令是否inner在实践中形成一个依赖链(为了估计性能)？

这条链可以形成多种方式.例如,是否ret依赖于前一条call指令的延迟,然后后续call指令是否依赖于ret,形成call -> ret -> call链？或者也许ret是独立但call不是,形成一个call -> call链？如果有链,是通过内存,寄存器,堆栈引擎,返回地址预测器¹还是什么？

动机:这个问题起源于对另一个问题的一系列评论,主要是这个评论和早期评论.

¹这里的术语可能有些不清楚:堆栈引擎通常被理解为将转换rsp修改指令处理为具有适当偏移的单个访问,因此push rax; push rbx可能会转换为某些临时寄存器,mov [t0], rax; mov [t0 - 8], …

我已阅读维基百科页面关于无序执行和推测性的exectution.

我不能理解的是相似之处和不同之处.在我看来,当推测执行没有确定条件的值时,它会使用无序执行.

当我阅读Meltdown和Spectre的论文并做了进一步的研究时,出现了混乱.它在陈述消融纸即熔毁是基于乱序执行,而其他一些资源,包括对维基页面sepeculative执行状态消融是基于推测执行.

我想对此有所澄清.

我正在阅读一些论文,他们要么可以互换使用存储缓冲区和存储队列,要么与不同的结构有关,而我无法跟进.这就是我认为的商店队列:

• 它是一个可关联搜索的FIFO队列,以获取顺序保存有关存储指令的信息.
• 它保留了商店地址和数据.
• 它保存商店指令的数据,直到指令变为非投机性,即它们达到退休阶段.存储指令的数据仅在到达退出阶段时才从存储队列发送到存储器(在这种情况下为L1高速缓存).这很重要,因为我们不希望将推测性商店数据写入内存,因为它会混乱有序内存状态,并且在错误预测的情况下我们无法修复内存状态.
• 在错误预测时,删除与错误预测指令之后获取的存储指令相对应的存储队列中的信息.
• 加载指令向L1高速缓存和存储队列发送读取请求.如果在存储队列中找到具有相同地址的数据,则将其转发到加载指令.否则,使用从L1获取的数据.

我不确定存储缓冲区是什么,但我认为只是一些缓冲区空间来保持退役存储指令的数据等待写入内存(同样,L1).

现在,这就是为什么我感到困惑.在此论文中,指出"我们提出可扩展存储缓冲器[SSB],这使私人/推测值直接进入L1高速缓存,从而避免不可缩放缔搜索常规存储缓冲器的".我认为他们所讨论的不可扩展的关联式可搜索传统结构就是我所知道的商店队列,因为他们也说

SSB通过将处理器可见/推测值直接转发到L1高速缓存的加载,消除了传统存储缓冲区的不可扩展的关联搜索.

正如我上面提到的,据我所知,数据转发到加载是通过存储队列完成的.在第一页的脚注中,也有人说

我们使用"存储队列"来指代在退役之前保存商店值的存储和"存储缓冲区"以在存储到存储器之前引用包含已退休存储值的存储.

这符合我上面解释的内容,但它与第一​​个引用中的"存储缓冲区"冲突.脚注对应于论文中的参考文献之一.他们说,在那篇参考文献中

存储缓冲区是存在于许多当前处理器中以实现以下一个或多个的机制:存储访问顺序,延迟隐藏和数据转发.

我再次认为实现这些机制的机制称为存储队列.他们后来在同一篇论文中说

通常使用非阻塞高速缓存和缓冲结构,例如写缓冲区,存储缓冲区,存储队列和加载队列.

因此,他们分别提到存储缓冲区和存储队列,但稍后不再提及存储队列.他们说

存储缓冲区维护存储的顺序,并且只有在完成所有先前的指令之后才允许存储

他们的商店缓冲模型与Mike Johnson的模型相同.在约翰逊的书(超标量微处理器设计)中,商店首先以获取顺序进入商店预订站.从那里,它们被发送到地址单元,并从地址单元被发送到"存储缓冲区"及其相应的数据.通过此存储缓冲区处理加载转发.我再一次认为这个结构被称为商店队列.在参考文献#2中,作者也提到了这一点

Alpha 21264微处理器有一个32项的推测商店缓冲区,商店一直存在,直到它退役."

我看了一篇关于Alpha 21264的论文,其中指出了这一点

商店首先将数据通过数据总线传输到推测性存储缓冲区.商店数据保留在推测商店缓冲区中,直到商店退休.退出后,数据将在空闲缓存周期内写入数据缓存.

也,

内部存储器系统维护一个32项加载队列(LDQ)和一个32项存储队列(STQ),用于管理它们在飞行中的引用.[...] Stores在退出并转储到数据缓存后以获取顺序退出STQ.[...] STQ CAM逻辑控制推测数据缓冲区.当较旧的商店之后发生较年轻的负载时,它可以绕过推测商店数据加载.

因此,听起来像在Alpha 21264中有一个存储队列,它以获取顺序保存有关存储指令的一些信息,但它不保留存储指令的数据.存储指令的数据保存在存储缓冲区中.

所以,在所有这些之后,我不确定存储缓冲区是什么.它只是存储队列的辅助结构,还是存储等待写入L1的数据的完全不同的结构.或者是别的什么？当我们说"存储缓冲区"时,我觉得有些作者的意思是"存储队列".有任何想法吗？

一方面，维基百科写了乱序执行的步骤：

1. 取指令。
2. 指令分派到指令队列（也称为指令缓冲区或保留站）。
3. 指令在队列中等待，直到其输入操作数可用。然后允许该指令在较早、较旧的指令之前离开队列。
4. 指令被发布到适当的功能单元并由该单元执行。
5. 结果在排队。
6. 只有在所有较旧的指令将其结果写回寄存器文件后，才会将该结果写回寄存器文件。这称为毕业或退休阶段。

类似的信息可以在《计算机组织与设计》一书中找到：

为了让程序表现得像在一个简单的有序流水线上运行，指令获取和解码单元需要按顺序发出指令，这允许跟踪依赖关系，并且提交单元需要将结果写入寄存器和程序获取顺序中的内存。这种保守的模式被称为有序提交……今天，所有动态调度的管道都使用有序提交。

因此，据我所知，即使指令以乱序方式执行，其执行结果也会保存在重新排序缓冲区中，然后以确定性顺序提交到内存/寄存器。

另一方面，有一个众所周知的事实，即现代 CPU 可以为性能加速目的重新排序内存操作（例如，可以重新排序两个相邻的独立加载指令）。维基百科在这里写到。

您能否解释一下这种差异？