c++ - Reemplazar un contador de bucle de 32 bits con 64 bits introduce desviaciones de rendimiento increíbles

performance optimization

Question

Estaba buscando la forma más rápida de hacer popcount grandes conjuntos de datos. Encontré un efecto muy extraño : cambiar la variable de bucle de unsigned a uint64_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 x megabytes donde x se lee desde la línea de comandos. Luego, iteramos sobre el búfer y utilizamos una versión desenrollada del intrínseco de popcount 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 de bucle interno unsigned está unsigned , en minúscula, la variable de bucle 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 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, ejecutando la test 1 (por lo que 1 MB de datos aleatorios):

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

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

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

Resultado: test 1

• sin firma 41959360000 0.398293 sec 26.3267 GB / s
• uint64_t 41959360000 0.680954 sec 15.3986 GB / s

Entonces, es casi el mismo resultado y aún es extraño. Pero ahora se pone 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 sabe 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 firma 41959360000 0.509156 sec 20.5944 GB / s
• uint64_t 41959360000 0.508673 sec 20.6139 GB / s

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

• sin firma 41959360000 0.677009 sec 15.4884 GB / s
• uint64_t 41959360000 0.676909 sec 15.4906 GB / s

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

Le pregunté a un colega con una CPU Ivy Bridge para compilar 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 de compilación. 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 un atol(argv[1]) ) y ponga una static antes de la variable, es decir:

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

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

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

Yay, otra alternativa más . Todavía tenemos los 26 GB / s u32 con u32 , pero logramos obtener u64 al menos desde los 13 GB / s hasta la versión de 20 GB / s. En la PC de mi u64 , la versión u64 llegó a ser incluso más rápida que la versión u32 , lo que u32 el resultado más rápido de todos. Lamentablemente, esto solo funciona para g++ , clang++ no parece preocuparse por la static .

Mi pregunta

¿Puedes explicar estos resultados? Especialmente:

• ¿Cómo puede haber tal diferencia entre u32 y u64 ?
• ¿Cómo puede reemplazar un código menos óptimo la sustitución de una no constante por un tamaño de búfer constante?
• ¿Cómo puede la inserción de la palabra clave static hacer que el bucle u64 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 cambios tan pequeños pueden 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 pueden mezclar los resultados nuevamente. Por supuesto, siempre quiero tener una versión que pueda cargar 26 GB / s. La única forma 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 volverse locos con pequeños cambios. ¿Qué piensas? ¿Hay otra forma de obtener el código de forma confiable con la mayor parte del rendimiento?

El desmontaje

Aquí está el desmontaje de los diversos resultados:

Versión de 26 GB / s desde 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

Versión de 13 GB / s desde g ++ / u64 / non-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

Versión de 15 GB / s desde clang ++ / u64 / non-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

Versión de 20 GB / s 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

Versión de 15 GB / s desde 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 utiliza lea . Algunas versiones usan jb para saltar, otras 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 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 será; He aprendido que en los bucles realmente calientes todos los detalles pueden importar, incluso los detalles que no parecen tener ninguna asociación con el código activo . Nunca he pensado qué tipo usar para una variable de bucle, pero como ves, un cambio tan pequeño puede hacer una diferencia del 100% . ¡Incluso el tipo de almacenamiento de un búfer puede hacer una gran diferencia, como vimos con la inserción de la palabra clave static delante de la variable de tamaño! En el futuro, siempre probaré varias alternativas en varios compiladores cuando escribo bucles realmente precisos y cruciales que son cruciales para el rendimiento del sistema.

Lo interesante también es que la diferencia de rendimiento sigue siendo tan alta, aunque ya he desenrollado el bucle cuatro veces. Por lo tanto, incluso si se desenrolla, puede verse afectado por importantes desviaciones de rendimiento. Bastante interesante.

Answer 1

¿Ha 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

Answer 2

¿Has intentado mover el paso de reducción fuera del bucle? Ahora mismo tienes 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 tienes un extraño aliasing, que no estoy seguro de que cumpla con las estrictas reglas de aliasing.

Answer 3

