当base + offset与基数不同时，是否存在惩罚？

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之后放置mov使得循环更慢。

Answer 1

优化规则：在指针连接的数据结构（如链表/树）中，将next或left / right指针放在对象的前16个字节中。 malloc通常返回16字节对齐的块（alignof(maxalign_t)），因此这将确保链接指针与对象的开始位于同一页面中。

确保重要结构成员与对象的开头位于同一页面的任何其他方式也将起作用。

---

Sandybridge系列通常具有5个周期的L1d负载使用延迟，但是有一个特殊情况用于指针追踪，具有基本+ disp寻址模式的小正位移。

当基本寄存器是[reg + 0..2047]加载而非ALU指令的结果时，Sandybridge系列对mov寻址模式有4个周期负载使用延迟。或者，如果reg+disp与reg页面不同，则会受到处罚。

基于Haswell和Skylake的这些测试结果（可能是原始的SnB但我们不知道），似乎所有以下条件都必须为真：

• base reg来自另一个负载。 （指针追逐的粗略启发式，通常意味着负载延迟可能是dep链的一部分）。如果通常分配对象不跨越页面边界，那么这是一个很好的启发式方法。 （HW显然可以检测输入从哪个执行单元转发。）
• 寻址模式是[reg]或[reg+disp8/disp32]。 （Or an indexed load with an xor-zeroed index register!通常没有实际用处，但可能会对问题/重命名阶段转换加载uops提供一些见解。）
• 位移<2048.即位11以上的所有位都为零（条件HW可以在没有完整的整数加法器/比较器的情况下进行检查。）
• （Skylake但不是Haswell / Broadwell）：最后一次加载不是重试的快速路径。 （所以base = 4或5次循环加载的结果，它会尝试快速路径。但是base = 10次循环重试负载的结果，它不会.SKL的罚款似乎是10，而HSW则为9 ）。 我不知道这是否是在该加载端口上尝试的最后一次加载，或者它实际上是产生该输入的加载发生了什么。或许平行追逐两个dep链的实验可能会有所启发;我只尝试了一个指针追逐dep链，混合了页面更改和非页面更改位移。

如果所有这些都是真的，加载端口推测最终有效地址将与基址寄存器在同一页面中。在负载使用延迟形成循环传输dep链时，例如链表或二叉树，这在实际情况下是有用的优化。

微架构解释（我最好的解释结果的猜测，而不是英特尔发布的任何内容）：

似乎索引L1dTLB是L1d负载延迟的关键路径。提前1个周期开始（不等待加法器的输出计算最终地址）使用地址的低12位来完成索引L1d索引的整个过程，然后将该组中的8个标记与高位进行比较TLB产生的物理地址的位。 （英特尔的L1d是VIPT 8路32kiB，所以它没有混叠问题，因为索引位都来自地址的低12位：页面内的偏移量在虚拟和物理地址中都是相同的。即低12位从virt转换为phys。）

由于我们没有找到跨越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部分）中记录了这个特例，但没有提到任何不同的页面限制，或者它仅用于指针追逐的事实，并且在有ALU时不会发生在dep链中的指令。

 (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)

围绕此表的文字也未提及Haswell / Skylake上存在的限制，也可能存在于SnB上（我不知道）。

也许Sandybridge没有这些限制，英特尔没有记录Haswell回归，否则英特尔首先没有记录限制。该表非常明确，寻址模式总是4c延迟，偏移量= 0..2047。

---

@ Harold将ALU指令作为加载/使用指针追逐依赖链的一部分的实验证实了这种效应导致了减速：ALU insn减少了总延迟，有效地给出了and rdx, rdx指令的负增量延迟这个特定的翻页案例中的mov rdx, [rdx-8] dep链。

---

此答案中的先前猜测包括在ALU中使用负载结果与另一个负载相关的建议是确定延迟的原因。这将是非常奇怪的，需要展望未来。对于我在循环中添加ALU指令的影响，这是错误的解释。 （我不知道页面交叉的9个循环效果，并且认为HW机制是加载端口内部结果的转发快速路径。这是有道理的。）

我们可以证明它是基本reg输入的来源，而不是加载结果的目的地：在页边界之前和之后的两个不同位置存储相同的地址。创建一个ALU => load => load的dep链，并检查它是否容易受到这种减速的第二个负载/能够通过简单的寻址模式从加速中受益。

%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 perf同时进行。

• off = 8，推测是正确的，我们得到总延迟= 10个周期= 1 + 5 + 4.（每次迭代10个周期）。
• off = 16，[rdi+off]负载很慢，我们得到16个周期/ iter = 1 + 5 + 10.（SKL的罚分似乎高于HSW）

在负载顺序颠倒（首先执行[rdi+off]加载）时，无论off = 8还是off = 16，它始终为10c，因此我们已经证明mov rdi, [rdi+off]如果输入来自ALU指令则不会尝试推测快速路径。

如果没有and和off=8，我们会得到预期的8c：两者都使用快速路径。 （@harold确认HSW在这里得到8分）。

没有and和off=16，我们每次得到15c：5 + 10。 mov rdi, [rdi+16]尝试快速路径并失败，取10c。然后mov rdi, [rdi]不会尝试快速路径，因为它的输入失败了。 （@ harold的HSW在这里需要13：4 + 9.因此，即使最后一个快速路径失败，HSW确实会尝试快速路径，并且HSW上的快速路径失败惩罚实际上仅为9而SKL为10 ）

