Cómo comparar correctamente un programa C ++ [con plantilla]

Question

< backgound >

Estoy en un punto en el que realmente necesito optimizar el código C ++. Estoy escribiendo una biblioteca para simulaciones moleculares y necesito agregar una nueva característica. Ya intenté agregar esta característica en el pasado, pero luego utilicé funciones virtuales llamadas en bucles anidados. Tenía malos sentimientos al respecto y la primera implementación demostró que era una mala idea. Sin embargo, esto estuvo bien para probar el concepto.

< / background >

Ahora necesito que esta característica sea lo más rápida posible (bueno, sin el código de ensamblaje o el cálculo de la GPU, todavía tiene que ser C ++ y más legible que menos). Ahora sé un poco más sobre plantillas y políticas de clase (del excelente libro de Alexandrescu) y creo que una generación de código en tiempo de compilación puede ser la solución.

Sin embargo, necesito probar el diseño antes de hacer el trabajo enorme de implementarlo en la biblioteca. La pregunta es sobre la mejor manera de probar la eficiencia de esta nueva característica.

Obviamente necesito activar las optimizaciones porque sin este g ++ (y probablemente también otros compiladores) mantendría algunas operaciones innecesarias en el código objeto. También necesito hacer un uso intensivo de la nueva función en el punto de referencia porque un delta de 1e-3 segundos puede marcar la diferencia entre un diseño bueno y uno malo (esta función se llamará millones de veces en el programa real).

El problema es que g ++ es a veces " demasiado inteligente " mientras optimiza y puede eliminar un ciclo completo si considera que el resultado de un cálculo nunca se usa. Ya lo he visto una vez al mirar el código de ensamblaje de salida.

Si agrego algo de impresión a stdout, el compilador se verá obligado a hacer el cálculo en el ciclo, pero probablemente compararé principalmente la implementación de iostream.

Entonces, ¿cómo puedo hacer un punto de referencia correcto de una pequeña característica extraída de una biblioteca? Pregunta relacionada: ¿es un enfoque correcto hacer este tipo de pruebas in vitro en una unidad pequeña o necesito todo el contexto?

¡Gracias por los consejos!

---

Parece que hay varias estrategias, desde opciones específicas del compilador que permiten un ajuste fino hasta soluciones más generales que deberían funcionar con cada compilador como volatile o extern.

Creo que intentaré todo esto. Muchas gracias por todas sus respuestas!

Answer 1

Si desea forzar al compilador any para que no descarte un resultado, haga que escriba el resultado en un objeto volátil. Esa operación no se puede optimizar, por definición.

template<typename T> void sink(T const& t) {
   volatile T sinkhole = t;
}

Sin sobrecarga iostream, solo una copia que debe permanecer en el código generado. Ahora, si está recopilando resultados de muchas operaciones, es mejor no descartarlos uno por uno. Estas copias aún pueden agregar algo de sobrecarga. En cambio, de alguna manera recolecte todos los resultados en un solo objeto no volátil (por lo que se necesitan todos los resultados individuales) y luego asigne ese objeto de resultado a un volátil. P.ej. si todas sus operaciones individuales producen cadenas, puede forzar la evaluación agregando todos los valores de caracteres juntos módulo 1 < < 32. Esto agrega casi ningún gasto general; las cadenas probablemente estarán en caché. El resultado de la adición se asignará posteriormente a volátil, por lo que cada char en cada picadura debe calcularse, no se permiten atajos.

Answer 2

A menos que tenga un compilador agresivo realmente (puede suceder), le sugiero que calcule una suma de verificación (simplemente agregue todos los resultados juntos) y genere la suma de verificación.

Aparte de eso, es posible que desee ver el código de ensamblaje generado antes de ejecutar cualquier punto de referencia para que pueda verificar visualmente que se están ejecutando los bucles.

Answer 3

Los compiladores solo pueden eliminar ramificaciones de código que no pueden suceder. Mientras no pueda descartar que se ejecute una rama, no la eliminará. Mientras haya alguna dependencia de datos en alguna parte, el código estará allí y se ejecutará. Los compiladores no son demasiado inteligentes para estimar qué aspectos de un programa no se ejecutarán y no lo intentan, porque ese es un problema de NP y difícilmente computable. Tienen algunas comprobaciones simples como if (0), pero eso es todo.

