为什么memcmp(a,b,4)只是有时被优化为uint32比较?

鉴于此代码:

#include <string.h> int equal4(const char* a, const char* b) { return memcmp(a, b, 4) == 0; } int less4(const char* a, const char* b) { return memcmp(a, b, 4) < 0; } 

x86_64上的GCC 7引入了对第一种情况的优化(Clang已经做了很长一段时间):

  mov eax, DWORD PTR [rsi] cmp DWORD PTR [rdi], eax sete al movzx eax, al 

但第二种情况仍然调用memcmp()

  sub rsp, 8 mov edx, 4 call memcmp add rsp, 8 shr eax, 31 

第二种情况可以应用类似的优化吗? 什么是最好的汇编,有没有明确的理由,为什么没有完成(通过海湾合作委员会或铿锵)?

在Godbolt的编译器资源pipe理器中查看: https ://godbolt.org/g/jv8fcf

如果您为little-endian平台生成代码,则将四字节memcmp不等式优化为单个DWORD比较是无效的。

memcmp比较单个字节时,它将从低地址字节转到高地址字节,而不pipe平台如何。

为了使memcmp归零,所有四个字节必须相同。 因此,比较顺序并不重要。 因此,DWORD优化是有效的,因为你忽略了结果的符号。

但是,当memcmp返回一个正数,字节顺序很重要。 因此,使用32位DWORD比较来实现相同的比较需要一个特定的字节顺序:平台必须是大字节,否则比较的结果是不正确的。

字节顺序是这里的问题。 考虑这个input:

 a = 01 00 00 03 b = 02 00 00 02 

如果将这两个数组作为32位整数进行比较,则会发现a较大(因为0x03000001> 0x02000002)。 在一个大型的机器上,这个testing可能会像预期的那样工作。

正如在其他答案/注释中所讨论的那样,使用memcmp(a,b,4) < 0相当于big-endian整数之间的unsigned比较。 在little-endian x86上,它不能像内存一样有效。

更重要的是,gcc7 / 8中这个行为的当前版本只查找memcmp() == 0或者!= 0 。 即使在一个大的endian目标,这可能内联一样有效的<> ,gcc不会这样做。 (Godbolt最新的big-endian编译器是PowerPC 64 gcc6.3,MIPS / MIPS64 gcc5.4。mips是big-endian MIPS, mipsel是little-endian MIPS。)如果用未来的gcctesting,使用a = __builtin_assume_align(a, 4)确保gcc不必担心非x86上的未alignment性能/正确性。 (或者只是使用const int32_t*而不是const char* 。)

如果/当gcc学习内联memcmp而不是EQ / NE时,gcc可能会在little-endian x86上做,当它的启发式告诉它额外的代码大小将是值得的。 例如在使用-fprofile-use (简档引导优化)进行编译时的热循环中。


如果您希望编译器为这种情况做好工作 ,您应该分配一个uint32_t并使用像ntohl这样的endian-conversion函数。 但要确保你select一个可以实际联机的 显然Windows有一个编译为DLL调用的ntohl 。 关于这个问题的其他答案对于一些便携式endian的东西,也有人不完美的尝试在portable_endian.h ,这个分叉 。 我正在研究一个版本,但从来没有完成/testing或发布。

指针转换可能是Undefined Behavior, 这取决于你写字节的方式和char*指向的内容 。 如果您不确定严格别名和/或alignment方式, abytes memcpy写入abytes 。 大多数编译器都擅长优化小型固定大小的memcpy

 // I know the question just wonders why gcc does what it does, // not asking for how to write it differently. // Beware of alignment performance or even fault issues outside of x86. #include <endian.h> #include <stdint.h> int equal4_optim(const char* a, const char* b) { uint32_t abytes = *(const uint32_t*)a; uint32_t bbytes = *(const uint32_t*)b; return abytes == bbytes; } int less4_optim(const char* a, const char* b) { uint32_t a_native = be32toh(*(const uint32_t*)a); uint32_t b_native = be32toh(*(const uint32_t*)b); return a_native < b_native; } 

我检查了Godbolt ,并编译成高效的代码(基本上与我在下面的asm中写的相同),特别是在大端平台上,甚至是旧的gcc。 它也比ICC17更好的代码,ICC17内联memcmp但只是一个字节比较循环(即使在== 0情况下)。


我认为这个手工制作的序列是less4()的最佳实现 (对于x86-64 SystemV调用约定,就像问题中使用的那样, const char *ardibrsi )。

 less4: mov edi, [rdi] mov esi, [rsi] bswap edi bswap esi # data loaded and byte-swapped to native unsigned integers xor eax,eax # solves the same problem as gcc's movzx, see below cmp edi, esi setb al # eax=1 if *a was Below(unsigned) *b, else 0 ret 

这些都是自K8和Core2( http://agner.org/optimize/ )以来,在Intel和AMD CPU上的所有单一指令。

不得不交换两个操作数,与== 0情况相比,有一个额外的代码尺寸成本:我们不能将其中一个负载折叠到cmp的内存操作数中。 (这节省了代码的大小,并且由于微融合, bswap )。这是在两个额外的bswap指令bswap

在支持movbe CPU上,它可以保存代码大小: movbe ecx, [rsi]是一个load + bswap。 在Haswell,它是2 uops,所以大概它解码到相同的bswap ecx mov ecx, [rsi] / bswap ecx 。 在Atom / Silvermont上,它正好在加载端口处理,所以更less的代码和更小的代码。

查看我的xor- setcc答案的setcc部分,了解为什么xor / cmp / setcc(使用clang)优于cmp / setcc / movzx(gcc的典型代码)。

在通常情况下,这将内联分支到结果上的代码中, setcc + zero-extend被replace为jcc ; 编译器优化了在寄存器中创build一个布尔返回值。 这是内联的又一个优点:库memcmp不得不创build一个整数布尔返回值,调用者testing ,因为没有x86 ABI /调用约定允许在标志中返回布尔条件。 (我不知道任何非x86调用约定)。 对于大多数的图书馆memcmp实现,也有很大的开销,在select一个策略取决于长度,也许alignment检查。 这可能相当便宜,但对于规模4,这将比所有真正的工作成本更多。

字节码是一个问题,但是字符是另一个字符。 例如,考虑您比较的四个字节是0x207f2020和0x20802020。 作为签名字符的80是-128,作为签名字符的7f是+127。 但是,如果你比较四个字节,没有比较会给你正确的顺序。

当然你可以用0x80808080做一个异或,然后你可以使用一个无符号的比较。