不幸的是，SKL没有意识到没有位移的[base]总能安全地使用快速路径。

---

在SKL上，循环中只有mov rdi, [rdi+16]，平均延迟为7.5个周期。基于对其他混音的测试，我认为它在5c和10c之间交替：在没有尝试快速路径的5c负载之后，下一个尝试并且失败，取10c。这使得下一次加载使用安全的5c路径。

在我们知道快速路径总是会失败的情况下，添加归零索引寄存器实际上会加快速度。或者不使用基本寄存器，如[nosplit off + rdi*1]，NASM组装到48 8b 3c 3d 10 00 00 00 mov rdi,QWORD PTR [rdi*1+0x10]。请注意，这需要一个disp32，因此对代码大小不利。

还要注意，微融合存储器操作数的索引寻址模式在某些情况下是非层叠的，而base + disp模式则不是。但是如果你使用的是纯粹的负载（比如mov或vbroadcastss），索引寻址模式就没有任何内在错误。但是，使用额外的归零寄存器并不是很好。

Answer 2

我已经在Haswell上进行了足够数量的实验，以确定在完全计算有效地址之前推测性地发出内存负载的确切时间。这些结果也证实了彼得的猜测。

我改变了以下参数：

• 从pageboundary的偏移量。使用的偏移量与pageboundary和加载指令的定义相同。
• 偏移的符号是+或 - 。定义中使用的符号始终与加载指令中使用的符号相反。
• pageboundary在可执行二进制文件中的对齐方式。

在以下所有图中，Y轴表示核心周期中的负载延迟。 X轴表示NS1S2形式的配置，其中N是偏移量，S1是定义中使用的偏移的符号，S2是加载指令中使用的符号。

下图显示仅在偏移为正或零时计算有效地址之前发出的负载。请注意，对于0-15之间的所有偏移，加载指令中使用的基址和有效地址都在同一4K页面内。

下一个图表显示了此模式更改的点。该变化发生在偏移213处，偏移213是最小偏移，其中加载指令中使用的基地址和有效地址都在不同的4K页内。

可以从前两个图表中得出的另一个重要观察是，即使基地址指向与有效地址不同的高速缓存集，也不会产生任何惩罚。所以似乎在计算有效地址后打开缓存集。这表明L1 DTLB命中延迟是2个周期（也就是说，L1D接收标记需要2个周期），但是打开缓存的数据数组和缓存的标记数组只需要1个周期（发生在平行下）。

下图显示当pageboundary在4K页面边界上对齐时会发生什么。在这种情况下，任何非零偏移都将使基本和有效地址位于不同的页面中。例如，如果pageboundary的基址是4096，则加载指令中使用的pageboundary的基址是4096 - offset，对于任何非零偏移，这显然在不同的4K页面中。

下一个图表显示模式从偏移2048开始再次变化。此时，在计算有效地址之前永远不会发出负载。

可以通过测量分派到装载端口2和3的uop数来确认该分析。退役的负载uop的总数是10亿（等于迭代次数）。然而，当测量的负载等待时间是9个周期时，分派给两个端口中的每个端口的负载微量的数量是10亿。此外，当负载等待时间为5或4个周期时，分配给两个端口中的每个端口的负载微量数量为5亿。所以会发生这样的事情：

• 加载单元检查偏移是否为非负且小于2048.在这种情况下，它将使用基址发出数据加载请求。它也将开始计算有效地址。
• 在下一个周期中，完成有效地址计算。如果结果是加载到不同的4K页面，则加载单元等待直到发出的加载完成，然后它丢弃结果并重放加载。无论哪种方式，它都为数据缓存提供设置索引和行偏移量。
• 在下一个周期中，执行标记比较，并将数据转发到加载缓冲区。 （我不确定在L1D或DTLB中是否会丢失地址推测负载是否会中止。）
• 在下一个周期中，加载缓冲区从缓存中接收数据。如果它应该丢弃数据，它将被丢弃，并告知调度程序重放负载，并禁用地址推测。否则，将写回数据。如果下面的指令需要数据进行地址计算，它将在下一个周期接收数据（因此如果所有其他操作数都准备就绪，它将在下一个周期发送）。

这些步骤解释了观察到的4,5和9周期延迟。

可能会发生目标页面是一个巨大的页面。在使用大页面时，加载单元知道基本地址和有效地址是否指向同一页面的唯一方法是让TLB向加载单元提供所访问页面的大小。然后，加载单元必须检查有效地址是否在该页面内。在现代处理器中，在TLB未命中时，使用dedicated page-walk hardware。在这种情况下，我认为加载单元不会将缓存集索引和缓存行偏移提供给数据缓存，并将使用实际有效地址来访问TLB。这需要启用页面漫游硬件来区分具有推测地址和其他负载的负载。只有当其他访问错过TLB时才会进行页面漫步。现在，如果目标页面被证明是一个巨大的页面并且它在TLB中是一个点击，则可能通知加载单元页面的大小大于4K或甚至可能是页面的确切大小。然后，加载单元可以更好地决定是否应该重放负载。但是，此逻辑应该只花费（可能错误的）数据到达为负载分配的加载缓冲区的时间。我想这次只有一个周期。