Mi humilde opinión es que posiblemente haya tenido algún otro problema anteriormente, como la forma en que C / C ++ evalúa las expresiones booleanas.

Pero de todos modos, dado que se trata de una prueba de velocidad, puede verificar que las cosas se llamen por sí mismo: ejecútelo una vez sin, luego otra vez con una prueba de valores de retorno. O una variable estática que se incrementa. Al final de la prueba, imprima el número generado. Los resultados serán iguales.

Para responder a su pregunta sobre las pruebas in vitro: Sí, haga eso. Si su aplicación es tan urgente, hágalo. Por otro lado, su descripción sugiere un problema diferente: si sus deltas están en un marco de tiempo de 1e-3 segundos, entonces eso suena como un problema de complejidad computacional, ya que el método en cuestión debe llamarse muy, muy a menudo (por pocas carreras, 1e-3 segundos es descuidado).

El dominio del problema que está modelando suena MUY complejo y los conjuntos de datos son probablemente enormes. Tales cosas son siempre un esfuerzo interesante. Sin embargo, primero asegúrese de tener absolutamente las estructuras de datos y algoritmos correctos, y micro optimice todo lo que quiera después de eso. Entonces, yo diría que primero mire todo el contexto. ;-)

Por curiosidad, ¿cuál es el problema que estás calculando?

Answer 4

Usted tiene mucho control sobre las optimizaciones para su compilación. -O1, -O2, etc. son solo alias para un grupo de interruptores.

De las páginas del manual

       -O2 turns on all optimization flags specified by -O.  It also turns
       on the following optimization flags: -fthread-jumps -falign-func‐
       tions  -falign-jumps -falign-loops  -falign-labels -fcaller-saves
       -fcrossjumping -fcse-follow-jumps  -fcse-skip-blocks
       -fdelete-null-pointer-checks -fexpensive-optimizations -fgcse
       -fgcse-lm -foptimize-sibling-calls -fpeephole2 -fregmove -fre‐
       order-blocks  -freorder-functions -frerun-cse-after-loop
       -fsched-interblock  -fsched-spec -fschedule-insns  -fsched‐
       ule-insns2 -fstrict-aliasing -fstrict-overflow -ftree-pre
       -ftree-vrp

Puede ajustar y usar este comando para ayudarlo a reducir qué opciones investigar.

       ...
       Alternatively you can discover which binary optimizations are
       enabled by -O3 by using:

               gcc -c -Q -O3 --help=optimizers > /tmp/O3-opts
               gcc -c -Q -O2 --help=optimizers > /tmp/O2-opts
               diff /tmp/O2-opts /tmp/O3-opts Φ grep enabled

Una vez que encuentre la optimización de culpret, no debería necesitar los cout.

Answer 5

Si esto es posible para usted, puede intentar dividir su código en:

• la biblioteca que desea probar compilada con todas las optimizaciones activadas
• un programa de prueba, que vincula dinámicamente la biblioteca, con optimizaciones desactivadas

