为什么打破LZCNT的"输出依赖性"很重要？

Question

为什么打破LZCNT的"输出依赖性"很重要？

performanceassemblyx86cpu-architecturemicro-optimization

41

在进行基准测试时，我发现吞吐量比我预计的要低得多，经过排查，我发现是LZCNT指令（TZCNT也会出现此问题）导致的，如下所示：

  xor ecx, ecx
_benchloop:
  lzcnt eax, edx
  add ecx, 1
  jnz _benchloop

并且：

  xor ecx, ecx
_benchloop:
  xor eax, eax  ; this shouldn't help, but it does
  lzcnt eax, edx
  add ecx, 1
  jnz _benchloop

第二个版本要快得多。这不应该是这样的。LZCNT没有理由依赖于其输出。与BSR / BSF不同，xZCNT指令总是覆盖其输出。

我在4770K上运行此程序，因此LZCNT和TZCNT不会像BSR / BSF一样被执行。

这里发生了什么？

- harold

也许 lzcnt 不能在 jnz（ZF！= 0）之后执行（它会更新 CF，ZF）。而 xor 则打破了依赖链？但是由于 add 无论如何都会撤销先前的标志，所以我不确定是否是这种情况。 - Brett Hale

只是为了确保：您能排除这是代码对齐问题，与lzcnt无关吗？ - PhiS

@PhiS 使用3个字节的 nop 而不是 xor eax，eax 使它再次变慢。 - harold

1

“xor”解决方案已经添加到gcc 4.9.2中：https://gcc.gnu.org/PR62011 - Falk Hüffner

9

供未来访问者参考，这只是微架构勘误（本质上是一个错误）。LZCNT没有理由在其输出上有一个输入依赖关系，但实际上确实存在。POPCNT指令也有相同的 bug，详见这里。 - Cody Gray

2个回答

4

沿着@BrettHale建议的路线，有可能（尽管很奇怪）你正在遇到一个角落情况下的部分标志更新停顿。理论上，标志状态应该仅仅被重命名，因为以下添加更新所有标志，但如果由于某些原因它没有被重命名，那么它将引入一个循环依赖关系，并且插入xor将打破该依赖关系。

很难确定这是否就是发生的事情，但乍一看似乎是最有可能的解释；您可以通过将xor替换为test（它也会打破标志依赖关系，但对寄存器依赖关系没有影响）来测试假设。

- Stephen Canon

抱歉回复晚了。那是一个好的理论，但不幸的是测试证明它是错误的。在将“xor”更改为“test”后，速度又变慢了。 - harold

2

@harold：这并不不幸。你似乎已经排除了对齐问题，我们刚刚排除了部分标志依赖性。“当你排除了不可能的，无论多么不可思议，剩下的必须是真相。”虽然我们可能还没有完全排除其他所有可能性，但看起来在您的处理器上实现的xZCNT与其重命名输出寄存器存在依赖关系。 - Stephen Canon

在得出结论之前，我还应该测试什么？ - harold

4

实际上，情况确实如此。这是英特尔 CPU 中的性能 bug。现在已经知道了这一点，gcc 尝试通过使用最近未被使用过的输出寄存器来解决它。谷歌应该能够找到一些相关信息。我不知道它是什么时候被发现的，也许是在这次问答活动之后。 - Peter Cordes

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- BeeOnRope · Accepted Answer

这只是你的 Intel Haswell CPU 和几个之前的 CPU 微架构上的限制。Skylake-S (客户端) 已经修复了 tzcnt 和 lzcnt 的问题，但是 popcnt 的问题一直存在，直到在 Cannon Lake 中修复为止。

在这些微架构上，tzcnt、lzcnt 和 popcnt 的目标操作数即使从语义上来说不是输入依赖项，但被视为输入依赖项。我怀疑这不是一个真正的“bug”：如果它只是一个意外行为/疏忽，我希望自从它被引入以来已经发布了几个新的微架构中的一个会修复它。

最有可能的是，这是基于以下两个因素之一或两者的设计妥协：

popcnt、lzcnt 和 tzcnt 的硬件与现有的 bsf 和 bsr 指令很可能是共用的。现实情况下，对于全零位输入的特殊情况，bsf 和 bsr 确实与上一个目标值有依赖关系，因为 Intel 芯片在这种情况下保持目标不变。因此，最简单的设计可能会导致在同一单元上执行其他类似指令继承相同的依赖性。
大多数 x86 双操作 ALU 指令都与目标操作数有依赖关系，因为它也被用作源操作数。这三个受影响的指令在某种程度上是独特的一元运算符，但与现有的单操作数运算符（如 not 和 neg）不同，它们具有不同的源操作数和目标操作数，使它们在表面上类似于大多数2输入指令。也许重命名器/调度电路只是没有区分这些一元带两个寄存器操作数与绝大多数没有这种依赖性的普通共享源/目标 2 输入指令之间的特殊情况。

事实上，对于 popcnt 的情况，英特尔已经发布了各种勘误，涵盖了诸如 HSD146（适用于 Haswell 台式机）和 SKL029（适用于 Skylake）等假依赖问题，其中写道：

POPCNT 指令的执行时间可能比预期长

问题：使用32位或64位操作数的 POPCNT 指令的执行可能会延迟到之前的非依赖性指令已经执行完毕。

影响：使用 POPCNT 指令的软件可能会出现比预期更低的性能。

解决方法：未确定。

我觉得这个勘误很不寻常，因为它实际上没有确定任何类型的功能缺陷或不符合规范的情况，而对于基本上所有其他勘误来说都是如此。Intel 实际上没有为 OoO 执行引擎文档化特定的性能模型，并且还有许多其他性能“陷阱”在多年间出现和消失（其中许多的影响比这个非常小的问题要大得多），它们并没有在勘误中记录。尽管如此，这可能证明它可以被视为一个 bug。奇怪的是，当 tzcnt 或 lzcnt 函数被引入时，勘误从未扩展到它们身上，尽管它们也存在相同的问题。

¹ 好吧，tzcnt 和 lzcnt 只出现在 Haswell 中，但是 popcnt 也有这个问题，它是在 Nehalem 中引入的——但是错误依赖问题可能只存在于 Sandy Bridge 或更高版本。

² 在实践中，虽然没有在 Intel 手册中记录，但由于 Intel 处理器在这种情况下的结果是未定义的，所以大多数或所有 Intel 处理器都将行为实现为在此情况下保持目标寄存器不变。AMD 确实记录并保证了 bsf 和 bsr 的行为。

（但不幸的是，与 tzcnt/lzcnt 相比，这些指令速度较慢。）

在AMD上(extra uops, 参见https://uops.info/), 因此，与其利用bsf的行为，对于AMD CPU，更好的选择通常是使用rep bsf，这样它将在支持该指令的CPU上解码为tzcnt，而在有足够空闲寄存器的情况下，解码为test/cmov。但是bsr即使对于非零输入也会产生不同的结果，因此您可能需要考虑利用它。)