Pregunta Reemplazar una variable de recuento de bucles de 32 bits con 64 bits introduce desviaciones de rendimiento locas


Estaba buscando la forma más rápida de popcount grandes conjuntos de datos. Encontré un muy raro efecto: cambiar la variable de bucle de unsigned a uint64_t hizo que el rendimiento cayera 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 ve, creamos un buffer de datos aleatorios, con el tamaño x megabytes donde x se lee desde la línea de comando. Después, iteramos sobre el buffer y usamos una versión desenrollada del x86 popcount intrínseco para realizar el popcount. Para obtener un resultado más preciso, hacemos la cuenta 10 000 veces. Medimos los tiempos para el popcount. En mayúsculas, la variable de ciclo interno es unsigned, en la minúscula, la variable de ciclo interno es uint64_t. Pensé que esto no debería hacer ninguna diferencia, pero lo contrario es el caso.

Los resultados (absolutamente locos)

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

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

Aquí están los resultados en mi Haswell  Core i7-4770K CPU a 3.50 GHz, ejecutándose test 1 (entonces 1 MB de datos aleatorios):

  • sin signo 41959360000 0.401554 sec 26.113 GB / s
  • uint64_t 41959360000 0.759822 sec 13.8003 GB / s

Como puede ver, el rendimiento del uint64_t la versión es sólo la mitad el de la unsigned ¡versión! El problema parece ser que se genera un ensamblaje diferente, pero ¿por qué? Primero, pensé en un error de compilación, así que lo intenté clang++ (Ubuntu Sonido metálico versión 3.4-1ubuntu3):

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

Resultado: test 1

  • sin firmar 41959360000 0.398293 sec 26.3267 GB / s
  • uint64_t 41959360000 0.680954 seg 15,3986 GB / s

Por lo tanto, es casi el mismo resultado y todavía es extraño. Pero ahora se vuelve súper extraño. Sustituyo el tamaño del búfer que se leyó de la entrada con una constante 1, entonces 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 tiempo de compilación. ¡Tal vez pueda agregar algunas optimizaciones! Aquí están los números para g++:

  • sin signo 41959360000 0.509156 sec 20.5944 GB / s
  • uint64_t 41959360000 0.508673 seg 20.6139 GB / s

Ahora, ambas versiones son igualmente rápidas. sin embargo, el unsigned  incluso más lento! Se cayó desde 26 a 20 GB/s, reemplazando una no constante por un valor constante conducen a un desoptimización. En serio, no tengo idea de lo que está pasando aquí! Pero ahora a clang++ con la nueva versión:

  • sin signo 41959360000 0.677009 sec 15,4884 GB / s
  • uint64_t 41959360000 0.676909 seg 15.4906 GB / s

¿Esperar lo? Ahora, ambas versiones cayeron al lento número de 15 GB / s. Por lo tanto, reemplazar una no constante por un valor constante incluso lleva a un código lento en ambos casos para Clang!

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

Más locura, por favor!

Tome el primer ejemplo (el que tiene atol(argv[1])) y poner un static antes de la variable, es decir:

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

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

  • sin signo 41959360000 0.396728 sec 26.4306 GB / s
  • uint64_t 41959360000 0.509484 seg 20.5811 GB / s

Yay, otra alternativa más. Todavía tenemos los rápidos 26 GB / s con u32, pero logramos obtener u64 ¡al menos desde la versión de 13 GB / s a ​​20 GB / s! En la PC de mi colega, u64 versión se hizo aún más rápido que el u32 versión, produciendo el resultado más rápido de todos. Lamentablemente, esto solo funciona para g++, clang++ no parece importarle static.

Mi pregunta

¿Puedes explicar estos resultados? Especialmente:

  • ¿Cómo puede haber tal diferencia entre u32 y u64?
  • ¿Cómo se puede reemplazar un no constante por un disparador de tamaño de búfer constante código menos óptimo?
  • ¿Cómo puede la inserción de la static palabra clave hacer la u64 ciclo más rápido? ¡Incluso más rápido que el código original en la computadora de mi colega!

