最小操作码大小 x86-64 strlen 实现

Question

我正在研究我的代码高尔夫/二进制可执行文件的最小操作码大小x86-64 strlen实现，该实现不应该超过某个大小（为了简单起见，请考虑演示场景）。
一般想法来自这里，大小优化想法来自这里和这里。

输入字符串地址在rdi，最大长度不大于Int32

xor   eax,eax ; 2 bytes
or    ecx,-1  ; 3 bytes
repne scasb   ; 2 bytes
not   ecx     ; 2 bytes
dec   ecx     ; 2 bytes

最终结果是ecx在11字节总数。

问题是关于设置ecx为-1

选项 1 已经说明

or ecx,-1 ; 3 bytes

选项 2

lea ecx,[rax-1] ; 3 bytes 

选项 3

stc         ; 1 byte
sbb ecx,ecx ; 2 bytes

选项 4 ，可能是最慢的一个

push -1 ; 2 bytes
pop rcx ; 1 byte

我的理解是：
选项 1 依赖于先前的ecx值
选项 2 依赖于先前的rax值
选项 3 我不确定它是否依赖于先前的ecx值？
选项 4 是最慢的一个？

这里有明显的赢家吗？
标准是保持操作码的大小尽可能小，并明智地选择最佳的一种。
我完全知道有使用现代 cpu 指令的实现，但这种遗留方法似乎是最小的。

Answer 1

对于一个 hacky 足够好的版本，我们知道rdi有一个有效的地址。这很可能edi不是一个小整数，因此 2 bytemov ecx, edi。但这并不安全，因为 RDI 可能指向刚刚超过 4GiB 边界的位置，因此很难证明它是安全的。除非您使用像 x32 这样的 ILP32 ABI，否则所有指针都低于 4GiB 标记。

因此，您可能需要使用 push rdi / pop rcx 复制完整的 RDI，各 1 个字节。但这会增加短字符串启动的额外延迟。如果您没有长度大于其起始地址的字符串，那么它应该是安全的。（但是，如果您有任何巨大的数组，那么对于 .data、.bss 或 .rodata 中的静态存储来说，这似乎是合理的；例如，Linux 非 PIE 可执行文件的加载时间约为0x401000= 1<<22。）

如果您只想让 rdi 指向终止0字节，而不是实际需要计数，那么这非常有用。或者，如果您的起始指针位于另一个寄存器中，那么您可以执行sub edi, edx某些操作并以这种方式获取长度，而不是处理rcx结果。（如果您知道结果适合 32 位，则不需要sub rdi, rdx，因为您知道该结果的高位无论如何都会为零。并且高输入位不会影响加法/减法的低输出位；进位从左到右传播.)

对于已知小于 255 字节的字符串，可以使用mov cl, -1(2 字节)。这rcx至少会产生 0xFF，甚至更高，具体取决于其中剩余的垃圾量。（当读取 RCX 时，Nehalem 和更早的版本会出现部分注册停顿，否则仅依赖于旧的 RCX）。不管怎样，然后mov al, -2/sub al, cl得到 8 位整数的长度。这可能有用也可能没用。

根据调用者的不同，rcx可能已经保存了一个指针值，在这种情况下，如果可以使用指针减法，则可以保持它不变。

在您提出的选项中

lea ecx,[rax-1]非常好，因为您只需进行异或归零eax，并且它是一个廉价的 1 uop 指令，具有 1 个周期延迟，并且可以在所有主流 CPU 上的多个执行端口上运行。

当您已经拥有另一个具有已知常量值的寄存器时，尤其是异或置零的寄存器时，3 字节lea几乎总是创建常量的最有效的 3 字节方法（如果可行的话）。（请参阅有效地将 CPU 寄存器中的所有位设置为 1）。

我完全知道有使用现代 CPU 指令的实现，但这种传统方法似乎是最小的一种。

是的，repne scasb非常紧凑。在典型的 Intel CPU 上，它的启动开销可能约为 15 个周期，根据Agner Fog的说法，它发出 >=6n uops，吞吐量 >= 2n 个周期，其中n是计数（即，它比较长的每字节 2 个周期）相比之下，启动开销是隐藏的），因此它的成本相形见绌lea。

错误依赖的东西ecx可能会延迟其启动，所以你肯定想要lea.

repne scasb无论您正在做什么，它可能都足够快，但它比pcmpeqb//慢。对于短的固定长度字符串，当长度为 4 或 8 个字节（包括终止 0）时，整数/非常好，假设您可以安全地过度读取字符串，即您不必担心结尾处的问题页面。不过，此方法的开销随字符串长度而变化。例如，对于字符串长度 = 7，您可以执行 4、2 和 1 个操作数大小，或者可以执行两个重叠 1 个字节的双字比较。喜欢; 。pmovmsbkcmpcmpjne""cmp dword [rdi], first_4_bytes / jnecmp dword [rdi+3], last_4_bytes / jne

有关 LEA 的更多详细信息

在 Sandybridge 系列 CPU 上，可以在与它和-0 发出到乱序 CPU 内核的 lea同一周期中将 分派到执行单元。-归零是在问题/重命名阶段处理的，因此uop以“已执行”状态进入ROB。指令不可能必须等待 RAX。（除非 xor 和 之间发生中断，但即便如此，我认为在恢复 RAX 之后和执行之前会有一个序列化指令，所以它不能陷入等待。）xorxorlealea

Simplelea可以在 SnB 上的端口 0 或端口 1 上运行，或者在 Skylake 上的端口 1 / 端口 5 上运行（每个时钟吞吐量 2 个，但有时在不同 SnB 系列 CPU 上运行不同端口）。这是 1 个周期的延迟，因此很难做得更好。

使用可以在任何 ALU 端口上运行的（5 字节），您不太可能看到任何加速mov ecx, -1。

在 AMD Ryzen 上，lea r32, [m]64 位模式下被视为“慢速”LEA，只能在 2 个端口上运行，并且延迟为 2c，而不是 1。更糟糕的是，Ryzen 无法消除异或归零。

您所做的微基准测试仅测量没有错误依赖项的版本的吞吐量，而不是延迟。这通常是一个有用的衡量标准，而且您确实碰巧得到了正确的答案，即lea最佳选择。

纯粹的吞吐量是否准确地反映了有关您的实际用例的任何信息是另一回事。如果字符串比较位于关键路径上，作为长或循环携带的数据依赖链的一部分，并且未被 a 破坏，那么您实际上可能依赖于延迟，而不是吞吐量，从而为您提供分支预测jcc+推测执行。（但是无分支代码通常更大，所以这不太可能）。

stc/sbb ecx,ecx很有趣，但只有 AMD CPU 才将其视为sbb依赖破坏（仅取决于 CF，而不取决于整数寄存器）。在 Intel Haswell 及更早版本上，sbb是一条 2 uop 指令（因为它有 3 个输入：2 个 GP 整数 + 标志）。它有 2c 的延迟，这就是它性能如此糟糕的原因。（延迟是循环携带的 dep 链。）

缩短序列的其他部分

strlen+2根据您正在做的事情，您也许也 可以使用，但要抵消另一个常量或其他东西。dec ecx在 32 位代码中只有 1 个字节，但 x86-64 没有短格式inc/dec指令。所以 not /dec 在 64 位代码中并不那么酷。

之后repne scas，你有ecx = -len - 2（如果你从 开始ecx = -1），并not给你-x-1（即+len + 2 - 1）。

 ; eax = 0
 ; ecx = -1
repne scasb      ; ecx = -len - 2
sub   eax, ecx   ; eax = +len + 2