modo rapido per verificare se un array di caratteri è zero

Question

Ho una matrice di byte, in memoria. Qual è il modo più veloce per vedere se tutti i byte dell'array sono zero?

Answer 1

Oggigiorno, breve di usare SIMD estensioni (come SSE su processori x86), si potrebbe anche iterate sull'array e confronta ciascun valore 0.

Nel lontano passato, eseguendo un confronto e il ramo condizionale per ogni elemento dell'array (in aggiunta al loop stesso) sarebbe stata considerata costosa e, a seconda di quanto spesso (o presto) ci si poteva aspettare che un elemento diverso da zero apparisse nell'array, si sarebbe potuto scegliere di fare completamente senza condizionali all'interno del ciclo , utilizzando esclusivamente bit per bit, o di rilevare eventuali bit impostati e rimandando il controllo effettivo fino a dopo il ciclo completa:

int sum = 0; 
for (i = 0; i < ARRAY_SIZE; ++i) { 
    sum |= array[i]; 
} 
if (sum != 0) { 
    printf("At least one array element is non-zero\n"); 
} 

Tuttavia, con i disegni di super-scalari pipeline di oggi processore completi di branch prediction, tutti gli approcci non-SSE sono virtualy indistinguibile all'interno di un ciclo. Se mai, confrontando ogni elemento a zero e uscendo anticipatamente dal ciclo (non appena si incontra il primo elemento diverso da zero), nel lungo periodo, si potrebbe essere più efficienti dell'approccio sum |= array[i] (che attraversa sempre l'intero array) a meno che, si presuma che il tuo array sia quasi sempre composto esclusivamente da zero (nel qual caso l'approccio sum |= array[i] senza branching utilizzando GCC -funroll-loops potrebbe fornire i numeri migliori - vedi i numeri sotto per un processore Athlon, i risultati possono variare con il modello di processore e produttore.)

#include <stdio.h> 

int a[1024*1024]; 

/* Methods 1 & 2 are equivalent on x86 */ 

int main() { 
    int i, j, n; 

# if defined METHOD3 
    int x; 
# endif 

    for (i = 0; i < 100; ++i) { 
# if defined METHOD3 
    x = 0; 
# endif 
    for (j = 0, n = 0; j < sizeof(a)/sizeof(a[0]); ++j) { 
#  if defined METHOD1 
     if (a[j] != 0) { n = 1; } 
#  elif defined METHOD2 
     n |= (a[j] != 0); 
#  elif defined METHOD3 
     x |= a[j]; 
#  endif 
    } 
# if defined METHOD3 
    n = (x != 0); 
# endif 

    printf("%d\n", n); 
    } 
} 

$ uname -mp 
i686 athlon 
$ gcc -g -O3 -DMETHOD1 test.c 
$ time ./a.out 
real 0m0.376s 
user 0m0.373s 
sys  0m0.003s 
$ gcc -g -O3 -DMETHOD2 test.c 
$ time ./a.out 
real 0m0.377s 
user 0m0.372s 
sys  0m0.003s 
$ gcc -g -O3 -DMETHOD3 test.c 
$ time ./a.out 
real 0m0.376s 
user 0m0.373s 
sys  0m0.003s 

$ gcc -g -O3 -DMETHOD1 -funroll-loops test.c 
$ time ./a.out 
real 0m0.351s 
user 0m0.348s 
sys  0m0.003s 
$ gcc -g -O3 -DMETHOD2 -funroll-loops test.c 
$ time ./a.out 
real 0m0.343s 
user 0m0.340s 
sys  0m0.003s 
$ gcc -g -O3 -DMETHOD3 -funroll-loops test.c 
$ time ./a.out 
real 0m0.209s 
user 0m0.206s 
sys  0m0.003s 

Answer 2

Se si vuole fare questo in 32-bit C, probabilmente solo un ciclo su l'array come un array intero a 32 bit e confrontarlo con 0, quindi assicurarsi che il materiale alla fine è anche 0.

Answer 3

Se la matrice è di qualsiasi dimensioni adeguate, il vostro fattore limitante su una CPU moderna sta per essere l'accesso al la memoria.

Assicurarsi di utilizzare il prefetching della cache per una distanza decente (ovvero 1-2 K) con qualcosa come __dcbt o prefetchnta (o prefetch0 se si utilizzerà nuovamente il buffer al più presto).

Si vorrà anche fare qualcosa come SIMD o SWAR ao più byte alla volta. Anche con parole a 32 bit, sarà 4 volte meno operazioni rispetto a una versione per carattere. Consiglierei di srotolare le or e di farle nutrire in un "albero" di o. Puoi vedere cosa intendo nel mio esempio di codice: questo sfrutta la capacità superscalare di eseguire due operazioni integer (le o) in parallelo facendo uso di operazioni che non hanno tutte le dipendenze dei dati intermedi. Uso una dimensione di albero di 8 (4x4, quindi 2x2, quindi 1x1) ma è possibile estenderla a un numero maggiore in base al numero di registri liberi presenti nell'architettura della CPU.

Il seguente esempio di pseudo-codice per il ciclo interno (senza prolog/epilog) utilizza inti a 32 bit ma è possibile eseguire 64/128-bit con MMX/SSE o qualsiasi altra cosa è disponibile. Questo sarà abbastanza veloce se hai precaricato il blocco nella cache. Inoltre, è necessario eseguire un controllo non allineato prima se il buffer non è allineato a 4 byte e dopo se il buffer (dopo l'allineamento) non è un multiplo di 32 byte di lunghezza.

const UINT32 *pmem = ***aligned-buffer-pointer***; 

UINT32 a0,a1,a2,a3; 
while(bytesremain >= 32) 
{ 
    // Compare an aligned "line" of 32-bytes 
    a0 = pmem[0] | pmem[1]; 
    a1 = pmem[2] | pmem[3]; 
    a2 = pmem[4] | pmem[5]; 
    a3 = pmem[6] | pmem[7]; 
    a0 |= a1; a2 |= a3; 
    pmem += 8; 
    a0 |= a2; 
    bytesremain -= 32; 
    if(a0 != 0) break; 
} 

if(a0!=0) then ***buffer-is-not-all-zeros*** 

mi sarebbe effettivamente suggerire incapsulare il confronto di una "linea" dei valori in una sola funzione e poi srotolare che un paio di volte con il prefetching cache.

Answer 4

Ecco una soluzione breve e rapida, se stai bene con l'utilizzo dell'assemblaggio in linea.

#include <stdio.h> 

int main(void) { 
    int checkzero(char *string, int length); 
    char str1[] = "wow this is not zero!"; 
    char str2[] = {0, 0, 0, 0, 0, 0, 0, 0}; 
    printf("%d\n", checkzero(str1, sizeof(str1))); 
    printf("%d\n", checkzero(str2, sizeof(str2))); 
} 

int checkzero(char *string, int length) { 
    int is_zero; 
    __asm__ (
     "cld\n" 
     "xorb %%al, %%al\n" 
     "repz scasb\n" 
     : "=c" (is_zero) 
     : "c" (length), "D" (string) 
     : "eax", "cc" 
    ); 
    return !is_zero; 
} 

Nel caso in cui non si ha familiarità con il montaggio, ti spiego quello che facciamo qui: salviamo la lunghezza della stringa in un registro, e chiedo al processore di eseguire la scansione del stringa per uno zero (specifichiamo questo impostando gli 8 bit inferiori dell'accumulatore, ovvero %%al, a zero), riducendo il valore di detto registro su ciascuna iterazione, finché non si incontra un byte diverso da zero. Ora, se la stringa era tutti zero, anche il registro sarà zero, poiché è stato decrementato di numero length di volte. Tuttavia, se è stato rilevato un valore diverso da zero, il "loop" che ha controllato gli zeri è stato interrotto prematuramente, e quindi il registro non sarà zero. Otteniamo quindi il valore di quel registro e restituiamo la sua negazione booleana.

Profiling questo ha dato i seguenti risultati:

$ time or.exe 

real 0m37.274s 
user 0m0.015s 
sys  0m0.000s 


$ time scasb.exe 

real 0m15.951s 
user 0m0.000s 
sys  0m0.046s 

(Entrambi i casi test è stato eseguito 100000 volte su array di dimensioni 100000. Il codice or.exe viene dalla risposta di Vlad chiamate di funzione sono stati eliminati in entrambi i casi..)

Answer 5

Dividere la metà della memoria selezionata e confrontare la prima parte con la seconda.
a. Se c'è differenza, non può essere lo stesso.
b. Se nessuna differenza si ripete per il primo semestre.

Caso peggiore 2 * N. Memoria efficiente e basata su memcmp.
Non so se dovrebbe essere usato nella vita reale, ma mi è piaciuta l'idea di autocontrollo.
Funziona per una lunghezza dispari. Capisci perché? :-)

bool memcheck(char* p, char chr, size_t size) { 
    // Check if first char differs from expected. 
    if (*p != chr) 
     return false; 
    int near_half, far_half; 
    while (size > 1) { 
     near_half = size/2; 
     far_half = size-near_half; 
     if (memcmp(p, p+far_half, near_half)) 
      return false; 
     size = far_half; 
    } 
    return true; 
} 

Answer 6

Misurata due implementazioni su ARM64, una con un ciclo con il ritorno nella fase iniziale falsa, quella che tutti i byte RUP:

int is_empty1(unsigned char * buf, int size) 
{ 
    int i; 
    for(i = 0; i < size; i++) { 
     if(buf[i] != 0) return 0; 
    } 
    return 1; 
} 

int is_empty2(unsigned char * buf, int size) 
{ 
    int sum = 0; 
    for(int i = 0; i < size; i++) { 
     sum |= buf[i]; 
    } 
    return sum == 0; 
} 

risultati:

Tutti i risultati, in microsecondi:

 is_empty1 is_empty2 
MEDIAN 0.350  3.554 
AVG  1.636  3.768 

solo risultati falsi:

 is_empty1 is_empty2 
MEDIAN 0.003  3.560 
AVG  0.382  3.777 

solo veri risultati:

 is_empty1 is_empty2 
MEDIAN 3.649  3,528 
AVG  3.857  3.751 

Sommario: solo per set di dati in cui la probabilità di falsi risultati è molto piccola, il secondo algoritmo utilizzando ORing esegui meglio, grazie al ramo omessa. In caso contrario, tornare presto è chiaramente la strategia più performante.

Answer 7

Rusty Russel's memeqzero è molto veloce.Riusa memcmp per il sollevamento pesante: https://github.com/rustyrussell/ccan/blob/master/ccan/mem/mem.c#L92.