Codifiqué un programa de 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 todos modos) es mejor, ya que el uso de uint_fast32_t hace que gcc use un uint de 64 bits.

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

Esto es obviamente un pirateo, 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 popcount interno domine el rendimiento, este es un buen comienzo .

Luego copié el código de bucle interno de la versión de 32 bits del programa, lo hackeé para que fuera de 64 bits, jugué con los registros para convertirlo en un reemplazo del 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 parte del compilador, no una ventaja real de velocidad / latencia de las instrucciones de 32 bits.

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

Answer 4

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

Obtengo estos resultados con un Mac Pro ( Westmere 6-Cores Xeon 3.33 GHz). Lo compilé con clang -O3 -msse4 -lstdc++ a.cpp -oa (-O2 obtiene el mismo resultado).

clang with 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

clang 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. Invertir el orden de prueba, el resultado es el mismo, por lo que descarta el factor de caché.
2. Tenga la instrucción for en sentido inverso: for (uint64_t i=size/8;i>0;i-=4) . Esto da el mismo resultado y prueba 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 conjetura salvaje:

El factor de velocidad viene en tres partes:

• código de caché: la versión uint64_t tiene un tamaño de código mayor, pero esto no tiene un 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. El acceso a un puntero con un desplazamiento de 64 bits solicita un registro y direccionamiento de 64 bits dedicados, mientras que puede usarlo de 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, búsqueda previa). Esto hace que 64 bits más rápido.

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

Answer 5

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 se debe a que 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 ensamblaje: r10 = bfrptr, r15 = bfrend, rsi = count, 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

Answer 6

No puedo dar una respuesta autorizada, pero ofrezco una visión general de una causa probable. Esta referencia muestra claramente que para las instrucciones en el cuerpo de su bucle hay una relación de 3: 1 entre la latencia y el rendimiento. También muestra los efectos del envío múltiple. Dado que hay (dar o tomar) tres unidades enteras en los procesadores x86 modernos, generalmente es posible enviar tres instrucciones por ciclo.

Por lo tanto, entre el rendimiento máximo de la tubería y el despacho múltiple y la falla de estos mecanismos, tenemos un factor de seis en el desempeño. Es bien sabido que la complejidad del conjunto de instrucciones x86 hace que sea bastante fácil que ocurran roturas extravagantes. El documento de arriba 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 los desplazamientos de 32 bits, tienen un rendimiento aceptable. Parece que la ruta de datos desde los 32 bits superiores hasta los 32 bits inferiores de la ALU no está bien diseñada.

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

Aquí, mi conjetura es la contención de unidades enteras: que los popcnt , contador de bucle y dirección apenas pueden ejecutarse a toda velocidad con el contador de 32 bits de ancho, pero el contador de 64 bits provoca la contención y las paradas de la tubería. Como solo hay alrededor de 12 ciclos en total, potencialmente 4 ciclos con múltiples despachos, ejecución por cuerpo de bucle, un solo bloqueo podría afectar razonablemente el tiempo de ejecución en un factor de 2.

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

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

Answer 7

TL; DR: use __builtin intrinsics en su lugar.

Pude hacer que gcc 4.8.4 (e incluso 4.7.3 en gcc.godbolt.org) genere un código óptimo para esto usando __builtin_popcountll que usa la misma instrucción de ensamblaje, pero no tiene ese error de dependencia falso.

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

Resultados:

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

Código de referencia:

#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 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 la 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:

Answer 8

Culpable: Dependencia de datos falsos (y el compilador ni siquiera lo sabe)

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

popcnt src, dest

Parece tener una dependencia falsa en el destino del registro de destino. A pesar de que la instrucción solo le escribe, la instrucción esperará hasta que el dest esté listo antes de ejecutarse.

Esta dependencia no solo popcnt los 4 popcnt s de una única iteración de bucle. Puede transmitir iteraciones de bucle, lo que hace imposible que el procesador paralice diferentes iteraciones de bucle.

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

En su caso, las velocidades son un resultado directo de lo que está atascado en la cadena de dependencia (falsa) en función de lo que el asignador de registros decidió hacer.

