最小操作码大小 x86-64 strlen 实现
Minimal opcode size x86-64 strlen implementation
我正在研究我的代码高尔夫/二进制可执行文件的最小操作码大小 x86-64 strlen 实现，这不应该超过一定尺寸（为简单起见考虑演示场景）。
总体思路来自here, size optimization ideas from and here.
输入字符串地址在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 指令的实现，但这种遗留方法似乎是最小的。
我在 Intel Core i7 4850HQ Haswell 2.3 GHz 上做了一些基准测试，发布版本没有附加调试器。在每个循环中，我测量 1000 个 asm 指令序列并重复 1000 万次以获得平均结果。
我已经制作了重复 asm 指令 100 次的宏。
#define lea100 asm{xor eax,eax};asm { lea ecx,[rax-1] }; // <== Copy pasted 100times
#define or100 asm{xor eax,eax};asm { or ecx,-1 }; // <== Copy pasted 100times
#define sbb100 asm{xor eax,eax};asm { stc };asm{sbb ecx,ecx}; // <== Copy pasted 100times
#define stack100 asm ("xor %eax,%eax;.byte 0x6A; .byte 0xFF ;pop %rcx;"); // <== Copy pasted 100times
为 MacOS 使用内联 asm 测试 C 代码
#include <stdio.h>
#include <CoreServices/CoreServices.h>
#include <mach/mach.h>
#include <mach/mach_time.h>
int main(int argc, const char * argv[]) {
uint64_t start;
uint64_t end;
uint64_t elapsed;
Nanoseconds elapsedNano;
uint64_t sum = 0;
for (int i = 0; i < 10000000 ; i++) {
// this will become
// call imp___stubs__mach_absolute_time
// mov r14, rax
start = mach_absolute_time();
//10x lea100 for example for total 1000
// call imp___stubs__mach_absolute_time
// sub rax, r14
end = mach_absolute_time();
elapsed = end - start;
elapsedNano = AbsoluteToNanoseconds( *(AbsoluteTime *) &elapsed );
uint64_t nano = * (uint64_t *) &elapsedNano;
sum += nano;
}
printf("%f\n",sum/10000000.0);
return 0;
}
结果
xor eax,eax
lea ecx,[rax-1]
205-216 纳秒
xor eax,eax
or ecx,-1
321-355 纳秒
xor eax,eax
push -1
pop rcx
322-359 纳秒
xor eax,eax
stc
sbb ecx,ecx
612-692 纳秒
对于 hacky 足够好的版本，我们知道 rdi 有一个有效地址。 edi 很可能不是一个小整数，因此 2 字节 mov ecx, edi。但这并不安全，因为 RDI 可能指向刚刚超过 4GiB 的边界，因此很难证明它是安全的。除非您使用像 x32 这样的 ILP32 ABI，否则所有指针都低于 4GiB 标记。
因此您可能需要使用 push rdi / pop rcx 复制完整的 RDI，每个 1 个字节。但这会增加短字符串启动的额外延迟。如果您没有长度大于其起始地址的字符串，那应该是安全的。 （但是如果你有任何巨大的数组，那是 plausible 用于静态存储在 .data、.bss 或 .rodata 中；例如 Linux 非 PIE 可执行文件在大约0x401000 = 1<<22.)
如果您只希望 rdi 指向终止 0 字节，而不是实际需要计数，这非常好。或者，如果您在另一个寄存器中有起始指针，那么您可以执行 sub edi, edx 或其他操作并以这种方式获取长度，而不是处理 rcx 结果。 （如果您知道结果适合 32 位，则不需要 sub rdi, rdx 因为您知道它的高位无论如何都会为零。并且高输入位不会影响 [=130= 的低输出位]; 进位从左向右传播。）
对于已知小于 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 个周期延迟，并且可以 运行 在所有主流的多个执行端口上CPUs.
如果您已经有另一个具有已知常量值的寄存器，尤其是异或归零的寄存器，则 3 字节 lea 几乎总是创建常量的最有效的 3 字节方法（如果可行）。 （参见 ）。
I'm fully aware there are implementations using modern cpu instructions, but this legacy approach seems the smallest one.
是的，repne scasb非常紧凑。在典型的 Intel CPU 上，它的启动开销可能大约是 15 个周期，根据 Agner Fog，它发出 >=6n 微指令，吞吐量 >= 2n 个周期，其中 n 是计数（即对于长比较，它比较每个字节 2 个周期，其中隐藏了启动开销），因此它使 lea.
的成本相形见绌
对 ecx 的错误依赖可能会延迟其启动，因此您绝对需要 lea.
repne scasb 可能对您正在做的任何事情都足够快，但它比 pcmpeqb / pmovmsbk / cmp 慢。对于短定长字符串，整数 cmp / jne 非常 当长度为 4 或 8 个字节时 （包括终止 0），假设您可以安全地过度阅读您的字符串，即您不必担心页面末尾的 ""。不过，此方法的开销随字符串长度而变化。例如，对于字符串长度 = 7，您可以执行 4、2 和 1 个操作数大小，或者您可以执行两个双字比较重叠 1 个字节。喜欢 cmp dword [rdi], first_4_bytes / jne； cmp dword [rdi+3], last_4_bytes / jne.
有关 LEA 的更多详细信息
在 Sandybridge-family CPU 上，lea 可以在与它相同的周期内被分派到一个执行单元，并且 xor-zero 被发布到 out-顺序 CPU 核心。 xor-归零是在issue/rename阶段处理的，所以uop以"already-executed"状态进入ROB。指令不可能一直等待 RAX。 （除非在 xor 和 lea 之间发生中断，但即便如此我认为在恢复 RAX 之后和 lea 可以执行之前会有一个序列化指令，所以它不会被卡住等待.)
简单 lea 可以 运行 在 SnB 上的端口 0 或端口 1，或 Skylake 上的端口 1 / 端口 5（每个时钟吞吐量 2 个，但有时不同 SnB 系列上的不同端口 CPU秒）。这是 1 个周期的延迟，所以很难做得更好。
您不太可能看到使用 mov ecx, -1（5 字节）可以在任何 ALU 端口上 运行 获得任何加速。
在 AMD Ryzen 上，64 位模式下的 lea r32, [m] 被视为 "slow" LEA，它只能在 2 个端口上 运行，并且具有 2c 延迟而不是 1。更糟糕的是，Ryzen 并没有消除异或归零。
您所做的微基准测试 只测量没有虚假依赖的版本的吞吐量，而不是延迟。这通常是一个有用的衡量标准，您确实得到了 lea 是最佳选择的正确答案。
纯吞吐量能否准确反映您的真实用例是另一回事。如果字符串比较在关键路径上作为长的或循环携带的数据依赖链的一部分，并且没有被 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
我正在研究我的代码高尔夫/二进制可执行文件的最小操作码大小 x86-64 strlen 实现，这不应该超过一定尺寸（为简单起见考虑演示场景）。
总体思路来自here, size optimization ideas from
输入字符串地址在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 指令的实现，但这种遗留方法似乎是最小的。
我在 Intel Core i7 4850HQ Haswell 2.3 GHz 上做了一些基准测试，发布版本没有附加调试器。在每个循环中，我测量 1000 个 asm 指令序列并重复 1000 万次以获得平均结果。
我已经制作了重复 asm 指令 100 次的宏。
#define lea100 asm{xor eax,eax};asm { lea ecx,[rax-1] }; // <== Copy pasted 100times
#define or100 asm{xor eax,eax};asm { or ecx,-1 }; // <== Copy pasted 100times
#define sbb100 asm{xor eax,eax};asm { stc };asm{sbb ecx,ecx}; // <== Copy pasted 100times
#define stack100 asm ("xor %eax,%eax;.byte 0x6A; .byte 0xFF ;pop %rcx;"); // <== Copy pasted 100times
为 MacOS 使用内联 asm 测试 C 代码
#include <stdio.h>
#include <CoreServices/CoreServices.h>
#include <mach/mach.h>
#include <mach/mach_time.h>
int main(int argc, const char * argv[]) {
uint64_t start;
uint64_t end;
uint64_t elapsed;
Nanoseconds elapsedNano;
uint64_t sum = 0;
for (int i = 0; i < 10000000 ; i++) {
// this will become
// call imp___stubs__mach_absolute_time
// mov r14, rax
start = mach_absolute_time();
//10x lea100 for example for total 1000
// call imp___stubs__mach_absolute_time
// sub rax, r14
end = mach_absolute_time();
elapsed = end - start;
elapsedNano = AbsoluteToNanoseconds( *(AbsoluteTime *) &elapsed );
uint64_t nano = * (uint64_t *) &elapsedNano;
sum += nano;
}
printf("%f\n",sum/10000000.0);
return 0;
}
结果
xor eax,eax
lea ecx,[rax-1]
205-216 纳秒
xor eax,eax
or ecx,-1
321-355 纳秒
xor eax,eax
push -1
pop rcx
322-359 纳秒
xor eax,eax
stc
sbb ecx,ecx
612-692 纳秒
对于 hacky 足够好的版本，我们知道 rdi 有一个有效地址。 edi 很可能不是一个小整数，因此 2 字节 mov ecx, edi。但这并不安全，因为 RDI 可能指向刚刚超过 4GiB 的边界，因此很难证明它是安全的。除非您使用像 x32 这样的 ILP32 ABI，否则所有指针都低于 4GiB 标记。
因此您可能需要使用 push rdi / pop rcx 复制完整的 RDI，每个 1 个字节。但这会增加短字符串启动的额外延迟。如果您没有长度大于其起始地址的字符串，那应该是安全的。 （但是如果你有任何巨大的数组，那是 plausible 用于静态存储在 .data、.bss 或 .rodata 中；例如 Linux 非 PIE 可执行文件在大约0x401000 = 1<<22.)
如果您只希望 rdi 指向终止 0 字节，而不是实际需要计数，这非常好。或者，如果您在另一个寄存器中有起始指针，那么您可以执行 sub edi, edx 或其他操作并以这种方式获取长度，而不是处理 rcx 结果。 （如果您知道结果适合 32 位，则不需要 sub rdi, rdx 因为您知道它的高位无论如何都会为零。并且高输入位不会影响 [=130= 的低输出位]; 进位从左向右传播。）
对于已知小于 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 个周期延迟，并且可以 运行 在所有主流的多个执行端口上CPUs.
如果您已经有另一个具有已知常量值的寄存器，尤其是异或归零的寄存器，则 3 字节 lea 几乎总是创建常量的最有效的 3 字节方法（如果可行）。 （参见
I'm fully aware there are implementations using modern cpu instructions, but this legacy approach seems the smallest one.
是的，repne scasb非常紧凑。在典型的 Intel CPU 上，它的启动开销可能大约是 15 个周期，根据 Agner Fog，它发出 >=6n 微指令，吞吐量 >= 2n 个周期，其中 n 是计数（即对于长比较，它比较每个字节 2 个周期，其中隐藏了启动开销），因此它使 lea.
对 ecx 的错误依赖可能会延迟其启动，因此您绝对需要 lea.
repne scasb 可能对您正在做的任何事情都足够快，但它比 pcmpeqb / pmovmsbk / cmp 慢。对于短定长字符串，整数 cmp / jne 非常 当长度为 4 或 8 个字节时 （包括终止 0），假设您可以安全地过度阅读您的字符串，即您不必担心页面末尾的 ""。不过，此方法的开销随字符串长度而变化。例如，对于字符串长度 = 7，您可以执行 4、2 和 1 个操作数大小，或者您可以执行两个双字比较重叠 1 个字节。喜欢 cmp dword [rdi], first_4_bytes / jne； cmp dword [rdi+3], last_4_bytes / jne.
有关 LEA 的更多详细信息
在 Sandybridge-family CPU 上，lea 可以在与它相同的周期内被分派到一个执行单元，并且 xor-zero 被发布到 out-顺序 CPU 核心。 xor-归零是在issue/rename阶段处理的，所以uop以"already-executed"状态进入ROB。指令不可能一直等待 RAX。 （除非在 xor 和 lea 之间发生中断，但即便如此我认为在恢复 RAX 之后和 lea 可以执行之前会有一个序列化指令，所以它不会被卡住等待.)
简单 lea 可以 运行 在 SnB 上的端口 0 或端口 1，或 Skylake 上的端口 1 / 端口 5（每个时钟吞吐量 2 个，但有时不同 SnB 系列上的不同端口 CPU秒）。这是 1 个周期的延迟，所以很难做得更好。
您不太可能看到使用 mov ecx, -1（5 字节）可以在任何 ALU 端口上 运行 获得任何加速。
在 AMD Ryzen 上，64 位模式下的 lea r32, [m] 被视为 "slow" LEA，它只能在 2 个端口上 运行，并且具有 2c 延迟而不是 1。更糟糕的是，Ryzen 并没有消除异或归零。
您所做的微基准测试 只测量没有虚假依赖的版本的吞吐量，而不是延迟。这通常是一个有用的衡量标准，您确实得到了 lea 是最佳选择的正确答案。
纯吞吐量能否准确反映您的真实用例是另一回事。如果字符串比较在关键路径上作为长的或循环携带的数据依赖链的一部分，并且没有被 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