Por qué std:: se empareja más rápido que std::tuple
Aquí está el código para probar.
Prueba de tupla:
using namespace std;
int main(){
vector<tuple<int,int>> v;
for (int var = 0; var < 100000000; ++var) {
v.push_back(make_tuple(var, var));
}
}
Prueba de par:
#include <vector>
using namespace std;
int main(){
vector<pair<int,int>> v;
for (int var = 0; var < 100000000; ++var) {
v.push_back(make_pair(var, var));
}
}
Hice la medición del tiempo a través del comando Linux time. Los resultados son:
| | -O0 | -O2 |
|:------|:-------:|:--------:|
| Pair | 8.9 s | 1.60 s |
| Tuple | 19.8 s | 1.96 s |
Me pregunto, por qué hay una diferencia tan grande entre esas dos estructuras de datos en O0, ya que deberían ser muy similares. Solo hay una pequeña diferencia en 02.
¿Por qué la diferencia en O0 es tan grande, y por qué hay alguna diferencia en absoluto?
EDITAR:
El código con v. resize ()
Par:
#include <vector>
using namespace std;
int main(){
vector<pair<int,int>> v;
v.resize(100000000);
for (int var = 0; var < 100000000; ++var) {
v[var] = make_pair(var, var);
}
}
Tupla:
#include<tuple>
#include<vector>
using namespace std;
int main(){
vector<tuple<int,int>> v;
v.resize(100000000);
for (int var = 0; var < 100000000; ++var) {
v[var] = make_tuple(var, var);
}
}
Resultados:
| | -O0 | -O2 |
|:------|:-------:|:--------:|
| Pair | 5.01 s | 0.77 s |
| Tuple | 10.6 s | 0.87 s |
EDITAR:
Mi sistema
g++ (GCC) 4.8.3 20140911 (Red Hat 4.8.3-7)
GLIBCXX_3.4.19
2 answers
Le falta alguna información crucial: ¿Qué compilador utiliza? ¿Qué se utiliza para medir el rendimiento del microbenchmark? ¿Qué implementación de biblioteca estándar utiliza?
Mi sistema:
g++ (GCC) 4.9.1 20140903 (prerelease)
GLIBCXX_3.4.20
De todos modos, ejecuté sus ejemplos, pero reservé el tamaño adecuado de los vectores primero para deshacerse de la sobrecarga de asignación de memoria. Con eso, curiosamente observo lo opuesto algo interesante - el reverso de lo que ves:
g++ -std=c++11 -O2 pair.cpp -o pair
perf stat -r 10 -d ./pair
Performance counter stats for './pair' (10 runs):
1647.045151 task-clock:HG (msec) # 0.993 CPUs utilized ( +- 1.94% )
346 context-switches:HG # 0.210 K/sec ( +- 40.13% )
7 cpu-migrations:HG # 0.004 K/sec ( +- 22.01% )
182,978 page-faults:HG # 0.111 M/sec ( +- 0.04% )
3,394,685,602 cycles:HG # 2.061 GHz ( +- 2.24% ) [44.38%]
2,478,474,676 stalled-cycles-frontend:HG # 73.01% frontend cycles idle ( +- 1.24% ) [44.55%]
1,550,747,174 stalled-cycles-backend:HG # 45.68% backend cycles idle ( +- 1.60% ) [44.66%]
2,837,484,461 instructions:HG # 0.84 insns per cycle
# 0.87 stalled cycles per insn ( +- 4.86% ) [55.78%]
526,077,681 branches:HG # 319.407 M/sec ( +- 4.52% ) [55.82%]
829,623 branch-misses:HG # 0.16% of all branches ( +- 4.42% ) [55.74%]
594,396,822 L1-dcache-loads:HG # 360.887 M/sec ( +- 4.74% ) [55.59%]
20,842,113 L1-dcache-load-misses:HG # 3.51% of all L1-dcache hits ( +- 0.68% ) [55.46%]
5,474,166 LLC-loads:HG # 3.324 M/sec ( +- 1.81% ) [44.23%]
<not supported> LLC-load-misses:HG
1.658671368 seconds time elapsed ( +- 1.82% )
Versus:
g++ -std=c++11 -O2 tuple.cpp -o tuple
perf stat -r 10 -d ./tuple
Performance counter stats for './tuple' (10 runs):
996.090514 task-clock:HG (msec) # 0.996 CPUs utilized ( +- 2.41% )
102 context-switches:HG # 0.102 K/sec ( +- 64.61% )
4 cpu-migrations:HG # 0.004 K/sec ( +- 32.24% )
181,701 page-faults:HG # 0.182 M/sec ( +- 0.06% )
2,052,505,223 cycles:HG # 2.061 GHz ( +- 2.22% ) [44.45%]
1,212,930,513 stalled-cycles-frontend:HG # 59.10% frontend cycles idle ( +- 2.94% ) [44.56%]
621,104,447 stalled-cycles-backend:HG # 30.26% backend cycles idle ( +- 3.48% ) [44.69%]
2,700,410,991 instructions:HG # 1.32 insns per cycle
# 0.45 stalled cycles per insn ( +- 1.66% ) [55.94%]
486,476,408 branches:HG # 488.386 M/sec ( +- 1.70% ) [55.96%]
959,651 branch-misses:HG # 0.20% of all branches ( +- 4.78% ) [55.82%]
547,000,119 L1-dcache-loads:HG # 549.147 M/sec ( +- 2.19% ) [55.67%]
21,540,926 L1-dcache-load-misses:HG # 3.94% of all L1-dcache hits ( +- 2.73% ) [55.43%]
5,751,650 LLC-loads:HG # 5.774 M/sec ( +- 3.60% ) [44.21%]
<not supported> LLC-load-misses:HG
1.000126894 seconds time elapsed ( +- 2.47% )
As se puede ver, en mi caso la razón son el número mucho mayor de ciclos estancados, tanto en el frontend, así como en el backend.
Ahora, ¿de dónde viene esto? Apuesto a que se trata de algún error en la inserción, similar a lo que se explica aquí: std:: regresión de rendimiento vectorial al habilitar C++11
De hecho, habilitar -flto iguala los resultados para mí:
Performance counter stats for './pair' (10 runs):
1021.922944 task-clock:HG (msec) # 0.997 CPUs utilized ( +- 1.15% )
63 context-switches:HG # 0.062 K/sec ( +- 77.23% )
5 cpu-migrations:HG # 0.005 K/sec ( +- 34.21% )
195,396 page-faults:HG # 0.191 M/sec ( +- 0.00% )
2,109,877,147 cycles:HG # 2.065 GHz ( +- 0.92% ) [44.33%]
1,098,031,078 stalled-cycles-frontend:HG # 52.04% frontend cycles idle ( +- 0.93% ) [44.46%]
701,553,535 stalled-cycles-backend:HG # 33.25% backend cycles idle ( +- 1.09% ) [44.68%]
3,288,420,630 instructions:HG # 1.56 insns per cycle
# 0.33 stalled cycles per insn ( +- 0.88% ) [55.89%]
672,941,736 branches:HG # 658.505 M/sec ( +- 0.80% ) [56.00%]
660,278 branch-misses:HG # 0.10% of all branches ( +- 2.05% ) [55.93%]
474,314,267 L1-dcache-loads:HG # 464.139 M/sec ( +- 1.32% ) [55.73%]
19,481,787 L1-dcache-load-misses:HG # 4.11% of all L1-dcache hits ( +- 0.80% ) [55.51%]
5,155,678 LLC-loads:HG # 5.045 M/sec ( +- 1.69% ) [44.21%]
<not supported> LLC-load-misses:HG
1.025083895 seconds time elapsed ( +- 1.03% )
Y para la tupla:
Performance counter stats for './tuple' (10 runs):
1018.980969 task-clock:HG (msec) # 0.999 CPUs utilized ( +- 0.47% )
8 context-switches:HG # 0.008 K/sec ( +- 29.74% )
3 cpu-migrations:HG # 0.003 K/sec ( +- 42.64% )
195,396 page-faults:HG # 0.192 M/sec ( +- 0.00% )
2,103,574,740 cycles:HG # 2.064 GHz ( +- 0.30% ) [44.28%]
1,088,827,212 stalled-cycles-frontend:HG # 51.76% frontend cycles idle ( +- 0.47% ) [44.56%]
697,438,071 stalled-cycles-backend:HG # 33.15% backend cycles idle ( +- 0.41% ) [44.76%]
3,305,631,646 instructions:HG # 1.57 insns per cycle
# 0.33 stalled cycles per insn ( +- 0.21% ) [55.94%]
675,175,757 branches:HG # 662.599 M/sec ( +- 0.16% ) [56.02%]
656,205 branch-misses:HG # 0.10% of all branches ( +- 0.98% ) [55.93%]
475,532,976 L1-dcache-loads:HG # 466.675 M/sec ( +- 0.13% ) [55.69%]
19,430,992 L1-dcache-load-misses:HG # 4.09% of all L1-dcache hits ( +- 0.20% ) [55.49%]
5,161,624 LLC-loads:HG # 5.065 M/sec ( +- 0.47% ) [44.14%]
<not supported> LLC-load-misses:HG
1.020225388 seconds time elapsed ( +- 0.48% )
Así que recuerde, -flto es su amigo y no se puede resultados extremos en código fuertemente templados. Usa perf stat para averiguar qué está pasando.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 11:54:44
Milianw no abordó el -O0 vs. -O2, así que me gustaría agregar una explicación para eso.
Se espera que std::tuple será más lento que std::pair cuando no optimizado, porque es un objeto más complicado. Un par tiene exactamente dos miembros, por lo que sus métodos son fáciles de definir. Pero la tupla tiene un número arbitrario de miembros y la única manera de iterar sobre la lista de argumentos de la plantilla es con recursión. Por lo tanto, la mayoría de las funciones para tupla manejan un miembro y luego recurren a maneja el resto, así que para 2-tupla tienes el doble de llamadas a funciones.
Ahora que están optimizados, el compilador insertará esa recursividad y no debería haber diferencia significativa. Que las pruebas confirman claramente. Eso se aplica a cosas con plantillas en general. Las plantillas se pueden escribir para proporcionar abstracción con poca o ninguna sobrecarga de tiempo de ejecución, pero eso se basa en optimizaciones para integrar todas las funciones triviales.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-03-01 07:53:48