当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]当基址寄存器是mov加载结果而不是ALU指令时,Sandybridge系列具有4周期负载使用延迟用于寻址模式.如果reg+disp在不同的页面中,则处以罚款reg.

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

• base reg来自另一个负载.(指针追逐的粗略启发式,通常意味着负载延迟可能是dep链的一部分).如果通常分配对象不跨越页面边界,那么这是一个很好的启发式方法.(HW显然可以检测输入从哪个执行单元转发.)
• 寻址模式是[reg]或[reg+disp8/disp32].(或者带有xor-zeroed索引寄存器的索引加载! 通常没有实际用处,但可能会对问题/重命名阶段转换加载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字节加载),则无论大页面如何,都会支付页面拆分惩罚,而不仅仅是缓存行拆分惩罚)

英特尔的优化手册在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)

围绕此表的文字也未提及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

perf在SKL i7-6700k上使用Linux 进行计时.

• 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]尝试快速路径和失败,以10℃.然后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),那么索引寻址模式本身并没有什么问题.但是,使用额外的归零寄存器并不是很好.