c++ performance

c++ - ¿Por qué la suma agrupada es más lenta con grupos ordenados que grupos sin clasificar?



performance (1)

Configurar / hacerlo lento

En primer lugar, el programa se ejecuta aproximadamente al mismo tiempo, independientemente de:

sumspeed$ time ./sum_groups < groups_shuffled 11558358 real 0m0.705s user 0m0.692s sys 0m0.013s sumspeed$ time ./sum_groups < groups_sorted 24986825 real 0m0.722s user 0m0.711s sys 0m0.012s

La mayor parte del tiempo se gasta en el bucle de entrada. Pero como estamos interesados ​​en 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:

sumspeed$ time ./sum_groups < groups_shuffled 1131838420 real 0m1.828s user 0m1.811s sys 0m0.016s sumspeed$ time ./sum_groups < groups_sorted 2494032110 real 0m3.189s user 0m3.169s sys 0m0.016s

perf diff

Ahora podemos usar perf para encontrar los puntos más populares en nuestro programa.

sumspeed$ perf record ./sum_groups < groups_shuffled 1166805982 [ perf record: Woken up 1 times to write data ] [kernel.kallsyms] with build id 3a2171019937a2070663f3b6419330223bd64e96 not found, continuing without symbols Warning: Processed 4636 samples and lost 6.95% samples! [ perf record: Captured and wrote 0.176 MB perf.data (4314 samples) ] sumspeed$ perf record ./sum_groups < groups_sorted 2571547832 [ perf record: Woken up 2 times to write data ] [kernel.kallsyms] with build id 3a2171019937a2070663f3b6419330223bd64e96 not found, continuing without symbols [ perf record: Captured and wrote 0.420 MB perf.data (10775 samples) ]

Y la diferencia entre ellos:

sumspeed$ perf diff [...] # Event ''cycles:uppp'' # # Baseline Delta Abs Shared Object Symbol # ........ ......... ................... ........................................................................ # 57.99% +26.33% sum_groups [.] main 12.10% -7.41% libc-2.23.so [.] _IO_getc 9.82% -6.40% libstdc++.so.6.0.21 [.] std::num_get<char, std::istreambuf_iterator<char, std::char_traits<c 6.45% -4.00% libc-2.23.so [.] _IO_ungetc 2.40% -1.32% libc-2.23.so [.] _IO_sputbackc 1.65% -1.21% libstdc++.so.6.0.21 [.] 0x00000000000dc4a4 1.57% -1.20% libc-2.23.so [.] _IO_fflush 1.71% -1.07% libstdc++.so.6.0.21 [.] std::istream::sentry::sentry 1.22% -0.77% libstdc++.so.6.0.21 [.] std::istream::operator>> 0.79% -0.47% libstdc++.so.6.0.21 [.] __gnu_cxx::stdio_sync_filebuf<char, std::char_traits<char> >::uflow [...]

Más tiempo en main() , que probablemente tiene grouped_sum() línea. Genial, muchas gracias, perf.

anotar perf

¿Hay alguna diferencia en el lugar donde se pasa el tiempo dentro de main() ?

Barajado:

sumspeed$ perf annotate -i perf.data.old [...] │ // 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) { │180: xor %eax,%eax │ test %rdi,%rdi │ ↓ je 1a4 │ nop │ p_out[p_g[i]] += p_x[i]; 6,88 │190: movslq (%r9,%rax,4),%rdx 58,54 │ mov (%r8,%rax,4),%esi │ #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) { 3,86 │ add $0x1,%rax │ p_out[p_g[i]] += p_x[i]; 29,61 │ add %esi,(%rcx,%rdx,4) [...]

Ordenados:

sumspeed$ perf annotate -i perf.data [...] │ // 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) { │180: xor %eax,%eax │ test %rdi,%rdi │ ↓ je 1a4 │ nop │ p_out[p_g[i]] += p_x[i]; 1,00 │190: movslq (%r9,%rax,4),%rdx 55,12 │ mov (%r8,%rax,4),%esi │ #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) { 0,07 │ add $0x1,%rax │ p_out[p_g[i]] += p_x[i]; 43,28 │ add %esi,(%rcx,%rdx,4) [...]

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 qué dice perf stat .

