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

12 minutos de lectura

avatar de usuario
Robar

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.

  • Respuesta de broma: int is_empty(char *buf, int size) { memset(buf, 0, size); return 1; }

    – Chris Lutz

    29 de septiembre de 2009 a las 17:31

  • Como nota al margen, realmente deberías usar size_t en lugar de int para valores que representan el tamaño de las matrices.

    – Chris Lutz

    29 de septiembre de 2009 a las 17:32

  • ¡Suena como un trabajo para el Dispositivo de Duff!

    – Michael Burr

    29 de septiembre de 2009 a las 17:35

  • @Rob: lo más probable es que esté atado al disco y no debería concentrarse en esto. Una lectura o escritura de 10 ms en el disco son millones y millones de ciclos de reloj en una CPU moderna. Optimizar la forma en que lee del disco obtendrá resultados mucho mejores.

    – Miguel

    29 de septiembre de 2009 a las 18:20

  • @Robar: kernelnewbies.org/Linux_2_6_28 mira 1.13 FIEMAP

    – sambowry

    29 de septiembre de 2009 a las 19:47

avatar de usuario
derobert

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.

  • +1 para información de sucursales, ya que el cartel busca microoptimización.

    – Ben M.

    29 de septiembre de 2009 a las 17:49

  • Tenga en cuenta que comparar grupos de 1 byte como un solo valor integral plantea problemas de alineación, lo que dificulta hacerlo de manera segura.

    – Chris Lutz

    29 de septiembre de 2009 a las 18:03

  • No hay forma de que realmente puedas optimizar este bucle en lo que respecta a la predicción de bifurcaciones. Un procesador moderno preferirá dar un salto hacia atrás en lugar de fallar si no tiene información de predicción y luego continuará prediciendo correctamente la bifurcación hasta que finalice el bucle. El resultado final es una predicción errónea por búfer, no puedo imaginar una manera de reducir esto a 0.

    – Falaína

    29 de septiembre de 2009 a las 18:50

  • No está hablando de la predicción del ciclo, está hablando de la predicción de probar que el contenido del búfer es cero (y mejorarlo haciendo menos comparaciones)

    – Esteban Canon

    29 de septiembre de 2009 a las 20:38

  • La alineación no complica demasiado las cosas. Procese los bytes de uno en uno hasta que tenga la alineación necesaria, luego caiga en un ciclo principal que usa comparaciones más grandes y tenga algunas comparaciones de un solo byte para limpiar los elementos sobrantes cuando haya terminado. La alineación es solo un dolor sustancial cuando se trata de múltiples búferes que pueden tener diferentes alineaciones relativas.

    – Esteban Canon

    29 de septiembre de 2009 a las 20:40

avatar de usuario
chris lutz

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.

  • Por otro lado, la versión memcmp estará limitada por el ancho de banda de la memoria, al igual que la versión C más inteligente si el compilador no es demasiado estúpido, pero la versión C tendrá medio la memoria para leer. Sin intentarlo, predigo que la versión C será al menos un 50% más rápida que la de memcmp.

    – Pascal Cuoq

    29 de septiembre de 2009 a las 17:50

  • a) ¿Qué versiones “C” está comparando? b) ¿Por qué memcmp() ¿toma mas tiempo?

    – Chris Lutz

    29 de septiembre de 2009 a las 17:53

  • En lugar de asignar memoria, podría usar: buf[0]==0 && !memcmp(buf, buf+1, tamaño-1).

    – Accipitridae

    29 de septiembre de 2009 a las 18:36

  • @Pascal – Sincronizándolo, el primero memcmp() La versión tiene casi la misma velocidad que la versión OP, cronometrándola constantemente levemente (como, 0.001s) más rápido.

    – Chris Lutz

    29 de septiembre de 2009 a las 18:42

  • Es posible que desee hacer eso static formación const, también. Esa versión es trivialmente compatible con la línea, lo que podría ser otra (pequeña) victoria.

    – café

    29 de septiembre de 2009 a las 22:30

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)

avatar de usuario
sambowry

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

avatar de usuario
Tomás

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

  • Mejor respuesta – votado a favor. ¿Podría mostrarme cómo poner esto en un programa GCC/Clang C como ASM integrado? (¿Esto requiere sintaxis de GAS?) ¿Existe una versión de 64 bits que use largos largos sin firmar?

    – abeja desvanecida

    22 de febrero de 2013 a las 10:37

  • +1 enfoque sólido – selecciones de liendres: debería ser LEA EDI, ... no ESI, y falta CLD para garantizar que la bandera de dirección esté clara.

    – Tony Delroy

    26 de abril de 2013 a las 10:22

  • ¡Cuidado, el ensamblador en línea no es analizable estáticamente por los compiladores y causa una valla de memoria de ordenamiento completa antes y después del bloque! esto puede ser horrible en algunos casos.

    – v.oddou

    10 de diciembre de 2015 a las 9:35

  • Desafortunadamente, repe scasd no es más rápido que un bucle normal. Instrucciones de almacenamiento y copia de cadenas (rep stos y rep movs) han optimizado implementaciones de microcódigo en CPU Intel, pero repe scas y repe cmps no También @TonyD: todas las ABI normales requieren que se borre el indicador de dirección al ingresar la función. cld es un desperdicio de una instrucción.

    – Peter Cordes

    28 de enero de 2016 a las 6:54


avatar de usuario
sufí

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.

  • Mejor respuesta – votado a favor. ¿Podría mostrarme cómo poner esto en un programa GCC/Clang C como ASM integrado? (¿Esto requiere sintaxis de GAS?) ¿Existe una versión de 64 bits que use largos largos sin firmar?

    – abeja desvanecida

    22 de febrero de 2013 a las 10:37

  • +1 enfoque sólido – selecciones de liendres: debería ser LEA EDI, ... no ESI, y falta CLD para garantizar que la bandera de dirección esté clara.

    – Tony Delroy

    26 de abril de 2013 a las 10:22

  • ¡Cuidado, el ensamblador en línea no es analizable estáticamente por los compiladores y causa una valla de memoria de ordenamiento completa antes y después del bloque! esto puede ser horrible en algunos casos.

    – v.oddou

    10 de diciembre de 2015 a las 9:35

  • Desafortunadamente, repe scasd no es más rápido que un bucle normal. Instrucciones de almacenamiento y copia de cadenas (rep stos y rep movs) han optimizado implementaciones de microcódigo en CPU Intel, pero repe scas y repe cmps no También @TonyD: todas las ABI normales requieren que se borre el indicador de dirección al ingresar la función. cld es un desperdicio de una instrucción.

    – Peter Cordes

    28 de enero de 2016 a las 6:54


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;

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad