Tengo 2 columnas de enteros delimitados por tabuladores, el primero de los cuales es un entero aleatorio, el segundo un entero que identifica el grupo, que puede generar este programa. ( generate_groups.cc)
#include <cstdlib>
#include <iostream>
#include <ctime>
int main(int argc, char* argv[]) {
int num_values = atoi(argv[1]);
int num_groups = atoi(argv[2]);
int group_size = num_values / num_groups;
int group = -1;
std::srand(42);
for (int i = 0; i < num_values; ++i) {
if (i % group_size == 0) {
++group;
}
std::cout << std::rand() << '\t' << group << '\n';
}
return 0;
}Luego uso un segundo programa ( sum_groups.cc) para calcular las sumas por grupo.
#include <iostream>
#include <chrono>
#include <vector>
// This is the function whose performance I am interested in
void grouped_sum(int* p_x, int *p_g, int n, int* p_out) {
for (size_t i = 0; i < n; ++i) {
p_out[p_g[i]] += p_x[i];
}
}
int main() {
std::vector<int> values;
std::vector<int> groups;
std::vector<int> sums;
int n_groups = 0;
// Read in the values and calculate the max number of groups
while(std::cin) {
int value, group;
std::cin >> value >> group;
values.push_back(value);
groups.push_back(group);
if (group > n_groups) {
n_groups = group;
}
}
sums.resize(n_groups);
// Time grouped sums
std::chrono::system_clock::time_point start = std::chrono::system_clock::now();
for (int i = 0; i < 10; ++i) {
grouped_sum(values.data(), groups.data(), values.size(), sums.data());
}
std::chrono::system_clock::time_point end = std::chrono::system_clock::now();
std::cout << (end - start).count() << std::endl;
return 0;
}Si luego ejecuto estos programas en un conjunto de datos de un tamaño determinado, y luego barajo el orden de las filas del mismo conjunto de datos, los datos barajados calculan las sumas ~ 2 veces o más rápido que los datos ordenados.
g++ -O3 generate_groups.cc -o generate_groups
g++ -O3 sum_groups.cc -o sum_groups
generate_groups 1000000 100 > groups
shuf groups > groups2
sum_groups < groups
sum_groups < groups2
sum_groups < groups2
sum_groups < groups
20784
8854
8220
21006Hubiera esperado que los datos originales que están ordenados por grupo tengan una mejor localidad de datos y sean más rápidos, pero observo el comportamiento opuesto. Me preguntaba si alguien puede hipotetizar la razón.
c++
performance
Jim
fuente
fuente
.at()un modo de depuraciónoperator[]que limita comprobando que verías.sum. En lugar desums.reserve(n_groups);que debe llamarsums.resize(n_groups);, eso es lo que @Shawn estaba insinuando.p_out[p_g[i]] += p_x[i];. Tal vez en el orden codificado original, los grupos realmente muestran una buena agrupación con respecto al acceso a lap_outmatriz. La clasificación de los valores puede causar un patrón de acceso indexado en grupo deficientep_out.Respuestas:
Configurar / hacerlo lento
En primer lugar, el programa se ejecuta aproximadamente al mismo tiempo, independientemente de:
La mayor parte del tiempo se gasta en el bucle de entrada. Pero como estamos interesados en el
grouped_sum(), ignoremos eso.Al cambiar el ciclo de referencia de 10 a 1000 iteraciones,
grouped_sum()comienza a dominar el tiempo de ejecución:perf diff
Ahora podemos utilizar
perfpara encontrar los puntos más populares en nuestro programa.Y la diferencia entre ellos:
Más tiempo en
main(), lo que probablemente se ha puesto engrouped_sum()línea. Genial, muchas gracias, perf.anotar perf
¿Hay alguna diferencia en el lugar donde se pasa el tiempo adentro
main()?Barajado:
Ordenados:
No, son las mismas dos instrucciones las que dominan. Por lo tanto, toman mucho tiempo en ambos casos, pero son aún peores cuando se ordenan los datos.
estadística de perf
Bueno. Pero deberíamos ejecutarlos la misma cantidad de veces, por lo que cada instrucción debe ser más lenta por alguna razón. Veamos que
perf statdice.Solo una cosa se destaca: stailt-cycles-frontend .
De acuerdo, el canal de instrucciones se está estancando. En la interfaz. Exactamente lo que eso significa probablemente varía entre microarquitecturas.
Sin embargo, tengo una suposición. Si eres generoso, incluso podrías llamarlo una hipótesis.
Hipótesis
Al ordenar la entrada, aumenta la localidad de las escrituras. De hecho, serán muy locales; Casi todas las adiciones que haga escribirán en la misma ubicación que la anterior.
Eso es genial para el caché, pero no para la canalización. Está introduciendo dependencias de datos, evitando que la siguiente instrucción de adición continúe hasta que la adición anterior se haya completado (o haya puesto el resultado a disposición de las instrucciones siguientes) )
Ese es tu problema.
Yo creo que.
Arreglando lo
Vectores de suma múltiple
En realidad, intentemos algo. ¿Qué pasaría si utilizáramos múltiples vectores de suma, cambiando entre ellos para cada suma, y luego los sumamos al final? Nos cuesta un poco de localidad, pero debería eliminar las dependencias de datos.
(el código no es bonito; ¡no me juzgues, internet!)
(ah, y también arreglé el cálculo de n_groups; estaba desactivado en uno).
Resultados
Después de configurar mi archivo MAKE para dar un
-DNSUMS=...argumento al compilador, podría hacer esto:El número óptimo de vectores de suma probablemente dependerá de la profundidad de la tubería de su CPU. Mi CPU de ultrabook de 7 años probablemente puede maximizar la tubería con menos vectores de los que necesitaría una nueva CPU de escritorio elegante.
Claramente, más no es necesariamente mejor; Cuando me volví loco con 128 vectores de suma, comenzamos a sufrir más por errores de caché, como lo demuestra la entrada aleatoria que se vuelve más lenta de lo ordenado, como había esperado originalmente. ¡Hemos cerrado el círculo! :)
Suma por grupo en el registro
(esto se agregó en una edición)
Agh, nerd sniped ! Si sabe que su entrada se ordenará y está buscando aún más rendimiento, la siguiente reescritura de la función (sin matrices de suma adicionales) es aún más rápida, al menos en mi computadora.
El truco en este es que le permite al compilador mantener el
gsumvariable, la suma del grupo, en un registro. Supongo (pero puede estar muy equivocado) que esto es más rápido porque el ciclo de retroalimentación en la tubería puede ser más corto aquí y / o menos accesos a la memoria. Un buen predictor de rama hará que la verificación adicional para la igualdad de grupo sea barata.Resultados
Es terrible para la entrada barajada ...
... pero es aproximadamente un 40% más rápido que mi solución de "muchas sumas" para entradas ordenadas.
Muchos grupos pequeños serán más lentos que algunos grandes, por lo que si esta es la implementación más rápida o no dependerá realmente de sus datos aquí. Y, como siempre, en su modelo de CPU.
Múltiples vectores de sumas, con desplazamiento en lugar de enmascaramiento de bits
Sopel sugirió cuatro adiciones desenrolladas como una alternativa a mi enfoque de enmascaramiento de bits. He implementado una versión generalizada de su sugerencia, que puede manejar diferentes
NSUMS. Cuento con que el compilador desenrolle el bucle interno para nosotros (lo que hizo, al menos paraNSUMS=4).Resultados
Hora de medir. Tenga en cuenta que desde que estaba trabajando en / tmp ayer, no tengo exactamente los mismos datos de entrada. Por lo tanto, estos resultados no son directamente comparables con los anteriores (pero probablemente lo suficientemente cerca).
Sí, el bucle interno con
NSUMS=8es el más rápido en mi computadora. En comparación con mi enfoque de "gsum local", también tiene el beneficio adicional de no volverse terrible para la entrada aleatoria.Interesante tener en cuenta: se
NSUMS=16vuelve peor queNSUMS=8. Esto podría ser porque estamos comenzando a ver más errores de caché o porque no tenemos suficientes registros para desenrollar el bucle interno correctamente.fuente
perf.Aquí es por qué los grupos ordenados son más lentos que los grupos no patrocinados;
Primero, aquí está el código de ensamblaje para el ciclo de suma:
Veamos las instrucciones de agregar, que es la razón principal de este problema;
Cuando el procesador ejecuta esta instrucción primero, emitirá una solicitud de lectura de memoria (carga) a la dirección en edx, luego agregará el valor de ecx y luego emitirá una solicitud de escritura (almacenamiento) para la misma dirección.
hay una función en el reordenamiento de la memoria del procesador de llamadas
y hay una regla
Entonces, si la siguiente iteración llega a la instrucción de agregar antes de que se complete la solicitud de escritura, no esperará si la dirección edx es diferente al valor anterior y emitirá la solicitud de lectura y se reordenó sobre la solicitud de escritura anterior y la instrucción de adición continuará. pero si la dirección es la misma, la instrucción de agregar esperará hasta que finalice la escritura anterior.
Tenga en cuenta que el bucle es corto y el procesador puede ejecutarlo más rápido de lo que el controlador de memoria completa la solicitud de escritura en memoria.
por lo tanto, para grupos ordenados, leerá y escribirá desde la misma dirección muchas veces consecutivas, por lo que perderá la mejora del rendimiento mediante el reordenamiento de la memoria; mientras tanto, si se usan grupos aleatorios, entonces cada iteración tendrá probablemente una dirección diferente, por lo que la lectura no esperará a una escritura más antigua y se reordenará antes; Agregar instrucción no esperará a la anterior.
fuente