¿Cuáles son algunas buenas estrategias para mejorar el rendimiento en serie de mi código?

66

Trabajo en ciencias computacionales y, como resultado, paso una cantidad no trivial de mi tiempo tratando de aumentar el rendimiento científico de muchos códigos, así como de comprender la eficiencia de estos códigos.

Supongamos que he evaluado el rendimiento en comparación con la legibilidad / reutilización / mantenibilidad del software en el que estoy trabajando, y he decidido que es hora de ir por el rendimiento. Supongamos también que sé que no tengo un mejor algoritmo para mi problema (en términos de flop / sy ancho de banda de memoria). También puede suponer que mi código base está en un lenguaje de bajo nivel como C, C ++ o Fortran. Finalmente, supongamos que no hay paralelismo en el código, o que solo estamos interesados ​​en el rendimiento en un solo núcleo.

¿Cuáles son las cosas más importantes para probar primero? ¿Cómo sé cuánto rendimiento puedo obtener?

Aron Ahmadia
fuente

Respuestas:

66

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_memalignlugar 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. gccofrece 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.

Pedro
fuente
44
A medida que avanzan las herramientas de creación de perfiles, no me olvidaría de Valgrind .
GertVdE
1
Estoy de acuerdo contigo Pedro, cuando el programa que se está optimizando es como un auto de carreras de F1, casi óptimo. Los programas que veo en la práctica, científicos y no, a menudo se parecen más a Cadillac Coupe DeVilles. Para obtener un rendimiento real, se pueden cortar toneladas de grasa. Después de eso, el ciclo de afeitado comienza a acelerarse.
Mike Dunlavey
1
@MikeDunlavey: completamente de acuerdo. Agregué una actualización a mi respuesta para abordar más problemas relacionados algorítmicamente.
Pedro
1
@MikeDunlavey, soy CS folk :)
Pedro
2
Lo demostré en una charla en U Mass. Lowell. Fue una demostración en vivo, que muestra todas las etapas de la aceleración 730x. Creo que un profesor entendió el punto, de media docena.
Mike Dunlavey
38

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 logy exp, 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:

¿Cuáles son las cosas más importantes para probar primero?

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).

¿Cómo sé cuánto rendimiento puedo obtener?

xβ(s+1,(ns)+1)sn1/(1x)n=10s=5x
ingrese la descripción de la imagen aquí
xx

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.

(s+1)/(n+2)=3/22=13.6%.) La curva inferior en el siguiente gráfico es su distribución:

ingrese la descripción de la imagen aquí

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.

ingrese la descripción de la imagen aquí

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.

2/0.3=6.671 - pbinom(1, numberOfSamples, sizeOfProblem)1 - pbinom(1, 20, 0.3) = 0.9923627

xβ(s+1,(ns)+1)nsy1/(1x)xyy1Distribución BetaPrime . Lo simulé con 2 millones de muestras, llegando a este comportamiento:

         distribution of speedup
               ratio y

 s, n    5%-ile  95%-ile  mean
 2, 2    1.58    59.30   32.36
 2, 3    1.33    10.25    4.00
 2, 4    1.23     5.28    2.50
 2, 5    1.18     3.69    2.00
 2,10    1.09     1.89    1.37
 2,20    1.04     1.37    1.17
 2,40    1.02     1.17    1.08

 3, 3    1.90    78.34   42.94
 3, 4    1.52    13.10    5.00
 3, 5    1.37     6.53    3.00
 3,10    1.16     2.29    1.57
 3,20    1.07     1.49    1.24
 3,40    1.04     1.22    1.11

 4, 4    2.22    98.02   52.36
 4, 5    1.72    15.95    6.00
 4,10    1.25     2.86    1.83
 4,20    1.11     1.62    1.31
 4,40    1.05     1.26    1.14

 5, 5    2.54   117.27   64.29
 5,10    1.37     3.69    2.20
 5,20    1.15     1.78    1.40
 5,40    1.07     1.31    1.17

(n+1)/(ns)s=ny

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!

ingrese la descripción de la imagen aquí

Mike Dunlavey
fuente
1
Uhm ... ¿No obtiene exactamente esta información mirando gráficos de llamadas de perfil o resúmenes de tipo "de abajo hacia arriba" según lo provisto por VTune?
Pedro
2
@Pedro: Si solo. En una muestra de pila (y variables relacionadas) se codifica la razón completa por la que se gasta el incremento de tiempo. No puede deshacerse de él a menos que sepa por qué se está gastando. Se pueden encontrar algunos problemas con información limitada, pero no todos . Si solo obtienes algunos de ellos, pero no todos, entonces los problemas que no obtienes terminan bloqueándote de nuevas aceleraciones. Mira aquí y aquí .
Mike Dunlavey
Podría decirse que está comparando su método con un mal perfil ... También podría revisar el perfil de cada rutina, independientemente de su contribución al tiempo total de ejecución, y buscar mejoras, con el mismo efecto. Lo que me preocupa en su enfoque es el creciente número de falsos positivos que terminará rastreando a medida que los "puntos críticos" en su código se vuelven cada vez más pequeños.
Pedro
@Pedro: solo sigue tomando muestras hasta que veas algo que puedas arreglar en más de una muestra. La distribución beta le dice cuánto puede ahorrar, si le importa, pero si tiene miedo de obtener menos velocidad de la que muestra, tenga en cuenta que está descartando la posibilidad de que también pueda ser más (y está sesgado a la derecha) ) El mayor peligro, con resumir perfiladores, son falsos negativos . Puede haber un problema, pero solo espera que su intuición lo detecte cuando el generador de perfiles no sea muy específico sobre dónde podría estar.
Mike Dunlavey
@Pedro: La única debilidad que conozco es cuando, al mirar una instantánea, no se puede entender por qué se está gastando ese tiempo, como si se trata simplemente de procesar eventos asíncronos donde se oculta el solicitante o protocolos asincrónicos. Para obtener un código más "normal", muéstrame un "buen" generador de perfiles y te mostraré un problema con el que tiene problemas o que simplemente no puede encontrar (haciéndote caer de nuevo en tu inteligencia falible). En general, la forma de construir un problema de este tipo es asegurarse de que el propósito que se está cumpliendo no pueda descifrarse localmente. Y tales problemas abundan en el software.
Mike Dunlavey
23

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.

