总结:我认为这不会比你预测的更糟(由于这种特殊情况没有特殊惩罚),但通常不值得这样做,因为分裂缓存/ TLB并且几乎没有其他好处。为了优化冷缓存情况,请考虑使用立即数据(例如,在使用之前将LUT存储到堆栈中,或者使用立即位图和
bt
指令可以做很多事情)。
理想情况下,您可以将常量与经常在此代码之前或之后运行的代码一起使用。编译器可以使用基于配置文件的优化来查找“热”数据并将其聚集在一起(至少英特尔的VTune帮助建议这可以帮助降低整体dTLB缺失率)。
可能的好处:对于数据加载,L2缓存命中,或者至少在函数不是微小的情况下DRAM页面局部性,如果缓存一开始就是冷的。
主要的缺点是缓存/TLB效率。代码行/页中的数据会污染L1I缓存和iTLB,而数据行/页中的代码会污染L1D缓存和dTLB。
缓存的第一条规则是
缓存有效。经常运行的代码(及其数据)通常在缓存中较热。不经常运行的代码对性能通常不重要。试图通过这种方式优化最坏情况可能会使最好情况更不可能(包括更多代码和数据足迹中的行/页会导致更多的L1I/L1D未命中和/或更多的TLB未命中)。
L2和外部缓存是统一的,但L1是分开的,理智的微体系结构也是这样做的,L1 TLB也是分开的,有多个原因(
芯片前端或执行单元上的物理近距离,读/写端口总数等),特别是在x86架构中,编译器生成的代码中几乎没有重叠的代码和数据。所有现代的x86设计也使用一个L2TLB来处理L1iTLB或L1dTLB的缺失。(英特尔的优化手册称其为STLB,即第二级)。
但与L2缓存不同,我认为Intel的STLB是iTLB和dTLB的受害者缓存。(我不记得在哪里读到这个,也找不到来源。)如果我没记错,在STLB中命中的L1TLB缺失会交换条目,因此不会驱逐或复制任何内容。在两个级别都缺失的情况下,页表行走只会将新条目加载到L1iTLB中。(我认为被驱逐的条目进入STLB,并且从该集合中的STLB中LRU条目被驱逐)。
因此,如果我对Intel CPU上的TLB行为正确,那么
movzx eax,byte [lut + eax]
的dTLB缺失将在STLB中缺失(如果缓存一开始就很冷),即使相同的页面必须已经在iTLB中热了以执行数据加载。至少,页表条目会在L1D缓存和任何内部页行走器缓存中保持热。
可以通过跳转页面并将自身作为数据加载的代码来测试这种行为。例如,重复此块:
here: mov eax,[rip+0]
/
jmp here+4096
/
align 4096
。然后查看来自数据加载(而不是代码获取)的stlb缺失的性能计数器。这将使4k或2M页面的代码/数据局部性变得不那么有价值,但仍然不会比完全分离更糟糕(除了污染问题,可能有有用的代码降低了总共触及的代码页数)。
如果函数和数据不都包含在同一缓存行中,函数中的早期加载可能会导致来自L1D(需求加载)和L1I(推测代码获取)的同一行的未完成缺失(到L2)。我不知道在任何x86 uarches上是否有任何问题。我猜想可能不比通常更糟,希望比两个不同行的未完成错过好。我猜测硬件不会触发任何种类的慢速边角情况处理,但我没有测试过。
如果函数和数据的结尾在下一页上,甚至可以从需求加载+代码获取同时为同一页进行iTLB和dTLB未命中。
然而,我认为从当前代码加载的数据通常会在L2中命中(尽管它可能仍然在L1I中热度很高,但被从L2和可能甚至从像Skylake-AVX512这样的CPU的L3中逐出)。这有时可能值得将两者混合到同一行中,尽管会导致数据工作集和缓存工作集的膨胀。
非x86:
ARM编译器(以及用于ldr r0, =constant
伪指令的汇编器)使用文字池来加载常量大于16位的小PC相对位移。我认为这些常量通常会在代码所在的同一页,有时会在同一个高速缓存行上。显然,ARM微架构被设计成能够高效地运行此类代码(除了不可避免的I-cache / D-cache空间浪费)。但是,代码大小 / 指令计数的好处通常是值得的。我不确定为什么这在ARM上很常见,而在其他RISC ISA(至少我认为它在MIPS / PowerPC上不常见)上不常见。现代ARM具有良好的支持,可使用2个指令创建任意32位常量,并且许多位模式可以使用单个指令(使用带有立即mov
或mvn
的移位寄存器)。
但是,没有理由期望x86微架构在处理这种情况时比默认情况更有效,因为这种模式在x86中并不常见。它不被编译器使用,而且唯一的RIP相对寻址模式使用rel32位移,所以即使将数据放置在代码附近,也没有代码大小优势。只有L3 / L2(和DRAM页面)的局部性好处。
这并不意味着我们应该期望它很慢,只是我们不能从ARM CPU需要高效支持它这一事实推断出x86的行为。使用/支持分页的ARM CPU可能具有偏爱这种模式的TLB分配策略,例如在iTLB缺失时分配L2TLB条目。(如果它们使用多级TLB)。
例如,CPU 的指令获取机制是否会因为在我的示例中超出返回(ret)并尝试将查找表解释为(无意义的)指令而混淆?
超出 ret 的推测执行通常不是问题,看起来如此。我曾经尝试过测试这个问题(使用了一个相当差的测试,我没有投入太多精力),但我没有发现任何影响。也许我没有足够大的测试来击败对于 ret 的分支预测,或者推测执行不像其他间接跳转那样继续超出 ret。即使 call 指令是函数的第一条指令,被调用者与该函数相邻,正确的返回地址也在 call 之后,而不是再次运行 call。因此,在 ret 后面执行指令的推测执行只有在某些情况下才有用,其中某些东西在堆栈上放置了一个虚假的返回地址。
如果您的数据之前的最后一条指令是一个间接的
jmp
,那么担心数据解码为指令是有意义的。您可以按照
Intel优化手册的建议,在它之后、数据之前放置一个
int3
或
ud2
来阻止推测执行:
3.4.1.6
分支类型选择
对于间接跳转,"fall-through"是回退的默认预测(但他们没有提到
ret
)。虚假指令会减慢分支恢复速度。
另外,直接跟在间接分支后面的数据可能会被分支预测硬件视为分支,从而分支到其他数据页执行。这可能会导致后续的自修改代码问题。
汇编/编译器编码规则14.(对M影响,对L通用)当存在间接分支时,请尝试将最可能成为间接分支目标的内容紧随其后。或者,如果间接分支很常见但不能被分支预测硬件预测,请在间接分支后面跟一个
UD2
指令,这将阻止处理器解码下行路径。
只读访问对于乱序流水线本身应该是可以的。只有在 EIP/RIP 附近(可能在2k或4k内)的写入访问会导致自修改代码机器核弹/流水线清除。(因此显然不要将其用于非const静态数据,通常也无法这样做,因为代码页通常被映射为只读/可执行但不可写。)
如果您的LUT足够小,请使用它作为立即数据而不是加载
如果冷缓存性能很重要,您可以使用一对mov r64,imm64
/ mov [m64],r64
指令将LUT存储到堆栈中。 (或者也可以使用mov r/m32,imm32
)。
立即位图非常适合设置bt
指令。 正如@Ross所指出的那样,您可以执行以下操作:
mov eax, 0x5555
bt eax, edi
setc al
或者将位图作为立即操作数传递给
test
指令:
xor eax, eax
bts eax, edi
test eax, 0x5555
setc al
编译器在许多case标签都运行相同代码的情况下,会使用这个技巧来处理switch语句,就像
此示例一样。在Godbolt上使用
gcc和clang。
另一个例子:
在编码挑战答案中的元音/辅音位图,可以将字符串按照其元音/辅音模式是否是回文分类。
在非常高负载的函数中,通常最好使用加载指令而不是立即数移动指令,特别是如果这样做可以节省多个
mov
操作。但是,即使通过对 ALU 指令使用内存操作数来节省一个融合域微操作也可能是值得的,因此存在冷启动与热启动缓存性能之间的权衡。 (但永远不要对内存操作数使用
bt
;
它的性能非常糟糕,因为它的 CISC 语义用于索引位串而不是像使用寄存器目标一样包装到由寻址模式选择的双字或四字中)。
或者干脆不使用LUT而是计算。例如,在x86上,支持奇偶校验(仅限低字节)的硬件可以使用
test eax,eax
/
setp al
。其他具有硬件popcnt的体系结构可以使用它并取低位作为偶/奇校验。
但是,其他问题可以通过使用LUT或小向量常量来节省大量工作。(可以使用广播加载器(如
movddup
或
vpbroadcastd
)或每个元素扩展(如
pmovsx
/
pmovzx
)进行压缩加载。)
xor eax, eax
test dil, dil
setp al
。 - Ross Ridgexor eax, eax
,因为至少在 SysV ABI 中,你被允许在其他字节中返回垃圾。把xor
放在那里可能仍然更快,因为它几乎是免费的,并且打破了对先前值的依赖(哪个更好取决于周围的代码)。 - BeeOnRopebt [lut], eax
setc al
替换 MOVZX 指令,并使用一个 2 字节的查找表。或者用mov di, 0x5555
bt di, ax
setc al
替换它,根本不需要表格。或者也许用movzx edi, dil
bt [lut], edi
setc al
替换整个函数,但这将需要一个 32 字节的查找表。所有这些都会在更大或更小的表格上交换更多或更少的指令,因此哪种更好取决于内存访问的成本如何。 - Ross Ridgepopcnt
这样没有提供此选项的示例。肯定比奇偶校验更复杂的东西涉及到激励示例。@RossRidge - BeeOnRope