Código de optimización

Question

Le dan un montón de código en su idioma favorito que se combina para formar una aplicación bastante complicada. Se ejecuta con bastante lentitud, y su jefe le ha pedido que lo optimice. ¿Cuáles son los pasos que sigue para optimizar el código de manera más eficiente?

¿Qué estrategias ha encontrado que es infructuoso al optimizar el código?

Reescribe: ¿En qué momento decide dejar de optimizar y decir "Esto es lo más rápido posible sin una reescritura completa". ¿En qué casos recomendaría una simple reescritura completa de todos modos? ¿Cómo harías para diseñarlo?

Answer 1

Perfil antes de intentar cualquier optimización.

9 veces de cada 10, el tiempo no se consumirá donde pueda adivinarlo.

La estrategia habitual sin éxito es la micro-optimización, cuando lo que realmente se necesita es el algoritmo apropiado.

obligatorio Donald Knuth cita:

"Debemos olvidarnos de pequeñas eficiencias, por ejemplo alrededor del 97% del tiempo: la optimización prematura es la raíz de todo mal"

Answer 2

pasos:

1. Medida
2. Analizar
3. Decidir
4. Implementar
5. Repita

En primer lugar obtener un perfilador para medir el código. No caiga en la trampa de suponer que sabe dónde están los cuellos de botella. Incluso después, si sus suposiciones demuestran ser correctas, no piense que puede omitir el paso de medición la próxima vez que tenga una tarea similar.

Luego analiza tus hallazgos. Mire el código, identifique los cuellos de botella sobre los que puede hacer algo que tendrán un efecto. Intente estimar cuánto de esto será una mejora.

Decida si desea seguir este camino, de acuerdo con su análisis. ¿Valdrán las ganancias? Es una reescritura garantizada? Tal vez descubras que, aunque funciona lento, es tan bueno como lo que se obtendrá o que estás cerca de la parte superior de la curva de rendimiento, donde el trabajo necesario para buscar una mejora minúscula no está garantizado.

Implemente sus cambios, realice la reescritura si es necesario o refactorice el código si esa es la ruta que ha bajado. Hazlo en pequeños pasos para que sea fácil medir si tu cambio dio lo que querías o si necesitas retroceder un paso y probar una ruta diferente.

luego volver al inicio y medir, analizar, decidir, ejecutar, etc.

Además, en la nota del código de refactorización. Lo primero que debe cambiar son los grandes enfoques a nivel de algoritmo.Cosas como reemplazar un algoritmo de clasificación por otro que funciona mejor, etc. No comience con optimizaciones de nivel de línea, por ejemplo, cómo obtener una línea que incremente un valor para ir un poco más rápido. Esas son optimizaciones de último nivel y generalmente no valen la pena, a menos que se ejecute en condiciones de rendimiento extremo.

Answer 3

ni siquiera se molestan en tratar nada sin algún tipo de perfiles, no puedo enfatizar esto lo suficiente! Desafortunadamente, todos los perfiladores que sé chupan o son caros (¡por los costos de negocio!), Así que dejaré que los demás hagan recomendaciones allí :).

Usted sabe que necesita una re-escritura cuando los datos que indica que necesita una re-escritura, que suena recursiva, pero en realidad sólo significa que el costo de su arquitectura o el software actual de pila es suficiente por sí misma para empujar sobre el acantilado de rendimiento, por lo que nada de lo que hagas en los cambios locales puede solucionar el problema general. Sin embargo, antes de salir del comando Archivo-> Nuevo ..., haga un plan, construya un prototipo y pruebe que el prototipo funciona mejor que el sistema actual para la misma tarea: ¡es sorprendente la frecuencia con la que no hay diferencia notoria!

Answer 4

Asegúrese de tener suficiente prueba de la unidad para asegurarse de que ninguna optimización que hará que no rompa nada

Asegúrese de calificar a su entorno de ejecución . En algún momento, un simple cambio en las opciones de ejecución puede recorrer un largo camino.

Entonces, y sólo entonces, empezar a analizar el código.

La decisión de reescritura (para un código que ya funciona) solo debe tenerse en cuenta si hay suficientes evoluciones futuras que pueden no ser compatibles con la arquitectura actual. Si
arreglos simples pueden acelerar un código que no se supone que evolucionar mucho, sin reescritura completa debería ser necesario.

El criterio para detener se suele determinar en colaboración con el usuario final (el cliente), pero sugeriría un documento formal que establezca los objetivos a alcanzar con este proceso de optimización.

Answer 5

Además de perfiles, como todo el mundo menciona, las dos soluciones siempre me dirijo a primera (después profilling) son memoization y perezoso de carga, ambos son fáciles de implementar y, normalmente, hacer una gran diferencia.

