ejemplos - Estrategias efectivas de optimización en los compiladores modernos de C++

comandos basicos de dev c++ (19)

¿Cuán conscientes son los compiladores de la caché? Por ejemplo, ¿vale la pena buscar reordenamiento de bucles anidados?

No puedo hablar por todos los compiladores, pero mi experiencia con GCC muestra que no optimizará mucho el código con respecto a la memoria caché. Esperaría que esto sea cierto para la mayoría de los compiladores modernos. La optimización como el reordenamiento de bucles anidados definitivamente puede afectar el rendimiento. Si crees que tienes patrones de acceso a la memoria que podrían llevar a muchos errores de caché, te interesará investigar esto.

Estoy trabajando en un código científico que es muy crítico para el rendimiento. Se ha escrito y probado una versión inicial del código, y ahora, con el generador de perfiles en la mano, es hora de comenzar los ciclos de afeitado de los puntos calientes.

Es bien sabido que algunas optimizaciones, por ejemplo, el desenrollado de bucles, son manejadas en estos días de manera mucho más efectiva por el compilador que por un programador que se entromete a mano. ¿Qué técnicas todavía valen la pena? Obviamente, ejecutaré todo lo que intento a través de un generador de perfiles, pero si existe una sabiduría convencional sobre lo que tiende a funcionar y lo que no, me ahorraría mucho tiempo.

Sé que la optimización depende mucho del compilador y de la arquitectura. Estoy usando el compilador C ++ de Intel que apunta al Core 2 Duo, pero también estoy interesado en lo que funciona bien para gcc, o para "cualquier compilador moderno".

Aquí hay algunas ideas concretas que estoy considerando:

¿Hay algún beneficio en reemplazar los contenedores / algoritmos STL por los enrollados a mano? En particular, mi programa incluye una cola de prioridad muy grande (actualmente una std::priority_queue ) cuya manipulación toma mucho tiempo total. ¿Es esto algo que vale la pena investigar, o la implementación de STL ya es probablemente la más rápida posible?
En líneas similares, para std::vector s cuyos tamaños necesarios son desconocidos pero tienen un límite superior razonablemente pequeño, ¿es rentable reemplazarlos con matrices asignadas estáticamente?
Descubrí que la asignación dinámica de memoria suele ser un cuello de botella grave y que su eliminación puede generar aceleraciones significativas. Como consecuencia, soy interesante en las compensaciones de rendimiento de devolver grandes estructuras temporales de datos por valor versus devolver por puntero vs. pasar el resultado por referencia. ¿Hay alguna manera de determinar de manera confiable si el compilador usará o no el RVO para un método dado (suponiendo que el llamante no necesita modificar el resultado, por supuesto)?
¿Cuán conscientes son los compiladores de la caché? Por ejemplo, ¿vale la pena buscar reordenamiento de bucles anidados?
Dada la naturaleza científica del programa, los números de coma flotante se usan en todas partes. Un cuello de botella significativo en mi código solía ser conversiones de coma flotante a enteros: el compilador emitiría código para guardar el modo de redondeo actual, lo cambiaría, realizaría la conversión y luego restablecería el antiguo modo de redondeo, aunque no haya nada en el programa ¡alguna vez cambió el modo de redondeo! Deshabilitar este comportamiento aceleró significativamente mi código. ¿Hay algún problema similar relacionado con los puntos flotantes que deba tener en cuenta?
Una consecuencia de que C ++ se compile y vincule por separado es que el compilador no puede hacer lo que parecerían ser optimizaciones muy simples, como mover las llamadas a métodos como strlen () fuera de las condiciones de terminación del ciclo. ¿Hay alguna optimización como esta que deba tener en cuenta porque el compilador no puede hacerla y debe hacerse a mano?
Por otro lado, ¿hay alguna técnica que deba evitar porque es probable que interfiera con la capacidad del compilador de optimizar automáticamente el código?

Por último, para cortar ciertos tipos de respuestas de raíz:

Entiendo que la optimización tiene un costo en términos de complejidad, confiabilidad y capacidad de mantenimiento. Para esta aplicación en particular, un mayor rendimiento vale estos costos.
Entiendo que las mejores optimizaciones a menudo son para mejorar los algoritmos de alto nivel, y esto ya se ha hecho.

¿Hay algún beneficio en reemplazar los contenedores / algoritmos STL por los enrollados a mano? En particular, mi programa incluye una cola de prioridad muy grande (actualmente una std :: priority_queue) cuya manipulación toma mucho tiempo total. ¿Es esto algo que vale la pena investigar, o la implementación de STL ya es probablemente la más rápida posible?

El STL es generalmente el caso general más rápido. Si tiene un caso muy específico, es posible que vea una aceleración con una mano enrollada. Por ejemplo, std :: sort (normalmente quicksort) es el tipo general más rápido, pero si sabes de antemano que tus elementos ya están prácticamente ordenados, entonces la ordenación por inserción podría ser una mejor opción.