Sé que la optimización es un territorio difícil, sin embargo, nunca pensé que esos pequeños cambios pudieran llevar a una Diferencia del 100% en tiempo de ejecución y que factores pequeños como un tamaño de búfer constante pueden volver a mezclar los resultados totalmente. Por supuesto, siempre quiero tener la versión que es capaz de popcount 26 GB / s. La única manera confiable en que puedo pensar es copiar y pegar el ensamblaje para este caso y usar el ensamblaje en línea. Esta es la única forma en que puedo deshacerme de los compiladores que parecen enloquecer por pequeños cambios. ¿Qué piensas? ¿Hay alguna otra forma de obtener de manera confiable el código con más rendimiento?

El Desmontaje

Aquí está el desmontaje para los diversos resultados:

26 GB / s versión de g ++ / u32 / non-const bufsize:

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

13 GB / s versión de g ++ / u64 / no-const bufsize:

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

15 GB / s versión de clang ++ / u64 / no-const bufsize:

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

20 GB / s versión de g ++ / u32 & 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

15 GB / s versión de clang ++ / u32 & 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) también es la más larga. Parece ser la única solución que usa lea. Algunas versiones usan jb para saltar, otros usan jne. Pero aparte de eso, todas las versiones parecen ser comparables. No veo de dónde podría originarse una brecha de rendimiento del 100%, pero no soy demasiado hábil para 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 eso en loops realmente calientes cada los detalles pueden importar, incluso detalles que no parecen tener ninguna asociación con el código de acceso directo. Nunca he pensado en qué tipo usar para una variable de bucle, pero como puede ver, un cambio menor puede hacer que 100% ¡diferencia! Incluso el tipo de almacenamiento de un buffer puede hacer una gran diferencia, como vimos con la inserción del staticpalabra clave en frente de la variable de tamaño! En el futuro, siempre probaré varias alternativas en varios compiladores cuando escribo bucles realmente cerrados y calientes que son cruciales para el rendimiento del sistema.

Lo interesante es también que la diferencia en el rendimiento sigue siendo tan alta, aunque ya he desenrollado el circuito cuatro veces. Entonces, incluso si se desenrolla, aún puede ser golpeado por las principales desviaciones de rendimiento. Bastante interesante.


1146
2017-08-01 10:33


origen


Respuestas:


Culpable: Dependencia de datos falsos (y el compilador ni siquiera es consciente de ello)

En los procesadores Sandy / Ivy Bridge y Haswell, la instrucción:

popcnt  src, dest

parece tener una dependencia falsa en el registro de destino dest. Aunque la instrucción solo le escriba, la instrucción esperará hasta dest está listo antes de ejecutar.

Esta dependencia no solo detiene a los 4 popcnts de una iteración de bucle único. Puede trasladarse a través de iteraciones de bucle, haciendo imposible que el procesador paralelice diferentes iteraciones de bucle.

los unsigned vs. uint64_t y otros ajustes no afectan directamente el problema. Pero influyen en el asignador de registro que asigna los registros a las variables.

En su caso, las velocidades son un resultado directo de lo que está pegado a la cadena de dependencia (falsa) dependiendo de lo que el asignador de registro decidió hacer.

  • 13 GB / s tiene una cadena: popcnt-add-popcnt-popcnt → próxima iteración
  • 15 GB / s tiene una cadena: popcnt-add-popcnt-add → próxima iteración
  • 20 GB / s tiene una cadena: popcnt-popcnt → próxima iteración
  • 26 GB / s tiene una cadena: popcnt-popcnt → próxima iteración

La diferencia entre 20 GB / sy 26 GB / s parece ser un artefacto menor del direccionamiento indirecto. De cualquier manera, el procesador comienza a golpear otros cuellos de botella una vez que alcances esta velocidad.