Answer 6

En primer lugar decidir cuál es su objetivo de optimización es - estableció un objetivo para medir el tiempo de las operaciones particulares en una plataforma de hardware dada. Mida el rendimiento con precisión (asegúrese de que sus resultados sean repetibles) y en un entorno similar a la producción (sin máquinas virtuales, etc. a menos que eso sea lo que usa en producción).

Entonces, si usted decide que es ya lo suficientemente rápido, puede detener allí.

Si aún no es lo suficientemente bueno, se necesitará un trabajo adicional, que es donde entra en juego el perfilado. Es posible que no pueda utilizar un generador de perfiles muy bien (por ejemplo, si afecta el comportamiento demasiado), en este caso, la instrumentación debería usarse en su lugar.

Answer 7

En primer lugar no se olvide siguientes:

• optimización prematura es la raíz de todos los males
• Rendimiento vienen del diseño

segundo lugar;

No asuma tratar de ver

Creo que esta es la regla de oro de la optimización, se prueba, a menos que se haga la prueba y demostrar que está funcionando no vas a saber.

En su caso, lo que yo haría es, en primer lugar, refactorizar el código, tenerlo en cuenta.

Si tienes pruebas unitarias tienes suerte sólo tiene que ir función por función y específicamente ir y comprobar más frecuentemente llamado código (utilizar perfiles para observar las llamadas y dónde están los cuellos de botella). Si no tiene pruebas, escriba algunas pruebas básicas que confirmen la salida general en algunas condiciones para que pueda asegurarse de que no está rompiendo nada y de forma gratuita para experimentar.

Answer 8

Asumiendo que el código necesita optimización, entonces usaría: 1.) Optimice la forma en que se manejan los almacenamientos intermedios utilizados - Optimización de caché. Las latencias de caché son una gran área que absorbe los ciclos de CPU como malos. aproximadamente en el rango de 5-10% de sobrecarga Utilice los almacenamientos intermedios de datos en la caché de manera eficiente.

2.) Los bucles críticos y las funciones intensivas de MCPS se pueden codificar en lenguaje ensamblador o utilizando las características intrínsecas de bajo nivel proporcionadas por el compilador para ese objetivo h/w.

3.) Las lecturas/escrituras de la memoria externa son costosas. minimizar el acceso a la memoria externa tanto como sea posible. O si tiene que acceder hágalo de una manera eficiente (datos útiles, acceso DMA PArallel, etc.)

En general, si obtiene alrededor del 20% de optimización (mejor caso) siguiendo las técnicas de optimización, diría que eso es lo suficientemente bueno y lo mejor sin una reestructuración importante del código, rediseño del algoritmo. Después de lo cual se convierte en truco, complicado y tedioso.

-AD

Answer 9

El lenguaje que he hecho la mayor optimización para computación numérica en C y C++ en Linux. Descubrí que la creación de perfiles, si bien es útil, puede sesgar los resultados de tiempo de ejecución de manera que las operaciones más baratas y frecuentes (como incrementos de iterador C++). Así que toma esos con un grano de sal. En términos de estrategias reales que produjeron una buena velocidad son:

1. Usar grupos numéricos en lugar de las matrices de objetos. Por ejemplo, C++ tiene un tipo de datos "complejo". Las operaciones en una matriz de estas fueron mucho más lentas que una operación similar en dos matrices de flotadores. Esto se puede generalizar para "usar los tipos de máquina" para cualquier código de rendimiento crítico.
2. Escriba el código para permitir que el compilador sea más eficaz en sus optimizaciones. Por ejemplo, si tiene una matriz de tamaño fijo, use índices de matriz para que funcione la vectorización automática (una característica del compilador de Intel).
3. Las instrucciones SIMD pueden proporcionar una buena aceleración si su problema encaja en el tipo de dominio para el que están diseñadas (multiplicar/dividir flotantes o ints todo al mismo tiempo). Esto es algo como MMX, SSE, SSE2, etc.
4. Uso de tablas de búsqueda con interpolación para funciones costosas donde los valores exactos no son importantes. Esto no siempre es bueno, ya que buscar los datos en la memoria puede ser caro por derecho propio.

Espero que eso te inspire.

Answer 10

Todas las buenas respuestas.

Me refinaría la parte de "medida" del consejo. Realizo mediciones con el fin de cuantificar cualquier mejora que pueda hacer. Sin embargo, para buscando lo que necesita ser reparado (y ese es un propósito diferente), obtengo varias muestras de la pila de llamadas, manualmente.

Supongamos, por simplicidad, que el programa tarda 20 giga-ciclos en ejecutarse, cuando debería tomar 10. Si lo paro 10 veces al azar, entonces en 5 de esas ocasiones, más o menos, estará en uno de esos ciclos innecesarios. Puedo ver si el ciclo es necesario mirando cada capa de la pila de llamadas. Si se puede eliminar cualquier instrucción de llamada en cualquier nivel de la pila, entonces el ciclo es innecesario. Si tal instrucción aparece en varias pilas, eliminarla hará que acelere el programa, en una cantidad que es aproximadamente el porcentaje de muestras de la pila en la que se encuentra.

Cualquier instrucción que aparezca en varias pilas es sospechosa: cuantas más pilas hay, más sospechosas. Ahora, call _main probablemente no sea uno que pueda eliminar, pero
foo.cpp:96 call std::vector::iterator:++
si aparece en varias pilas, es definitivamente un foco de atención.

Uno puede, por motivos de estilo, no querer para reemplazarlo, pero uno sabrá aproximadamente qué precio en rendimiento se está pagando para esa elección.

Por lo tanto, la optimización consiste en identificar a los sospechosos y encontrar la manera de reemplazarlos o eliminarlos.

La parte difícil (y lo he hecho muchas veces) es entender qué es necesario y qué no. Para eso, absorberás una comprensión de cómo y por qué se hacen las cosas en ese programa, de modo que si alguna actividad es un ciclo-cerdo, puedes saber cómo reemplazarla de manera segura.

Algunos cerdos de ciclo pueden ser fáciles de arreglar, pero se encontrará rápidamente con aquellos que no sabe cómo reemplazar de forma segura. Para eso, necesitas estar más familiarizado con el código.

Te ayudará si puedes elegir el cerebro de alguien que ya trabajó en el programa.

De lo contrario (suponiendo que el código es ~ 10^6 líneas, como he trabajado) puede obtener cierta aceleración con bastante facilidad, pero para ir más allá, puede llevar meses llegar a donde se siente cómodo cambios significativos.

Answer 11

Como muchos otros ya han indicado, perfilar es su primer paso.

Agregaría que centrarse en estructuras de datos y algoritmos como primer paso es generalmente más rentable que sumergirse directamente en micro-optimizaciones.

Por un lado, el compilador normalmente realizará muchos de los trucos de optimización clásicos para usted de todos modos (y, a menudo mejor que usted). Esto es especialmente cierto en lenguajes más modernos como C# que en lenguajes C más antiguos, menos restringidos, ya que el compilador tiene más conocimiento de la estructura del programa; peor aún, confundir el código "optimizando" puede hacer que al compilador le resulte más difícil aplicar sus propias optimizaciones más eficientes.

En su mayoría, hay mucho más margen para mejorar las cosas cuando comienza a mejorar el gran oh de sus operaciones. Por ejemplo, buscar en una lista vinculada es O (n); lo que significa que el tiempo necesario para buscarlo aumenta a la misma velocidad que el tamaño de los datos almacenados en él. La búsqueda de una tabla hash es solo O (1), por lo que puede agregar más datos sin aumentar el tiempo de búsqueda (hay otros factores cuando dejamos el mundo teórico, por lo que esto no es del todo cierto, pero es cierto que la mayoría de los hora).

Enredando con sus bucles para que corran de mayor a menor, por lo que el código generado puede ahorrar un par de ciclos de reloj con un JumpIfZero en lugar de un JumpIfLessThan que probablemente no tendrá el mismo grado de impacto.

Answer 12

Las buenas estrategias

Además de las leyes básicas de optimización mencionados (medida, no optimizan si no es necesario), y aunque la pregunta formulada explícitamente eficiencia, siempre refactor dicho código durante mi inspección

Normalmente, el código con mal rendimiento también está mal documentado. Así que con la refactorización me aseguro de que el código esté mejor documentado por sí mismo y sea más fácil de entender. Esa es la base para asegurarme de saber lo que estoy optimizando (ya que en la mayoría de los casos, los requisitos para esa porción de código tampoco estarán completamente disponibles).

Cuándo dejar de

Con una aplicación muy mal desempeño, por lo general tendrá un aumento en el tiempo de ejecución se muestra para un solo método (o conjunto de métodos relacionados) en su perfilador, mostrando un error de programación o defecto de diseño. Así que, por lo general, me detengo si el tiempo de ejecución de los métodos perfilados se distribuye en la mayoría de los casos (o si la mayoría de los métodos de cuello de botella que se muestran son de plataforma, como los métodos de Sun Java). Si sus clientes exigen mayor optimización, tendrá que rediseñar partes más grandes de la aplicación en lugar de optimizar el código existente.