De forma similar, para los std :: vectores cuyos tamaños necesarios son desconocidos pero tienen un límite superior razonablemente pequeño, ¿es rentable reemplazarlos con matrices asignadas estáticamente?

Esto depende de dónde va a hacer la asignación estática. Una cosa que intenté a lo largo de esta línea fue asignar de forma estática una gran cantidad de memoria en la pila, y luego volver a usarla más tarde. Resultados? La memoria del montón fue sustancialmente más rápida. El hecho de que un elemento esté en la pila no hace que sea más rápido acceder a él; la velocidad de la memoria de la pila también depende de elementos como la memoria caché. Un conjunto global estáticamente asignado no puede ser más rápido que el montón. Supongo que ya has probado técnicas como reservar el límite superior. Si tiene muchos vectores que tienen el mismo límite superior, considere mejorar la memoria caché mediante un vector de estructuras, que contienen los miembros de datos.

I''ve found that dynamic memory allocation is often a severe bottleneck, and that eliminating it can lead to significant speedups. As a consequence I''m interesting in the performance tradeoffs of returning large temporary data structures by value vs. returning by pointer vs. passing the result in by reference. Is there a way to reliably determine whether or not the compiler will use RVO for a given method (assuming the caller doesn''t need to modify the result, of course)?

I personally normally pass the result in by reference in this scenario. It allows for a lot more re-use. Passing large data structures by value and hoping that the compiler uses RVO is not a good idea when you can just manually use RVO yourself.

How cache-aware do compilers tend to be? For example, is it worth looking into reordering nested loops?

I found that they weren''t particularly cache-aware. The issue is that the compiler doesn''t understand your program and can''t predict the vast majority of it''s state, especially if you depend heavily on heap. If you have a profiler that ships with your compiler, for example Visual Studio''s Profile Guided Optimization, then this can produce excellent speedups.

Given the scientific nature of the program, floating-point numbers are used everywhere. A significant bottleneck in my code used to be conversions from floating point to integers: the compiler would emit code to save the current rounding mode, change it, perform the conversion, then restore the old rounding mode --- even though nothing in the program ever changed the rounding mode! Disabling this behavior significantly sped up my code. Are there any similar floating-point-related gotchas I should be aware of?

There are different floating-point models - Visual Studio gives an fp:fast compiler setting. As for the exact effects of doing such, I can''t be certain. However, you could try altering the floating point precision or other settings in your compiler and checking the result.

One consequence of C++ being compiled and linked separately is that the compiler is unable to do what would seem to be very simple optimizations, such as move method calls like strlen() out of the termination conditions of loop. Are there any optimization like this one that I should look out for because they can''t be done by the compiler and must be done by hand?

I''ve never come across such a scenario. However, if you''re genuinely concerned about such, then the option remains to do it manually. One of the things that you could try is calling a function on a const reference, suggesting to the compiler that the value won''t change.

One of the other things that I want to point out is the use of non-standard extensions to the compiler, for example provided by Visual Studio is __assume. http://msdn.microsoft.com/en-us/library/1b3fsfxw(VS.80).aspx

There''s also multithread, which I would expect you''ve gone down that road. You could try some specific opts, like another answer suggested SSE.

Edit: I realized that a lot of the suggestions I posted referenced Visual Studio directly. That''s true, but, GCC almost certainly provides alternatives to the majority of them. I just have personal experience with VS most.

¿Hay algún beneficio en reemplazar los contenedores / algoritmos STL por los enrollados a mano? En particular, mi programa incluye una cola de prioridad muy grande (actualmente una std :: priority_queue) cuya manipulación toma mucho tiempo total. ¿Es esto algo que vale la pena investigar, o la implementación de STL ya es probablemente la más rápida posible?

Supongo que sabe que los contenedores STL se basan en copiar los elementos. En ciertos casos, esto puede ser una pérdida significativa. Guarde los punteros y verá un aumento en el rendimiento si realiza una gran cantidad de manipulación de contenedores. Por otro lado, puede reducir la ubicación del caché y hacerte daño. Otra opción es usar asignadores especializados.

Ciertos contenedores (por ejemplo, map , set , list ) dependen de mucha manipulación del puntero. Aunque contra intuitivo, a menudo puede conducir a un código más rápido para reemplazarlos por vector . El algoritmo resultante podría ir de O(1) u O(log n) a O(n) , pero debido a la localidad de memoria caché puede ser mucho más rápido en la práctica. Perfil para estar seguro.

Mencionaste que estás usando priority_queue , que me imagino que paga mucho por reorganizar los elementos, especialmente si son grandes. Puede intentar cambiar el contenedor subyacente (quizás deque o especializado). Casi seguro que almacenaré punteros, de nuevo, perfil para estar seguro.

