¡Optimización! - ¿Qué es? ¿Cómo se hace?

Question

Es común escuchar acerca de "código altamente optimizado" o de algún desarrollador que necesita optimizar el suyo y otras cosas. Sin embargo, como programador autodidacta, nunca he entendido realmente a qué se refieren exactamente las personas cuando hablan de esas cosas.

¿Le gustaría explicarle la idea general? Además, recomiende algunos materiales de lectura y realmente lo que quiera decir al respecto. Siéntase libre de despotricar y predicar.

Answer 1

La optimización significa tratar de mejorar los programas de computadora para cosas tales como la velocidad. La pregunta es muy amplia, porque la optimización puede incluir compiladores que mejoran los programas de velocidad o seres humanos que hacen lo mismo.

Answer 2

Optimizar es un término que usamos perezosamente para significar "hacer algo mejor de una cierta manera". Raramente "optimizamos" algo, más, simplemente lo mejoramos hasta que cumpla con nuestras expectativas.

Las optimizaciones son cambios que realizamos con la esperanza de optimizar alguna parte del programa. Un programa totalmente optimizado generalmente significa que el desarrollador lanzó legibilidad fuera de la ventana y ha recodificado el algoritmo de forma no obvia para minimizar el "tiempo de pared". (No es un requisito que el "código optimizado" ser difícil de leer, es sólo una tendencia.)

Uno puede optimizar para:

• El consumo de memoria - Hacer un programa o del algoritmo de tamaño en tiempo de ejecución más pequeña .

• Consumo de CPU - Hace que el algoritmo sea menos intensivo desde el punto de vista informático.

• tiempo pared - Hacer todo lo necesario para hacer algo más rápido

• legibilidad - En lugar de hacer su aplicación mejor para el equipo, que puede hacer que sea más fácil para los seres humanos que lo lea.

Algunas técnicas comunes (y demasiado generalizadas) para optimizar el código incluyen:

• cambiar el algoritmo para mejorar las características de rendimiento. Si tiene un algoritmo que toma O (n^2) tiempo o espacio, intente reemplazar ese algoritmo con uno que tome O (n * log n).

• Para aliviar el consumo de memoria, revise el código y busque la memoria desperdiciada. Por ejemplo, si tiene una aplicación de uso intensivo de cadenas, puede cambiar a utilizar Referencias de subcadenas (donde una referencia contiene un puntero a la cadena, más índices para definir sus límites) en lugar de asignar y copiar la memoria de la cadena original.

• Para aliviar el consumo de CPU, guarde en la memoria caché tantos resultados intermedios como pueda. Por ejemplo, si necesita calcular la desviación estándar de un conjunto de datos, guarde ese único resultado numérico en lugar de recorrer el conjunto cada vez que necesite conocer el desarrollador std.

Answer 3

La idea general es que cuando se crea el árbol de fuentes en la fase de compilación, antes de generar el código de analizarlo, lo hace un paso adicional (optimización), donde, basado en ciertas heurísticas, que contrae las ramas juntas , elimine las ramas que no se utilizan o agregue nodos adicionales para las variables temporales que se usan varias veces.

Piense en cosas como esta pieza de código:

a=(b+c)*3-(b+c) 

cual se traduce en

 - 
    *  + 
    + 3 b c 
    b c 

Para un analizador sería obvio que el + nodo con sus 2 descendientes son idénticos, por lo se fusionarían en una variable temporal, t, y el árbol se reescribirá:

 - 
    *  t 
    t 3 

N un analizador de flujo aún mejor sería ver que desde que t es un número entero, el árbol podría simplificarse aún más a:

 * 
    t  2 

y el código intermediario que había corrido su generación de código paso en finalmente sería

int t=b+c; 
a=t*2; 

con t marcado como una variable de registro, que es exactamente lo que se escribiría para el ensamblaje.

Una última nota: puede optimizar para algo más que la velocidad de tiempo de ejecución. También puede optimizar el consumo de memoria, que es lo contrario. Donde desenrollar bucles y crear copias temporales ayudaría a acelerar su código, también usarían más memoria, por lo que es una compensación en lo que su objetivo es.

Answer 4

Aquí hay un ejemplo de alguna optimización (que soluciona una decisión mal hecha) que hice recientemente. Es muy básico, pero espero que ilustre que se pueden obtener buenos beneficios incluso a partir de cambios simples, y que la "optimización" no es mágica, solo se trata de tomar las mejores decisiones para llevar a cabo la tarea en cuestión.

En una aplicación en la que estaba trabajando había varias estructuras de datos LinkedList que se estaban utilizando para contener varias instancias de foo.

Cuando la aplicación estaba en uso, con mucha frecuencia comprobaba si el objeto incluido en la LinkedListed X. A medida que la cantidad de X empezaba a crecer, noté que la aplicación funcionaba más lentamente de lo que debería.

