Reemplazar un contador de bucle de 32 bits por uno de 64 bits introduce desviaciones locas de rendimiento con _mm_popcnt_u64 en las CPU Intel

Estaba buscando la forma más rápida de acceder a popcountgrandes conjuntos de datos. Encontré un efecto muy extraño : cambiar la variable del bucle de unsignedauint64_t hizo que el rendimiento cayera en un 50% en mi PC.

El punto de referencia

#include <iostream>
#include <chrono>
#include <x86intrin.h>

int main(int argc, char* argv[]) {

    using namespace std;
    if (argc != 2) {
       cerr << "usage: array_size in MB" << endl;
       return -1;
    }

    uint64_t size = atol(argv[1])<<20;
    uint64_t* buffer = new uint64_t[size/8];
    char* charbuffer = reinterpret_cast<char*>(buffer);
    for (unsigned i=0; i<size; ++i)
        charbuffer[i] = rand()%256;

    uint64_t count,duration;
    chrono::time_point<chrono::system_clock> startP,endP;
    {
        startP = chrono::system_clock::now();
        count = 0;
        for( unsigned k = 0; k < 10000; k++){
            // Tight unrolled loop with unsigned
            for (unsigned i=0; i<size/8; i+=4) {
                count += _mm_popcnt_u64(buffer[i]);
                count += _mm_popcnt_u64(buffer[i+1]);
                count += _mm_popcnt_u64(buffer[i+2]);
                count += _mm_popcnt_u64(buffer[i+3]);
            }
        }
        endP = chrono::system_clock::now();
        duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
        cout << "unsigned\t" << count << '\t' << (duration/1.0E9) << " sec \t"
             << (10000.0*size)/(duration) << " GB/s" << endl;
    }
    {
        startP = chrono::system_clock::now();
        count=0;
        for( unsigned k = 0; k < 10000; k++){
            // Tight unrolled loop with uint64_t
            for (uint64_t i=0;i<size/8;i+=4) {
                count += _mm_popcnt_u64(buffer[i]);
                count += _mm_popcnt_u64(buffer[i+1]);
                count += _mm_popcnt_u64(buffer[i+2]);
                count += _mm_popcnt_u64(buffer[i+3]);
            }
        }
        endP = chrono::system_clock::now();
        duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
        cout << "uint64_t\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
             << (10000.0*size)/(duration) << " GB/s" << endl;
    }

    free(charbuffer);
}

Como puede ver, creamos un búfer de datos aleatorios, con un tamaño de xmegabytes donde xse lee desde la línea de comando. Luego, iteramos sobre el búfer y usamos una versión desenrollada del popcountintrínseco x86 para realizar el popcount. Para obtener un resultado más preciso, hacemos el popcount 10.000 veces. Medimos los tiempos para el popcount. En mayúsculas, la variable del bucle interno es unsigned, en minúsculas, la variable del bucle interno esuint64_t . Pensé que esto no debería hacer ninguna diferencia, pero es todo lo contrario.

Los resultados (absolutamente locos)

Lo compilo así (versión g++: Ubuntu 4.8.2-19ubuntu1):

g++ -O3 -march=native -std=c++11 test.cpp -o test

Aquí están los resultados en mi CPU Haswell Core i7-4770K a 3,50 GHz, en ejecución test 1(es decir, 1 MB de datos aleatorios):

• sin firmar 41959360000 0,401554 seg 26,113 GB/s
• uint64_t 41959360000 0,759822 seg 13,8003 GB/s

Como puede ver, ¡el rendimiento de la uint64_tversión es solo la mitad del de la unsignedversión! El problema parece ser que se genera un ensamblaje diferente, pero ¿por qué? Primero, pensé en un error del compilador, así que lo intenté clang++(Ubuntu Clang versión 3.4-1ubuntu3):

clang++ -O3 -march=native -std=c++11 teest.cpp -o test

Resultado:test 1

• sin firmar 41959360000 0,398293 seg 26,3267 GB/s
• uint64_t 41959360000 0,680954 segundos 15,3986 GB/s

Entonces, es casi el mismo resultado y sigue siendo extraño. Pero ahora se vuelve súper extraño. Reemplazo el tamaño del búfer que se leyó desde la entrada con una constante 1, así que cambio:

uint64_t size = atol(argv[1]) << 20;

a

uint64_t size = 1 << 20;

Por lo tanto, el compilador ahora conoce el tamaño del búfer en el momento de la compilación. ¡Quizás pueda agregar algunas optimizaciones! Aquí están los números de g++:

• sin firmar 41959360000 0,509156 seg 20,5944 GB/s
• uint64_t 41959360000 0,508673 segundos 20,6139 GB/s

Ahora ambas versiones son igualmente rápidas. Sin embargo, ¡se unsigned volvieron aún más lentos ! Cayó de 26a 20 GB/s, reemplazando así un valor no constante por un valor constante que condujo a una desoptimización . En serio, ¡no tengo ni idea de lo que está pasando aquí! Pero ahora clang++con la nueva versión:

• sin firmar 41959360000 0,677009 seg 15,4884 GB/s
• uint64_t 41959360000 0,676909 segundos 15,4906 GB/s

¿Esperar lo? Ahora, ambas versiones cayeron a la lenta cifra de 15 GB/s. Por lo tanto, reemplazar un valor no constante por un valor constante incluso conduce a un código lento en ambos casos para Clang.

Le pregunté a un colega con un Ivy Bridge. que compilara mi punto de referencia. Obtuvo resultados similares, por lo que no parece ser Haswell. Debido a que dos compiladores producen resultados extraños aquí, tampoco parece ser un error del compilador. Aquí no tenemos una CPU AMD, por lo que solo pudimos probar con Intel.

¡Más locura, por favor!

Tome el primer ejemplo (el que tiene atol(argv[1])) y coloque a staticantes de la variable, es decir:

static uint64_t size=atol(argv[1])<<20;

Aquí están mis resultados en g++:

• sin firmar 41959360000 0,396728 seg 26,4306 GB/s
• uint64_t 41959360000 0,509484 segundos 20,5811 GB/s

Sí, otra alternativa más . Todavía tenemos los rápidos 26 GB/s con u32, ¡pero logramos pasar u64al menos de la versión de 13 GB/s a la de 20 GB/s! En la PC de mi colega, la u64versión se volvió incluso más rápida que la u32versión anterior, obteniendo el resultado más rápido de todos. Lamentablemente esto solo le funciona a él g++no clang++parece importarlestatic .

Mi pregunta

¿Puedes explicar estos resultados? Especialmente:

• ¿Cómo puede haber tanta diferencia entre u32yu64 ?
• ¿Cómo puede reemplazar un tamaño de búfer no constante por un tamaño de búfer constante desencadenar un código menos óptimo? ?
• ¿ Cómo puede la inserción de la staticpalabra clave acelerar el u64ciclo? ¡Incluso más rápido que el código original en la computadora de mi colega!

Sé que la optimización es un territorio complicado, sin embargo, nunca pensé que cambios tan pequeños pudieran llevar a una diferencia del 100%. en el tiempo de ejecución y que pequeños factores como un tamaño de búfer constante puedan volver a mezclar totalmente los resultados. Por supuesto, siempre quiero tener la versión que sea capaz de contar con 26 GB/s. La única forma confiable que se me ocurre es copiar y pegar el ensamblaje para este caso y usar el ensamblaje en línea. Esta es la única manera de deshacerme de los compiladores que parecen volverse locos con pequeños cambios. ¿Qué opinas? ¿Existe otra forma de obtener de manera confiable el código con mayor rendimiento?

El desmontaje

Aquí está el desmontaje de los distintos resultados:

Versión de 26 GB/s de g++/u32/tamaño de buf no constante :

0x400af8:
lea 0x1(%rdx),%eax
popcnt (%rbx,%rax,8),%r9
lea 0x2(%rdx),%edi
popcnt (%rbx,%rcx,8),%rax
lea 0x3(%rdx),%esi
add %r9,%rax
popcnt (%rbx,%rdi,8),%rcx
add $0x4,%edx
add %rcx,%rax
popcnt (%rbx,%rsi,8),%rcx
add %rcx,%rax
mov %edx,%ecx
add %rax,%r14
cmp %rbp,%rcx
jb 0x400af8

Versión de 13 GB/s de g++/u64/tamaño de buf no constante :

0x400c00:
popcnt 0x8(%rbx,%rdx,8),%rcx
popcnt (%rbx,%rdx,8),%rax
add %rcx,%rax
popcnt 0x10(%rbx,%rdx,8),%rcx
add %rcx,%rax
popcnt 0x18(%rbx,%rdx,8),%rcx
add $0x4,%rdx
add %rcx,%rax
add %rax,%r12
cmp %rbp,%rdx
jb 0x400c00

Versión de 15 GB/s de clang++ / u64 / tamaño de buf no constante :

0x400e50:
popcnt (%r15,%rcx,8),%rdx
add %rbx,%rdx
popcnt 0x8(%r15,%rcx,8),%rsi
add %rdx,%rsi
popcnt 0x10(%r15,%rcx,8),%rdx
add %rsi,%rdx
popcnt 0x18(%r15,%rcx,8),%rbx
add %rdx,%rbx
add $0x4,%rcx
cmp %rbp,%rcx
jb 0x400e50

Versión de 20 GB/s de g++ / u32 y u64 / const bufsize :

0x400a68:
popcnt (%rbx,%rdx,1),%rax
popcnt 0x8(%rbx,%rdx,1),%rcx
add %rax,%rcx
popcnt 0x10(%rbx,%rdx,1),%rax
add %rax,%rcx
popcnt 0x18(%rbx,%rdx,1),%rsi
add $0x20,%rdx
add %rsi,%rcx
add %rcx,%rbp
cmp $0x100000,%rdx
jne 0x400a68

Versión de 15 GB/s de clang++ / u32 y u64 / const bufsize :

0x400dd0:
popcnt (%r14,%rcx,8),%rdx
add %rbx,%rdx
popcnt 0x8(%r14,%rcx,8),%rsi
add %rdx,%rsi
popcnt 0x10(%r14,%rcx,8),%rdx
add %rsi,%rdx
popcnt 0x18(%r14,%rcx,8),%rbx
add %rdx,%rbx
add $0x4,%rcx
cmp $0x20000,%rcx
jb 0x400dd0

Curiosamente, ¡la versión más rápida (26 GB/s) es también la más larga! Parece ser la única solución que utiliza lea. Algunas versiones usan jbpara saltar, otras usan jne. Pero aparte de eso, todas las versiones parecen comparables. No veo de dónde podría originarse una brecha de rendimiento del 100%, pero no soy muy experto en descifrar el ensamblaje. La versión más lenta (13 GB/s) parece incluso muy corta y buena. ¿Alguien puede explicar esto?

Lecciones aprendidas

No importa cuál sea la respuesta a esta pregunta; He aprendido que en bucles realmente activos cada detalle puede importar, incluso los detalles que no parecen tener ninguna asociación con el código activo . Nunca pensé en qué tipo usar para una variable de bucle, pero como puede ver, ¡un cambio tan pequeño puede marcar una diferencia del 100% ! Incluso el tipo de almacenamiento de un búfer puede marcar una gran diferencia, como vimos con la inserción de la staticpalabra clave delante de la variable de tamaño. En el futuro, siempre probaré varias alternativas en varios compiladores cuando escribo bucles realmente ajustados y activos que son cruciales para el rendimiento del sistema.

Lo interesante también es que la diferencia de rendimiento sigue siendo muy grande, aunque ya he desenrollado el bucle cuatro veces. Entonces, incluso si lo desenrollas, aún puedes sufrir desviaciones importantes en el rendimiento. Bastante interesante.

Aug 01 '14 17:08 gexicide

Codifiqué un programa C equivalente para experimentar y puedo confirmar este extraño comportamiento. Es más, gcccree que el entero de 64 bits (que probablemente debería ser de size_ttodos modos...) es mejor, ya que su uso uint_fast32_thace que gcc utilice un uint de 64 bits.

Jugué un poco con el ensamblaje:
simplemente tome la versión de 32 bits, reemplace todas las instrucciones/registros de 32 bits con la versión de 64 bits en el bucle popcount interno del programa. Observación: ¡el código es tan rápido como la versión de 32 bits!

Obviamente, esto es un truco, ya que el tamaño de la variable no es realmente de 64 bits, ya que otras partes del programa todavía usan la versión de 32 bits, pero mientras el bucle popcount interno domine el rendimiento, este es un buen comienzo. .

Luego copié el código del bucle interno de la versión de 32 bits del programa, lo modifiqué para que fuera de 64 bits y modifiqué los registros para reemplazar el bucle interno de la versión de 64 bits. Este código también se ejecuta tan rápido como la versión de 32 bits.

Mi conclusión es que se trata de una mala programación de instrucciones por parte del compilador, no de una ventaja real de velocidad/latencia de las instrucciones de 32 bits.

(Advertencia: corté el ensamblaje, podría haber roto algo sin darme cuenta. No lo creo).

Aug 01 '2014 22:08 EOF

Esta no es una respuesta, pero es difícil de leer si pongo los resultados en un comentario.

Obtengo estos resultados con una Mac Pro ( Westmere 6-Cores Xeon 3,33 GHz). Lo compilé con clang -O3 -msse4 -lstdc++ a.cpp -o a(-O2 obtiene el mismo resultado).

resonar conuint64_t size=atol(argv[1])<<20;

unsigned    41950110000 0.811198 sec    12.9263 GB/s
uint64_t    41950110000 0.622884 sec    16.8342 GB/s

resonar conuint64_t size=1<<20;

unsigned    41950110000 0.623406 sec    16.8201 GB/s
uint64_t    41950110000 0.623685 sec    16.8126 GB/s

También intenté:

1. Invierta el orden de la prueba, el resultado es el mismo por lo que descarta el factor de caché.
2. Tenga la fordeclaración al revés: for (uint64_t i=size/8;i>0;i-=4). Esto da el mismo resultado y demuestra que la compilación es lo suficientemente inteligente como para no dividir el tamaño entre 8 en cada iteración (como se esperaba).

Aquí está mi suposición descabellada:

El factor de velocidad se divide en tres partes:

• caché de código: uint64_tla versión tiene un tamaño de código mayor, pero esto no tiene efecto en mi CPU Xeon. Esto hace que la versión de 64 bits sea más lenta.

• Instrucciones utilizadas. Tenga en cuenta no solo el recuento de bucles, sino que también se accede al búfer con un índice de 32 y 64 bits en las dos versiones. Acceder a un puntero con un desplazamiento de 64 bits solicita un registro y direccionamiento dedicados de 64 bits, mientras que puede usar inmediato para un desplazamiento de 32 bits. Esto puede hacer que la versión de 32 bits sea más rápida.

• Las instrucciones sólo se emiten en la compilación de 64 bits (es decir, captación previa). Esto hace que los 64 bits sean más rápidos.

Los tres factores juntos coinciden con los resultados aparentemente contradictorios observados.

Aug 01 '2014 11:08 Non-maskable Interrupt

Probé esto con Visual Studio 2013 Express , usando un puntero en lugar de un índice, lo que aceleró un poco el proceso. Sospecho que esto se debe a que el direccionamiento es desplazamiento + registro, en lugar de desplazamiento + registro + (registro <<3). Código C++.

   uint64_t* bfrend = buffer+(size/8);
   uint64_t* bfrptr;

// ...

   {
      startP = chrono::system_clock::now();
      count = 0;
      for (unsigned k = 0; k < 10000; k++){
         // Tight unrolled loop with uint64_t
         for (bfrptr = buffer; bfrptr < bfrend;){
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
         }
      }
      endP = chrono::system_clock::now();
      duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "uint64_t\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
           << (10000.0*size)/(duration) << " GB/s" << endl;
   }

código ensamblador: r10 = bfrptr, r15 = bfrend, rsi = recuento, rdi = búfer, r13 = k:

$LL5@main:
        mov     r10, rdi
        cmp     rdi, r15
        jae     SHORT $LN4@main
        npad    4
$LL2@main:
        mov     rax, QWORD PTR [r10+24]
        mov     rcx, QWORD PTR [r10+16]
        mov     r8, QWORD PTR [r10+8]
        mov     r9, QWORD PTR [r10]
        popcnt  rdx, rax
        popcnt  rax, rcx
        add     rdx, rax
        popcnt  rax, r8
        add     r10, 32
        add     rdx, rax
        popcnt  rax, r9
        add     rsi, rax
        add     rsi, rdx
        cmp     r10, r15
        jb      SHORT $LL2@main
$LN4@main:
        dec     r13
        jne     SHORT $LL5@main

Aug 02 '2014 03:08 rcgldr