Mark Booth
fuente
8

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

Wolfgang Bangerth
fuente
3
De acuerdo en principio, pero no se debe subestimar la interacción entre el rendimiento de un algoritmo / estructura de datos y los detalles del hardware subyacente. Por ejemplo, los árboles binarios balanceados son excelentes para buscar / almacenar datos, pero dependiendo de la latencia de la memoria global, una tabla hash puede ser mejor.
Pedro
1
Convenido. Los algoritmos y la estructura de datos pueden proporcionar mejoras de O (10) a O (100). Sin embargo, para algunos problemas informáticos limitados (como en los cálculos de dinámica molecular, astrofísica, procesamiento de imágenes y video en tiempo real, finanzas) un ciclo crítico altamente sintonizado puede significar un tiempo de ejecución general de la aplicación de 3x a 10x más rápido.
fcruz
He visto bucles anidados mal ordenados en códigos de "producción" de tamaño considerable. Aparte de eso, creo que tienes razón.
dmckee
8

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

gprof es bastante bueno, pero solo te dice cuánto tiempo tarda cada función en lugar de cada línea.

Apple OS X

Es posible que desee probar Shark . Está disponible en el sitio para desarrolladores de Apple en Descargas> Herramientas para desarrolladores> CHUD 4.6.2, la versión anterior aquí . CHUD también contiene otras herramientas de creación de perfiles, como la interfaz BigTop, la herramienta de búsqueda de índice PMC, el generador de perfiles de nivel de función de Saturno y muchos otros comandos. Shark vendrá con una versión de línea de comandos.

Dan
fuente
+1 perfil? Sí, en cierto modo ... Es mucho mejor que adivinar, pero aquí hay una lista de problemas que se aplican especialmente a gprof y a muchos otros perfiladores.
Mike Dunlavey
¿Es Shark un comando antiguo en OS X? Más aquí . Con Mountain Lion, ¿debo usar instrumentos?
hhh
@hhh: Era un generador de perfiles de GUI para Mac, aunque parece que ya no se mantiene. No he programado en una máquina Apple desde que escribí esta respuesta, así que no puedo ayudarte mucho.
Dan
1
Está disponible en el sitio para desarrolladores de Apple en Descargas> Herramientas para desarrolladores> CHUD 4.6.2. La versión anterior aquí y contiene todo tipo de perfiles: desafortunadamente esta instalación no se realiza correctamente: "Comuníquese con el fabricante", no tengo idea sobre el error. Shark fue sacado del Xcode aparentemente después de Lion y luego regresó al sitio Apple Dev después de ser una herramienta gratuita en MacUpdate.
hhh
@hhh: Pareces más calificado para responder esto que yo. Siéntase libre de editar mi respuesta para actualizarla, o escriba la suya.
Dan
7

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.

skillman
fuente
5

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:

  1. 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.

  2. 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.

  3. 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.

  4. 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/

  • "Optimización de software en C ++: una guía de optimización para plataformas Windows, Linux y Mac"
  • "Optimización de subrutinas en lenguaje ensamblador: una guía de optimización para plataformas x86"
  • "La microarquitectura de las CPU Intel, AMD y VIA: una guía de optimización para programadores de ensamblaje y fabricantes de compiladores"
  • "Tablas de instrucciones: listas de latencias de instrucciones, rendimientos y desgloses de microoperaciones para CPU Intel, AMD y VIA"
  • "Convenciones de llamadas para diferentes compiladores de C ++ y sistemas operativos"
nathanielng
fuente
3

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.

stali
fuente
3

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.

Marca de alto rendimiento
fuente
No estoy de acuerdo con el último punto. Saber lo que su compilador puede hacer es una cosa, pero escribir su código para que su compilador pueda hacer algo con él es un problema completamente diferente. No hay indicadores de compilación que clasifiquen sus datos por usted, use una precisión menor cuando sea necesario o reescriba sus bucles más internos de modo que tengan pocas o ninguna ramificación. Conocer su compilador es algo bueno, pero solo lo ayudará a escribir un mejor código, no mejorará su código per se.
Pedro
1

Una manera fácil de perfilar un programa (en Linux) es usarlo perfen statmodo. La forma más sencilla es simplemente ejecutarlo como

perf stat ./my_program args ...

y le dará un montón de estadísticas útiles de rendimiento:

Performance counter stats for './simd_test1':

     3884.559489 task-clock                #    1.000 CPUs utilized
              18 context-switches          #    0.005 K/sec
               0 cpu-migrations            #    0.000 K/sec
             383 page-faults               #    0.099 K/sec
  10,911,904,779 cycles                    #    2.809 GHz
 <not supported> stalled-cycles-frontend
 <not supported> stalled-cycles-backend
  14,346,983,161 instructions              #    1.31  insns per cycle
   2,143,017,630 branches                  #  551.676 M/sec
          28,892 branch-misses             #    0.00% of all branches

     3.885986246 seconds time elapsed

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 reportcuál es una forma fácil de perfilar. Lea las páginas del manual para obtener más información.

Mark Lakata
fuente