Para probar esto, utilicé el ensamblaje en línea para eludir el compilador y obtener exactamente el ensamblaje que deseo. También dividí el count variable para romper todas las otras dependencias que puedan interferir con los puntos de referencia.

Aquí están los resultados:

Sandy Bridge Xeon @ 3.5 GHz: (El código de prueba completo se puede encontrar en la parte inferior)

  • GCC 4.6.3: g++ popcnt.cpp -std=c++0x -O3 -save-temps -march=native
  • Ubuntu 12

Diferentes registros: 18.6195 GB / s

.L4:
    movq    (%rbx,%rax,8), %r8
    movq    8(%rbx,%rax,8), %r9
    movq    16(%rbx,%rax,8), %r10
    movq    24(%rbx,%rax,8), %r11
    addq    $4, %rax

    popcnt %r8, %r8
    add    %r8, %rdx
    popcnt %r9, %r9
    add    %r9, %rcx
    popcnt %r10, %r10
    add    %r10, %rdi
    popcnt %r11, %r11
    add    %r11, %rsi

    cmpq    $131072, %rax
    jne .L4

Mismo registro: 8.49272 GB / s

.L9:
    movq    (%rbx,%rdx,8), %r9
    movq    8(%rbx,%rdx,8), %r10
    movq    16(%rbx,%rdx,8), %r11
    movq    24(%rbx,%rdx,8), %rbp
    addq    $4, %rdx

    # This time reuse "rax" for all the popcnts.
    popcnt %r9, %rax
    add    %rax, %rcx
    popcnt %r10, %rax
    add    %rax, %rsi
    popcnt %r11, %rax
    add    %rax, %r8
    popcnt %rbp, %rax
    add    %rax, %rdi

    cmpq    $131072, %rdx
    jne .L9

Mismo registro con la cadena rota: 17.8869 GB / s

.L14:
    movq    (%rbx,%rdx,8), %r9
    movq    8(%rbx,%rdx,8), %r10
    movq    16(%rbx,%rdx,8), %r11
    movq    24(%rbx,%rdx,8), %rbp
    addq    $4, %rdx

    # Reuse "rax" for all the popcnts.
    xor    %rax, %rax    # Break the cross-iteration dependency by zeroing "rax".
    popcnt %r9, %rax
    add    %rax, %rcx
    popcnt %r10, %rax
    add    %rax, %rsi
    popcnt %r11, %rax
    add    %rax, %r8
    popcnt %rbp, %rax
    add    %rax, %rdi

    cmpq    $131072, %rdx
    jne .L14

Entonces, ¿qué salió mal con el compilador?

Parece que ni GCC ni Visual Studio saben que popcnt tiene una dependencia tan falsa Sin embargo, estas dependencias falsas no son infrecuentes. Solo se trata de si el compilador es consciente de ello.

popcnt no es exactamente la instrucción más utilizada. Entonces, no es realmente una sorpresa que un compilador importante se pierda algo como esto. También parece que no hay documentación en ninguna parte que mencione este problema. Si Intel no lo revela, nadie de afuera lo sabrá hasta que alguien lo encuentre por casualidad.

