Reemplazar un contador de bucle de 32 bits con 64 bits introduce desviaciones de rendimiento locas
Estaba buscando la forma más rápida depopcount grandes conjuntos de datos. Me encontré con unmuy raro efecto: Cambiar la variable de bucle deunsigned auint64_t redujo el rendimiento en un 50% en mi PC.
#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, cuyo tamaño esx megabytes dondex se lee desde la línea de comando. Luego, iteramos sobre el búfer y usamos una versión desenrollada del x86popcount intrínseco para realizar el popcount. Para obtener un resultado más preciso, hacemos el conteo pop 10,000 veces. Medimos los tiempos para el popcount. En mayúsculas, la variable del bucle interno esunsigned, en minúsculas, la variable del bucle interno esuint64_t. Pensé que esto no debería hacer ninguna diferencia, pero lo contrario es el caso.
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 miHaswell Core i7-4770K CPU a 3.50 GHz, funcionandotest 1 (por lo tanto, 1 MB de datos aleatorios):
Como puede ver, el rendimiento de lauint64_t la versión essólo la mitad el de losunsigned ¡versión! El problema parece ser que se genera un ensamblaje diferente, pero ¿por qué? Primero, pensé en un error del compilador, así que intentéclang++ (UbuntuSonido metálico versión 3.4-1ubuntu3):
clang++ -O3 -march=native -std=c++11 teest.cpp -o test
Resultado:test 1
Entonces, es casi el mismo resultado y sigue siendo 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 constante1, 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. ¡Quizás pueda agregar algunas optimizaciones! Aquí están los números parag++:
Ahora, ambas versiones son igualmente rápidas. sin embargo, elunsigned se hizo aún más lento! Se cayó de26 a20 GB/s, reemplazando así un no constante por un valor constante conduce a undesoptimización. En serio, no tengo idea de lo que está pasando aquí. Pero ahora aclang++ con la nueva versión:
¿Esperar lo? Ahora, ambas versiones cayeron allento número de 15 GB / s. Por lo tanto, reemplazar un valor no constante por un valor constante incluso conduce a un código lento enambos casos para Clang!
Le pregunté a un colega con unIvy Bridge CPU 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 del compilador. No tenemos una CPU AMD aquí, por lo que solo pudimos probar con Intel.
¡Más locura, por favor!Tome el primer ejemplo (el que tieneatol(argv[1])) y poner unstatic antes 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 seg26.4306 GB / suint64_t 41959360000 0.509484 segundos20.5811 GB / sYay, otra alternativa más. Todavía tenemos los rápidos 26 GB / s conu32, pero logramosu64 ¡Al menos desde la versión de 13 GB / s hasta la de 20 GB / s!En la PC de mi colega, elu64 la versión se hizo aún más rápida que lau32 versión, produciendo el resultado más rápido de todos. Lamentablemente, esto solo funciona parag++, clang++ no parece importarlestatic.
¿Puedes explicar estos resultados? Especialmente:
¿Cómo puede haber tanta diferencia entreu32 yu64?¿Cómo se puede reemplazar un disparador no constante por un tamaño de búfer constante?código menos óptimo?¿Cómo puede la inserción de lastatic la palabra clave hace elu64 bucle 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 complicado, sin embargo, nunca pensé que cambios tan pequeños pueden conducir a una100% de diferencia en tiempo de ejecución y que pequeños factores como un tamaño de búfer constante pueden volver a mezclar los resultados totalmente. Por supuesto, siempre quiero tener la versión que sea capaz de contar 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 forma en que puedo deshacerme de los compiladores que parecen volverse locos con pequeños cambios. ¿Qué piensas? ¿Hay alguna otra manera de obtener el código de manera confiable con el mayor rendimiento?
El desmontajeAquí está el desmontaje de los distintos resultados:
Versión de 26 GB / s deg ++ / u32 / tamaño 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 deg ++ / u64 / tamaño 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 declang ++ / u64 / tamaño 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 deg ++ / 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 declang ++ / 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) también es la más larga. Parece ser la única solución que usalea. Algunas versiones usanjb para saltar, otros usanjne. 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 muy 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?
No importa cuál sea la respuesta a esta pregunta; He aprendido que en bucles realmente calientescada los detalles pueden importarincluso detalles que no parecen tener ninguna asociación con el hot code. Nunca pensé en qué tipo usar para una variable de bucle, pero como puede ver, un cambio tan pequeño puede hacer que100% ¡diferencia! Incluso el tipo de almacenamiento de un búfer puede marcar una gran diferencia, como vimos con la inserción delstatic palabra clave frente a la variable de tamaño! En el futuro, siempre probaré varias alternativas en varios compiladores al escribir bucles realmente ajustados y dinámicos que son cruciales para el rendimiento del sistema.
Lo interesante también es que la diferencia de rendimiento sigue siendo muy alta, aunque ya he desenrollado el ciclo cuatro veces. Entonces, incluso si se desenrolla, aún puede ser golpeado por grandes desviaciones de rendimiento. Bastante interesante.