把代码和只读数据放在一起是否是个好主意?

6

在回答另一个问题时,我想到了一些我一直想知道的事情:将函数需要的少量非代码数据放在函数旁边而不是传统方法中的另一个部分是否明智?

假设您有一个使用小型只读查找表的小函数。通常的方法似乎是将查找表定位在数据段(例如.rodata),这将通常使其与函数本身的文本相距一定距离。

例如,一个简单的函数,使用16个条目的LUT计算字节的奇偶性:

GLOBAL parity

SECTION .text
parity:
  mov   eax, edi
  shr   edi, 4
  xor   eax, edi
  and   eax, 15
  movzx eax, byte [lut + eax]
  ret

SECTION .rodata
lut:
db 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1

现在这个方法恰好只有16个字节的代码,查找表也是16个字节。所以它们可以很容易地适应同一个缓存行。 这似乎是一个双赢 - 查找表始终在函数中被访问,仅仅由函数访问,因此我们通过将代码和数据并排放置,潜在地将从冷启动调用此函数的成本从2个缓存未命中降低到1个。

GLOBAL parity

SECTION .text
parity:
  mov   eax, edi
  shr   edi, 4
  xor   eax, edi
  and   eax, 15
  movzx eax, byte [lut + eax]
  ret

lut:
db 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1

这与以前相同,只是将表格放在函数1之后的.text部分。

据我所知,在大多数体系结构/可执行格式中通常允许这样做,那么它有什么问题呢?

例如,CPU的指令获取机制是否会因为在我的示例中超出ret并尝试将查找表解释为(无意义)指令而感到困惑?


1请注意,我故意将表格放在代码后面,因为首先需要代码,但也许根据关键字优先,不管怎样交互都不清楚。


3
在x86平台上,你可以使用BT指令来压缩查找表的大小,然而最快计算奇偶校验的方法可能是xor eax, eax test dil, dil setp al - Ross Ridge
@RossRidge - 的确 - 我选择奇偶校验作为一个简单易懂的例子,但是在我写的时候,我想“好吧,我希望有人不要尝试在x86上使用奇偶标志 : )”。从技术上讲,我认为你不一定需要 xor eax, eax,因为至少在 SysV ABI 中,你被允许在其他字节中返回垃圾。把 xor 放在那里可能仍然更快,因为它几乎是免费的,并且打破了对先前值的依赖(哪个更好取决于周围的代码)。 - BeeOnRope
我不太明白在这里如何使用“BT”,你能详细解释一下吗? - BeeOnRope
2
你可以用 bt [lut], eax setc al 替换 MOVZX 指令,并使用一个 2 字节的查找表。或者用 mov di, 0x5555 bt di, ax setc al 替换它,根本不需要表格。或者也许用 movzx edi, dil bt [lut], edi setc al 替换整个函数,但这将需要一个 32 字节的查找表。所有这些都会在更大或更小的表格上交换更多或更少的指令,因此哪种更好取决于内存访问的成本如何。 - Ross Ridge
1
啊,是的 - 在这种情况下(1位返回值),您可以将表压缩到每个条目1位,这样就可以使用更小的表打开很多权衡。也许我应该使用像popcnt这样没有提供此选项的示例。肯定比奇偶校验更复杂的东西涉及到激励示例。@RossRidge - BeeOnRope
2个回答

2
总结:我认为这不会比你预测的更糟(由于这种特殊情况没有特殊惩罚),但通常不值得这样做,因为分裂缓存/ 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位常量,并且许多位模式可以使用单个指令(使用带有立即movmvn的移位寄存器)。

但是,没有理由期望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优化手册的建议,在它之后、数据之前放置一个int3ud2来阻止推测执行:

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           ; 1U << arg

test  eax, 0x5555
setc  al

编译器在许多case标签都运行相同代码的情况下,会使用这个技巧来处理switch语句,就像此示例一样。在Godbolt上使用gcc和clang
另一个例子:在编码挑战答案中的元音/辅音位图,可以将字符串按照其元音/辅音模式是否是回文分类。
在非常高负载的函数中,通常最好使用加载指令而不是立即数移动指令,特别是如果这样做可以节省多个 mov 操作。但是,即使通过对 ALU 指令使用内存操作数来节省一个融合域微操作也可能是值得的,因此存在冷启动与热启动缓存性能之间的权衡。 (但永远不要对内存操作数使用bt它的性能非常糟糕,因为它的 CISC 语义用于索引位串而不是像使用寄存器目标一样包装到由寻址模式选择的双字或四字中)。
或者干脆不使用LUT而是计算。例如,在x86上,支持奇偶校验(仅限低字节)的硬件可以使用test eax,eax / setp al。其他具有硬件popcnt的体系结构可以使用它并取低位作为偶/奇校验。
但是,其他问题可以通过使用LUT或小向量常量来节省大量工作。(可以使用广播加载器(如movddupvpbroadcastd)或每个元素扩展(如pmovsx/pmovzx)进行压缩加载。)

1
我能想到的一件事是,虽然它很好地利用了L2及更高级别的缓存,但对于在L1数据和指令缓存被分割的架构中,它并不是很明显的优胜者1,因为该行将出现在L1D和L1I缓存中的两个中,浪费了每个缓存中的一些空间(例如,在L1I中缓存查找表所使用的空间是被浪费掉的)。

1也就是说,今天几乎所有的主要架构 - 几乎每个人都是修改哈佛...


1
要用尽 L1I 缓存(32kiB!!占据 8 位机器全内存的一半)需要编写相当冗长的代码,这听起来像是 C++ 的泛型或某些受管理语言 JIT 的东西,而不是经过性能优化的代码。如果代码已经没有经过性能优化,由于集成的 LUT 导致的一个缓存未命中对全局范围几乎没有什么影响。(是的,我知道我说话有点过分,并且充满假设,但实际上这只是毫无意义的评论……在性能代码领域中,没有进行剖析就纯粹是胡说八道,不能太认真对待)。 - Ped7g
@Ped7g - 实际上,许多应用程序都遭受 L1I 缓存的影响,例如像浏览器这样具有大量代码的应用程序。当然,像视频编码器这样的小型高度调整的应用程序可能不会遭受影响,但是像游戏引擎这样的应用程序通常会有足够多的代码来耗尽 L1I 缓存。 - BeeOnRope
好的,但浏览器并不是性能调优的软件。我的意思是,以Firefox为例...它的一半运行在JavaScript中(甚至不算它正在显示的页面,我指的只是浏览器本身)。此时,就没有必要再考虑L1缓存的耗尽了,这就像考虑2000kg豪华轿车座椅套的额外重量是否应该去掉一样。游戏引擎通常会做更多(约50倍)比其他任何软件都复杂的事情,特别是同时进行许多不同的复杂操作,它们的代码通常足够密集,我可以接受它。 - Ped7g
当然,你是对的,像浏览器这样笨重的东西永远不可能与一个小巧精细的代码相媲美...也许更好的例子是Linux内核。浏览LKML,你会发现性能是一个非常重要的焦点:很多改变仅仅是为了性能,如果它们的表现不够好,那么这些改变就会被拒绝,新的硬件特性通常只有在它们提高性能的情况下才会被使用等等。我认为许多核心内核黑客在低级别问题上非常熟练。让L1I失效是内核中的一个关键问题... - BeeOnRope
@Ped7g - 是的,但当然反面观点是简单的分析通常会显示LUT非常出色。因此我认为还有一个类似的推论:“糟糕的分析比没有分析更糟糕”。 - BeeOnRope
显示剩余4条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接