std::regresión de rendimiento vectorial al habilitar C++ 11

9 minutos de lectura

avatar de usuario
milianw

He encontrado una regresión de rendimiento interesante en un pequeño fragmento de C++, cuando habilito C++11:

#include <vector>

struct Item
{
  int a;
  int b;
};

int main()
{
  const std::size_t num_items = 10000000;
  std::vector<Item> container;
  container.reserve(num_items);
  for (std::size_t i = 0; i < num_items; ++i) {
    container.push_back(Item());
  }
  return 0;
}

Con g ++ (GCC) 4.8.2 20131219 (versión preliminar) y C ++ 03 obtengo:

milian:/tmp$ g++ -O3 main.cpp && perf stat -r 10 ./a.out

Performance counter stats for './a.out' (10 runs):

        35.206824 task-clock                #    0.988 CPUs utilized            ( +-  1.23% )
                4 context-switches          #    0.116 K/sec                    ( +-  4.38% )
                0 cpu-migrations            #    0.006 K/sec                    ( +- 66.67% )
              849 page-faults               #    0.024 M/sec                    ( +-  6.02% )
       95,693,808 cycles                    #    2.718 GHz                      ( +-  1.14% ) [49.72%]
  <not supported> stalled-cycles-frontend 
  <not supported> stalled-cycles-backend  
       95,282,359 instructions              #    1.00  insns per cycle          ( +-  0.65% ) [75.27%]
       30,104,021 branches                  #  855.062 M/sec                    ( +-  0.87% ) [77.46%]
            6,038 branch-misses             #    0.02% of all branches          ( +- 25.73% ) [75.53%]

      0.035648729 seconds time elapsed                                          ( +-  1.22% )

Por otro lado, con C++ 11 habilitado, el rendimiento se degrada significativamente:

milian:/tmp$ g++ -std=c++11 -O3 main.cpp && perf stat -r 10 ./a.out

Performance counter stats for './a.out' (10 runs):

        86.485313 task-clock                #    0.994 CPUs utilized            ( +-  0.50% )
                9 context-switches          #    0.104 K/sec                    ( +-  1.66% )
                2 cpu-migrations            #    0.017 K/sec                    ( +- 26.76% )
              798 page-faults               #    0.009 M/sec                    ( +-  8.54% )
      237,982,690 cycles                    #    2.752 GHz                      ( +-  0.41% ) [51.32%]
  <not supported> stalled-cycles-frontend 
  <not supported> stalled-cycles-backend  
      135,730,319 instructions              #    0.57  insns per cycle          ( +-  0.32% ) [75.77%]
       30,880,156 branches                  #  357.057 M/sec                    ( +-  0.25% ) [75.76%]
            4,188 branch-misses             #    0.01% of all branches          ( +-  7.59% ) [74.08%]

    0.087016724 seconds time elapsed                                          ( +-  0.50% )

¿Alguien puede explicar esto? Hasta ahora, mi experiencia fue que STL se vuelve más rápido al habilitar C++ 11, esp. gracias a mover la semántica.

EDITAR: Como se sugiere, usando container.emplace_back(); en cambio, el rendimiento está a la par con la versión C++03. ¿Cómo puede la versión C++03 lograr lo mismo para push_back?

milian:/tmp$ g++ -std=c++11 -O3 main.cpp && perf stat -r 10 ./a.out

Performance counter stats for './a.out' (10 runs):

        36.229348 task-clock                #    0.988 CPUs utilized            ( +-  0.81% )
                4 context-switches          #    0.116 K/sec                    ( +-  3.17% )
                1 cpu-migrations            #    0.017 K/sec                    ( +- 36.85% )
              798 page-faults               #    0.022 M/sec                    ( +-  8.54% )
       94,488,818 cycles                    #    2.608 GHz                      ( +-  1.11% ) [50.44%]
  <not supported> stalled-cycles-frontend 
  <not supported> stalled-cycles-backend  
       94,851,411 instructions              #    1.00  insns per cycle          ( +-  0.98% ) [75.22%]
       30,468,562 branches                  #  840.991 M/sec                    ( +-  1.07% ) [76.71%]
            2,723 branch-misses             #    0.01% of all branches          ( +-  9.84% ) [74.81%]

   0.036678068 seconds time elapsed                                          ( +-  0.80% )

  • Si compila para ensamblar, puede ver lo que sucede debajo del capó. Ver también stackoverflow.com/questions/8021874/…

    – Rueda dentada

    07/01/2014 a las 17:15

  • que pasa si cambias push_back(Item()) a emplace_back() en la versión C++ 11?

    – Rueda dentada

    7 de enero de 2014 a las 17:17

  • Véase más arriba, que “arregla” la regresión. Sin embargo, todavía me pregunto por qué push_back retrocede en el rendimiento entre C++ 03 y C++ 11.

    – milianw

    7 de enero de 2014 a las 17:24

  • @milianw Resulta que estaba compilando el programa equivocado. Ignora mis comentarios.

    usuario1508519

    7 de enero de 2014 a las 18:03

  • Con clang3.4 la versión C++11 es más rápida, 0.047s vs 0.058 para la versión C++98

    – Pretoriano

    07/01/2014 a las 19:33