Ejecuté un generador de perfiles, y me di cuenta de que cada llamada 'myList.Contains (x)' tenía O (N) porque la lista tiene que recorrer cada elemento que contiene hasta que llega al final o encuentra una coincidencia. Esto definitivamente no fue eficiente.

¿Qué hice para optimizar este código? Cambié la mayoría de las estructuras de datos LinkedList a HashSets, que pueden hacer una llamada '.Contains (X)' en O (1), mucho mejor.

Answer 5

Voy a despotricar sin ningún consejo práctico.

Measure First. La optimización se debe hacer a los lugares donde importa. El código altamente optimizado es a menudo difícil de mantener y una fuente de problemas. En lugares donde el código no ralentiza la ejecución de todos modos, siempre prefiero la facilidad de mantenimiento a las optimizaciones.Familiarícese con la creación de perfiles, tanto intrusiva (instrumentada) como no intrusiva (estadística baja general). Aprenda a leer una pila perfilada, comprenda dónde se gasta la exclusiva tiempo/tiempo exclusivo, por qué aparecen ciertos patrones y cómo identificar los puntos problemáticos.

No puede arreglar lo que no puede medir. Haga que su programa informe a través de alguna infraestructura de rendimiento lo que hace y los tiempos que toma. Vengo de un fondo de Win32, así que estoy acostumbrado a los contadores de rendimiento y soy extremadamente generoso al rociarlos sobre mi código. Yo incluso automatized the code to generate them.

Y finalmente algunas palabras sobre optimizaciones. La mayoría de las discusiones sobre optimización veo que se enfocan en cosas que cualquier compilador optimizará para ti de forma gratuita. En mi experiencia, la mayor fuente de ganancias para 'código altamente optimizado' se encuentra completamente en otra parte: acceso a la memoria. En las arquitecturas modernas, la CPU está inactiva la mayor parte del tiempo, esperando que se sirva memoria en sus tuberías. Entre caídas de caché L1 y L2, TLB falta, NUMA acceso de nodo cruzado e incluso GPF que deben obtener la página del disco, el patrón de acceso a la memoria de una aplicación moderna es la optimización más importante que uno puede realizar. Estoy exagerando un poco, por supuesto habrá cargas de trabajo de ejemplo que no beneficiarán a la localidad de acceso a memoria de estas técnicas. Pero la mayoría de las aplicaciones lo harán. Para ser específico, lo que estas técnicas significan es simple: agrupe sus datos en memoria para que una sola CPU pueda trabajar en un rango de memoria ajustado que contenga todo lo que necesita, sin costosas referencias de memoria fuera de sus líneas de caché o su página actual. En la práctica, esto puede significar algo tan simple como acceder a una matriz por filas en lugar de por columnas.

le recomiendo que lea el Alpha-Sort paper presented at the VLDB conference en 1995. En este trabajo se presenta la forma de caché algoritmos sensibles diseñados específicamente para las modernas arquitecturas de CPU pueden soplar fuera del agua el viejo test anteriores:

argumentamos que las arquitecturas modernas requieren que los diseñadores de algoritmo reexaminen su uso de la jerarquía de memoria . Alphasort utiliza agrupado estructuras de datos para obtener un buen caché localidad ...

Answer 6

le sugiero que lea un poco de la teoría primera (de libros, o en Google de diapositivas de las clases):

• Las estructuras de datos y algoritmos: cuál es la notación O(), cómo calcularla, qué estructuras de datos y algoritmos se pueden usar para reducir la O-complejidad
  Libro: Introducción a los algoritmos por Thomas H. Cormen, Charles E. Leiserson, y Ronald L. Rivest

• Los compiladores y montaje - cómo el código se traduce a instrucciones de máquina

• la arquitectura del ordenador - cómo la CPU, la memoria RAM, memoria caché, las predicciones Branch, ejecución fuera de orden ... funciona

• operativo - sistemas de modo de núcleo, de modo de usuario, procesos de programación/hilos, exclusiones mutuas, semáforos, colas de mensajes

Después de leer un poco de cada uno, usted debe tener una comprensión básica de todo el diff diferentes aspectos de la optimización

Nota: He wiki-ed esto para que la gente pueda agregar recomendaciones de libros.

Answer 7

Voy con la idea de que optimizar un código es obtener los mismos resultados en menos tiempo. Y totalmente optimizado solo significa que se quedaron sin ideas para hacerlo más rápido. ¡Lanzo grandes cubos de desprecio a los reclamos de un código "totalmente optimizado"! No hay tal cosa.

¿Desea hacer que su aplicación/programa/módulo funcione más rápido? Lo primero que debe hacer (como se mencionó anteriormente) es medir también conocido como perfil. No adivine dónde optimizar. No eres tan inteligente y estarás equivocado. Mis suposiciones son incorrectas todo el tiempo y grandes porciones de mi año se dedican a la creación de perfiles y a la optimización. Entonces haz que la computadora lo haga por ti. Para PC VTune es un gran generador de perfiles. Creo que VS2008 tiene un generador de perfiles integrado, pero no lo he investigado. De lo contrario, mida funciones y piezas grandes de código con contadores de rendimiento. Encontrará un código de muestra para usar los contadores de rendimiento en MSDN.

¿A dónde van sus ciclos? Probablemente estés esperando datos provenientes de la memoria principal. Ir a leer en L1 & L2 cachés. Comprender cómo funciona el caché es la mitad de la batalla. Sugerencia: utilice estructuras compactas y compactas que se ajusten mejor a una línea de caché.

La optimización es muy divertida. Y nunca termina :)

Un gran libro sobre optimización es Escribir un gran código: Understanding the Machine de Randall Hyde.

Answer 8

Optimización un programa significa: hacer que se ejecute más rápido

La única manera de hacer el programa más rápido es lo que es hacer menos:

• encontrar un algoritmo que utiliza un menor número de operaciones (por ejemplo, N log N en lugar de N^2)
• evite los componentes lentos de su máquina (mantenga los objetos en caché en lugar de en la memoria principal, o en la memoria principal en lugar de en d isk); ¡reducir el consumo de memoria casi siempre ayuda!

Otras reglas:

• En la búsqueda de oportunidades de optimización, se adhieren al 80-20 en reglas: 20% del código de programa típico representa el 80% del tiempo de ejecución.
• Mida antes y después de cada intento de optimización; a menudo, las optimizaciones no.
• ¡Optimice solo después de que el programa se ejecute correctamente!

Además, hay maneras de hacer un programa parece ser más rápido:

• separada de procesamiento de eventos GUI de tareas de back-end; Priorizar los cambios visibles por el usuario contra el cálculo del back-end para mantener el front-end "ágil"
• darle al usuario algo para leer mientras se realizan operaciones largas (¿notaron las presentaciones de diapositivas mostradas por los instaladores?)

Answer 9

Asegúrese de que su aplicación arroje resultados correctos antes de comenzar a optimizarla.

Answer 10

Esta es una buena pregunta.

Por lo general, la mejor práctica es 1) simplemente escriba el código para hacer lo que necesita, 2) luego trate el rendimiento, pero solo si es un problema. Si el programa es "lo suficientemente rápido", no es un problema.

Si el programa no es lo suficientemente rápido (como lo hace esperar), intente ajustar el rendimiento. La optimización del rendimiento no es como la programación. En la programación, piensas primero y luego haces algo. En la optimización del rendimiento, pensar primero es un error, porque eso es adivinando.

No adivine qué arreglar; diagnosticar lo que el programa está haciendo. Todo el mundo lo sabe, pero sobre todo lo hacen de todos modos. Es natural decir "Podría ser el problema es X, Y o Z", pero solo el novato actúa en las suposiciones. El profesional dice "pero probablemente estoy equivocado".

Existen diferentes formas de diagnosticar problemas de rendimiento.

Lo más simple es simplemente pasar por un solo paso a través del programa en el nivel de lenguaje ensamblador, y no tomar ningún atajo. De esa manera, si el programa está haciendo cosas innecesarias, entonces están haciendo las mismas cosas, y será dolorosamente obvio.

Otra es obtener una herramienta de creación de perfiles, y como otros dicen, medir, medir, medir.

Personalmente no me importa medir. Creo que es un microscopio difuso con el propósito de detectar problemas de rendimiento. Prefiero this method y this is an example of its use.

Buena suerte.

AGREGADO: creo que encontrará, si realiza este ejercicio varias veces, aprenderá qué prácticas de codificación tienden a generar problemas de rendimiento y las evitará instintivamente. (Esto es sutilmente diferente de la "optimización prematura", que supone al principio que debe preocuparse por el rendimiento. De hecho, probablemente sepa, si no lo sabe ya, que la preocupación prematura por el rendimiento puede causar la problema que trata de evitar.)

Answer 11

Sin embargo, como programador autodidacta, nunca he entendido realmente qué significa exactamente la gente cuando habla de tales cosas.

Déjame compartir un secreto contigo: nadie lo hace. Hay ciertas áreas donde sabemos matemáticamente qué es y qué no es lento. Pero en su mayor parte, el rendimiento es demasiado complicado para poder entenderlo. Si acelera una parte de su código, hay una buena posibilidad de que esté disminuyendo la velocidad de otro.

Por lo tanto, cualquier persona que le dice que un método es más rápido que el otro, hay una buena posibilidad de que sólo están adivinando menos una de las tres cosas son ciertas:

1. Tienen datos
2. Son elegir un algoritmo que saben que es más rápido matemáticamente.
3. Están eligiendo una estructura de datos que saben que es más rápida matemáticamente.