(Actualizar:  A partir de la versión 4.9.2, GCC es consciente de esta falsa dependencia y genera código para compensarlo cuando las optimizaciones están habilitadas. Los principales compiladores de otros proveedores, incluidos Clang, MSVC e incluso el propio ICC de Intel, aún no conocen esta errata de microarquitectura y no emitirán código que la compense.

¿Por qué la CPU tiene una dependencia tan falsa?

Solo podemos especular, pero es probable que Intel tenga el mismo manejo para muchas instrucciones de dos operandos. Instrucciones comunes como add, sub tomar dos operandos, ambos de los cuales son entradas. Entonces Intel probablemente empujó popcnt en la misma categoría para mantener el diseño del procesador simple.

Los procesadores AMD no parecen tener esta falsa dependencia.


El código de prueba completo está a continuación para referencia:

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

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

   using namespace std;
   uint64_t size=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;
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "popcnt %4, %4  \n\t"
                "add %4, %0     \n\t"
                "popcnt %5, %5  \n\t"
                "add %5, %1     \n\t"
                "popcnt %6, %6  \n\t"
                "add %6, %2     \n\t"
                "popcnt %7, %7  \n\t"
                "add %7, %3     \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "No Chain\t" << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "popcnt %4, %%rax   \n\t"
                "add %%rax, %0      \n\t"
                "popcnt %5, %%rax   \n\t"
                "add %%rax, %1      \n\t"
                "popcnt %6, %%rax   \n\t"
                "add %%rax, %2      \n\t"
                "popcnt %7, %%rax   \n\t"
                "add %%rax, %3      \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                : "rax"
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "Chain 4   \t"  << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "xor %%rax, %%rax   \n\t"   // <--- Break the chain.
                "popcnt %4, %%rax   \n\t"
                "add %%rax, %0      \n\t"
                "popcnt %5, %%rax   \n\t"
                "add %%rax, %1      \n\t"
                "popcnt %6, %%rax   \n\t"
                "add %%rax, %2      \n\t"
                "popcnt %7, %%rax   \n\t"
                "add %%rax, %3      \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                : "rax"
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "Broken Chain\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }

   free(charbuffer);
}

Un punto de referencia igualmente interesante se puede encontrar aquí: http://pastebin.com/kbzgL8si
Este punto de referencia varía la cantidad de popcnts que están en la cadena de dependencia (falsa).

False Chain 0:  41959360000 0.57748 sec     18.1578 GB/s
False Chain 1:  41959360000 0.585398 sec    17.9122 GB/s
False Chain 2:  41959360000 0.645483 sec    16.2448 GB/s
False Chain 3:  41959360000 0.929718 sec    11.2784 GB/s
False Chain 4:  41959360000 1.23572 sec     8.48557 GB/s

1307
2017-08-01 22:41



Codifiqué un programa C equivalente para experimentar, y puedo confirmar este extraño comportamiento. Además, gcc cree que el entero de 64 bits (que probablemente debería ser un size_t de todos modos ...) para ser mejor, como usar uint_fast32_t hace que gcc use un uint de 64 bits.

Hice un poco de burla con la asamblea:
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 de cuenta interno del programa. Observación: el código es ¡tan rápido como la versión de 32 bits!

Esto es obviamente un hack, ya que el tamaño de la variable no es realmente de 64 bits, ya que otras partes del programa aún usan la versión de 32 bits, pero mientras el bucle de cuenta 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 pirateé para que fuera de 64 bits, jugueteé con los registros para reemplazarlo por 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 esta es una mala programación de instrucciones por el compilador, no la velocidad real / latencia de las instrucciones de 32 bits.

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


47
2017-08-01 22:55



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

Obtengo estos resultados con un 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 con uint64_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 con uint64_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 la orden de prueba, el resultado es el mismo, por lo que descarta el factor de caché.
  2. Tener el for declaració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 por 8 en cada iteración (como se esperaba).

Aquí está mi loca suposición:

El factor de velocidad viene en tres partes:

  • caché de código: uint64_t la versión tiene un tamaño de código más grande, pero esto no tiene ningún 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 se accede al búfer con un índice de 32 y 64 bits en las dos versiones. Al acceder a un puntero con un desplazamiento de 64 bits, se solicita un registro y un direccionamiento de 64 bits dedicados, mientras que puede usar el inmediato para un desplazamiento de 32 bits. Esto puede hacer que la versión de 32 bits sea más rápida.

  • Las instrucciones solo se emiten en la compilación de 64 bits (es decir, captación previa). Esto hace 64-bit más rápido.

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


24
2017-08-01 11:04



