Por que o memcmp é muito mais rápido que uma verificação de loop?

Por que o memcmp(a, b, size) é muito mais rápido que:

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

É memcmp uma instrução da CPU ou algo assim? Deve ser bem profundo, porque eu tenho uma aceleração massiva usando memcmp no loop.

memcmp é frequentemente implementado em assembly para tirar proveito de vários resources específicos da arquitetura, o que pode torná-lo muito mais rápido que um simples loop em C.

Como um “builtin”

O GCC suporta memcmp (assim como várias outras funções) como builtins . Em algumas versões / configurações do GCC, uma chamada para memcmp será reconhecida como __builtin_memcmp . Em vez de emitir uma call para a function de biblioteca memcmp , o GCC emitirá um punhado de instruções para atuar como uma versão inline otimizada da function.

No x86, isso aproveita o uso da instrução cmpsb , que compara uma seqüência de bytes em um local de memory para outro. Isso é acoplado ao prefixo do repe , então as strings são comparadas até que não sejam mais iguais, ou uma contagem é esgotada. (Exatamente o que o memcmp faz).

Dado o seguinte código:

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

gcc version 3.4.4 no Cygwin gera a seguinte assembly:

 ; (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) 

Referência:

  • instrução cmpsb

Como uma function de biblioteca

Versões altamente otimizadas do memcmp existem em muitas bibliotecas padrão do C. Geralmente, eles aproveitam as instruções específicas da arquitetura para trabalhar com muitos dados em paralelo.

No Glibc, há versões do memcmp para x86_64 que podem aproveitar as seguintes extensões de conjunto de instruções:

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

A parte legal é que a glibc detectará (em tempo de execução) o mais novo conjunto de instruções que a sua CPU possui e executará a versão otimizada para ela. Veja este trecho de 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) 

No kernel do Linux

O Linux não parece ter uma versão otimizada do memcmp para x86_64, mas sim para o memcpy , em arch/x86/lib/memcpy_64.S . Note que é usada a infra-estrutura de alternativas ( arch/x86/kernel/alternative.c ) para não apenas decidir em tempo de execução qual versão usar, mas realmente corrigir para tomar essa decisão apenas uma vez na boot.

Geralmente é um compilador intrínseco que é traduzido em assembly rápida com instruções especializadas para comparar blocos de memory.

memcmp intrínseco

É memcmp uma instrução da CPU ou algo assim?

É pelo menos uma function intrínseca fornecida pelo compilador altamente otimizada. Possivelmente uma única instrução de máquina, ou duas, dependendo da plataforma, que você não especificou.

Sim, no hardware da Intel, há uma instrução de assembly única para esse loop. O tempo de execução irá usar isso. (Eu não me lembro exatamente, era algo como rep cmps[b|w] , dependendo também do datasize)