6

我正在研究我的代码打高尔夫球/二进制可执行文件的最小操作码大小x86-64 strlen实现，它不应该超过一定大小（为简单起见，请考虑 demoscene）。
总体思路来自这里，尺寸优化思路来自这里和这里。

输入字符串地址 in 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 指令的实现，但这种传统方法似乎是最小的一种。

4

2 回答 2

3

对于 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 bytes)。这rcx至少会产生 0xFF，甚至更高，具体取决于其中留下的高垃圾。（当读取 RCX 时，这在 Nehalem 和更早的时候有一个部分注册停止，否则只是对旧 RCX 的依赖）。无论如何，然后mov al, -2/sub al, cl得到一个 8 位整数的长度。这可能有用也可能没用。

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

在您提出的选项中

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

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

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

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

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

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

有关 LEA 的更多详细信息

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

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

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

在 AMD Ryzen 上，lea r32, [m]在 64 位模式下被视为只能在 2 个端口上运行的“慢”LEA，并且延迟为 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
于 2018-04-20T15:53:46.083 回答
2

我在 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 纳秒

于 2018-04-19T17:52:52.550 回答