为什么memcmp(a,b,4)有时只针对uint32比较进行优化？

Question

鉴于此代码:

#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

是否可以对第二种情况应用类似的优化？什么是最好的装配,有没有明确的理由为什么它没有完成(由GCC或Clang)？

在Godbolt的Compiler Explorer上看到它:https://godbolt.org/g/jv8fcf

Answer 1

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

当memcmp比较各个字节时,无论平台如何,它都从低寻址字节变为高寻址字节.

为了memcmp返回零,所有四个字节必须相同.因此,比较的顺序无关紧要.因此,DWORD优化是有效的,因为您忽略了结果的符号.

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

Answer 2

字节序是这里的问题.考虑这个输入:

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

如果通过将它们视为32位整数来比较这两个数组,那么您会发现它a更大(因为0x03000001> 0x02000002).在大端机器上,这个测试可能会按预期工作.

Answer 3

正如其他答案/评论中所讨论的,使用memcmp(a,b,4) < 0等同于unsigned大端整数之间的比较.它无法像== 0little-endian x86 那样高效地内联.

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

如果/当gcc学会内联memcmp除了EQ/NE之外的其他情况,gcc会在小端x86上执行它,当它的启发式告诉它额外的代码大小是值得的.例如,在使用-fprofile-use(轮廓引导优化)进行编译时的热循环中.

如果你希望编译器在这种情况下做得很好,你应该分配给a uint32_t并使用endian-conversion函数ntohl.但请确保选择一个可以内联的内容; 显然Windows有一个ntohl编译DLL调用.对于某些便携式端点的东西,请参阅该问题的其他答案,以及某人对a的一个不完美的尝试portable_endian.h,以及它的这个分支.我正在研究一个版本一段时间,但从未完成/测试或发布它.

指针转换可能是Undefined Behavior,具体取决于您编写字节的方式以及char*指向的内容.如果你不确定严格别名和/或对齐,请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中写的相同),特别是在big-endian平台上,即使是旧的gcc.它也比ICC17提供了更好的代码,ICC17内联memcmp但仅限于字节比较循环(即使是这种== 0情况).

我认为这个手工制作的序列是less4()(对于x86-64 SystemV调用约定,如问题中使用的const char *ain in rdi和bin rsi)的最佳实现.

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的单指令.

必须bswap两个操作数都有一个额外的代码大小成本与== 0情况:我们不能将其中一个加载折叠到内存操作数cmp.(这可以节省代码大小,并且可以通过微融合来实现.)这是最重要的两条bswap指令.

在支持的CPU上movbe,它可以保存代码大小: movbe ecx, [rsi]是一个load + bswap.在Haswell上,它是2 uops,所以可能它解码为与mov ecx, [rsi]/ 相同的uops bswap ecx.在Atom/Silvermont上,它在加载端口处理,因此它的uops更少,代码更小.

见的setcc我XOR归零部分答案更多关于为什么XOR/CMP/setcc(其中铛用途)比CMP好/ setcc/MOVZX(典型的GCC).

在通常的情况下,这内联到分支结果的代码中,setcc + zero-extend被替换为jcc ; 编译器优化在寄存器中创建布尔返回值. 这是内联的另一个优点:库memcmp必须创建一个调用程序测试的整数布尔返回值,因为没有x86 ABI /调用约定允许在flags中返回布尔条件.(我不知道任何非x86调用约定也可以这样做).对于大多数库memcmp实现,根据长度和可能的对齐检查选择策略也会产生很大的开销.这可能相当便宜,但对于4号,它将超过所有实际工作的成本.