X86 预取优化："computed goto" 线程代码
X86 prefetching optimizations: "computed goto" threaded code
我有一个相当重要的问题，我的计算图有循环和多个 "computational paths"。我没有制作一个调度程序循环，其中每个顶点将被一个接一个地调用，我有一个想法将所有预先分配的 "frame objects" 放在堆中（代码+数据）。
这有点类似于线程代码（甚至更好：CPS），只是在堆上跳来跳去，执行代码。每个代码段都与堆中自己的 "frame pointer" 相关联，并使用与之相关的数据。帧始终保持分配状态。该代码仅在已知位置产生副作用，计算（如果需要）下一个 goto 值并跳转到那里。
我还没有尝试过（要使它正确，这将是一项艰巨的任务，我完全了解所有的困难）所以我想问问 x86 机器方面的专家：它能比调度程序循环更快吗？我知道在硬件中对 call/ret 指令进行了多项优化。
访问相对于堆栈指针或任何其他指针的数据有区别吗？是否有间接跳转的预取（跳转到存储在寄存器中的值？）。
这个想法可行吗？
P.S。如果你读过这篇文章但仍然不明白我的意思（请原谅我解释失败的尝试），请把这整个想象成一组许多预先分配的 堆上的协同程序 相互屈服。过程中没有使用标准的 x86 堆栈，因为一切都在堆上。
直接从一个块跳到另一个块通常是分支预测的胜利，与 return 到一个父间接分支相比，尤其是在 CPU 比 Intel Haswell 更早的情况下。
从每个块的尾部开始跳转，每个分支都有不同的分支预测历史。给定的块通常跳转到同一个下一个块，或者具有几个目标地址的简单模式，这可能很常见。这通常可以很好地预测，因为每个分支都有一个更简单的模式，并且分支历史分布在多个分支上。
如果所有调度都从一个间接分支发生，则可能只有一个 BTB（分支目标缓冲区）条目，并且模式太复杂而无法很好地预测。
Intel Haswell 中的现代 TAGE 分支预测器和后来使用最近的分支历史记录 BTB 索引，包括间接分支目的地，确实解决了这个问题。查看 Indexed branch overhead on X86 64 bit mode, and search for Haswell in https://danluu.com/branch-prediction/
上的评论
具体来说，分支预测和解释器的性能 -
不要相信 Folklore (2015)，作者 Rohou、Swamy 和 Seznec 在解释器基准测试中比较了 Nehalem、SandyBridge 和 Haswell，并用单个 switch 陈述。他们发现 Haswell 做得更好，可能使用了 ITTAGE 预测器。
他们不测试 AMD CPUs。 自打桩机使用 Perceptron neural networks for branch prediction 以来，AMD 发布了一些关于其 CPU 的信息。我不知道他们用一个间接分支处理调度循环的能力如何。
Darek Mihocka discusses this pattern 在解释 CPU 模拟器的上下文中，它从不同指令（或简化的 uops）的处理程序块跳到另一个块。他详细介绍了各种策略在 Core2、Pentium4 和 AMD Phenom 上的性能。 （写于 2008 年）。当前 CPU 上的现代分支预测器最像 Core2。
他最终展示了他所谓的 Nostradamus Distributor 模式，用于检查提前退出（功能 return 函数指针，或 "fire escape" 哨兵），在分支预测友好方法。如果您不需要，请参阅文章的前半部分，他谈到了区块之间的直接跳转链接与中央分发服务器。
他甚至哀叹 x86 中缺少代码预取指令。这对于 Pentium 4 来说可能是一个更大的问题，与来自跟踪缓存的 运行ning 相比，填充跟踪缓存的初始解码 非常 慢。 Sandybridge-family 有一个解码的 uop 缓存，但它不是跟踪缓存，解码器仍然足够强大，不会在 uop 缓存未命中时出错。锐龙类似。
Is there a difference between accessing data relative to the stack pointer or any other pointer?
没有。您甚至可以在跳跃后设置 rsp，这样每个块都可以有自己的堆栈。如果您安装了任何信号处理程序，rsp 需要指向有效内存。另外，如果你想 call 任何普通的库函数，你需要 rsp 作为堆栈指针，因为它们会想要 ret.
Is there a prefetching for an indirect jump (jump to value stored in register?).
预取到 L2 可能很有用如果您在准备好执行间接跳转之前很久就知道分支目标地址。所有当前的 x86 CPUs 使用分离的 L1I / L1D 缓存，所以 prefetcht0 会污染 L1D 而没有任何好处，但 prefetcht1 可能有用（提取到 L2 和 L3）。或者它可能根本没有用，如果代码在 L2 中已经很热。
还有用处：尽早计算跳转目标地址，这样乱序执行可以解决分支，而大量工作在乱序内核中排队。这最大限度地减少了管道中的潜在气泡。如果可能，使计算独立于其他内容。
最好的情况是在 jmp 之前的许多指令的寄存器中的地址，因此一旦 jmp 在执行端口上获得一个周期，它就可以向前端提供正确的目的地 -结束（如果分支预测错误则重新引导）。最坏的情况是分支目标是分支之前的长指令依赖链的结果。几个独立的指令，and/or 内存间接跳转，没问题；一旦它们在 OOO 调度程序中，乱序执行应该找到 运行 这些指令的周期。
也有分离的L1iTLB和L1dTLB，但L2TLB在大多数微架构上通常是统一的。但是 IIRC，L2TLB 作为 L1 TLB 的受害者缓存。预取可能会触发页面遍历以填充 L1 数据 TLB 中的条目，但在某些微体系结构上这无助于避免 iTLB 未命中。 （至少它会将页面 table 数据本身放入 L1D 或页面遍历硬件中的内部页面目录缓存中，因此同一条目的另一个页面遍历会很快。但是由于 CPU除了 Intel Skylake（及更高版本）只有一个硬件页面遍历单元，如果在第一页遍历仍在发生时发生 iTLB 未命中，它可能无法立即开始，因此如果您的代码实际上可能会受到伤害太分散了，你会得到 iTLB 未命中。）
使用 2MB 大页面作为内存块，你将 JIT 到内存块以减少 TLB 未命中。可能最好将代码布置在一个相当紧凑的区域中，并将数据分开。 DRAM 局部效应是真实存在的。 （我认为 DRAM 页面通常大于 4kiB，但这是硬件问题，您无法选择。在已打开的页面中访问延迟较低。）
参见 Agner Fog's microarch pdf, and also Intel's optimization manual.. (And AMD's manual too, if you are worried about AMD CPUs). See more links in the x86 标签 wiki。
Is this idea even viable?
是的，可能。
如果可能，当一个块总是跳到另一个块时，通过使块连续来消除跳转。
数据的相对寻址很容易：x86-64 具有 RIP 相对寻址。
您可以 lea rdi, [rel some_label] 然后从那里建立索引，或者直接对您的一些静态数据使用 RIP 相对寻址。
您将对您的代码进行 JIT 处理，因此只需计算从当前指令末尾到要访问的数据的带符号偏移量，这就是您的 RIP 相对偏移量。与位置无关的代码 + 静态数据在 x86-64 中很容易。
我有一个相当重要的问题，我的计算图有循环和多个 "computational paths"。我没有制作一个调度程序循环，其中每个顶点将被一个接一个地调用，我有一个想法将所有预先分配的 "frame objects" 放在堆中（代码+数据）。
这有点类似于线程代码（甚至更好：CPS），只是在堆上跳来跳去，执行代码。每个代码段都与堆中自己的 "frame pointer" 相关联，并使用与之相关的数据。帧始终保持分配状态。该代码仅在已知位置产生副作用，计算（如果需要）下一个 goto 值并跳转到那里。
我还没有尝试过（要使它正确，这将是一项艰巨的任务，我完全了解所有的困难）所以我想问问 x86 机器方面的专家：它能比调度程序循环更快吗？我知道在硬件中对 call/ret 指令进行了多项优化。
访问相对于堆栈指针或任何其他指针的数据有区别吗？是否有间接跳转的预取（跳转到存储在寄存器中的值？）。
这个想法可行吗？
P.S。如果你读过这篇文章但仍然不明白我的意思（请原谅我解释失败的尝试），请把这整个想象成一组许多预先分配的 堆上的协同程序 相互屈服。过程中没有使用标准的 x86 堆栈，因为一切都在堆上。
直接从一个块跳到另一个块通常是分支预测的胜利，与 return 到一个父间接分支相比，尤其是在 CPU 比 Intel Haswell 更早的情况下。
从每个块的尾部开始跳转，每个分支都有不同的分支预测历史。给定的块通常跳转到同一个下一个块，或者具有几个目标地址的简单模式，这可能很常见。这通常可以很好地预测，因为每个分支都有一个更简单的模式，并且分支历史分布在多个分支上。
如果所有调度都从一个间接分支发生，则可能只有一个 BTB（分支目标缓冲区）条目，并且模式太复杂而无法很好地预测。
Intel Haswell 中的现代 TAGE 分支预测器和后来使用最近的分支历史记录 BTB 索引，包括间接分支目的地，确实解决了这个问题。查看 Indexed branch overhead on X86 64 bit mode, and search for Haswell in https://danluu.com/branch-prediction/
上的评论具体来说，分支预测和解释器的性能 -
不要相信 Folklore (2015)，作者 Rohou、Swamy 和 Seznec 在解释器基准测试中比较了 Nehalem、SandyBridge 和 Haswell，并用单个 switch 陈述。他们发现 Haswell 做得更好，可能使用了 ITTAGE 预测器。
他们不测试 AMD CPUs。 自打桩机使用 Perceptron neural networks for branch prediction 以来，AMD 发布了一些关于其 CPU 的信息。我不知道他们用一个间接分支处理调度循环的能力如何。
Darek Mihocka discusses this pattern 在解释 CPU 模拟器的上下文中，它从不同指令（或简化的 uops）的处理程序块跳到另一个块。他详细介绍了各种策略在 Core2、Pentium4 和 AMD Phenom 上的性能。 （写于 2008 年）。当前 CPU 上的现代分支预测器最像 Core2。
他最终展示了他所谓的 Nostradamus Distributor 模式，用于检查提前退出（功能 return 函数指针，或 "fire escape" 哨兵），在分支预测友好方法。如果您不需要，请参阅文章的前半部分，他谈到了区块之间的直接跳转链接与中央分发服务器。
他甚至哀叹 x86 中缺少代码预取指令。这对于 Pentium 4 来说可能是一个更大的问题，与来自跟踪缓存的 运行ning 相比，填充跟踪缓存的初始解码 非常 慢。 Sandybridge-family 有一个解码的 uop 缓存，但它不是跟踪缓存，解码器仍然足够强大，不会在 uop 缓存未命中时出错。锐龙类似。
Is there a difference between accessing data relative to the stack pointer or any other pointer?
没有。您甚至可以在跳跃后设置 rsp，这样每个块都可以有自己的堆栈。如果您安装了任何信号处理程序，rsp 需要指向有效内存。另外，如果你想 call 任何普通的库函数，你需要 rsp 作为堆栈指针，因为它们会想要 ret.
Is there a prefetching for an indirect jump (jump to value stored in register?).
预取到 L2 可能很有用如果您在准备好执行间接跳转之前很久就知道分支目标地址。所有当前的 x86 CPUs 使用分离的 L1I / L1D 缓存，所以 prefetcht0 会污染 L1D 而没有任何好处，但 prefetcht1 可能有用（提取到 L2 和 L3）。或者它可能根本没有用，如果代码在 L2 中已经很热。
还有用处：尽早计算跳转目标地址，这样乱序执行可以解决分支，而大量工作在乱序内核中排队。这最大限度地减少了管道中的潜在气泡。如果可能，使计算独立于其他内容。
最好的情况是在 jmp 之前的许多指令的寄存器中的地址，因此一旦 jmp 在执行端口上获得一个周期，它就可以向前端提供正确的目的地 -结束（如果分支预测错误则重新引导）。最坏的情况是分支目标是分支之前的长指令依赖链的结果。几个独立的指令，and/or 内存间接跳转，没问题；一旦它们在 OOO 调度程序中，乱序执行应该找到 运行 这些指令的周期。
也有分离的L1iTLB和L1dTLB，但L2TLB在大多数微架构上通常是统一的。但是 IIRC，L2TLB 作为 L1 TLB 的受害者缓存。预取可能会触发页面遍历以填充 L1 数据 TLB 中的条目，但在某些微体系结构上这无助于避免 iTLB 未命中。 （至少它会将页面 table 数据本身放入 L1D 或页面遍历硬件中的内部页面目录缓存中，因此同一条目的另一个页面遍历会很快。但是由于 CPU除了 Intel Skylake（及更高版本）只有一个硬件页面遍历单元，如果在第一页遍历仍在发生时发生 iTLB 未命中，它可能无法立即开始，因此如果您的代码实际上可能会受到伤害太分散了，你会得到 iTLB 未命中。）
使用 2MB 大页面作为内存块，你将 JIT 到内存块以减少 TLB 未命中。可能最好将代码布置在一个相当紧凑的区域中，并将数据分开。 DRAM 局部效应是真实存在的。 （我认为 DRAM 页面通常大于 4kiB，但这是硬件问题，您无法选择。在已打开的页面中访问延迟较低。）
参见 Agner Fog's microarch pdf, and also Intel's optimization manual.. (And AMD's manual too, if you are worried about AMD CPUs). See more links in the x86 标签 wiki。
Is this idea even viable?
是的，可能。
如果可能，当一个块总是跳到另一个块时，通过使块连续来消除跳转。
数据的相对寻址很容易：x86-64 具有 RIP 相对寻址。
您可以 lea rdi, [rel some_label] 然后从那里建立索引，或者直接对您的一些静态数据使用 RIP 相对寻址。
您将对您的代码进行 JIT 处理，因此只需计算从当前指令末尾到要访问的数据的带符号偏移量，这就是您的 RIP 相对偏移量。与位置无关的代码 + 静态数据在 x86-64 中很容易。