sumspeed$ perf stat ./sum_groups < groups_shuffled 1138880176 Performance counter stats for ''./sum_groups'': 1826,232278 task-clock (msec) # 0,999 CPUs utilized 72 context-switches # 0,039 K/sec 1 cpu-migrations # 0,001 K/sec 4 076 page-faults # 0,002 M/sec 5 403 949 695 cycles # 2,959 GHz 930 473 671 stalled-cycles-frontend # 17,22% frontend cycles idle 9 827 685 690 instructions # 1,82 insn per cycle # 0,09 stalled cycles per insn 2 086 725 079 branches # 1142,639 M/sec 2 069 655 branch-misses # 0,10% of all branches 1,828334373 seconds time elapsed sumspeed$ perf stat ./sum_groups < groups_sorted 2496546045 Performance counter stats for ''./sum_groups'': 3186,100661 task-clock (msec) # 1,000 CPUs utilized 5 context-switches # 0,002 K/sec 0 cpu-migrations # 0,000 K/sec 4 079 page-faults # 0,001 M/sec 9 424 565 623 cycles # 2,958 GHz 4 955 937 177 stalled-cycles-frontend # 52,59% frontend cycles idle 9 829 009 511 instructions # 1,04 insn per cycle # 0,50 stalled cycles per insn 2 086 942 109 branches # 655,014 M/sec 2 078 204 branch-misses # 0,10% of all branches 3,186768174 seconds time elapsed

Solo se destaca una cosa: 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 adición, 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!)

#include <iostream> #include <chrono> #include <vector> #ifndef NSUMS #define NSUMS (4) // must be power of 2 (for masking to work) #endif // 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[i & (NSUMS-1)][p_g[i]] += p_x[i]; } } int main() { std::vector<int> values; std::vector<int> groups; std::vector<int> sums[NSUMS]; 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+1; } } for (int i=0; i<NSUMS; ++i) { sums[i].resize(n_groups); } // Time grouped sums std::chrono::system_clock::time_point start = std::chrono::system_clock::now(); int* sumdata[NSUMS]; for (int i = 0; i < NSUMS; ++i) { sumdata[i] = sums[i].data(); } for (int i = 0; i < 1000; ++i) { grouped_sum(values.data(), groups.data(), values.size(), sumdata); } for (int i = 1; i < NSUMS; ++i) { for (int j = 0; j < n_groups; ++j) { sumdata[0][j] += sumdata[i][j]; } } std::chrono::system_clock::time_point end = std::chrono::system_clock::now(); std::cout << (end - start).count() << " with NSUMS=" << NSUMS << std::endl; return 0; }

(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=... al compilador, podría hacer esto:

sumspeed$ for n in 1 2 4 8 128; do make -s clean && make -s NSUMS=$n && (perf stat ./sum_groups < groups_shuffled && perf stat ./sum_groups < groups_sorted) 2>&1 | egrep ''^[0-9]|frontend''; done 1134557008 with NSUMS=1 924 611 882 stalled-cycles-frontend # 17,13% frontend cycles idle 2513696351 with NSUMS=1 4 998 203 130 stalled-cycles-frontend # 52,79% frontend cycles idle 1116188582 with NSUMS=2 899 339 154 stalled-cycles-frontend # 16,83% frontend cycles idle 1365673326 with NSUMS=2 1 845 914 269 stalled-cycles-frontend # 29,97% frontend cycles idle 1127172852 with NSUMS=4 902 964 410 stalled-cycles-frontend # 16,79% frontend cycles idle 1171849032 with NSUMS=4 1 007 807 580 stalled-cycles-frontend # 18,29% frontend cycles idle 1118732934 with NSUMS=8 881 371 176 stalled-cycles-frontend # 16,46% frontend cycles idle 1129842892 with NSUMS=8 905 473 182 stalled-cycles-frontend # 16,80% frontend cycles idle 1497803734 with NSUMS=128 1 982 652 954 stalled-cycles-frontend # 30,63% frontend cycles idle 1180742299 with NSUMS=128 1 075 507 514 stalled-cycles-frontend # 19,39% frontend cycles idle

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 adicional) es aún más rápida, al menos en mi computadora.

// This is the function whose performance I am interested in void grouped_sum(int* p_x, int *p_g, int n, int* p_out) { int i = n-1; while (i >= 0) { int g = p_g[i]; int gsum = 0; do { gsum += p_x[i--]; } while (i >= 0 && p_g[i] == g); p_out[g] += gsum; } }

El truco en este es que le permite al compilador mantener la variable gsum , 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 ...

sumspeed$ time ./sum_groups < groups_shuffled 2236354315 real 0m2.932s user 0m2.923s sys 0m0.009s