A lo largo de líneas similares, para std :: vectores cuyos tamaños necesarios son desconocidos pero tienen un límite superior razonablemente pequeño, ¿es rentable reemplazarlos con matrices asignadas estáticamente?

Nuevamente, esto puede ayudar con una pequeña cantidad, dependiendo del caso de uso. Puede evitar la asignación de montón, pero solo si no necesita que su matriz sobreviva a la pila ... o podría reserve() el tamaño en el vector para que haya menos copia en la reasignación.

Descubrí que la asignación dinámica de memoria suele ser un cuello de botella grave y que su eliminación puede generar aceleraciones significativas. Como consecuencia, soy interesante en las compensaciones de rendimiento de devolver grandes estructuras temporales de datos por valor versus devolver por puntero vs. pasar el resultado por referencia. ¿Hay alguna manera de determinar de manera confiable si el compilador usará o no el RVO para un método dado (suponiendo que el llamante no necesita modificar el resultado, por supuesto)?

Puede ver el ensamblaje generado para ver si se aplica RVO, pero si devuelve puntero o referencia, puede estar seguro de que no hay copia. Si esto ayudará dependerá de lo que esté haciendo, por ejemplo, no puede devolver referencias a los temporales. Puede usar arenas para asignar y reutilizar objetos, para no pagar una penalización de montón grande.

¿Cuán conscientes son los compiladores de la caché? Por ejemplo, ¿vale la pena buscar reordenamiento de bucles anidados?

He visto aceleraciones dramáticas (seriamente dramáticas) en este ámbito. Vi más mejoras a partir de esto de lo que más tarde vi de multihilo de mi código. Las cosas pueden haber cambiado en los cinco años desde, solo una forma de estar seguros, de perfil.

Por otro lado, ¿hay alguna técnica que deba evitar porque es probable que interfiera con la capacidad del compilador de optimizar automáticamente el código?

Use explicit en sus constructores de argumento único. La construcción y destrucción temporal de objetos puede estar oculta en su código.
Tenga en cuenta las llamadas de constructor de copia oculta en objetos grandes. En algunos casos, considere reemplazar con punteros.
Perfil, perfil, perfil Ajuste las áreas que son cuellos de botella.

¿Hay algún beneficio en reemplazar los contenedores / algoritmos STL por los enrollados a mano?

En general, no a menos que esté trabajando con una implementación deficiente. No reemplazaría un contenedor STL o algoritmo solo porque crees que puedes escribir un código más estricto. Lo haría solo si la versión de STL es más general de lo que debe ser para su problema. Si puede escribir una versión más simple que hace justo lo que necesita, entonces puede haber algo de velocidad para ganar allí.

Una excepción que he visto es reemplazar una std :: string de copy-on-write con una que no requiera sincronización de subprocesos.

para std :: vectores cuyos tamaños necesarios son desconocidos pero tienen un límite superior razonablemente pequeño, ¿es rentable reemplazarlos con matrices asignadas estáticamente?

Improbable. Pero si usa mucho tiempo asignando hasta cierto tamaño, puede ser rentable agregar una llamada a reserva ().

las compensaciones de rendimiento de la devolución de grandes estructuras de datos temporales por valor frente a la devolución por puntero frente a pasar el resultado por referencia.

Cuando trabajo con contenedores, paso iteradores para las entradas y un iterador de salida, que todavía es bastante general.

¿Cuán conscientes son los compiladores de la caché? Por ejemplo, ¿vale la pena buscar reordenamiento de bucles anidados?

No muy. Sí. Encuentro que las predicciones de bifurcación omitida y los patrones de acceso a la memoria hostil a la memoria caché son los dos principales factores de riesgo del rendimiento (una vez que has llegado a los algoritmos razonables). Muchos códigos antiguos usan pruebas de "salida anticipada" para reducir los cálculos. Pero en los procesadores modernos, eso suele ser más costoso que hacer las matemáticas e ignorar el resultado.

Un cuello de botella significativo en mi código solía ser conversiones de coma flotante a enteros

Sip. Recientemente descubrí el mismo problema.

Una consecuencia de que C ++ se compile y vincule por separado es que el compilador no puede hacer lo que parecerían ser optimizaciones muy simples, como mover las llamadas a métodos como strlen () fuera de las condiciones de terminación del ciclo.

Algunos compiladores pueden lidiar con esto. Visual C ++ tiene una opción de "generación de código de tiempo de enlace" que efectiva revoca el compilador para realizar más optimizaciones. Y, en el caso de funciones como strlen , muchos compiladores reconocerán eso como una función intrínseca.

