¿Un enfoque más rápido para verificar un búfer de cero en C?

Estoy buscando un método más rápido para lograr esto:

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

Me doy cuenta de que estoy buscando una micro optimización innecesaria excepto en casos extremos, pero sé que existe un método más rápido y tengo curiosidad por saber qué es.

En muchas arquitecturas, comparar 1 byte toma la misma cantidad de tiempo que 4 u 8, o incluso 16. 4 bytes normalmente es fácil (ya sea int o long), y 8 también lo es (long o long long). 16 o superior probablemente requiera ensamblaje en línea para, por ejemplo, usar una unidad vectorial.

Además, las predicciones erróneas de una rama realmente duelen, puede ayudar a eliminar las ramas. Por ejemplo, si el búfer está casi siempre vacío, en lugar de probar cada bloque contra 0, péguelos juntos y pruebe el resultado final.

Expresar esto es difícil en C portátil: lanzar un char* para long* viola el aliasing estricto. Pero afortunadamente puedes usar memcpy para expresar de forma portátil una carga de varios bytes sin alinear que puede crear un alias de cualquier cosa. Los compiladores lo optimizarán al asm que desee.

Por ejemplo, esta implementación de trabajo en progreso (https://godbolt.org/z/3hXQe7) en el explorador del compilador Godbolt muestra que puede obtener un buen bucle interno (con algunos gastos generales de inicio) al cargar dos uint_fast32_t vars (a menudo de 64 bits) con memcpy y luego verificando tmp1 | tmp2porque muchas CPU establecerán indicadores de acuerdo con un resultado OR, por lo que esto le permite verificar dos palabras por el precio de una.

Lograr que se compile de manera eficiente para los objetivos sin cargas no alineadas eficientes requiere una alineación manual en el código de inicio, e incluso entonces es posible que gcc no esté en línea con el memcpy para cargas donde no se puede probar alineamiento.

Una forma potencial, inspirada en la idea descartada de Kieveli:

int is_empty(char *buf, size_t size)
{
    static const char zero[999] = { 0 };
    return !memcmp(zero, buf, size > 999 ? 999 : size);
}

Tenga en cuenta que no puede hacer que esta solución funcione para tamaños arbitrarios. Podrías hacer esto:

int is_empty(char *buf, size_t size)
{
    char *zero = calloc(size);
    int i = memcmp(zero, buf, size);
    free(zero);
    return i;
}

Pero cualquier asignación de memoria dinámica será más lenta que la que tiene. La única razón por la que la primera solución es más rápida es porque puede usar memcmp()que será optimizado a mano en lenguaje ensamblador por los escritores de la biblioteca y será mucho más rápido que cualquier cosa que pueda codificar en C.

EDITAR: una optimización que nadie más ha mencionado, basada en observaciones anteriores sobre la “probabilidad” de que el búfer esté en el estado X: si un búfer no está vacío, ¿es más probable que no esté vacío al principio o al final? Si es más probable que tenga cruft al final, puede comenzar su verificación al final y probablemente vea un pequeño aumento de rendimiento.

EDIT 2: Gracias a Accipitridae en los comentarios:

int is_empty(char *buf, size_t size)
{
    return buf[0] == 0 && !memcmp(buf, buf + 1, size - 1);
}

Básicamente, esto compara el búfer consigo mismo, con una verificación inicial para ver si el primer elemento es cero. De esa manera, cualquier elemento distinto de cero causará memcmp() fallar No sé cómo se compararía esto con el uso de otra versión, pero sé que fallará rápidamente (incluso antes de que hagamos un bucle) si el primer elemento es distinto de cero. Si es más probable que tenga cruft al final, cambie buf[0] para buf[size] para obtener el mismo efecto.

Los puntos de referencia proporcionados anteriormente (https://stackoverflow.com/a/1494499/2154139) no son precisos. Implican que func3 es mucho más rápido que las otras opciones.

Sin embargo, si cambia el orden de las pruebas, de modo que func3 esté antes que func2, verá que func2 es mucho más rápido.

Tenga cuidado al ejecutar puntos de referencia de combinación dentro de una sola ejecución… los efectos secundarios son grandes, especialmente cuando se reutilizan las mismas variables. ¡Mejor ejecutar las pruebas aisladas!

Por ejemplo, cambiándolo a:

int main(){
  MEASURE( func3 );
  MEASURE( func3 );
  MEASURE( func3 );
  MEASURE( func3 );
  MEASURE( func3 );
}

me da:

func3: zero          14243
func3: zero           1142
func3: zero            885
func3: zero            848
func3: zero            870

Esto realmente me estaba molestando ya que no podía ver cómo func3 podría funcionar mucho más rápido que func2.

(perdon por la respuesta, y no como comentario, no tenia reputacion)

Cuatro funciones para probar el cero de un búfer con una evaluación comparativa simple:

#include <stdio.h> 
#include <string.h> 
#include <wchar.h> 
#include <inttypes.h> 

#define SIZE (8*1024) 
char zero[SIZE] __attribute__(( aligned(8) ));

#define RDTSC(var)  __asm__ __volatile__ ( "rdtsc" : "=A" (var)); 

#define MEASURE( func ) { \ 
  uint64_t start, stop; \ 
  RDTSC( start ); \ 
  int ret = func( zero, SIZE ); \ 
  RDTSC( stop ); \ 
  printf( #func ": %s   %12"PRIu64"\n", ret?"non zero": "zero", stop-start ); \ 
} 


int func1( char *buff, size_t size ){
  while(size--) if(*buff++) return 1;
  return 0;
}

int func2( char *buff, size_t size ){
  return *buff || memcmp(buff, buff+1, size-1);
}

int func3( char *buff, size_t size ){
  return *(uint64_t*)buff || memcmp(buff, buff+sizeof(uint64_t), size-sizeof(uint64_t));
}

int func4( char *buff, size_t size ){
  return *(wchar_t*)buff || wmemcmp((wchar_t*)buff, (wchar_t*)buff+1, size/sizeof(wchar_t)-1);
}

int main(){
  MEASURE( func1 );
  MEASURE( func2 );
  MEASURE( func3 );
  MEASURE( func4 );
}

Resultado en mi vieja PC:

func1: zero         108668
func2: zero          38680
func3: zero           8504
func4: zero          24768

Si su programa es solo x86 o solo x64, puede optimizar fácilmente usando el ensamblador en línea. La instrucción REPE SCASD escaneará un búfer hasta que se encuentre un dword que no sea EAX.

Dado que no existe una función de biblioteca estándar equivalente, es probable que ningún compilador/optimizador pueda usar estas instrucciones (como lo confirma el código de Sufian).

Desde el encabezado, algo como esto funcionaría si la longitud de su búfer está alineada en 4 bytes (sintaxis MASM):

_asm {
   CLD                ; search forward
   XOR EAX, EAX       ; search for non-zero
   LEA EDI, [buf]     ; search in buf
   MOV ECX, [buflen]  ; search buflen bytes
   SHR ECX, 2         ; using dwords so len/=4
   REPE SCASD         ; perform scan
   JCXZ bufferEmpty:  ; completes? then buffer is 0
}

Tomás

EDITAR: actualizado con las correcciones de Tony D

Para algo tan simple, necesitará ver qué código está generando el compilador.

$ gcc -S -O3 -o empty.s empty.c

Y el contenido del montaje:

        .text
        .align 4,0x90
.globl _is_empty
_is_empty:
        pushl       %ebp
        movl        %esp, %ebp
        movl        12(%ebp), %edx  ; edx = pointer to buffer
        movl        8(%ebp), %ecx   ; ecx = size
        testl       %edx, %edx
        jle L3
        xorl        %eax, %eax
        cmpb        $0, (%ecx)
        jne L5
        .align 4,0x90
L6:
        incl        %eax            ; real guts of the loop are in here
        cmpl        %eax, %edx
        je  L3
        cmpb        $0, (%ecx,%eax) ; compare byte-by-byte of buffer
        je  L6
L5:
        leave
        xorl        %eax, %eax
        ret
        .align 4,0x90
L3:
        leave
        movl        $1, %eax
        ret
        .subsections_via_symbols

Esto está muy optimizado. El bucle hace tres cosas:

• Aumentar el desplazamiento
• Compare el desplazamiento con el tamaño
• Compare los datos de bytes en la memoria en base + desplazamiento a 0

Podría optimizarse un poco más al comparar palabra por palabra, pero luego debería preocuparse por la alineación y demás.

Cuando todo lo demás falla, mida primero, no adivine.

Intente verificar el búfer usando una variable de tamaño int donde sea posible (debe estar alineado).

Fuera de mi cabeza (sigue el código sin compilar, sin probar; es casi seguro que hay al menos un error aquí. Esto solo da una idea general):

/* check the start of the buf byte by byte while it's unaligned */
while (size && !int_aligned( buf)) {
    if (*buf != 0) {
        return 0;
    }

    ++buf;
    --size;
}


/* check the bulk of the buf int by int while it's aligned */

size_t n_ints = size / sizeof( int);
size_t rem = size / sizeof( int);

int* pInts = (int*) buf;

while (n_ints) {
    if (*pInt != 0) {
        return 0;
    }

    ++pInt;
    --n_ints;
}


/* now wrap up the remaining unaligned part of the buf byte by byte */

buf = (char*) pInts;

while (rem) {
    if (*buf != 0) {
        return 0;
    }

    ++buf;
    --rem;
}

return 1;