为什么memcmp比for循环检查快得多？

Question

为什么memcmp(a, b, size)比这快得多:

for(i = 0; i < nelements; i++) {
    if a[i] != b[i] return 0;
}
return 1;

memcmp是CPU指令还是什么？它必须非常深,因为我memcmp在循环中使用了大量的加速.

Answer 1

memcmp经常在装配实现采取一些具体的体系结构的特征的优点,它可以使多比C.一个简单的循环更快

作为"内置"

GCC支持memcmp(以及大量其他功能)作为内置.在GCC的某些版本/配置中,呼叫memcmp将被识别为__builtin_memcmp.GCC不会call发送到memcmp库函数,而是发出一些指令作为函数的优化内联版本.

在x86上,这利用了cmpsb指令的使用,该指令将一个内存位置的字节串与另一个内存位置进行比较.这与repe前缀相结合,因此比较字符串直到它们不再相等,或计数耗尽.(究竟是什么memcmp).

给出以下代码:

int test(const void* s1, const void* s2, int count)
{
    return memcmp(s1, s2, count) == 0;
}

gcc version 3.4.4 在Cygwin上生成以下程序集:

; (prologue)
mov     esi, [ebp+arg_0]    ; Move first pointer to esi
mov     edi, [ebp+arg_4]    ; Move second pointer to edi
mov     ecx, [ebp+arg_8]    ; Move length to ecx

cld                         ; Clear DF, the direction flag, so comparisons happen
                            ; at increasing addresses
cmp     ecx, ecx            ; Special case: If length parameter to memcmp is
                            ; zero, don't compare any bytes.
repe cmpsb                  ; Compare bytes at DS:ESI and ES:EDI, setting flags
                            ; Repeat this while equal ZF is set
setz    al                  ; Set al (return value) to 1 if ZF is still set
                            ; (all bytes were equal).
; (epilogue) 

参考:

• cmpsb 指令

作为库函数

memcmp许多C标准库中存在高度优化的版本.这些通常会利用特定于体系结构的指令来并行处理大量数据.

在Glibc中,memcmp x86_64的版本可以利用以下指令集扩展:

• SSE2 -sysdeps/x86_64/memcmp.S
• SSE4 -sysdeps/x86_64/multiarch/memcmp-sse4.S
• SSSE3 -sysdeps/x86_64/multiarch/memcmp-ssse3.S

很酷的部分是glibc将检测(在运行时)CPU的最新指令集,并执行为其优化的版本.请参阅以下代码段sysdeps/x86_64/multiarch/memcmp.S:

ENTRY(memcmp)
    .type   memcmp, @gnu_indirect_function
    LOAD_RTLD_GLOBAL_RO_RDX
    HAS_CPU_FEATURE (SSSE3)
    jnz 2f
    leaq    __memcmp_sse2(%rip), %rax
    ret 

2:  HAS_CPU_FEATURE (SSE4_1)
    jz  3f  
    leaq    __memcmp_sse4_1(%rip), %rax
    ret 

3:  leaq    __memcmp_ssse3(%rip), %rax
    ret 

END(memcmp)

在Linux内核中

Linux似乎没有memcmp针对x86_64 的优化版本,但它确实适用memcpy于arch/x86/lib/memcpy_64.S.请注意,使用替代基础结构(arch/x86/kernel/alternative.c)不仅可以在运行时决定使用哪个版本,而且实际上修补自身只能在启动时做出此决定.