• 13 GB / s tiene una cadena: popcnt - add - popcnt - popcnt → siguiente iteración
• 15 GB / s tiene una cadena: popcnt - add - popcnt - add → siguiente iteración
• 20 GB / s tiene una cadena: popcnt - popcnt → siguiente iteración
• 26 GB / s tiene una cadena: popcnt - popcnt → siguiente 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 alcanza esta velocidad.

Para probar esto, usé el ensamblaje en línea para omitir el compilador y obtener exactamente el ensamblaje que quiero. También divido la variable de count para romper todas las demás dependencias que puedan alterar 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

Registros diferentes: 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 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 son conscientes de que popcnt tiene una dependencia tan falsa. Sin embargo, estas dependencias falsas no son infrecuentes. Es solo una cuestión 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. Tampoco parece haber documentación en ninguna parte que mencione este problema. Si Intel no lo revela, nadie lo sabrá hasta que alguien lo encuentre por casualidad.

( Actualización: a partir de la versión 4.9.2 , GCC está al tanto de esta dependencia falsa y genera un código para compensarlo cuando las optimizaciones están habilitadas. Los compiladores principales de otros proveedores, incluidos Clang, MSVC e incluso el propio ICC de Intel aún no lo saben este error de microarquitectura y no emitirá código que lo 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. Por lo tanto, Intel probablemente popcnt a popcnt en la misma categoría para mantener el diseño del procesador simple.

Los procesadores de AMD no parecen tener esta dependencia falsa.

El código de prueba completo se encuentra a continuación como 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);
}

Una referencia igualmente interesante se puede encontrar aquí: http://pastebin.com/kbzgL8si
Este punto de referencia varía el número de popcnt s 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

Answer 9

En primer lugar, trate de estimar el rendimiento máximo: examine https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf , en particular, el apéndice C.

En su caso, la tabla C-10 muestra que la instrucción POPCNT tiene una latencia = 3 relojes y un rendimiento = 1 reloj. El rendimiento muestra su velocidad máxima en relojes (se multiplica por la frecuencia central y 8 bytes en caso de popcnt64 para obtener el mejor número de ancho de banda posible).

Ahora examine qué compilador hizo y sume los rendimientos de todas las demás instrucciones en el bucle. Esto le dará la mejor estimación posible para el código generado.

Por último, observe las dependencias de datos entre las instrucciones en el bucle, ya que forzarán una gran latencia en lugar de un rendimiento, así que divida las instrucciones de iteración única en las cadenas de flujo de datos y calcule la latencia a través de ellas para luego seleccionarlas al máximo. dará una estimación aproximada teniendo en cuenta las dependencias del flujo de datos.

Sin embargo, en su caso, solo escribir el código de la manera correcta eliminaría todas estas complejidades. En lugar de acumular en la misma variable de conteo, solo acumule en diferentes (como count0, count1, ... count8) y súmelos al final. O incluso crear una serie de conteos [8] y acumularlos en sus elementos: tal vez, incluso se vectorizará y obtendrá un rendimiento mucho mejor.

PS y nunca ejecute un punto de referencia durante un segundo, primero caliente el núcleo y luego ejecute el bucle durante al menos 10 segundos o más 100 segundos. de lo contrario, probará el firmware de administración de energía y la implementación de DVFS en hardware :)

PPS Escuché debates interminables sobre cuánto tiempo debería correr realmente el punto de referencia. La mayoría de las personas más inteligentes incluso preguntan por qué 10 segundos, no 11 o 12. Debo admitir que esto es divertido en teoría. En la práctica, simplemente vas y ejecutas el benchmark cientos de veces seguidas y registras las desviaciones. Eso es gracioso. La mayoría de las personas cambian de fuente y ejecutan el banco después de eso UNA VEZ exactamente para capturar el nuevo récord de rendimiento. Haz las cosas correctas bien.