De lo contrario, puede especificar un nivel de optimización diferente (parece que está usando gcc ...) para la función de prueba con el atributo de optimización (consulte http://gcc.gnu.org/onlinedocs/gcc/Function-Attributes.html#Function-Attributes ) .

Answer 6

Podría crear una función ficticia en un archivo cpp separado que no hace nada, pero toma como argumento el tipo de resultado de su cálculo. Luego puede llamar a esa función con los resultados de su cálculo, forzando a gcc a generar el código intermedio, y la única penalización es el costo de invocar una función (¡lo cual no debería sesgar sus resultados a menos que lo llame un lote ! ).

Answer 7

#include <iostream>

// Mark coords as extern.
// Compiler is now NOT allowed to optimise away coords
// This it can not remove the loop where you initialise it.
// This is because the code could be used by another compilation unit
extern double coords[500][3];
double coords[500][3];

int main()
{

//perform a simple initialization of all coordinates:
for (int i=0; i<500; ++i)
 {
   coords[i][0] = 3.23;
   coords[i][1] = 1.345;
   coords[i][2] = 123.998;
 }


std::cout << "hello world !"<< std::endl;
return 0;
}

Answer 8

edit : lo más fácil que puede hacer es simplemente usar los datos de una manera espuria después de que la función se haya ejecutado y fuera de sus puntos de referencia. Me gusta,

StartBenchmarking(); // ie, read a performance counter
for (int i=0; i<500; ++i)
 {
   coords[i][0] = 3.23;
   coords[i][1] = 1.345;
   coords[i][2] = 123.998;
 }
StopBenchmarking(); // what comes after this won't go into the timer

// this is just to force the compiler to use coords
double foo;
for (int j = 0 ; j < 500 ; ++j )
{
  foo += coords[j][0] + coords[j][1] + coords[j][2]; 
}
cout << foo;

---

Lo que a veces me funciona en estos casos es ocultar la prueba in vitro dentro de una función y pasar los conjuntos de datos de referencia a través de punteros volátiles . Esto le dice al compilador que no debe colapsar las escrituras posteriores en esos punteros (porque podrían ser por ejemplo E / S mapeadas en memoria). Entonces,

void test1( volatile double *coords )
{
  //perform a simple initialization of all coordinates:
  for (int i=0; i<1500; i+=3)
  {
    coords[i+0] = 3.23;
    coords[i+1] = 1.345;
    coords[i+2] = 123.998;
  }
}

Por alguna razón, aún no me he dado cuenta de que no siempre funciona en MSVC, pero a menudo sí lo hace: mire la salida del ensamblaje para estar seguro. También recuerde que volátil frustrará algunas optimizaciones del compilador (prohíbe que el compilador mantenga los contenidos del puntero en el registro y obliga a que las escrituras ocurran en el orden del programa), por lo que esto solo es confiable si lo está utilizando para el escritura final de datos.

En general, las pruebas in vitro como esta son muy útiles siempre que recuerde que no es toda la historia. Por lo general, pruebo mis nuevas rutinas matemáticas de forma aislada de esta manera para poder iterar rápidamente solo sobre las características de caché y canalización de mi algoritmo en datos consistentes.

La diferencia entre un perfil de probeta como este y ejecutarlo en " el mundo real " significa que obtendrá conjuntos de datos de entrada que varían enormemente (a veces en el mejor de los casos, a veces en el peor de los casos, a veces patológico), el caché estará en un estado desconocido al ingresar a la función, y puede tener otros subprocesos golpeando el bus; por lo que debe ejecutar algunos puntos de referencia en esta función in vivo también cuando haya terminado.

Answer 9

No sé si GCC tiene una función similar, pero con VC ++ puede usar:

#pragma optimize

para activar / desactivar selectivamente las optimizaciones. Si GCC tiene capacidades similares, puede construir con optimización completa y simplemente desactivarlo cuando sea necesario para asegurarse de que se llame a su código.

Answer 10

Solo un pequeño ejemplo de una optimización no deseada:

#include <vector>
#include <iostream>

using namespace std;

int main()
{
double coords[500][3];

//perform a simple initialization of all coordinates:
for (int i=0; i<500; ++i)
 {
   coords[i][0] = 3.23;
   coords[i][1] = 1.345;
   coords[i][2] = 123.998;
 }


cout << "hello world !"<< endl;
return 0;
}

Si comenta el código de " doble coords [500] [3] " al final del ciclo for generará exactamente el mismo código de ensamblaje (solo lo intenté con g ++ 4.3.2). Sé que este ejemplo es demasiado simple, y no pude mostrar este comportamiento con un std :: vector de un simple & Quot; Coordenadas & Quot; estructura.

Sin embargo, creo que este ejemplo todavía muestra que algunas optimizaciones pueden introducir errores en el punto de referencia y quería evitar algunas sorpresas de este tipo al introducir un nuevo código en una biblioteca. Es fácil imaginar que el nuevo contexto podría evitar algunas optimizaciones y conducir a una biblioteca muy ineficiente.

Lo mismo también debería aplicarse con las funciones virtuales (pero no lo pruebo aquí). Utilizado en un contexto donde un enlace estático haría el trabajo, estoy bastante seguro de que los compiladores decentes deberían eliminar la llamada indirecta adicional para la función virtual. Puedo probar esta llamada en un bucle y concluir que llamar a una función virtual no es tan importante. Luego lo llamaré cientos de miles de veces en un contexto en el que el compilador no puede adivinar cuál será el tipo exacto del puntero y tendrá un aumento del 20% del tiempo de ejecución ...

Answer 11

al inicio, leer desde un archivo. en su código, diga if (input == " x ") cout < < result_of_benchmark;

El compilador no podrá eliminar el cálculo, y si se asegura de que la entrada no sea " x " ;, no comparará el iostream.