manera rápida de comprobar si una matriz de caracteres es cero

Question

Tengo una matriz de bytes, en la memoria. ¿Cuál es la forma más rápida de ver si todos los bytes en la matriz son cero?

Answer 1

Hoy en día, corto de utilizar extensiones SIMD (como SSE en procesadores x86), puede ser que también iterar sobre la matriz y comparar cada valor a 0.

en el pasado distante, realizando una comparación y rama condicional para cada elemento en la matriz (en Además de la rama del bucle en sí mismo) se habría considerado caro y, dependiendo de la frecuencia (o temprano) en que podría esperar que apareciera un elemento distinto de cero en el conjunto, podría haber elegido completamente sin condicionales dentro del ciclo , utilizando exclusivamente a nivel de bits, o para detectar cualquier bits fijados y diferir la verificación real hasta después de que el bucle termina:

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"); 
} 

sin embargo, con diseños súper-escalar pipeline de hoy procesador completos con branch prediction, todas las aproximaciones que no son de la ESS son virtualy indistinguible dentro de un bucle. En todo caso, comparar cada elemento con cero y salir del ciclo temprano (tan pronto como se encuentre el primer elemento distinto de cero) podría ser, a largo plazo, más eficiente que el enfoque sum |= array[i] (que siempre atraviesa toda la matriz) a menos, es decir, se espera que su matriz para ser casi siempre compuesta exclusivamente de ceros (en cuyo caso, haciendo que el enfoque sum |= array[i] verdaderamente sin sucursales mediante el uso de GCC -funroll-loops podría darle los mejores números - ver los números de abajo para un procesador Athlon, los resultados pueden variar con el modelo de procesador y fabricante.)

#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

Si usted quiere hacer esto en 32-bit C, probablemente sólo un bucle sobre la matriz como una matriz de enteros de 32 bits y compararlo con 0, a continuación, asegúrese de que el material al final es también 0.

Answer 3

Si la matriz es de cualquier tamaño decente, el factor limitante en una CPU moderna va a ser el acceso a la memoria.

Asegúrese de utilizar la obtención previa de caché para una distancia decente por delante (es decir 1-2K) con algo como __dcbt o prefetchnta (o prefetch0 si se va a utilizar el búfer de nuevo pronto).

También tendrá que hacer algo como SIMD o SWAR o múltiples bytes a la vez. Incluso con palabras de 32 bits, será 4 veces menos operaciones que una versión por personaje. Recomiendo desenrollar los or's y hacerlos alimentar en un "árbol" de or's. Puede ver lo que quiero decir en mi ejemplo de código: esto aprovecha la capacidad superescalar para hacer dos operaciones enteras (las or) en paralelo al hacer uso de operaciones que no tienen tantas dependencias de datos intermedios. Utilizo un tamaño de árbol de 8 (4x4, luego 2x2, luego 1x1) pero puede expandirlo a un número mayor dependiendo de la cantidad de registros libres que tenga en la arquitectura de su CPU.

El siguiente ejemplo de pseudocódigo para el bucle interno (sin prólogo/epilog) utiliza entradas de 32 bits, pero puede hacer 64/128-bit con MMX/SSE o lo que esté disponible para usted. Esto será bastante rápido si ha captado previamente el bloque en la memoria caché. También es posible que necesite realizar una verificación sin alinear antes si su búfer no está alineado con 4 bytes y luego si su búfer (después de la alineación) no tiene un múltiplo de 32 bytes de longitud.

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*** 

De hecho, me sugieren que encapsula el comparar de una "línea" de los valores en una sola función y luego desenrollar que un par de veces con la obtención previa de caché.

Answer 4

Aquí hay una solución corta y rápida, si está de acuerdo con el uso del ensamblaje en línea.

#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; 
} 

En caso de que usted no está familiarizado con el montaje, voy a explicar lo que hacemos aquí: almacenamos la longitud de la cadena en un registro, y pido al procesador para escanear la cadena para un cero (especificamos esto estableciendo los 8 bits inferiores del acumulador, es decir, %%al, en cero), reduciendo el valor de dicho registro en cada iteración, hasta que se encuentre un byte distinto de cero. Ahora, si la cadena fue todo ceros, el registro también será cero, ya que se disminuyó length número de veces. Sin embargo, si se encuentra un valor distinto de cero, el "bucle" que verificó los ceros terminó prematuramente y, por lo tanto, el registro no será cero. Luego obtenemos el valor de ese registro y devolvemos su negación booleana.

de perfiles de este modo se obtuvieron los siguientes resultados:

$ time or.exe 

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


$ time scasb.exe 

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

(Ambos casos prueba se ejecutó 100000 veces en matrices de tamaño 100000. El código or.exe proviene de la respuesta de Vlad Las llamadas a funciones fueron eliminados en ambos casos..)

Answer 5

Divida la mitad de la memoria marcada y compare la primera parte con la segunda.
a. Si hay alguna diferencia, no puede ser lo mismo.
b. Si no hay diferencia repite para la primera mitad.

Peor caso 2 * N. Memoria eficiente y basada en memcmp.
No estoy seguro de si debería usarse en la vida real, pero me gustó la idea de autocomparación.
Funciona para longitud impar. ¿Ves por qué? :-)

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

midieron dos implementaciones en ARM64, uno utilizando un bucle de retorno con el principio falso, uno que la SRO todos los bytes:

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

Resultados:

Todos los resultados, en microsegundos:

 is_empty1 is_empty2 
MEDIAN 0.350  3.554 
AVG  1.636  3.768 

única falsos resultados:

 is_empty1 is_empty2 
MEDIAN 0.003  3.560 
AVG  0.382  3.777 

resultados sólo verdaderos:

 is_empty1 is_empty2 
MEDIAN 3.649  3,528 
AVG  3.857  3.751 

Resumen: sólo para los conjuntos de datos donde la probabilidad de resultados falsos es muy pequeña, el segundo algoritmo utilizando ORing realiza mejor, debido a la rama omitido. De lo contrario, regresar temprano es claramente la estrategia de mejor desempeño.

Answer 7

Rusty Russel's memeqzero es muy rápido.Reutiliza memcmp para hacer el trabajo pesado: https://github.com/rustyrussell/ccan/blob/master/ccan/mem/mem.c#L92.