performance - logo - hbase

¿Por qué std:: pair es más rápido que std:: tuple?

Question

Aquí está el código para probar.

Prueba Tuple:

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 de tiempo a través del comando de tiempo de Linux. Los resultados son:

|       |   -O0   |    -O2   |
|:------|:-------:|:--------:|
| Pair  |   8.9 s |  1.60 s  |
| Tuple |  19.8 s |  1.96 s  |

Me pregunto por qué es tan grande la diferencia 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é existe alguna diferencia?

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);
    }
}

Tuple:

#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

Answer 1

Te falta información crucial: ¿qué compilador utilizas? ¿Qué usas para medir el rendimiento del microbenchmark? ¿Qué implementación de biblioteca estándar usas?

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 deshacerme de la sobrecarga de asignación de memoria. Con eso, observo curiosamente lo contrario, 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% )

como puede ver, en mi caso la razón es la cantidad mucho mayor de ciclos estancados, tanto en la interfaz como en el servidor.

Ahora, ¿de dónde viene esto? Apuesto a que se trata de una alineación fallida, similar a lo que se explica aquí: std :: regresión del 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 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 la falla en la alineación puede tener resultados extremos en el código con -flto plantillas. Usa la perf stat de perf stat para descubrir qué está sucediendo.

Answer 2

milianw no abordó el -O0 vs. -O2 , así que me gustaría añadir una explicación para eso.

Es totalmente esperado que std::tuple sea ​​más lento que std::pair cuando no está 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 forma de iterar sobre la lista de argumentos de la plantilla es con recursividad. Por lo tanto, la mayoría de las funciones para tuple manejan un miembro y luego recurse para manejar el resto, por lo que para 2-tuple tiene el doble de llamadas a funciones.

Ahora, cuando estén optimizados, el compilador alineará esa recursión y no debería haber una diferencia significativa. Que las pruebas confirman claramente. Eso se aplica a cosas con muchas plantillas en general. Las plantillas se pueden escribir para proporcionar abstracción con muy poca sobrecarga de tiempo de ejecución, pero eso depende de las optimizaciones para alinear todas las funciones triviales.