¿Hay alguna optimización como esta que deba tener en cuenta porque el compilador no puede hacerla y debe hacerse a mano? Por otro lado, ¿hay alguna técnica que deba evitar porque es probable que interfiera con la capacidad del compilador de optimizar automáticamente el código?

Cuando optimiza en este nivel bajo, hay pocas reglas prácticas confiables. Los compiladores variarán. Mida su solución actual y decida si es demasiado lenta. Si es así, proponga una hipótesis (p. Ej., "¿Qué pasa si reemplazo las declaraciones if internas con una tabla de búsqueda?"). Podría ser útil ("elimina espacios debido a predicciones de bifurcaciones fallidas") o podría perjudicar ("el patrón de acceso de búsqueda daña la coherencia del caché"). Experimenta y mide incrementalmente.

A menudo clonaré la implementación directa y #ifdef HAND_OPTIMIZED un #ifdef HAND_OPTIMIZED / #ifdef HAND_OPTIMIZED / #endif para cambiar entre la versión de referencia y la versión modificada. Es útil para el posterior mantenimiento y validación del código. Me comprometo con cada experimento exitoso para cambiar el control y mantener un registro (hoja de cálculo) con el número de lista de cambios, los tiempos de ejecución y la explicación de cada paso de la optimización. A medida que aprendo más sobre cómo se comporta el código, el registro facilita la copia de seguridad y la bifurcación en otra dirección.

Necesita un marco para ejecutar pruebas de tiempo reproducibles y para comparar los resultados con la versión de referencia para asegurarse de no introducir errores inadvertidamente.

One consequence of C++ being compiled and linked separately is that the compiler is unable to do what would seem to be very simple optimizations, such as move method calls like strlen() out of the termination conditions of loop. Are there any optimization like this one that I should look out for because they can''t be done by the compiler and must be done by hand?

On some compilers this is incorrect. The compiler has perfect knowledge of all code across all translation units (including static libraries) and can optimize the code the same way it would do if it were in a single translation unit. A few ones that support this feature come to my mind:

Microsoft Visual C++ compilers
Intel C++ Compiler
LLVC-GCC
GCC (I think, not sure)

El uso de grupos de búferes de memoria puede tener un gran beneficio de rendimiento en comparación con la asignación dinámica. Más aún si reducen o evitan la fragmentación del montón en ejecuciones largas.
Tenga en cuenta la ubicación de los datos. Si tiene una mezcla significativa de datos locales y globales, puede estar trabajando demasiado en el mecanismo de caché. Intente mantener los conjuntos de datos muy cerca para aprovechar al máximo la validez de la línea de caché.
A pesar de que los compiladores hacen un trabajo maravilloso con bucles, todavía los examino cuando se ajusta el rendimiento. Puede detectar fallas arquitectónicas que producen órdenes de magnitud donde el compilador solo puede recortar porcentajes.
Si una cola de prioridad única está usando mucho tiempo en su operación, puede ser beneficioso crear una batería de colas que representen cubos de prioridad. En este caso, se negociaría la complejidad de la velocidad.
Noté que no mencionaste el uso de las instrucciones tipo SSE. ¿Podrían ser aplicables a su tipo de crujido de números?

La mejor de las suertes.

Acerca de los contenedores STL.

La mayoría de las personas aquí afirman que STL ofrece una de las implementaciones más rápidas posibles de los algoritmos de contenedor. Y digo lo contrario: para los escenarios más reales que toman los contenedores STL, se obtiene un rendimiento realmente catastrófico .

La gente discute sobre la complejidad de los algoritmos utilizados en STL. Aquí STL es bueno: O (1) para list / queue , vector (amortizado) y O (log (N)) para map . ¡Pero este no es el cuello de botella real del rendimiento de una aplicación típica! Para muchas aplicaciones, el verdadero cuello de botella son las operaciones de montón ( malloc / free , new / delete , etc.).

Una operación típica en la list cuesta solo unos pocos ciclos de CPU. En un map , algunas decenas pueden ser más (esto depende del estado de la memoria caché y del registro (N), por supuesto). Y las operaciones de montón típicas cuestan de cazadores a miles (!!!) de ciclos de CPU. Para aplicaciones multiproceso, por ejemplo, también requieren sincronización (operaciones entrelazadas). Además, en algunos sistemas operativos (como Windows XP), las funciones de almacenamiento dinámico se implementan completamente en el modo kernel.

De modo que el rendimiento real de los contenedores STL en un escenario típico está dominado por la cantidad de operaciones de almacenamiento dinámico que realizan. Y aquí son desastrosos. No porque se hayan implementado mal, sino por su diseño . Es decir, esta es la cuestión del diseño.

Por otro lado, hay otros contenedores que están diseñados de manera diferente. Una vez que he diseñado y escrito tales contenedores para mis propias necesidades:

http://www.codeproject.com/KB/recipes/Containers.aspx

Y resultó ser superior desde el punto de vista del rendimiento, y no solo.

Pero recientemente descubrí que no soy el único que pensaba en esto. boost::intrusive es la biblioteca de contenedores que se implementa de la manera similar a lo que hice entonces.

Sugiero que lo intentes (si no lo hiciste)

Aquí hay algunas cosas que había usado:

plantillas para especializar los límites de los bucles más internos (los hace realmente rápidos)
use __restrict__ palabras clave __restrict__ para los problemas de alias
reservar vectores de antemano a los valores por defecto.
evite usar el mapa (puede ser muy lento)
vector append / insert puede ser significativamente lento. Si ese es el caso, las operaciones sin procesar pueden hacerlo más rápido
Alineación de memoria de N-byte (Intel tiene pragma alineado, http://www.intel.com/software/products/compilers/docs/clin/main_cls/cref_cls/common/cppref_pragma_vector.htm )
tratando de mantener la memoria dentro de los cachés L1 / L2.
compilado con NDEBUG
perfil usando oprofilo, use opannotate para buscar líneas específicas (la tara stl es claramente visible en ese momento)

aquí hay partes de muestra de datos de perfil (para que sepa dónde buscar problemas)

* Output annotated source file with samples * Output all files * * CPU: Core 2, speed 1995 MHz (estimated) -- * Total samples for file : "/home/andrey/gamess/source/blas.f" * * 1020586 14.0896 -- * Total samples for file : "/home/andrey/libqc/rysq/src/fock.cpp" * * 962558 13.2885 -- * Total samples for file : "/usr/include/boost/numeric/ublas/detail/matrix_assign.hpp" * * 748150 10.3285 -- * Total samples for file : "/usr/include/boost/numeric/ublas/functional.hpp" * * 639714 8.8315 -- * Total samples for file : "/home/andrey/gamess/source/eigen.f" * * 429129 5.9243 -- * Total samples for file : "/usr/include/c++/4.3/bits/stl_algobase.h" * * 411725 5.6840 --

ejemplo de código de mi proyecto

template<int ni, int nj, int nk, int nl> inline void eval(const Data::density_type &D, const Data::fock_type &F, const double *__restrict Q, double scale) { const double * __restrict Dij = D[0]; ... double * __restrict Fij = F[0]; ... for (int l = 0, kl = 0, ijkl = 0; l < nl; ++l) { for (int k = 0; k < nk; ++k, ++kl) { for (int j = 0, ij = 0; j < nj; ++j, ++jk, ++jl) { for (int i = 0; i < ni; ++i, ++ij, ++ik, ++il, ++ijkl) {

Eche un vistazo a las excelentes diapositivas de Trampas de programación orientada a objetos para obtener información sobre el código de reestructuración para la localidad. En mi experiencia, obtener una mejor localidad es casi siempre la mayor ganancia.

Proceso general:

Aprenda a apreciar la Vista de desarmado en su depurador, o haga que su sistema de compilación genere los archivos de ensamblaje intermedio (.s) si es posible. Esté atento a los cambios o a las cosas que parecen atroces: incluso sin familiaridad con una determinada arquitectura de conjunto de instrucciones, ¡debería poder ver algunas cosas con bastante claridad! (A veces consulto una serie de archivos .s con los correspondientes cambios .cpp / .c, solo para aprovechar las maravillosas herramientas de mi SCM para ver cómo el código y el asm correspondiente cambian con el tiempo).
Obtenga un generador de perfiles que pueda ver los contadores de rendimiento de su CPU o, al menos, adivine las fallas de caché. (AMD CodeAnalyst, cachegrind, vTune, etc.)

Algunas otras cosas específicas:

Comprender el aliasing estricto. Una vez que lo haga, haga uso de restrict si su compilador lo tiene. (¡Examine el desastre aquí también!)
Echa un vistazo a los diferentes modos de coma flotante en tu procesador y compilador. Si no necesita el rango desnormalizado, elegir un modo sin esto puede dar como resultado un mejor rendimiento. (Parece que ya ha hecho algunas cosas en esta área, según su análisis de los modos de redondeo).
Definitivamente, evite allocs: call reserve en std::vector cuando pueda, o use std::array cuando conozca el tamaño en tiempo de compilación.
Use pools de memoria para aumentar la localidad y disminuir la sobrecarga alloc / free; también para garantizar la alineación de la línea de caché y evitar ping-ponging.
Use asignadores de marcos si está asignando elementos en patrones predecibles, y puede darse el lujo de desasignar todo de una vez.
Tenga en cuenta las invariantes . Algo que usted sabe que es invariante puede no serlo para el compilador, por ejemplo, un uso de una estructura o miembro de clase en un ciclo. Encuentro que la forma más sencilla de caer en el hábito correcto es dar un nombre a todo y preferir nombrar cosas fuera de los bucles. Por ejemplo, const int threshold = m_currentThreshold; o tal vez Thing * const pThing = pStructHoldingThing->pThing; Afortunadamente, normalmente puede ver cosas que necesitan este tratamiento en la vista de desmontaje. Esto también ayuda con la depuración más tarde (¡hace que la ventana watch / locals se comporte mucho mejor en compilaciones de depuración)!
Evitar escrituras en bucles si es posible: acumular primero, luego escribir o agrupar algunas escrituras. YMMV, por supuesto.

WRT su pregunta std::priority_queue : insertar cosas en un vector (el backend predeterminado para una priority_queue) tiende a mover una gran cantidad de elementos. Si puede dividirse en fases, donde inserta datos, luego ordene, y léalo una vez que esté ordenado, probablemente estará mucho mejor. Aunque definitivamente perderá la localidad, puede encontrar que una estructura más autoordenada como std :: map o std :: set vale la pena, pero esto depende realmente de sus patrones de uso.

Si estuviera trabajando en esto, esperaría una etapa final en la que cosas como la localización de caché y las operaciones vectoriales entren en juego.

Sin embargo, antes de llegar a la etapa final, esperaría encontrar una serie de problemas de diferentes tamaños que tienen menos que ver con la optimización del nivel de compilación, y más que ver con cosas extrañas que nunca podrían adivinarse, pero una vez encontradas, son simples de solucionar Por lo general, giran en torno al sobrediseño de clases y problemas de estructura de datos.

Aquí hay un ejemplo de este tipo de proceso.

He descubierto que las clases de contenedor generalizadas con iteradores, que en principio el compilador puede optimizar hasta ciclos mínimos, a menudo no están tan optimizados por algún motivo oscuro. También he escuchado otros casos en SO donde sucede esto.

Otros han dicho, antes de hacer cualquier otra cosa, perfil. Estoy de acuerdo con ese enfoque, excepto que creo que hay una mejor manera, y está indicado en ese enlace. Cada vez que me pregunto si algo específico, como STL, podría ser un problema, es posible que tenga razón , PERO, supongo. La idea ganadora fundamental en la optimización del rendimiento es averiguar , no adivinar. Es fácil averiguar con certeza qué se está tomando el tiempo, así que no adivine.

Y creo que la pista principal que cualquiera podría darle es: medir , medir , medir . Eso y mejorar tus algoritmos.
La forma en que utilizas ciertas características del lenguaje, la versión del compilador, la implementación de std lib, la plataforma, la máquina: todas desempeñan su papel en el rendimiento y no has mencionado muchas de ellas y ninguno de nosotros ha tenido tu configuración exacta.

En cuanto a reemplazar std::vector : use un reemplazo directo (por ejemplo, este ) y simplemente pruébelo.

Here hay un buen documento sobre el tema.

¿Hay algún beneficio en reemplazar los contenedores / algoritmos STL por los enrollados a mano?
Solo consideraría esto como una última opción. Los contenedores y algoritmos STL han sido probados exhaustivamente. Crear otros nuevos es costoso en términos de tiempo de desarrollo.

De forma similar, para los std :: vectores cuyos tamaños necesarios son desconocidos pero tienen un límite superior razonablemente pequeño, ¿es rentable reemplazarlos con matrices asignadas estáticamente?
Primero, intente reservar espacio para los vectores. Consulte el método std::vector::reserve . Un vector que sigue creciendo o cambiando a tamaños más grandes va a desperdiciar memoria dinámica y tiempo de ejecución. Agregue un código para determinar un buen valor para un límite superior.

Descubrí que la asignación dinámica de memoria suele ser un cuello de botella grave y que su eliminación puede generar aceleraciones significativas. Como consecuencia, soy interesante en las compensaciones de rendimiento de devolver grandes estructuras temporales de datos por valor versus devolver por puntero vs. pasar el resultado por referencia. ¿Hay alguna manera de determinar de manera confiable si el compilador usará o no el RVO para un método dado (suponiendo que el llamante no necesita modificar el resultado, por supuesto)?
Como una cuestión de principio, siempre pase estructuras grandes por referencia o puntero. Prefiere pasar por referencia constante. Si está utilizando punteros, considere usar punteros inteligentes.

¿Cuán conscientes son los compiladores de la caché? Por ejemplo, ¿vale la pena buscar reordenamiento de bucles anidados?
Los compiladores modernos son muy conscientes de las cachés de instrucciones (conductos) e intentan evitar que se vuelvan a cargar. Siempre puede ayudar a su compilador escribiendo código que utiliza menos ramas (desde if , switch , bucle constructs y llamadas a funciones ).

Puede ver un aumento de rendimiento más significativo al ajustar su programa para optimizar la caché de datos . Busque en la web Diseño basado en datos . Hay muchos excelentes artículos sobre este tema.

Dada la naturaleza científica del programa, los números de coma flotante se usan en todas partes. Un cuello de botella significativo en mi código solía ser conversiones de coma flotante a enteros: el compilador emitiría código para guardar el modo de redondeo actual, lo cambiaría, realizaría la conversión y luego restablecería el antiguo modo de redondeo, aunque no haya nada en el programa ¡alguna vez cambió el modo de redondeo! Deshabilitar este comportamiento aceleró significativamente mi código. ¿Hay algún problema similar relacionado con los puntos flotantes que deba tener en cuenta?
Para mayor precisión, mantenga todo como un double . Ajuste para redondear solo cuando sea necesario y quizás antes de mostrar. Esto cae dentro de la regla de optimización, Usa menos código, elimina el código extraño o de madera muerta .

Consulte también la sección anterior sobre cómo reservar espacio en contenedores antes de usarlos.

Algunos procesadores pueden cargar y almacenar números de coma flotante más rápido o tan rápido como números enteros. Esto requeriría recopilar datos de perfil antes de optimizar. Sin embargo, si sabes que hay una resolución mínima, puedes usar enteros y cambiar tu base a esa resolución mínima. Por ejemplo, cuando se trata de dinero estadounidense, los enteros pueden usarse para representar 1/100 o 1/1000 de un dólar.

Una consecuencia de que C ++ se compile y vincule por separado es que el compilador no puede hacer lo que parecerían ser optimizaciones muy simples, como mover las llamadas a métodos como strlen () fuera de las condiciones de terminación del ciclo. ¿Hay alguna optimización como esta que deba tener en cuenta porque el compilador no puede hacerla y debe hacerse a mano?
Esta es una suposición incorrecta. Los compiladores pueden optimizar en función de la firma de la función, especialmente si los parámetros usan correctamente const . Siempre me gusta ayudar al compilador moviendo cosas constantes fuera del ciclo. Para un valor límite superior, como una longitud de cadena, asígnelo a una variable const antes del ciclo. El modificador const ayudará al Optimizer.

Siempre existe la optimización de cuenta regresiva en bucles. Para muchos procesadores, un salto en el registro igual a cero es más eficiente que comparar y saltar si es menor que .

Por otro lado, ¿hay alguna técnica que deba evitar porque es probable que interfiera con la capacidad del compilador de optimizar automáticamente el código?
Evitaría las "micro optimizaciones". Si tiene alguna duda, imprima el código de ensamblado generado por el compilador (para el área que está cuestionando) en la configuración de optimización más alta. Intente volver a escribir el código para expresar el código de ensamblado del compilador. Optimiza este código, si puedes. Cualquier cosa más requiere instrucciones específicas de la plataforma.

Ideas y conceptos de optimización

1. Las computadoras prefieren ejecutar instrucciones secuenciales.
La ramificación los molesta. Algunos procesadores modernos tienen suficiente memoria caché de instrucciones para contener el código para pequeños bucles. En caso de duda, no provoques ramas.

2. Eliminar los requisitos
Menos código, más rendimiento.

3. Optimice los diseños antes del código Muchas veces, se puede obtener más rendimiento cambiando el diseño frente a cambiar la implementación del diseño. Menos diseño promueve menos código, genera más rendimiento.

4. Considere la organización de datos Optimice los datos.
Organice los campos usados frecuentemente en las substructures . Configure tamaños de datos para que quepan en una línea de caché de datos. Eliminar datos constantes de las estructuras de datos.
Use el especificador const tanto como sea posible.

5. Considere el intercambio de páginas. Los sistemas operativos cambiarán su programa o tarea por otro. Muchas veces en un ''archivo de intercambio'' en el disco duro. Descomponer el código en fragmentos que contienen código muy ejecutado y código menos ejecutado ayudará al sistema operativo. Además, coagula código muy usado en unidades más ajustadas. La idea es reducir el intercambio de código desde el disco duro (como recuperar funciones "lejanas"). Si el código debe ser intercambiado, debe ser como una unidad.

6. Considere optimizaciones de E / S (también incluye E / S de archivos).
La mayoría de E / S prefiere menos trozos de datos grandes a muchos fragmentos pequeños de datos. A los discos duros les gusta seguir girando. Los paquetes de datos más grandes tienen menos sobrecarga que los paquetes más pequeños.
Formatee los datos en un búfer y luego escriba el búfer.

7. Eliminar la competencia
Deshágase de cualquier programa y tarea que compita con su aplicación para los procesadores. Tareas como escanear virus y reproducir música. Incluso los controladores de E / S quieren una parte de la acción (razón por la cual desea reducir el número o las transacciones de E / S).

Esto debería mantenerte ocupado por un tiempo. :-)

Here is something that worked for me once. I can''t say that it will work for you. I had code on the lines of

switch(num) { case 1: result = f1(param); break; case 2: result = f2(param); break; //... }

Then I got a serious performance boost when I changed it to

// init: funcs[N] = {f1, f2 /*...*/}; // later in the code: result = (funcs[num])(param);

Perhaps someone here can explain the reason the latter version is better. I suppose it has something to do with the fact that there are no conditional branches there.

If you are doing heavy floating point math you should consider using SSE to vectorize your computations if that maps well to your problem.

Google SSE intrinsics for more information about this.

If you work on big matrices for instance, consider tiling your loops to improve the locality. This often leads to dramatic improvements. You can use VTune/PTU to monitor the L2 cache misses.

My current project is a media server, with multi thread processing (C++ language). It''s a time critical application, once low performance functions could cause bad results on media streaming like lost of sync, high latency, huge delays and so.

The strategy i usually use to grantee the best performance possible is to minimize the amount of heavy operational system calls that allocate or manage resources like memory, files, sockets and so.

At first i wrote my own STL, network and file manage classes.

All my containers classes ("MySTL") manage their own memory blocks to avoid multiple alloc (new) / free (delete) calls. The objects released are enqueued on a memory block pool to be reused when needed. On that way i improve performance and protect my code against memory fragmentation.

The parts of the code that need to access lower performance system resources (like files, databases, script, network write) i use separate threads for them. But not one thread for each unit (like not 1 thread for each socket), if so the operational system would lose performance while managing a high number of threads. So you can group objects of same classes to be processed on a separate thread if possible.

For example, if you have to write data to a network socket, but the socket write buffer is full, i save the data on a sendqueue buffer (which shares memory with all sockets together) to be sent on a separate thread as soon as the sockets become writeable again. At this way your main threads should never stop processing on a blocked state waiting for the operational system frees a specific resource. All the buffers released are saved and reused when needed.

After all a profile tool would be welcome to look for program bottles and shows which algorithms should be improved.

i got succeeded using that strategy once i have servers running like 500+ days on a linux machine without rebooting, with thousands users logging everyday.

[02:01] -alpha.ip.tv- Uptime: 525days 12hrs 43mins 7secs

The STL priority queue implementation is fairly well-optimized for what it does, but certain kinds of heaps have special properties that can improve your performance on certain algorithms. Fibonacci heaps are one example. Also, if you''re storing objects with a small key and a large amount of satellite data, you''ll get a major improvement in cache performance if you store that data separately, even if it means storing one extra pointer per object.

As for arrays, I''ve found std::vector to even slightly out-perform compile-time-constant arrays. That said, its optimizations are general, and specific knowledge of your algorithm''s access patterns may allow you to optimize further for cache locality, alignment, coloring, etc. If you find that your performance drops significantly past a certain threshold due to cache effects, hand-optimized arrays may move that problem size threshold by as much as a factor of two in some cases, but it''s unlikely to make a huge difference for small inner loops that fit easily within the cache, or large working sets that exceed the size of any CPU cache. Work on the priority queue first.

Most of the overhead of dynamic memory allocation is constant with respect to the size of the object being allocated. Allocating one large object and returning it by a pointer isn''t going to hurt much as much as copying it. The threshold for copying vs. dynamic allocation varies greatly between systems, but it should be fairly consistent within a chip generation.

Compilers are quite cache-aware when cpu-specific tuning is turned on, but they don''t know the size of the cache. If you''re optimizing for cache size, you may want to detect that or have the user specify it at run-time, since that will vary even between processors of the same generation.

As for floating point, you absolutely should be using SSE. This doesn''t necessarily require learning SSE yourself, as there are many libraries of highly-optimized SSE code that do all sorts of important scientific computing operations. If you''re compiling 64-bit code, the compiler might emit some SSE code automatically, as SSE2 is part of the x86_64 instruction set. SSE will also save you some of the overhead of x87 floating point, since it''s not converting back and forth to 80-bit values internally. Those conversions can also be a source of accuracy problems, since you can get different results from the same set of operations depending on how they get compiled, so it''s good to be rid of them.

i''m surprised no one has mentioned these two:

Link time optimization clang and g++ from 4.5 on support link time optimizations. I''ve heard that on g++ case, the heuristics is still pretty inmature but it should improve quickly since the main architecture is laid out.
Benefits range from inter procedural optimizations at object file level, including highly sought stuff like inling of virtual calls (devirtualization)
Project inlining this might seem to some like very crude approach, but it is that very crudeness which makes it so powerful: this amounts at dumping all your headers and .cpp files into a single, really big .cpp file and compile that; basically it will give you the same benefits of link-time optimization in your trip back to 1999. Of course, if your project is really big, you''ll still need a 2010 machine; this thing will eat your RAM like there is no tomorrow. However, even in that case, you can split it in more than one no-so-damn-huge .cpp file