¿Aún no estás convencido? Simplemente use la versión C de benchmark por assp1r1n3 ( https://.com/a/37026212/9706746 ) e intente 100 en lugar de 10000 en el ciclo de reintentos.

Mis 7960X shows, con RETRY = 100:

Cuenta: 203182300 Transcurridos: 0.008385 segundos Velocidad: 12.505379 GB / s

Cuenta: 203182300 Transcurridos: 0.011063 segundos Velocidad: 9.478225 GB / s

Cuenta: 203182300 Transcurridos: 0.011188 segundos Velocidad: 9.372327 GB / s

Cuenta: 203182300 Transcurridos: 0.010393 segundos Velocidad: 10.089252 GB / s

Cuenta: 203182300 Transcurridos: 0.009076 segundos Velocidad: 11.553283 GB / s

con RETRY = 10000:

Cuenta: 20318230000 Transcurridos: 0.661791 segundos Velocidad: 15.844519 GB / s

Cuenta: 20318230000 Transcurridos: 0.665422 segundos Velocidad: 15.758060 GB / s

Cuenta: 20318230000 Transcurridos: 0.660983 segundos Velocidad: 15.863888 GB / s

Cuenta: 20318230000 Transcurridos: 0.665337 segundos Velocidad: 15.760073 GB / s

Cuenta: 20318230000 Transcurridos: 0.662138 segundos Velocidad: 15.836215 GB / s

PPPS Finalmente, en "respuesta aceptada" y otro misterio ;-)

Usemos la respuesta de assp1r1n3: tiene un núcleo de 2,5 Ghz. POPCNT tiene un reloj de 1 hora, su código usa popcnt de 64 bits. Entonces, las matemáticas son 2.5GHz * 1 reloj * 8 bytes = 20 GB / s para su configuración. Está viendo 25Gb / s, tal vez debido al aumento de turbo a alrededor de 3GHz.

Por lo tanto, vaya a ark.intel.com y busque i7-4870HQ: https://ark.intel.com/products/83504/Intel-Core-i7-4870HQ-Processor-6M-Cache-up-to-3-70-GHz-?q=i7-4870HQ

Ese núcleo podría alcanzar hasta 3.7 Ghz y la tasa máxima real es de 29.6 GB / s para su hardware. Entonces, ¿dónde está otro 4GB / s? Tal vez, se gasta en la lógica de bucle y otros códigos circundantes dentro de cada iteración.

Ahora, ¿ dónde está esta dependencia falsa? El hardware corre a una velocidad casi máxima. Tal vez mi matemática sea mala, a veces sucede :)

PPPPPS Todavía hay personas que sugieren que la errata de HW es la culpable, así que sigo la sugerencia y creé el ejemplo en línea de ASM, vea a continuación.

En mi 7960X, la primera versión (con salida única a cnt0) se ejecuta a 11MB / s, la segunda versión (con salida a cnt0, cnt1, cnt2 y cnt3) se ejecuta a 33MB / s. Y se podría decir - ¡voilá! es la dependencia de salida.

Bien, tal vez, el punto que señalé es que no tiene sentido escribir código como este y no es un problema de dependencia de salida sino una generación de código simple. No estamos probando hardware, estamos escribiendo código para liberar el máximo rendimiento. Podría esperar que HW OOO cambie el nombre y oculte esas "dependencias de salida" pero, Gash, simplemente haga lo correcto y nunca enfrentará ningún misterio.

uint64_t builtin_popcnt1a(const uint64_t* buf, size_t len)
{
uint64_t cnt0, cnt1, cnt2, cnt3;
cnt0 = cnt1 = cnt2 = cnt3 = 0;
uint64_t val = buf[0];
#if 0
__asm__ __volatile__ (
"1:/n/t"
"popcnt %2, %1/n/t"
"popcnt %2, %1/n/t"
"popcnt %2, %1/n/t"
"popcnt %2, %1/n/t"
"subq $4, %0/n/t"
"jnz 1b/n/t"
: "+q" (len), "=q" (cnt0)
: "q" (val)
:
);
#else
__asm__ __volatile__ (
"1:/n/t"
"popcnt %5, %1/n/t"
"popcnt %5, %2/n/t"
"popcnt %5, %3/n/t"
"popcnt %5, %4/n/t"
"subq $4, %0/n/t"
"jnz 1b/n/t"
: "+q" (len), "=q" (cnt0), "=q" (cnt1), "=q" (cnt2), "=q" (cnt3)
: "q" (val)
:
);
#endif
return cnt0;
}