Rendimiento de bucle de 64 bits en x86

performance algorithm

Question

Necesitaba una función de suma de comprobación de Internet (suma de comprobación del complemento de uno) para un código de procesamiento ICMP IPv4 utilizando sockets sin procesar y me he topado con un comportamiento que no puedo explicar en un procesador Intel de 64 bits (con gcc 4.8.2). Me preguntaba si alguien podría arrojar algo de luz sobre eso.

Implementé una primera función de suma de comprobación utilizando un acumulador de 32 bits y realizando sumas de 16 bits. Luego implementé lo mismo usando un acumulador de 64 bits y sumas de 32 bits, pensando que menos sumas resultarían en una ejecución más rápida. El resultado es que la primera implementación se ejecuta dos veces más rápido que la segunda (con optimización de O3). Simplemente no puedo entender por qué ...

El código siguiente no realiza realmente sumas de comprobación precisas (lo he simplificado), pero ilustra el problema. Ambos compilados como de 64 bits se ejecutan en plataformas nativas de 64 bits (LP64: 16 bits cortos, int 32 bits, largos 64 bits, punteros de 64 bits).

1. Acumulador de 32 bits y sumas de 16 bits.

   unsigned short
   cksum_16_le(unsigned char* data, size_t size)
   {
       unsigned short word;
       unsigned int sum = 0;
       unsigned int i;
   
       for(i = 0; i < size - 1; i += 2)
           sum += *((unsigned short*) (data + i));
   
       sum = (sum & 0xffff) + (sum >> 16);
       sum = (sum & 0xffff) + (sum >> 16);
   
       return ~sum;
   }

50,000 llamadas a funciones sobre los mismos datos de 10k: ~ 1.1 segundos.

1. Acumulador de 64 bits y sumas de 32 bits.

   unsigned short
   cksum_32_le(unsigned char* data, size_t size)
   {
       unsigned long word;
       unsigned long sum = 0;
       unsigned int i;
   
       for(i = 0; i < size - 3; i += 4)
           sum += *((unsigned int*) (data + i));
   
       sum = (sum & 0xffffffff) + (sum >> 32);
       sum = (sum & 0xffffffff) + (sum >> 32);
       sum = (sum & 0xffff) + (sum >> 16);
       sum = (sum & 0xffff) + (sum >> 16);
   
       return ~sum;
   }

50,000 llamadas a funciones sobre los mismos datos de 10k: ~ 2.2 segundos.

Actualizar:

Parece que el problema se debe al hardware. La ejecución de los diagnósticos de memoria reveló errores ocasionales de paridad de bus (no estoy seguro de por qué esto afectaría a la versión de 32 bits más que a la versión de 16 bits, pero ya está). El código se ejecuta como se espera en otros servidores. Se eliminará la pregunta en las próximas horas (debido a que está relacionado con el hardware, ya no es particularmente útil).

Actualización final:

Curiosamente, la sustitución de los bucles for bucles while y la compilación con la optimización de O3 (que se muestra a continuación para la caja del acumulador de 64 bits) hace que las cajas del acumulador de 32 bits y de 64 bits funcionen a velocidades idénticas. Esto se debe a que el compilador realiza algunos desenrollamientos de bucles (de forma extraña, no desenrolla el bucle for ) y realiza la suma utilizando registros mmx ...

uint64_t sum = 0;
const uint32_t* dptr = (const uint32_t*) data;

while (size > 3)
{
    sum += (uint32_t) *dptr++;
    size -= 4;
}

Answer 1

¿Estás haciendo difícil el trabajo del compilador? En el bucle interno, está calculando el desplazamiento de bytes por su elección de paso de índice y la conversión. Esto podría estar impidiendo el desenrollamiento del bucle o cualquier otra optimización que intente asumir la alineación. También podría no permitir que el compilador utilice los modos de direccionamiento y salga a calcular la dirección efectiva (o LEA).

Si estuviera haciendo esto, pondría el puntero de datos en la parte superior del bucle a tu tipo de zancada e incrementaría tu contador de bucle en 1. El compilador podría ser un poco más feliz.

Answer 2

Creo que no se puede desenrollar el bucle "for" debido a la conversión de char * a unsigned int *. Las conversiones de tipo a menudo impiden que el compilador optimice el código, porque en este caso no se puede realizar un análisis de alias perfecto. Si primero declara un puntero local adicional para emitir su puntero de "datos" antes del bucle, de modo que no haya ningún lanzamiento en el bucle, el compilador debería poder optimizar el bucle "para".

Answer 3

Respuesta probable: la condición "i <tamaño - 1" se puede compilar y ejecutar más eficientemente que "i <tamaño - 3". Primero, solo se requiere una instrucción de disminución en lugar de la otra, lo que requiere que una constante 3 también se cargue en algún lugar. Este cálculo se ejecuta con cada iteración. Debe almacenar el resultado de este cálculo en otro lugar.

Esto no tiene nada que ver con el bucle while. Cuando reescribió el ciclo while, también cambió la condición de iteración y eliminó la causa anterior.

También preferiría hacer el casting de tipo fuera del bucle, pero eso también revela una restricción: sus datos deben

Answer 4

Tuve un problema similar como este antes; No pude encontrar ningún problema en ninguno de nuestros códigos. PERO lo que funcionó para mí fue cambiar el compilador.

Mi conjetura es que GCC está escribiendo Asamblea en desuso.

Si puede descompilar su aplicación, podríamos arrojar más luz sobre el problema, pero simplemente no hay suficiente información para continuar aquí.

Cuando descompuse mi código, lo que encontré es que estaba reescribiendo un método completo varias veces. pero eso podría ser para mí.

Espero que esto te haya ayudado, hay poca o ninguna información sobre esto en cualquier lugar.

Si tuviera que adivinar que estaría de acuerdo con Learner, estoy bastante seguro de que el código descompilado apuntaría al bucle for. Estoy muy interesado con este tema así que por favor comenta de nuevo.

Answer 5

sum += *((unsigned int*) (data + i)); 

No me gusta un reparto así

Acumulador de 64 bits y sumas de 32 bits.

desde que escribiste:

Ambos compilados como de 64 bits se ejecutan en plataformas nativas de 64 bits (LP64: corto de 16 bits, int de 32 bits, largo> 64 bits, punteros de 64 bits).

Yo sugeriría usar (sin firmar largo *). Algunas personas aconsejan verificar en código desensamblado lo que sucede en la realidad. Creo que es debido a su int * cast con acumulador largo.

¿Qué pasa sin O2 <> O3 flag? ¿Podría mostrar cuál es la velocidad en el modo de compilación normal?