我有一个相当重要的问题,我的计算图有循环和多个“计算路径”。我没有创建一个调度器循环,每个顶点都将被一个接一个地调用,我有一个想法,把所有预先分配的“框架对象”放在堆中(代码+数据)。
这在某种程度上类似于线程化代码(或者更好:CPS),只是在堆中跳来跳去,执行代码。每个代码段都与堆中自己的“帧指针”相关联,并使用与之相关的数据。帧始终保持分配状态。代码只是在已知位置产生副作用,计算(如果需要)下一个后藤值并跳到那里。
我还没有尝试过它(这将是一个重大的承诺,使其正确,我完全知道所有的困难),所以我想问x86机械Maven:它能比调度器循环更快吗?我知道有几种针对call/ret指令的优化在硬件中发生。
访问相对于堆栈指针的数据和访问任何其他指针的数据有什么区别吗?间接跳转(跳转到寄存器中存储的值?)有预取吗?
这个主意可行吗?
另外,如果你读了这篇文章,仍然不明白我的意思(原谅我解释的失败),把这个整体想象成一个堆上许多预先分配的**协程的集合,它们彼此让步。标准的x86栈在这个过程中不使用,因为所有的东西都在堆上。
1条答案
按热度按时间csga3l581#
直接从一个块跳到另一个块通常是分支预测的优势,而不是返回到一个父间接分支,尤其是在比Intel Haswell更老的CPU上。
由于从每个块的尾部跳转,每个分支都有不同的分支预测器历史。对于给定的块来说,通常跳转到同一个下一个块,或者具有一对目标地址的简单模式是很常见的。这通常可以很好地预测,因为每个分支都有一个简单的模式,并且分支历史分布在多个分支上。
如果所有的分派都发生在一个间接分支上,那么它可能只有一个BTB(分支目标缓冲区)条目,而且模式太复杂,它无法很好地预测。
Rohou、Swamy和Seznec的**Branch Prediction and the Performance of Interpreters - Don’t Trust Folklore(2015)**比较了Nehalem、SandyBridge和Haswell在解释器基准测试上的表现,并测量了使用单个
switch
语句的调度循环的实际误预测率,他们发现Haswell做得更好,可能使用了ITTAGE预测器。Darek Mihocka discusses this pattern在一个解释CPU模拟器的上下文中,它从一个处理程序块跳到另一个处理程序块,用于不同的指令(或简化的uop)。他详细介绍了Core2、Pentium4和AMD Phenom上各种策略的性能。(它写于2008年)。当前CPU上的现代分支预测器最像Core2。
最后,他提出了一种称为诺查丹玛斯分发器(Nostradamus Distributor)的模式,用于检查早期溢出(函数返回一个函数指针,或者一个"防火出口"标记)。如果你不需要这种模式,请参阅文章的前半部分,他讨论了块之间跳转的直接链接与中央分发器。
他甚至哀叹x86中缺少代码预取指令。这可能是奔腾4的一个更大的问题,与从跟踪缓存运行相比,初始解码填充跟踪缓存是 * 非常 * 慢的。Sandybridge系列有一个解码的uop缓存,但它不是跟踪缓存,解码器仍然足够强大,当uop缓存未命中时不会被吸入。Ryzen也是如此。
访问相对于堆栈指针的数据和访问任何其他指针的数据有什么区别吗?
不。你甚至可以在跳转后设置
rsp
,这样每个块都可以有自己的堆栈。如果你安装了任何信号处理程序,rsp
需要指向有效的内存。同样,如果你想能够call
任何普通的库函数,你需要rsp
作为堆栈指针,因为它们会想要ret
。是否存在间接跳转的预取(跳转到寄存器中存储的值?)
如果您在准备执行间接跳转之前就知道分支目标地址,那么预取到L2可能会很有用**。当前所有x86 CPU都使用L1I/L1D分离缓存,因此
prefetcht0
会污染L1D,但没有任何好处,但是prefetcht1
可能会很有用(预取到L2和L3)。或者,如果代码在L2中已经很热,那么它可能根本没有用。还可用于:尽可能早地计算跳转目标地址,这样乱序执行可以在大量工作在乱序核心排队时解析分支。这可以最小化管道中潜在的气泡。如果可能,保持计算独立于其他工作。
最好的情况是在寄存器中寻址
jmp
之前的许多指令,这样,只要jmp
在执行端口上获得一个周期,它就可以向前端提供正确的目的地(并且如果分支预测出错则重新引导)。最坏的情况是当分支目标是正好在分支之前的指令的长相关性链的结果时。和/或存储器间接跳转也可以;一旦指令进入OOO调度程序,乱序执行就应该找到周期来运行这些指令。L1iTLB和L1dTLB也是分开的,但L2TLB通常在大多数微体系结构上是统一的。但是IIRC,L2TLB作为L1 TLB的牺牲品高速缓存工作。预取可能触发页遍历以填充L1数据TLB中的条目。但在某些微体系结构上,这无助于避免iTLB未命中。(至少它会将页表数据本身放入L1D或页遍历硬件中的内部页目录缓存中,所以对相同条目的另一次页面遍历将是快速的。但是由于除了IntelSkylake(以及更高版本)之外的CPU只有1个硬件页面遍历单元,如果iTLB未命中发生在第一次页遍历仍在进行的时候,它可能无法立即开始,因此如果代码过于分散,导致iTLB未命中,实际上可能会造成损害。)
使用2MB的大页面作为JIT内存块,以减少TLB未命中。可能最好将代码布局在一个相当紧凑的区域中,数据是分开的。DRAM局部性效应是真实存在的。(我认为DRAM页面通常大于4kB,但这是硬件问题,你无法选择。在已经打开的页面中访问延迟较低。)
请参阅Agner Fog's microarch pdf,以及英特尔的优化手册(如果你担心AMD的CPU,也可以参阅AMD的手册)。
这个主意可行吗?
是的,可能吧。
如果可能,当一个块总是跳转到另一个块时,通过使块连续来取消跳转。
数据的相对寻址非常简单:x86 - 64具有RIP相对编址。
您可以使用
lea rdi, [rel some_label]
,然后从那里建立索引,或者直接对某些静态数据使用RIP相对寻址。你可能会对代码进行JITting,所以只需计算从当前指令末尾到要访问的数据的带符号偏移量,这就是RIP相关偏移量。位置无关代码+静态数据在x86 - 64中很容易实现。
PREFETCHIT0 [rip+rel32]
将代码预取到缓存的"所有级别",或prefetchit1
预取到除L1i以外的所有级别。这些指令是一个NOP,其寻址模式不同于RIP相对寻址模式,或者是在不支持它们的CPU上。(也许它们也可以启动iTLB甚至uop缓存,或者至少可以在纸上。)英特尔截至2022年12月的"未来扩展"手册中的文档建议目标地址是一些指令的开始。
预取只有在足够早的情况下才有用,而且它不能解决预测错误的问题。解释器预取当前指令 * 之后 * 的字节码指令的代码可能是成功的,也可能不是。**
prefetchit0
不能这样做,它只能与RIP相对寻址一起工作。* * 可能是因为CPU的代码获取部分(如L1i和iTLB)没有用于任意地址的AGU,如果它通过向这些地址提供地址来工作的话?因此,它对预取运行时变量代码位置没有帮助。