avatar de usuario
Ali

Puedo reproducir sus resultados en mi máquina con las opciones que escribe en su publicación.

Sin embargo, si también habilito optimización del tiempo de enlace (También paso el -flto flag a gcc 4.7.2), los resultados son idénticos:

(Estoy compilando tu código original, con container.push_back(Item());)

$ g++ -std=c++11 -O3 -flto regr.cpp && perf stat -r 10 ./a.out 

 Performance counter stats for './a.out' (10 runs):

         35.426793 task-clock                #    0.986 CPUs utilized            ( +-  1.75% )
                 4 context-switches          #    0.116 K/sec                    ( +-  5.69% )
                 0 CPU-migrations            #    0.006 K/sec                    ( +- 66.67% )
            19,801 page-faults               #    0.559 M/sec                  
        99,028,466 cycles                    #    2.795 GHz                      ( +-  1.89% ) [77.53%]
        50,721,061 stalled-cycles-frontend   #   51.22% frontend cycles idle     ( +-  3.74% ) [79.47%]
        25,585,331 stalled-cycles-backend    #   25.84% backend  cycles idle     ( +-  4.90% ) [73.07%]
       141,947,224 instructions              #    1.43  insns per cycle        
                                             #    0.36  stalled cycles per insn  ( +-  0.52% ) [88.72%]
        37,697,368 branches                  # 1064.092 M/sec                    ( +-  0.52% ) [88.75%]
            26,700 branch-misses             #    0.07% of all branches          ( +-  3.91% ) [83.64%]

       0.035943226 seconds time elapsed                                          ( +-  1.79% )



$ g++ -std=c++98 -O3 -flto regr.cpp && perf stat -r 10 ./a.out 

 Performance counter stats for './a.out' (10 runs):

         35.510495 task-clock                #    0.988 CPUs utilized            ( +-  2.54% )
                 4 context-switches          #    0.101 K/sec                    ( +-  7.41% )
                 0 CPU-migrations            #    0.003 K/sec                    ( +-100.00% )
            19,801 page-faults               #    0.558 M/sec                    ( +-  0.00% )
        98,463,570 cycles                    #    2.773 GHz                      ( +-  1.09% ) [77.71%]
        50,079,978 stalled-cycles-frontend   #   50.86% frontend cycles idle     ( +-  2.20% ) [79.41%]
        26,270,699 stalled-cycles-backend    #   26.68% backend  cycles idle     ( +-  8.91% ) [74.43%]
       141,427,211 instructions              #    1.44  insns per cycle        
                                             #    0.35  stalled cycles per insn  ( +-  0.23% ) [87.66%]
        37,366,375 branches                  # 1052.263 M/sec                    ( +-  0.48% ) [88.61%]
            26,621 branch-misses             #    0.07% of all branches          ( +-  5.28% ) [83.26%]

       0.035953916 seconds time elapsed  

En cuanto a las razones, hay que mirar el código ensamblador generado (g++ -std=c++11 -O3 -S regr.cpp). En el modo C++11, el código generado está significativamente más desordenado que para el modo C++98 y enmarcando la función
void std::vector<Item,std::allocator<Item>>::_M_emplace_back_aux<Item>(Item&&)
falla en modo C++11 con el valor predeterminado inline-limit.

Esta línea fallida tiene un efecto dominó. No porque se llame a esta función (¡ni siquiera se llama!) sino porque tenemos que estar preparados: Si se llama, los argumentos de la función (Item.a y Item.b) ya debe estar en el lugar correcto. Esto conduce a un código bastante desordenado.

