performance - 当 base+offset 与 base 位于不同的页面时，是否有惩罚？

Question

这三个片段的执行时间:

pageboundary: dq (pageboundary + 8)
...

    mov rdx, [rel pageboundary]
.loop:
    mov rdx, [rdx - 8]
    sub ecx, 1
    jnz .loop

还有这个:

pageboundary: dq (pageboundary - 8)
...

    mov rdx, [rel pageboundary]
.loop:
    mov rdx, [rdx + 8]
    sub ecx, 1
    jnz .loop

还有这个:

pageboundary: dq (pageboundary - 4096)
...

    mov rdx, [rel pageboundary]
.loop:
    mov rdx, [rdx + 4096]
    sub ecx, 1
    jnz .loop

在 4770K 上，第一个片段每次迭代大约 5 个周期，第二个片段每次迭代大约 9 个周期，然后第三个片段每次迭代 5 个周期。它们都访问完全相同的地址，即 4K 对齐。在第二个代码段中，只有地址计算跨越了页面边界: rdx 和 rdx + 8 不属于同一页面，加载仍然对齐。偏移量大时，它又回到了 5 个周期。

这种效果一般是如何工作的？

通过 ALU 指令路由加载结果，如下所示:

.loop:
    mov rdx, [rdx + 8]
    or rdx, 0
    sub ecx, 1
    jnz .loop

使每次迭代需要 6 个周期，这与 5+1 是有意义的。 Reg+8 应该是一个特殊的快速加载，AFAIK 需要 4 个周期，所以即使在这种情况下似乎也有一些惩罚，但只有 1 个周期。

使用这样的测试来回应一些评论:

.loop:
    lfence
    ; or rdx, 0
    mov rdx, [rdx + 8]
    ; or rdx, 0
    ; uncomment one of the ORs
    lfence
    sub ecx, 1
    jnz .loop

将 or 放在 mov 之前使循环比没有任何 or 更快，将 or 放在 0x23141 之后使其更慢 a131414。

Answer 1

优化规则:在链表/树等指针连接数据结构中，将 next 或 left/right 指针放在对象的前 16 个字节中。 malloc 通常返回 16 字节对齐的块( alignof(maxalign_t) )，因此这将确保链接指针与对象的开头位于同一页面中。
确保重要的结构成员与对象的开头位于同一页面的任何其他方法也将起作用。

Sandybridge 系列通常具有 5 个周期的 L1d 负载使用延迟，但有一种特殊情况，用于使用 base+disp 寻址模式进行小正位移的指针追逐。
Sandybridge 系列对于 [reg + 0..2047] 寻址模式有 4 个周期的负载使用延迟，当基本 reg 是 mov 加载的结果，而不是 ALU 指令时。或者，如果 reg+disp 与 reg 位于不同的页面中，则惩罚。
根据 Haswell 和 Skylake(可能还有原始 SnB 但我们不知道)的这些测试结果，似乎以下所有条件都必须为真:

base reg 来自另一个负载 。 (指针追逐的粗略启发式方法，通常意味着加载延迟可能是 dep 链的一部分)。如果对象的分配通常不跨越页面边界，那么这是一个很好的启发式方法。 (硬件显然可以检测到输入是从哪个执行单元转发的。)

寻址模式为 [reg] 或 [reg+disp8/disp32] 。 ( Or an indexed load with an xor-zeroed index register! 通常没有实际用处，但可能会提供一些有关问题/重命名阶段转换负载 uops 的见解。)

位移 < 2048 。即第 11 位以上的所有位都为零(硬件可以在没有全整数加法器/比较器的情况下检查。)

( Skylake 但不是 Haswell/Broadwell ):最后一次加载不是重试的快速路径。 (所以 base = 4 或 5 个周期加载的结果，它将尝试快速路径。但 base = 10 个周期重试加载的结果，它不会。SKL 的惩罚似乎是 10，而 HSW 的惩罚是 9 )。
我不知道是否是在该加载端口上尝试的最后一次加载很重要，或者是否实际上是产生该输入的负载发生了什么。也许并行追踪两条深度链的实验可以提供一些启示；我只尝试了一个指针追逐 dep 链，混合了页面更改和非页面更改位移。

如果所有这些都是真的，加载端口推测最终的有效地址将与基址寄存器在同一页中。 在实际情况下，当负载使用延迟形成循环携带的深度链(例如链表或二叉树)时，这是一种有用的优化。
微架构解释 (我对解释结果的最佳猜测，并非来自英特尔发布的任何内容):
似乎对 L1dTLB 进行索引是 L1d 加载延迟的关键路径。提前开始 1 个周期(不等待加法器的输出来计算最终地址)将使用地址的低 12 位索引 L1d 的整个过程缩短一个周期，然后将该组中的 8 个标记与高位进行比较TLB 产生的物理地址位。 (Intel 的 L1d 是 VIPT 8-way 32kiB，所以它没有混叠问题，因为索引位都来自地址的低 12 位:页面内的偏移量，在虚拟和物理地址中都是相同的。即低 12 位可免费从 virt 转换为 phy。)
由于我们没有发现跨越 64 字节边界的影响，我们知道加载端口在索引缓存之前添加位移。
正如 Hadi 所建议的那样，如果第 11 位有进位，加载端口可能会让错误的 TLB 加载完成，然后使用正常路径重新加载。 ( 在 HSW 上，总加载延迟 = 9。在 SKL 上，总加载延迟可以是 7.5 或 10 )。
立即中止并在下一个周期重试(使其为 5 或 6 个周期而不是 9 个周期)理论上是可能的，但请记住，加载端口是流水线化的，每个时钟吞吐量为 1 个。调度程序希望能够在下一个周期向加载端口发送另一个 uop，而 Sandybridge 系列将延迟标准化为 5 个周期或更短的所有内容。 (没有 2 周期指令)。
我没有测试 2M 大页面是否有帮助，但可能没有。我认为 TLB 硬件足够简单，以至于它无法识别 1 页高的索引仍然会选择相同的条目。因此，它可能会在位移跨越 4k 边界时进行缓慢的重试，即使它在同一个大页面中。 (分页加载以这种方式工作:如果数据实际上跨越了 4k 边界(例如从第 4 页加载 8 字节)，您将支付分页惩罚，而不仅仅是缓存行拆分惩罚，而不管大页面如何)

Intel's optimization manual 在 2.4.5.2 L1 DCache 部分(在 Sandybridge 部分)中记录了这种特殊情况，但没有提到任何不同的页面限制，或者仅在指针不存在的情况下dep 链中的 ALU 指令。

 (Sandybridge)
Table 2-21. Effect of Addressing Modes on Load Latency
-----------------------------------------------------------------------
Data Type             |  Base + Offset > 2048    | Base + Offset < 2048
                      |  Base + Index [+ Offset] |
----------------------+--------------------------+----------------------
Integer               |            5             |  4
MMX, SSE, 128-bit AVX |            6             |  5
X87                   |            7             |  6
256-bit AVX           |            7             |  7
 (remember, 256-bit loads on SnB take 2 cycles in the load port, unlike on HSW/SKL)

这张 table 周围的文字也没有提到 Haswell/Skylake 上存在的限制，也可能存在于 SnB 上(我不知道)。
也许 Sandybridge 没有这些限制并且英特尔没有记录 Haswell 回归，或者英特尔只是没有记录这些限制。该表非常确定寻址模式始终为 4c 延迟，偏移量 = 0..2047。

@Harold 将 ALU 指令作为加载/使用指针追踪依赖链的一部分的实验 证实正是这种影响导致了速度减慢:ALU insn 减少了总延迟，有效地提供了一条指令，例如 1342x 时的负延迟在这个特定的页面交叉情况下添加到 and rdx, rdx dep 链。

此答案中先前的猜测包括建议使用 ALU 中的负载结果与另一个负载是决定延迟的因素。那将是非常奇怪的，需要展望 future 。就我而言，将 ALU 指令添加到循环中的效果是错误的解释。 (我不知道页面交叉的 9 周期效应，并且认为硬件机制是加载端口内结果的转发快速路径。那是有道理的。)
我们可以证明重要的是基本 reg 输入的来源，而不是加载结果的目的地 :在页面边界之前和之后的 2 个不同位置存储相同的地址。创建一个 ALU => 负载 => 负载的 dep 链，并检查它是第 2 个容易受到这种减速影响的负载/能够通过简单的寻址模式从加速中受益。

%define off  16
    lea    rdi, [buf+4096 - 16]
    mov    [rdi], rdi
    mov    [rdi+off], rdi

    mov     ebp, 100000000
.loop:

    and    rdi, rdi
    mov    rdi, [rdi]        ; base comes from AND
    mov    rdi, [rdi+off]    ; base comes from a load

    dec   ebp
    jnz  .loop

    ... sys_exit_group(0)

section .bss
align 4096
buf:    resb 4096*2

在 SKL i7-6700k 上使用 Linux mov rdx, [rdx-8] 计时。

perf ，推测是正确的，我们得到总延迟 = 10 个周期 = 1 + 5 + 4。(每次迭代 10 个周期)。

off = 8 , off = 16 加载很慢，我们得到 16 个周期/iter = 1 + 5 + 10。(SKL 的惩罚似乎比 HSW 更高)

随着加载顺序颠倒(首先执行 [rdi+off] 加载)，无论 off=8 还是 off=16，它始终为 10c，因此我们已经证明，如果 [rdi+off] 的输入来自 ALU 指令，则不会尝试推测性快速路径.
如果没有 mov rdi, [rdi+off] 和 and ，我们会得到预期的每次迭代 8c:两者都使用快速路径。 (@harold 确认 HSW 在这里也有 8 个)。
如果没有 off=8 和 and ，我们每次迭代得到 15c: 5+10 。 off=16 尝试快速路径并失败，占用 10c。然后 mov rdi, [rdi+16] 不会尝试快速路径，因为它的输入失败。 ( @harold 的 HSW 在此处取 13: 4 + 9 。因此，即使最后一条快速路径失败，HSW 也确实尝试了快速路径，并且快速路径失败惩罚在 10 HSW 与 10 HSW 上确实只有 9。在 SKL)
不幸的是，SKL 没有意识到没有位移的 mov rdi, [rdi] 总是可以安全地使用快速路径。

在 SKL 上，循环中只有 [base]，平均延迟为 7.5 个周期。基于对其他混合的测试，我认为它在 5c 和 10c 之间交替:在没有尝试快速路径的 5c 负载之后，下一个确实尝试并失败了，取了 10c。这使得下一个负载使用安全的 5c 路径。
在我们知道快速路径总是会失败的情况下，添加一个归零的索引寄存器实际上会加快它的速度。或者不使用基址寄存器，例如 mov rdi, [rdi+16] ，NASM 将其组装为 [nosplit off + rdi*1] 。请注意，这需要一个 disp32，因此对代码大小不利。
还要注意，微融合内存操作数的索引寻址模式在某些情况下是未分层的，而 base+disp 模式则不是。但是，如果您使用的是纯负载(如 48 8b 3c 3d 10 00 00 00 mov rdi,QWORD PTR [rdi*1+0x10] 或 mov )，则索引寻址模式本身没有任何问题。但是，使用额外的归零寄存器并不是很好。

在 Ice Lake 上，这种用于指针追逐加载的特殊 4 周期快速路径消失了:在 L1 中命中的 GP 寄存器加载现在通常需要 5 个周期，基于索引的存在或偏移量的大小没有区别。