¿Por qué es memcmp mucho más rápido que una prueba de bucle?

¿Por qué es memcmp(a, b, size) mucho más rápido que:

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

¿Es memcmp una instrucción de CPU o algo así? Debe ser bastante profundo porque obtuve una aceleración masiva usando memcmp en el ciclo.

memcmp menudo se implementa en ensamblaje para aprovechar una serie de características específicas de la architecture, lo que puede hacer que sea mucho más rápido que un simple bucle en C.

Como un “builtin”

GCC admite memcmp (así como un montón de otras funciones) como builtins . En algunas versiones / configuraciones de GCC, una llamada a memcmp se reconocerá como __builtin_memcmp . En lugar de emitir una call a la función de biblioteca de memcmp , GCC emitirá un puñado de instrucciones para actuar como una versión en línea optimizada de la función.

En x86, esto aprovecha el uso de la instrucción cmpsb , que compara una cadena de bytes en una ubicación de memoria con otra. Esto se combina con el prefijo repe , por lo que las cadenas se comparan hasta que ya no son iguales o se agota el recuento. (Exactamente lo que hace memcmp ).

Dado el siguiente código:

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

gcc version 3.4.4 en Cygwin genera el siguiente conjunto:

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

Referencia:

  • instrucción cmpsb

Como una función de biblioteca

Existen versiones altamente optimizadas de memcmp en muchas bibliotecas estándar de C. Por lo general, aprovecharán las instrucciones específicas de la architecture para trabajar con muchos datos en paralelo.

En Glibc, existen versiones de memcmp para x86_64 que pueden aprovechar las siguientes extensiones del conjunto de instrucciones:

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

La parte más interesante es que glibc detectará (en tiempo de ejecución) la última instrucción configurada que tiene su CPU, y ejecutará la versión optimizada para ello. Vea este fragmento 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) 

En el kernel de Linux

Linux no parece tener una versión optimizada de memcmp para x86_64, pero sí para memcpy , en arch/x86/lib/memcpy_64.S . Tenga en cuenta que se utiliza la infraestructura de alternativas ( arch/x86/kernel/alternative.c ) para no solo decidir en tiempo de ejecución qué versión usar, sino que realmente se aplica un parche para tomar esta decisión solo una vez en el arranque.

Por lo general, es un comstackdor intrínseco que se traduce en un ensamblaje rápido con instrucciones especializadas para comparar bloques de memoria.

memcmp intrínseco

¿Es memcmp una instrucción de CPU o algo así?

Es al menos una función intrínseca proporcionada por el comstackdor muy optimizada. Posiblemente una sola instrucción de máquina, o dos, dependiendo de la plataforma, que no haya especificado.

Sí, en el hardware de Intel, hay una sola instrucción de ensamblaje para tal bucle. El tiempo de ejecución usará eso. (No recuerdo exactamente, era algo así como rep cmps[b|w] , dependiendo también del tamaño de la información)