Aquí está la parte relevante del código generado para el caso en que la alineación tiene éxito:

.L42:
    testq   %rbx, %rbx  # container$D13376$_M_impl$_M_finish
    je  .L3 #,
    movl    $0, (%rbx)  #, container$D13376$_M_impl$_M_finish_136->a
    movl    $0, 4(%rbx) #, container$D13376$_M_impl$_M_finish_136->b
.L3:
    addq    $8, %rbx    #, container$D13376$_M_impl$_M_finish
    subq    $1, %rbp    #, ivtmp.106
    je  .L41    #,
.L14:
    cmpq    %rbx, %rdx  # container$D13376$_M_impl$_M_finish, container$D13376$_M_impl$_M_end_of_storage
    jne .L42    #,

Este es un bucle for agradable y compacto. Ahora, comparemos esto con el de la falló en línea caso:

.L49:
    testq   %rax, %rax  # D.15772
    je  .L26    #,
    movq    16(%rsp), %rdx  # D.13379, D.13379
    movq    %rdx, (%rax)    # D.13379, *D.15772_60
.L26:
    addq    $8, %rax    #, tmp75
    subq    $1, %rbx    #, ivtmp.117
    movq    %rax, 40(%rsp)  # tmp75, container.D.13376._M_impl._M_finish
    je  .L48    #,
.L28:
    movq    40(%rsp), %rax  # container.D.13376._M_impl._M_finish, D.15772
    cmpq    48(%rsp), %rax  # container.D.13376._M_impl._M_end_of_storage, D.15772
    movl    $0, 16(%rsp)    #, D.13379.a
    movl    $0, 20(%rsp)    #, D.13379.b
    jne .L49    #,
    leaq    16(%rsp), %rsi  #,
    leaq    32(%rsp), %rdi  #,
    call    _ZNSt6vectorI4ItemSaIS0_EE19_M_emplace_back_auxIIS0_EEEvDpOT_   #

Este código está desordenado y suceden muchas más cosas en el bucle que en el caso anterior. Antes de la función call (se muestra la última línea), los argumentos deben colocarse apropiadamente:

leaq    16(%rsp), %rsi  #,
leaq    32(%rsp), %rdi  #,
call    _ZNSt6vectorI4ItemSaIS0_EE19_M_emplace_back_auxIIS0_EEEvDpOT_   #

Aunque esto nunca se ejecuta realmente, el ciclo organiza las cosas antes:

movl    $0, 16(%rsp)    #, D.13379.a
movl    $0, 20(%rsp)    #, D.13379.b

Esto conduce al código desordenado. Si no hay función call porque la alineación tiene éxito, solo tenemos 2 instrucciones de movimiento en el bucle y no hay problema con el %rsp (puntero de pila). Sin embargo, si la alineación falla, obtenemos 6 movimientos y nos metemos mucho con el %rsp.

Sólo para corroborar mi teoría (nótese el -finline-limit), ambos en modo C++11:

 $ g++ -std=c++11 -O3 -finline-limit=105 regr.cpp && perf stat -r 10 ./a.out

 Performance counter stats for './a.out' (10 runs):

         84.739057 task-clock                #    0.993 CPUs utilized            ( +-  1.34% )
                 8 context-switches          #    0.096 K/sec                    ( +-  2.22% )
                 1 CPU-migrations            #    0.009 K/sec                    ( +- 64.01% )
            19,801 page-faults               #    0.234 M/sec                  
       266,809,312 cycles                    #    3.149 GHz                      ( +-  0.58% ) [81.20%]
       206,804,948 stalled-cycles-frontend   #   77.51% frontend cycles idle     ( +-  0.91% ) [81.25%]
       129,078,683 stalled-cycles-backend    #   48.38% backend  cycles idle     ( +-  1.37% ) [69.49%]
       183,130,306 instructions              #    0.69  insns per cycle        
                                             #    1.13  stalled cycles per insn  ( +-  0.85% ) [85.35%]
        38,759,720 branches                  #  457.401 M/sec                    ( +-  0.29% ) [85.43%]
            24,527 branch-misses             #    0.06% of all branches          ( +-  2.66% ) [83.52%]

       0.085359326 seconds time elapsed                                          ( +-  1.31% )

 $ g++ -std=c++11 -O3 -finline-limit=106 regr.cpp && perf stat -r 10 ./a.out

 Performance counter stats for './a.out' (10 runs):

         37.790325 task-clock                #    0.990 CPUs utilized            ( +-  2.06% )
                 4 context-switches          #    0.098 K/sec                    ( +-  5.77% )
                 0 CPU-migrations            #    0.011 K/sec                    ( +- 55.28% )
            19,801 page-faults               #    0.524 M/sec                  
       104,699,973 cycles                    #    2.771 GHz                      ( +-  2.04% ) [78.91%]
        58,023,151 stalled-cycles-frontend   #   55.42% frontend cycles idle     ( +-  4.03% ) [78.88%]
        30,572,036 stalled-cycles-backend    #   29.20% backend  cycles idle     ( +-  5.31% ) [71.40%]
       140,669,773 instructions              #    1.34  insns per cycle        
                                             #    0.41  stalled cycles per insn  ( +-  1.40% ) [88.14%]
        38,117,067 branches                  # 1008.646 M/sec                    ( +-  0.65% ) [89.38%]
            27,519 branch-misses             #    0.07% of all branches          ( +-  4.01% ) [86.16%]

       0.038187580 seconds time elapsed                                          ( +-  2.05% )

De hecho, si le pedimos al compilador que se esfuerce un poco más para alinear esa función, la diferencia en el rendimiento desaparece.


Entonces, ¿cuál es la conclusión de esta historia? Esas líneas fallidas pueden costarle mucho y debe hacer un uso completo de las capacidades del compilador: Solo puedo recomendar la optimización del tiempo de enlace. Dio un aumento significativo en el rendimiento de mis programas (hasta 2.5x) y todo lo que tenía que hacer era aprobar el -flto bandera. ¡Es un trato bastante bueno! 😉

Sin embargo, no recomiendo tirar tu código a la basura con la palabra clave en línea; deja que el compilador decida qué hacer. (El optimizador puede tratar la palabra clave en línea como un espacio en blanco de todos modos).


Gran pregunta, +1!

  • NÓTESE BIEN: inline no tiene nada que ver con la función en línea; significa “definido en línea” no “por favor en línea esto”. Si realmente desea solicitar la inserción, use __attribute__((always_inline)) o similar.

    – Jon Purdy

    24 de enero de 2014 a las 19:07

  • @JonPurdy No del todo, por ejemplo, las funciones de miembros de clase están implícitamente en línea. inline también es una solicitud hacia el compilador de que le gustaría que la función esté en línea y, por ejemplo, el Compilador Intel C ++ solía dar advertencias de rendimiento si no cumplía con su solicitud. (No he revisado icc recientemente si todavía lo hace). Desafortunadamente, he visto a personas destrozando su código con inline y esperando que ocurra el milagro. yo no usaría __attribute__((always_inline)); lo más probable es que los desarrolladores del compilador sepan mejor qué poner en línea y qué no. (A pesar del contraejemplo aquí).

    – Alí

    24/01/2014 a las 19:25

  • @JonPurdy Por otro lado, si define una función en línea que no es una función miembro de una clase, entonces no tiene más remedio que marcarlo en línea; de lo contrario, obtendrá múltiples errores de definición del enlazador. Si eso es lo que quisiste decir, entonces está bien.

    – Alí

    24/01/2014 a las 19:25


  • Sí, eso es lo que quise decir. La norma dice “El inline El especificador indica a la implementación que se prefiere la sustitución en línea del cuerpo de la función en el punto de llamada al mecanismo habitual de llamada de función. (§7.1.2.2) Sin embargo, no se requieren implementaciones para realizar esa optimización, ya que es en gran medida una coincidencia que inline Las funciones a menudo resultan ser buenas candidatas para insertarlas. Así que es mejor ser explícito y usar un pragma de compilador.

    – Jon Purdy

    25 de enero de 2014 a las 1:05

  • @JonPurdy En cuanto a la primera mitad: Sí, eso es lo que quise decir al decir “Los optimizador se le permite tratar la palabra clave en línea como un espacio en blanco de todos modos”. En cuanto al pragma del compilador, no lo usaría, lo dejaría en manos de la optimización del tiempo de enlace, ya sea en línea o no. Hace un trabajo bastante bueno; también resolvió automáticamente este problema discutido aquí en la respuesta.

    – Alí

    25 de enero de 2014 a las 1:12


¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad