terminar - ¿Por qué memcmp es mucho más rápido que una verificación de bucle for?

for i in range python español

Question

¿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 utilizando memcmp en el bucle.

Answer 1

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

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

Answer 2

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

memcmp intrínseco

Answer 3

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

Answer 4

memcmp menudo se implementa en ensamblaje para aprovechar una serie de características específicas de la arquitectura, que pueden hacerlo 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 será reconocida como __builtin_memcmp . En lugar de emitir una call a la función de biblioteca 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 a otra. Esto se combina con el prefijo repe , por lo que las cadenas se comparan hasta que ya no son iguales, o se agota la cuenta. (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 ensamblaje:

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

Versiones altamente optimizadas de memcmp existen en muchas bibliotecas estándar de C. Estos usualmente aprovecharán las instrucciones específicas de la arquitectura para trabajar con muchos datos en paralelo.

En Glibc, hay versiones de memcmp para x86_64 que pueden aprovechar las siguientes extensiones de conjuntos 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 interesante es que glibc detectará (en tiempo de ejecución) la configuración más reciente que tiene su CPU y ejecutará la versión optimizada para ella. Vea este fragmento de sysdeps/x86_64/multiarch/memcmp.S desde 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

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