Perché memcmp è molto più veloce di un controllo ciclo for?

Percmemcmp(a, b, size) molto più veloce di:

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

Memcmp è un’istruzione della CPU o qualcosa del genere? Deve essere piuttosto profondo perché ho ottenuto una massiccia accelerazione usando memcmp sul loop.

memcmp viene spesso implementato in assembly per sfruttare un numero di funzionalità specifiche dell’architettura, che possono renderlo molto più veloce di un semplice ciclo in C.

Come “costruito”

GCC supporta memcmp (così come una tonnellata di altre funzioni) come built-in . In alcune versioni / configurazioni di GCC, una chiamata a memcmp verrà riconosciuta come __builtin_memcmp . Invece di emettere una call alla funzione di libreria memcmp , GCC emetterà una manciata di istruzioni per fungere da una versione inline ottimizzata della funzione.

Su x86, questo sfrutta l’uso dell’istruzione cmpsb , che confronta una stringa di byte in una posizione di memoria in un’altra. Questo è accoppiato con il prefisso repe , quindi le stringhe vengono confrontate fino a quando non sono più uguali o un conteggio è esaurito. (Esattamente quello che fa memcmp ).

Dato il seguente codice:

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

gcc version 3.4.4 su Cygwin genera il seguente 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) 

Riferimento:

  • istruzione cmpsb

Come funzione di libreria

Esistono versioni ottimizzate di memcmp in molte librerie C standard. Questi in genere sfruttano le istruzioni specifiche dell’architettura per lavorare con molti dati in parallelo.

In Glibc, ci sono versioni di memcmp per x86_64 che possono trarre vantaggio dalle seguenti estensioni dell’insieme di istruzioni:

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

La parte interessante è che glibc rileverà (in fase di esecuzione) le ultime istruzioni impostate dalla CPU, ed eseguirà la versione ottimizzata per essa. Vedi questo snippet da 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) 

Nel kernel di Linux

Linux non sembra avere una versione ottimizzata di memcmp per x86_64, ma lo fa per memcpy , in arch/x86/lib/memcpy_64.S . Si noti che viene utilizzata l’infrastruttura alternativa ( arch/x86/kernel/alternative.c ) per non solo decidere in fase di esecuzione quale versione utilizzare, ma in realtà applicando le patch in modo da prendere questa decisione solo una volta all’avvio.

Di solito è un compilatore intrinseco che viene tradotto in assembly rapido con istruzioni specializzate per confrontare blocchi di memoria.

memcmp intrinseco

Memcmp è un’istruzione della CPU o qualcosa del genere?

È almeno una funzione intrinseca fornita dal compilatore altamente ottimizzata. Forse una singola istruzione della macchina, o due, a seconda della piattaforma, che non hai specificato.

Sì, su hardware Intel, c’è una singola istruzione di assemblaggio per tale ciclo. Il runtime lo utilizzerà. (Non ricordo esattamente, era qualcosa come rep cmps[b|w] , a seconda anche del datasize)