... pero es aproximadamente un 40% más rápido que mi solución de "muchas sumas" para entradas ordenadas.

sumspeed$ time ./sum_groups < groups_sorted 809694018 real 0m1.501s user 0m1.496s sys 0m0.005s

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 para NSUMS=4 ).

#include <iostream> #include <chrono> #include <vector> #ifndef NSUMS #define NSUMS (4) // must be power of 2 (for masking to work) #endif #ifndef INNER #define INNER (0) #endif #if INNER // This is the function whose performance I am interested in void grouped_sum(int* p_x, int *p_g, int n, int** p_out) { size_t i = 0; int quadend = n & ~(NSUMS-1); for (; i < quadend; i += NSUMS) { for (int k=0; k<NSUMS; ++k) { p_out[k][p_g[i+k]] += p_x[i+k]; } } for (; i < n; ++i) { p_out[0][p_g[i]] += p_x[i]; } } #else // 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[i & (NSUMS-1)][p_g[i]] += p_x[i]; } } #endif int main() { std::vector<int> values; std::vector<int> groups; std::vector<int> sums[NSUMS]; 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+1; } } for (int i=0; i<NSUMS; ++i) { sums[i].resize(n_groups); } // Time grouped sums std::chrono::system_clock::time_point start = std::chrono::system_clock::now(); int* sumdata[NSUMS]; for (int i = 0; i < NSUMS; ++i) { sumdata[i] = sums[i].data(); } for (int i = 0; i < 1000; ++i) { grouped_sum(values.data(), groups.data(), values.size(), sumdata); } for (int i = 1; i < NSUMS; ++i) { for (int j = 0; j < n_groups; ++j) { sumdata[0][j] += sumdata[i][j]; } } std::chrono::system_clock::time_point end = std::chrono::system_clock::now(); std::cout << (end - start).count() << " with NSUMS=" << NSUMS << ", INNER=" << INNER << std::endl; return 0; }

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).

sumspeed$ for n in 2 4 8 16; do for inner in 0 1; do make -s clean && make -s NSUMS=$n INNER=$inner && (perf stat ./sum_groups < groups_shuffled && perf stat ./sum_groups < groups_sorted) 2>&1 | egrep ''^[0-9]|frontend''; done; done1130558787 with NSUMS=2, INNER=0 915 158 411 stalled-cycles-frontend # 16,96% frontend cycles idle 1351420957 with NSUMS=2, INNER=0 1 589 408 901 stalled-cycles-frontend # 26,21% frontend cycles idle 840071512 with NSUMS=2, INNER=1 1 053 982 259 stalled-cycles-frontend # 23,26% frontend cycles idle 1391591981 with NSUMS=2, INNER=1 2 830 348 854 stalled-cycles-frontend # 45,35% frontend cycles idle 1110302654 with NSUMS=4, INNER=0 890 869 892 stalled-cycles-frontend # 16,68% frontend cycles idle 1145175062 with NSUMS=4, INNER=0 948 879 882 stalled-cycles-frontend # 17,40% frontend cycles idle 822954895 with NSUMS=4, INNER=1 1 253 110 503 stalled-cycles-frontend # 28,01% frontend cycles idle 929548505 with NSUMS=4, INNER=1 1 422 753 793 stalled-cycles-frontend # 30,32% frontend cycles idle 1128735412 with NSUMS=8, INNER=0 921 158 397 stalled-cycles-frontend # 17,13% frontend cycles idle 1120606464 with NSUMS=8, INNER=0 891 960 711 stalled-cycles-frontend # 16,59% frontend cycles idle 800789776 with NSUMS=8, INNER=1 1 204 516 303 stalled-cycles-frontend # 27,25% frontend cycles idle 805223528 with NSUMS=8, INNER=1 1 222 383 317 stalled-cycles-frontend # 27,52% frontend cycles idle 1121644613 with NSUMS=16, INNER=0 886 781 824 stalled-cycles-frontend # 16,54% frontend cycles idle 1108977946 with NSUMS=16, INNER=0 860 600 975 stalled-cycles-frontend # 16,13% frontend cycles idle 911365998 with NSUMS=16, INNER=1 1 494 671 476 stalled-cycles-frontend # 31,54% frontend cycles idle 898729229 with NSUMS=16, INNER=1 1 474 745 548 stalled-cycles-frontend # 31,24% frontend cycles idle

Sí, el bucle interno con NSUMS=8 es 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.

Es interesante notar: NSUMS=16 vuelve peor que NSUMS=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.

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 21006

Hubiera 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.