No puedo dar una respuesta autorizada, pero proporciono una descripción de una posible causa. Esta referencia muestra muy claramente que para las instrucciones en el cuerpo de su ciclo hay una relación de 3: 1 entre la latencia y el rendimiento. También muestra los efectos del despacho múltiple. Como hay tres unidades enteras (dar o recibir) en los procesadores modernos x86, generalmente es posible enviar tres instrucciones por ciclo.

Entonces, entre el pipeline máximo y el rendimiento de despacho múltiple y el fallo de estos mecanismos, tenemos un factor de seis en el rendimiento. Es bastante conocido que la complejidad del conjunto de instrucciones x86 hace que sea bastante fácil que se produzca una rotura peculiar. El documento anterior tiene un gran ejemplo:

El rendimiento del Pentium 4 para los cambios a la derecha de 64 bits es realmente pobre. El desplazamiento a la izquierda de 64 bits, así como todos los cambios de 32 bits tienen un rendimiento aceptable. Parece que la ruta de datos desde los 32 bits superiores a los 32 bits inferiores de la ALU no está bien diseñada.

Personalmente me encontré con un extraño caso en el que un bucle caliente funcionó considerablemente más lento en un núcleo específico de un chip de cuatro núcleos (AMD si mal no recuerdo). En realidad obtuvimos un mejor rendimiento en un cálculo de reducción de mapa desactivando ese núcleo.

Aquí mi conjetura es contención para unidades enteras: que el popcnt, el contador de bucles y los cálculos de direcciones apenas pueden ejecutarse a toda velocidad con el contador de 32 bits de ancho, pero el contador de 64 bits causa contención y bloqueos de tuberías. Como solo hay aproximadamente 12 ciclos en total, posiblemente 4 ciclos con despacho múltiple, por ejecución del cuerpo del bucle, un solo bloqueo podría afectar razonablemente el tiempo de ejecución por un factor de 2.

El cambio inducido por el uso de una variable estática, que supongo que solo causa un pequeño reordenamiento de las instrucciones, es otra pista de que el código de 32 bits está en un punto de inflexión para la contención.

Sé que este no es un análisis riguroso, pero es una explicación plausible.


10
2017-08-01 20:12



Has intentado pasar -funroll-loops -fprefetch-loop-arrays a GCC?

Obtengo los siguientes resultados con estas optimizaciones adicionales:

[1829] /tmp/so_25078285 $ cat /proc/cpuinfo |grep CPU|head -n1
model name      : Intel(R) Core(TM) i3-3225 CPU @ 3.30GHz
[1829] /tmp/so_25078285 $ g++ --version|head -n1
g++ (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3

[1829] /tmp/so_25078285 $ g++ -O3 -march=native -std=c++11 test.cpp -o test_o3
[1829] /tmp/so_25078285 $ g++ -O3 -march=native -funroll-loops -fprefetch-loop-arrays -std=c++11     test.cpp -o test_o3_unroll_loops__and__prefetch_loop_arrays

[1829] /tmp/so_25078285 $ ./test_o3 1
unsigned        41959360000     0.595 sec       17.6231 GB/s
uint64_t        41959360000     0.898626 sec    11.6687 GB/s

[1829] /tmp/so_25078285 $ ./test_o3_unroll_loops__and__prefetch_loop_arrays 1
unsigned        41959360000     0.618222 sec    16.9612 GB/s
uint64_t        41959360000     0.407304 sec    25.7443 GB/s

9
2017-08-04 15:37



Intenté esto con Visual Studio 2013 Express, usando un puntero en lugar de un índice, lo que aceleró el proceso un poco. Sospecho que esto es porque el direccionamiento es offset + register, en lugar de offset + register + (register << 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 de ensamblado: r10 = bfrptr, r15 = bfrend, rsi = conteo, rdi = buffer, 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

9
2017-08-02 03:48



¿Has intentado mover el paso de reducción fuera del circuito? En este momento tiene una dependencia de datos que realmente no es necesaria.

Tratar:

  uint64_t subset_counts[4] = {};
  for( unsigned k = 0; k < 10000; k++){
     // Tight unrolled loop with unsigned
     unsigned i=0;
     while (i < size/8) {
        subset_counts[0] += _mm_popcnt_u64(buffer[i]);
        subset_counts[1] += _mm_popcnt_u64(buffer[i+1]);
        subset_counts[2] += _mm_popcnt_u64(buffer[i+2]);
        subset_counts[3] += _mm_popcnt_u64(buffer[i+3]);
        i += 4;
     }
  }
  count = subset_counts[0] + subset_counts[1] + subset_counts[2] + subset_counts[3];

También tiene algún tipo de alias extraño que no estoy seguro que cumpla con las estrictas reglas de aliasing.


7
2017-08-01 18:33



TL; DR: uso __builtin intrínsecos en su lugar.

Pude hacer gcc 4.8.4 (e incluso 4.7.3 en gcc.godbolt.org) generan un código óptimo para esto al usar __builtin_popcountllque usa la misma instrucción de ensamblaje, pero no tiene ese error de falsa dependencia.

No estoy 100% seguro de mi código de evaluación comparativa, pero objdump la salida parece compartir mis puntos de vista. Uso algunos otros trucos (++i vs i++) para hacer que el compilador desenrolle el bucle sin ningún movl instrucción (comportamiento extraño, debo decir).

Resultados:

Count: 20318230000  Elapsed: 0.411156 seconds   Speed: 25.503118 GB/s

Código de Benchmarking:

#include <stdint.h>
#include <stddef.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>

uint64_t builtin_popcnt(const uint64_t* buf, size_t len){
  uint64_t cnt = 0;
  for(size_t i = 0; i < len; ++i){
    cnt += __builtin_popcountll(buf[i]);
  }
  return cnt;
}

int main(int argc, char** argv){
  if(argc != 2){
    printf("Usage: %s <buffer size in MB>\n", argv[0]);
    return -1;
  }
  uint64_t size = atol(argv[1]) << 20;
  uint64_t* buffer = (uint64_t*)malloc((size/8)*sizeof(*buffer));

  // Spoil copy-on-write memory allocation on *nix
  for (size_t i = 0; i < (size / 8); i++) {
    buffer[i] = random();
  }
  uint64_t count = 0;
  clock_t tic = clock();
  for(size_t i = 0; i < 10000; ++i){
    count += builtin_popcnt(buffer, size/8);
  }
  clock_t toc = clock();
  printf("Count: %lu\tElapsed: %f seconds\tSpeed: %f GB/s\n", count, (double)(toc - tic) / CLOCKS_PER_SEC, ((10000.0*size)/(((double)(toc - tic)*1e+9) / CLOCKS_PER_SEC)));
  return 0;
}

Opciones de compilación:

gcc --std=gnu99 -mpopcnt -O3 -funroll-loops -march=native bench.c -o bench

Versión de GCC:

gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4

Versión del kernel de Linux:

3.19.0-58-generic

Información de CPU:

processor   : 0
vendor_id   : GenuineIntel
cpu family  : 6
model       : 70
model name  : Intel(R) Core(TM) i7-4870HQ CPU @ 2.50 GHz
stepping    : 1
microcode   : 0xf
cpu MHz     : 2494.226
cache size  : 6144 KB
physical id : 0
siblings    : 1
core id     : 0
cpu cores   : 1
apicid      : 0
initial apicid  : 0
fpu     : yes
fpu_exception   : yes
cpuid level : 13
wp      : yes
flags       : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ss ht syscall nx rdtscp lm constant_tsc nopl xtopology nonstop_tsc eagerfpu pni pclmulqdq ssse3 fma cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand hypervisor lahf_lm abm arat pln pts dtherm fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 invpcid xsaveopt
bugs        :
bogomips    : 4988.45
clflush size    : 64
cache_alignment : 64
address sizes   : 36 bits physical, 48 bits virtual
power management:

5
2018-05-04 11:14