En primer lugar, como han señalado el experto y Dan , la elaboración de perfiles es esencial. Personalmente uso el amplificador VTune de Intel en Linux, ya que me da una visión muy detallada de dónde se pasó el tiempo haciendo qué.
Si no va a cambiar el algoritmo (es decir, si no habrá cambios importantes que vuelvan obsoletas todas sus optimizaciones), le sugiero que busque algunos detalles de implementación comunes que puedan marcar una gran diferencia:
Localidad de la memoria : ¿los datos que se leen / usan juntos también se almacenan juntos, o estás recogiendo fragmentos aquí y allá?
Alineación de memoria : ¿están sus dobles realmente alineados a 4 bytes? ¿Cómo empacaste tu structs
? Para ser pedante, use en posix_memalign
lugar de malloc
.
Eficiencia de la memoria caché : la localidad se encarga de la mayoría de los problemas de eficiencia de la memoria caché, pero si tiene algunas estructuras de datos pequeñas que lee / escribe a menudo, ayuda si son un múltiplo entero o una fracción de una línea de memoria caché (generalmente 64 bytes). También ayuda si sus datos están alineados con el tamaño de una línea de caché. Esto puede reducir drásticamente la cantidad de lecturas necesarias para cargar una pieza de datos.
Vectorización : No, no te vuelvas loco con un ensamblador codificado a mano. gcc
ofrece tipos de vectores que se traducen a SSE / AltiVec / cualquier instrucción automáticamente.
Paralelismo a nivel de instrucción : el hijo bastardo de la vectorización. Si algunos cálculos repetidos a menudo no se vectorizan bien, puede intentar acumular valores de entrada y calcular varios valores a la vez. Es algo así como desenrollar el bucle. Lo que está explotando aquí es que su CPU generalmente tendrá más de una unidad de punto flotante por núcleo.
Precisión aritmética : ¿realmente necesita una aritmética de doble precisión en todo lo que hace? Por ejemplo, si está calculando una corrección en una iteración de Newton, generalmente no necesita todos los dígitos que está calculando. Para una discusión más profunda, vea este documento.
Algunos de estos trucos se usan en daxpy_cvec
este hilo. Dicho esto, si estás usando Fortran (no es un lenguaje de bajo nivel en mis libros), tendrás muy poco control sobre la mayoría de estos "trucos".
Si está ejecutando en un hardware dedicado, por ejemplo, un clúster que utiliza para todas sus ejecuciones de producción, es posible que también desee leer los detalles de las CPU utilizadas. No es que debas escribir cosas en ensamblador directamente para esa arquitectura, pero puede inspirarte a encontrar algunas otras optimizaciones que quizás te hayas perdido. Conocer una característica es un primer paso necesario para escribir código que pueda explotarla.
Actualizar
Ha pasado un tiempo desde que escribí esto y no me había dado cuenta de que se había convertido en una respuesta tan popular. Por esta razón, me gustaría agregar un punto importante:
- Hable con su informático local : ¿no sería genial si hubiera una disciplina que se ocupara exclusivamente de hacer que los algoritmos y / o los cálculos fueran más eficientes / elegantes / paralelos, y todos pudiéramos pedirles consejo? Bueno, buenas noticias, esa disciplina existe: la informática. Lo más probable es que su institución tenga un departamento completo dedicado a ello. Habla con estos chicos.
Estoy seguro de que varios científicos no informáticos traerán recuerdos de discusiones frustrantes con dicha disciplina que no condujeron a nada, o recuerdos de las anécdotas de otras personas. No te desanimes. La colaboración interdisciplinaria es algo complicado, y requiere un poco de trabajo, pero las recompensas pueden ser enormes.
En mi experiencia, como informático (CS), el truco está en lograr las expectativas y la comunicación correctas.
Expectativa : un CS solo lo ayudará si él / ella piensa que su problema es interesante. Esto prácticamente excluye intentar optimizar / vectorizar / paralelizar un fragmento de código que ha escrito, pero que en realidad no ha comentado, por un problema que no entienden. Los CS suelen estar más interesados en el problema subyacente, por ejemplo, los algoritmos utilizados para resolverlo. No les des tu solución , dales tu problema .
Además, prepárese para que el CS diga " este problema ya se ha resuelto ", y solo le dé una referencia a un documento. Un consejo: lea ese documento y, si realmente se aplica a su problema, implemente el algoritmo que sugiera. No se trata de una CS presumida, es una CS que simplemente te ayudó. No se ofenda, recuerde: si el problema no es computacionalmente interesante, es decir, ya se ha resuelto y la solución se muestra óptima, no funcionarán, y mucho menos lo codificarán.
Comunicación : recuerde que la mayoría de los CS no son expertos en su campo y explique el problema en términos de lo que está haciendo, en lugar de cómo y por qué . Por lo general, realmente no nos importa el por qué y el cómo es, bueno, lo que hacemos mejor.
Por ejemplo, actualmente estoy trabajando con un grupo de Cosmólogos Computacionales para escribir una mejor versión de su código de simulación, basado en SPH y Multipoles . Tomó cerca de tres reuniones dejar de hablar en términos de materia oscura y halo de galaxias (¿eh?) Y profundizar en el núcleo del cálculo, es decir, que necesitan encontrar a todos los vecinos dentro de un radio determinado de cada partícula, calcular algunos cantidad sobre ellos, y luego atropellar a todos dichos vecinos nuevamente y aplicar esa cantidad en algún otro cálculo. Luego mueva las partículas, o al menos algunas de ellas, y vuelva a hacerlo todo. Verá, mientras que el primero puede ser increíblemente interesante (¡lo es!), El segundo es lo que necesito entender para comenzar a pensar en algoritmos.
Pero me estoy desviando del punto principal: si está realmente interesado en hacer que su cálculo sea rápido, y usted no es un informático, vaya a hablar con uno.
El software científico no es muy diferente de otro software, en cuanto a cómo saber qué necesita ajuste.
El método que uso es una pausa aleatoria . Estas son algunas de las aceleraciones que ha encontrado para mí:
Si se pasa una gran parte del tiempo en funciones como
log
yexp
, puedo ver cuáles son los argumentos de esas funciones, en función de los puntos desde los que se les llama. A menudo se les llama repetidamente con el mismo argumento. Si es así, la memorización produce un factor de aceleración masiva.Si estoy usando las funciones BLAS o LAPACK, puedo encontrar que se gasta una gran parte del tiempo en rutinas para copiar matrices, multiplicar matrices, transformar Choleski, etc.
La rutina para copiar matrices no está ahí por la velocidad, está ahí por conveniencia. Puede encontrar que hay una manera menos conveniente, pero más rápida, de hacerlo.
Las rutinas para multiplicar o invertir matrices, o tomar transformaciones choleski, tienden a tener argumentos de caracteres que especifican opciones, como 'U' o 'L' para el triángulo superior o inferior. Nuevamente, esos están ahí por conveniencia. Lo que encontré fue que, dado que mis matrices no eran muy grandes, las rutinas pasaban más de la mitad de su tiempo llamando a la subrutina para comparar caracteres solo para descifrar las opciones. Escribir versiones para propósitos especiales de las rutinas matemáticas más costosas produjo una aceleración masiva.
Si solo puedo ampliar el último: la rutina de matriz de multiplicación DGEMM llama a LSAME para decodificar sus argumentos de caracteres. Si se analiza el porcentaje de tiempo inclusivo (la única estadística que vale la pena mirar), los perfiladores considerados "buenos" podrían mostrar que DGEMM usa un porcentaje del tiempo total, como el 80%, y LSAME usa un porcentaje del tiempo total, como el 50%. Mirando lo primero, te sentirías tentado a decir "bueno, debe estar muy optimizado, así que no puedo hacer mucho al respecto". Mirando lo último, te sentirías tentado a decir "¿Eh? ¿De qué se trata todo eso? Es solo una pequeña rutina. ¡Este perfilador debe estar equivocado!"
No está mal, simplemente no te dice lo que necesitas saber. Lo que muestra una pausa aleatoria es que DGEMM está en el 80% de las muestras de pila y LSAME está en el 50%. (No necesita muchas muestras para detectar eso. 10 generalmente es suficiente.) Además, en muchas de esas muestras, DGEMM está en el proceso de llamar a LSAME desde un par de líneas de código diferentes.
Así que ahora sabes por qué ambas rutinas están tomando tanto tiempo inclusivo. También sabe de qué parte de su código están siendo llamados para pasar todo este tiempo. Es por eso que uso pausas aleatorias y tomo una visión icónica de los perfiladores, sin importar qué tan bien estén. Están más interesados en obtener mediciones que en contarle lo que está sucediendo.
Es fácil suponer que las rutinas de la biblioteca matemática se han optimizado en el enésimo grado, pero de hecho se han optimizado para ser utilizables para una amplia gama de propósitos. Necesita ver lo que realmente está sucediendo, no lo que es fácil de asumir.
AGREGADO: Entonces, para responder sus dos últimas preguntas:
Tome 10-20 muestras de pila, y no solo las resuma, entienda lo que cada una le está diciendo. Haga esto primero, último y en el medio. (No hay "intento", joven Skywalker).
Como te he señalado antes, puedes repetir todo el procedimiento hasta que no puedas más, y la relación de aceleración compuesta puede ser bastante grande.
Considere si tomamos hasta 40 muestras (más de las que he tenido al mismo tiempo) y solo vimos un problema en dos de ellas. El costo estimado (modo) de ese problema es del 5%, como se muestra en la curva más alta.
¿Qué es un "falso positivo"? Es que si soluciona un problema, se da cuenta de una ganancia tan pequeña de lo esperado, que lamenta haberlo solucionado. Las curvas muestran (si el problema es "pequeño") que, si bien la ganancia podría ser menor que la fracción de las muestras que lo muestran, en promedio será mayor.
Existe un riesgo mucho más grave: un "falso negativo". Eso es cuando hay un problema, pero no se encuentra. (Esto contribuye al "sesgo de confirmación", donde la ausencia de evidencia tiende a tratarse como evidencia de ausencia).
Lo que obtienes con un generador de perfiles (uno bueno) es que obtienes una medición mucho más precisa (por lo tanto, menos posibilidades de falsos positivos), a expensas de una información mucho menos precisa sobre cuál es realmente el problema (por lo tanto, menos posibilidades de encontrarlo y obtener cualquier ganancia). Eso limita la aceleración general que se puede lograr.
Animaría a los usuarios de los perfiladores a informar los factores de aceleración que realmente obtienen en la práctica.
Hay otro punto para hacerse re. La pregunta de Pedro sobre falsos positivos.
Mencionó que podría haber una dificultad para resolver problemas pequeños en un código altamente optimizado. (Para mí, un pequeño problema es uno que representa el 5% o menos del tiempo total).
Dado que es completamente posible construir un programa que sea totalmente óptimo, excepto el 5%, este punto solo puede abordarse empíricamente, como en esta respuesta . Para generalizar a partir de la experiencia empírica, es así:
Un programa, tal como está escrito, generalmente contiene varias oportunidades para la optimización. (Podemos llamarlos "problemas", pero a menudo son un código perfectamente bueno, simplemente capaces de una mejora considerable). Este diagrama ilustra un programa artificial que tarda cierto tiempo (por ejemplo, 100 s) y contiene los problemas A, B, C, ... que, cuando se encuentra y repara, ahorra 30%, 21%, etc. de los 100 originales.
Observe que el problema F cuesta el 5% del tiempo original, por lo que es "pequeño" y difícil de encontrar sin 40 o más muestras.
Sin embargo, las primeras 10 muestras encuentran fácilmente el problema A. ** Cuando eso se arregla, el programa solo toma 70 segundos, para una aceleración de 100/70 = 1.43x. Eso no solo hace que el programa sea más rápido, sino que aumenta, en esa proporción, los porcentajes tomados por los problemas restantes. Por ejemplo, el problema B originalmente tomó 21 segundos, que era el 21% del total, pero después de eliminar A, B toma 21 de 70, o 30%, por lo que es más fácil de encontrar cuando se repite todo el proceso.
Una vez que el proceso se repite cinco veces, ahora el tiempo de ejecución es de 16,8 segundos, de los cuales el problema F es del 30%, no del 5%, por lo que 10 muestras lo encuentran fácilmente.
Entonces ese es el punto. Empíricamente, los programas contienen una serie de problemas que tienen una distribución de tamaños, y cualquier problema encontrado y solucionado hace que sea más fácil encontrar los restantes. Para lograr esto, ninguno de los problemas se puede omitir porque, si lo están, se sientan allí tomando tiempo, limitando la aceleración total y sin poder magnificar los problemas restantes. Por eso es muy importante encontrar los problemas que se esconden .
Si se encuentran y solucionan los problemas A a F, la aceleración es 100 / 11.8 = 8.5x. Si se pierde uno de ellos, por ejemplo D, entonces la aceleración es solo 100 / (11.8 + 10.3) = 4.5x. Ese es el precio pagado por los falsos negativos.
Entonces, cuando el generador de perfiles dice "no parece haber ningún problema significativo aquí" (es decir, buen codificador, este es un código prácticamente óptimo), tal vez sea correcto, y tal vez no lo sea. (Un falso negativo .) No sabe con certeza si hay más problemas que solucionar, para una mayor velocidad, a menos que pruebe con otro método de creación de perfiles y descubra que los hay. En mi experiencia, el método de creación de perfiles no necesita una gran cantidad de muestras, resumidas, sino una pequeña cantidad de muestras, donde cada muestra se entiende lo suficiente como para reconocer cualquier oportunidad de optimización.
1 - pbinom(1, numberOfSamples, sizeOfProblem)
1 - pbinom(1, 20, 0.3) = 0.9923627
Este es un gráfico de la distribución de los factores de aceleración y sus medias para 2 aciertos de 5, 4, 3 y 2 muestras. Por ejemplo, si se toman 3 muestras, y 2 de ellas son coincidencias con un problema, y ese problema puede eliminarse, el factor de aceleración promedio sería 4x. Si se ven los 2 aciertos en solo 2 muestras, la aceleración promedio no está definida, ¡conceptualmente porque existen programas con bucles infinitos con probabilidad distinta de cero!
fuente
No solo tiene que tener un conocimiento íntimo de su compilador , también tiene un conocimiento íntimo de su arquitectura de destino y sistema operativo de .
¿Qué puede afectar el rendimiento?
Si desea exprimir hasta la última gota de rendimiento, cada vez que cambie su arquitectura de destino, tendrá que ajustar y volver a optimizar su código. Algo que fue una optimización con una CPU puede volverse subóptimo en la próxima revisión de esa misma CPU.
Un excelente ejemplo de esto sería el caché de la CPU. Mueva su programa de una CPU con un caché pequeño y rápido a uno con un poco más lento, ligeramente mayor caché y su perfilado podría cambiar significativamente.
Incluso si la arquitectura de destino no cambia, los cambios de bajo nivel en un sistema operativo también pueden afectar el rendimiento. Los parches de mitigación Spectre y Meltdown tuvieron un gran impacto en algunas cargas de trabajo, por lo que podrían forzar una reevaluación de sus optimizaciones.
¿Cómo puedo mantener mi código optimizado?
Al desarrollar código altamente optimizado, debe mantenerlo modular y facilitar el intercambio de diferentes versiones del mismo algoritmo, posiblemente incluso seleccionando la versión específica utilizada en tiempo de ejecución, dependiendo de los recursos disponibles y el tamaño / complejidad de datos a procesar.
La modularidad también significa poder usar el mismo conjunto de pruebas en todas sus versiones optimizadas y no optimizadas, lo que le permite verificar que todas se comporten igual y perfilar cada una rápidamente en una comparación de igual a igual . Entro en un poco más de detalle en mi respuesta a Cómo documentar y enseñar a otros código computacionalmente "optimizado más allá del reconocimiento"..
Otras lecturas
Además, recomendaría echar un vistazo al excelente artículo de Ulrich Drepper Lo que todo programador debería saber sobre la memoria , cuyo título es un homenaje a lo igualmente fantástico de David Goldberg Lo que todo informático debería saber sobre la aritmética de punto flotante .
Recuerde que cada optimización tiene el potencial de convertirse en una futura anti-optimización , por lo que debe considerarse un posible olor a código, que debe mantenerse al mínimo. Mi respuesta a ¿Es importante la microoptimización al codificar? proporciona un ejemplo concreto de esto desde la experiencia personal.
fuente
Creo que usted formula la pregunta demasiado estrictamente. En mi opinión, una actitud útil es vivir bajo la suposición de que solo los cambios en las estructuras de datos y los algoritmos pueden generar ganancias de rendimiento significativas en códigos que son más de unas pocas 100 líneas, y creo que todavía tengo que encontrar un contraejemplo para este reclamo
fuente
Lo primero que debe hacer es perfilar su código. Desea averiguar qué partes de su programa lo están ralentizando antes de comenzar a optimizar, de lo contrario podría terminar optimizando una parte de su código que de todos modos no consumía gran parte del tiempo de ejecución.
Linux
Apple OS X
fuente
En cuanto a la cantidad de rendimiento que puede obtener, tome los resultados del perfil de su código y supongamos que identifica una pieza que toma la fracción "p" del tiempo. Si tuviera que mejorar el rendimiento de esa pieza solo por un factor de "s", su aceleración general será 1 / ((1-p) + p / s). Por lo tanto, puede aumentar al máximo su velocidad en un factor de 1 / (1-p). Esperemos que tengas áreas de alta p! Este es el equivalente de la Ley de Amdahl para la optimización en serie.
fuente
La optimización de su código debe hacerse con cuidado. Supongamos también que ya ha depurado el código. Puede ahorrar mucho tiempo si sigue ciertas prioridades, a saber:
Utilice bibliotecas altamente optimizadas (u optimizadas profesionalmente) cuando sea posible. Algunos ejemplos pueden incluir las bibliotecas FFTW, OpenBlas, Intel MKL, NAG, etc. A menos que tenga un gran talento (como el desarrollador de GotoBLAS), probablemente no pueda vencer a los profesionales.
Use un generador de perfiles (ya se han nombrado algunos en la siguiente lista en este hilo: Intel Tune, valgrind, gprof, gcov, etc.) para averiguar qué partes de su código toman más tiempo. No tiene sentido perder el tiempo optimizando porciones de código que rara vez se llaman.
De los resultados del generador de perfiles, observe la parte de su código que tomó más tiempo. Determine cuál es la naturaleza de su algoritmo: ¿está vinculado a la CPU o a la memoria? Cada uno requiere un conjunto diferente de técnicas de optimización. Si tiene muchos errores de caché, la memoria podría ser el cuello de botella: la CPU está perdiendo ciclos de reloj esperando que la memoria esté disponible. Piense si el bucle encaja en el caché L1 / L2 / L3 de su sistema. Si tiene declaraciones "if" en su bucle, verifique si el generador de perfiles dice algo sobre la predicción errónea de la rama. ¿Cuál es la penalización de predicción errónea de la rama de su sistema? Por cierto, puede obtener datos de predicción errónea de sucursales de los manuales de referencia de optimización de Intel [1]. Tenga en cuenta que la penalización de predicción errónea de la rama es específica del procesador, como verá en el manual de Intel.
Por último, aborde los problemas identificados por el generador de perfiles. Una serie de técnicas ya se han discutido aquí. También hay disponibles varios recursos buenos, confiables e integrales sobre optimización. Por nombrar solo dos, está el Manual de referencia de optimización de Intel [1] y los cinco manuales de optimización de Agner Fog [2]. Tenga en cuenta que hay algunas cosas que quizás no necesite hacer, si el compilador ya lo hace, por ejemplo, desenrollar bucles, alinear memoria, etc. Lea cuidadosamente la documentación del compilador.
Referencias
[1] Manual de referencia de optimización de arquitecturas Intel 64 e IA-32: http://www.intel.sg/content/dam/doc/manual/64-ia-32-architectures-optimization-manual.pdf
[2] Agner Fog, "Recursos de optimización de software": http://www.agner.org/optimize/
fuente
No soy un científico computacional como muchos otros aquí (así que podría estar equivocado :)) pero en estos días no tiene mucho sentido gastar demasiado tiempo en el rendimiento en serie siempre que usemos libs estándar. Podría valer más la pena dedicar tiempo / esfuerzo adicional para hacer que el código sea más escalable.
En cualquier caso, aquí hay dos ejemplos (si aún no los ha leído) sobre cómo se mejoró el rendimiento (para problemas FE no estructurados).
Serie : Vea la segunda mitad del resumen y el texto relacionado.
Paralelo : Especialmente la fase de inicialización, en la sección 4.2.
fuente
Esto es quizás más una meta-respuesta que una respuesta ...
Debe desarrollar una familiaridad íntima con su compilador. Puede adquirir esto más eficientemente leyendo el manual y experimentando con las opciones.
Gran parte de los buenos consejos que dispensa @Pedro se pueden implementar ajustando la compilación en lugar del programa.
fuente
Una manera fácil de perfilar un programa (en Linux) es usarlo
perf
enstat
modo. La forma más sencilla es simplemente ejecutarlo comoy le dará un montón de estadísticas útiles de rendimiento:
A veces también enumerará las cargas y fallas de D-cache. Si ve muchos errores de caché, entonces su programa requiere mucha memoria y no trata bien los cachés. En estos días, las CPU son cada vez más rápidas que el ancho de banda de la memoria, y generalmente el problema siempre es el acceso a la memoria.
También puede probar
perf record ./my_program; perf report
cuál es una forma fácil de perfilar. Lea las páginas del manual para obtener más información.fuente