Optimización (informática)

La optimización  es la modificación de un sistema para mejorar su eficiencia. Un sistema puede ser un solo programa de computadora , un dispositivo digital, una colección de computadoras o incluso una red completa.

Aunque el objetivo de la optimización es obtener un sistema óptimo, no siempre se logra un sistema verdaderamente óptimo en el proceso de optimización. Un sistema optimizado suele ser óptimo para una sola tarea o grupo de usuarios: en algún lugar puede ser más importante reducir el tiempo requerido para que el programa complete el trabajo, incluso a costa de consumir más memoria; en aplicaciones donde la memoria es más importante, se pueden elegir algoritmos más lentos con requisitos de memoria más pequeños.

Además, a menudo no existe una solución universal (que funciona bien en todos los casos), por lo que los ingenieros utilizan soluciones de  compensación para optimizar solo los parámetros clave. Además, el esfuerzo requerido para lograr un programa completamente óptimo que no se puede mejorar más, casi siempre excede el beneficio que se puede obtener de este, por lo que, por regla general, el proceso de optimización se completa antes de que se alcance la optimización total. Afortunadamente, en la mayoría de los casos, incluso con esto, se logran mejoras notables.

La optimización debe hacerse con cuidado. Tony Hoare dijo por primera vez, y Donald Knuth repitió a menudo más tarde el famoso dicho: “La optimización prematura es la raíz de todos los males”. Es muy importante tener un algoritmo de voz y un prototipo de trabajo para empezar.

Fundamentos

Algunas tareas a menudo se pueden hacer de manera más eficiente. Por ejemplo, un programa en C que suma todos los números enteros del 1 al N:

int i , suma = 0 ; para ( yo = 1 ; yo <= norte ; yo ++ ) suma += yo ;

Suponiendo que no haya desbordamiento aquí , este código se puede reescribir de la siguiente manera usando la fórmula matemática adecuada :

int suma = ( norte * ( norte + 1 )) / 2 ;

El término "optimización" generalmente implica que el sistema conserva la misma funcionalidad. Sin embargo, a menudo se pueden lograr mejoras significativas en el rendimiento eliminando la funcionalidad redundante. Por ejemplo, suponiendo que el programa no necesita admitir más de 100 elementos en la entrada , es posible utilizar la asignación estática en lugar de la asignación dinámica más lenta .

Compensaciones

La optimización se centra principalmente en el tiempo de ejecución único o repetido, el uso de la memoria, el espacio en disco, el ancho de banda o algún otro recurso. Esto generalmente requiere compensaciones: un parámetro se optimiza a expensas de otros. Por ejemplo, aumentar el tamaño de la memoria caché del software de algo mejora el rendimiento del tiempo de ejecución, pero también aumenta el consumo de memoria. Otras compensaciones comunes incluyen la transparencia y la expresividad del código, casi siempre a costa de la desoptimización. Los algoritmos especializados complejos requieren más esfuerzo de depuración y aumentan la posibilidad de errores .

Varias áreas

En investigación de operaciones , la optimización es el problema de determinar los valores de entrada de una función para la cual tiene un valor máximo o mínimo. A veces hay restricciones en estos valores, tal tarea se conoce como optimización restringida .

En programación , la optimización generalmente significa modificar el código y su configuración de compilación para una arquitectura dada para producir software más eficiente.

Los problemas típicos tienen tantas posibilidades que los programadores generalmente solo pueden permitir que se use una solución "suficientemente buena".

Cuellos de botella

Para optimizar, debe encontrar un cuello de botella ( cuello de botella en inglés -  bottleneck ): una parte crítica del código, que es el principal consumidor del recurso necesario. Mejorar alrededor del 20% del código a veces implica cambiar el 80% de los resultados, según el principio de Pareto . La fuga de recursos (memoria, identificadores, etc.) también puede provocar una caída en la velocidad de ejecución del programa. Para buscar dichas fugas, se utilizan herramientas especiales de depuración y se utilizan perfiladores para detectar cuellos de botella .

El diseño arquitectónico de un sistema tiene una influencia particularmente fuerte en su desempeño. La elección del algoritmo afecta la eficiencia más que cualquier otro elemento de diseño. Los algoritmos y estructuras de datos más complejos pueden manejar bien una gran cantidad de elementos, mientras que los algoritmos simples son buenos para pequeñas cantidades de datos: la sobrecarga de inicializar un algoritmo más complejo puede superar el beneficio de usarlo.

Cuanta más memoria utiliza un programa, más rápido suele ejecutarse. Por ejemplo, un programa de filtro normalmente lee cada línea, filtra y genera esa línea directamente. Por lo tanto, solo usa memoria para almacenar una línea, pero su rendimiento suele ser muy pobre. El rendimiento se puede mejorar mucho leyendo todo el archivo y luego escribiendo el resultado filtrado; sin embargo, este método usa más memoria. El almacenamiento en caché de resultados también es eficiente, pero requiere más memoria para su uso.

Las técnicas más simples para optimizar programas en términos de tiempo de CPU

La optimización en términos del tiempo del procesador es especialmente importante para los programas computacionales en los que los cálculos matemáticos tienen una gran participación. Aquí hay algunas técnicas de optimización que un programador puede usar al escribir el código fuente del programa.

Inicialización de objetos de datos

En muchos programas, alguna parte de los objetos de datos debe inicializarse , es decir, se les deben asignar valores iniciales. Tal asignación se realiza al comienzo del programa o, por ejemplo, al final del ciclo. La inicialización adecuada del objeto ahorra un valioso tiempo de CPU. Entonces, por ejemplo, cuando se trata de inicializar matrices, es probable que usar un bucle sea menos eficiente que declarar esa matriz como una asignación directa.

Programación de operaciones aritméticas

En el caso de que una parte significativa del tiempo del programa se dedique a los cálculos aritméticos, se ocultan reservas considerables para aumentar la velocidad del programa en la programación correcta de las expresiones aritméticas (y lógicas). Es importante que varias operaciones aritméticas difieran significativamente en velocidad. En la mayoría de las arquitecturas, las operaciones más rápidas son la suma y la resta. La multiplicación es más lenta, seguida de la división. Por ejemplo, el cálculo del valor de la expresión , donde  es una constante, para argumentos de coma flotante se realiza más rápido en la forma , donde  es una constante calculada en la etapa de compilación del programa (de hecho, la operación de división lenta se reemplaza por la operación de multiplicación rápida). Para un argumento entero , es más rápido calcular la expresión en la forma (la operación de multiplicación se reemplaza por la operación de suma) o usar la operación de desplazamiento a la izquierda (que no proporciona una ganancia en todos los procesadores). Estas optimizaciones se denominan reducción de la fuerza de operación . La multiplicación de argumentos enteros por una constante en los procesadores de la familia x86 se puede hacer de manera eficiente usando instrucciones del ensamblador , y en lugar de usar instrucciones : LEASHLADDMUL/IMUL

; Operando fuente en el registro EAX ADD EAX , EAX ; multiplicación por 2 LEA EAX , [ EAX + 2 * EAX ] ; multiplicación por 3 SHL EAX , 2 ; multiplicación por 4 LEA EAX , [ 4 * EAX ] ; otra forma de implementar la multiplicación por 4 LEA EAX , [ EAX + 4 * EAX ] ; multiplicación por 5 LEA EAX , [ EAX + 2 * EAX ] ; multiplicar por 6 SUMAR EAX , EAX ; etc.

Estas optimizaciones son de microarquitectura y normalmente el compilador de optimización las realiza de forma transparente para el programador .

Se dedica relativamente mucho tiempo a llamar subrutinas (pasar parámetros en la pila , guardar registros y direcciones de retorno, llamar a constructores de copias). Si la subrutina contiene una pequeña cantidad de acciones, se puede implementar en línea ( inglés  en línea ): todas sus declaraciones se copian en cada nuevo sitio de llamada (hay una serie de restricciones en las sustituciones en línea: por ejemplo, la subrutina no debe ser recursiva ). Esto elimina la sobrecarga de llamar a la subrutina, pero aumenta el tamaño del archivo ejecutable. En sí mismo, el aumento del tamaño del archivo ejecutable no es significativo, sin embargo, en algunos casos, el código ejecutable puede ir más allá de la memoria caché de instrucciones , lo que provocará una caída significativa en la velocidad de ejecución del programa. Por lo tanto, los compiladores de optimización modernos suelen tener configuraciones de optimización para el tamaño del código y la velocidad de ejecución.

El rendimiento también depende del tipo de operandos. Por ejemplo, en el lenguaje Turbo Pascal , debido a la implementación de la aritmética de enteros, la operación de suma resulta ser la más lenta para operandos de tipo Bytey ShortInt: a pesar de que las variables ocupan un byte, las operaciones aritméticas para ellas son de dos bytes y al realizar operaciones en estos tipos, el byte alto de los registros se reinicia y el operando se copia de la memoria al byte bajo del registro. Esto conduce a costos adicionales de tiempo.

Al programar expresiones aritméticas, se debe elegir tal forma de su notación para que se minimice el número de operaciones "lentas". Consideremos tal ejemplo. Sea necesario calcular un polinomio de 4º grado:

Siempre que el cálculo del grado se realice multiplicando la base un cierto número de veces, es fácil encontrar que esta expresión contiene 10 multiplicaciones (operaciones "lentas") y 4 sumas (operaciones "rápidas"). Esta misma expresión se puede escribir como:

Esta forma de notación se llama esquema de Horner . Esta expresión tiene 4 multiplicaciones y 4 sumas. El número total de operaciones se ha reducido casi a la mitad, y el tiempo para calcular el polinomio también disminuirá en consecuencia. Estas optimizaciones son algorítmicas y, por lo general, el compilador no las realiza automáticamente.

Ciclos

El tiempo de ejecución de los ciclos de diferentes tipos también difiere. El tiempo de ejecución de un ciclo con un contador y un ciclo con una condición posterior, en igualdad de condiciones, el ciclo con una condición previa se ejecuta un poco más (alrededor de 20-30%).

Cuando utilice bucles anidados, tenga en cuenta que el tiempo de CPU dedicado a procesar una construcción de este tipo puede depender del orden de los bucles anidados. Por ejemplo, un bucle anidado con un contador en Turbo Pascal :

for j := 1 to 100000 do for k := 1 to 1000 do a := 1 ; for j := 1 to 1000 do for k := 1 to 100000 do a := 1 ;

El ciclo de la columna de la izquierda dura aproximadamente un 10 % más que el de la columna de la derecha.

A primera vista, tanto en el primer como en el segundo caso, el operador de asignación se ejecuta 100.000.000 de veces y el tiempo dedicado a él debería ser el mismo en ambos casos. Pero no lo es. Esto se explica por el hecho de que la inicialización del ciclo (procesamiento por parte del procesador de su encabezado para determinar los valores inicial y final del contador, así como el paso de incremento del contador) lleva tiempo. En el primer caso, el bucle exterior se inicializa 1 vez y el bucle interior se inicializa 100.000 veces, es decir, se realizan un total de 100.001 inicializaciones. En el segundo caso, solo hay 1001 de tales inicializaciones.

Los bucles anidados con condiciones previas y posteriores se comportan de manera similar. Podemos concluir que al programar bucles anidados, si es posible, haga que el bucle con el menor número de repeticiones sea el más exterior y el bucle con el mayor número de repeticiones el más interior.

Si los bucles contienen accesos a la memoria (generalmente cuando se procesan matrices), para el uso más eficiente de la memoria caché y la captación previa del hardware de datos de la memoria (en inglés  Hardware Prefetch ), el orden de omisión de las direcciones de memoria debe ser lo más secuencial posible. Un ejemplo clásico de tal optimización es el reordenamiento de bucles anidados al realizar la multiplicación de matrices .

Fragmentos de código invariantes

La optimización de fragmentos de código invariantes está estrechamente relacionada con el problema de la programación óptima de bucles. Dentro del bucle pueden existir expresiones cuyos fragmentos no dependan en modo alguno de la variable de control del bucle. Se llaman fragmentos de código invariantes . Los compiladores modernos a menudo detectan la presencia de dichos fragmentos y los optimizan automáticamente. Esto no siempre es posible y, a veces, el rendimiento de un programa depende completamente de cómo se programe el bucle. Como ejemplo, considere el siguiente fragmento de programa ( lenguaje Turbo Pascal ):

for i := 1 to n do begin ... for k := 1 to p do for m := 1 to q do do begin a [ k , m ] := Sqrt ( x * k * m - i ) + Abs ( u * i - x * m + k ) ; b [ k , m ] := Sin ( x * k * i ) + Abs ( u * i * m + k ) ; fin ; ... soy := 0 ; bm := 0 ; for k := 1 to p do for m := 1 to q do begin am := am + a [ k , m ] / c [ k ] ; bm := bm + b [ k , metro ] / c [ k ] ; fin ; fin ;

Aquí, los fragmentos de código invariantes son el sumando Sin(x * k * i)en el primer bucle sobre la variable my la operación de división por el elemento de matriz c[k]en el segundo bucle sobre m. Los valores del seno y el elemento del arreglo no cambian en el ciclo sobre la variable m, por lo tanto, en el primer caso, puede calcular el valor del seno y asignarlo a una variable auxiliar que se usará en la expresión dentro del bucle. En el segundo caso, puede realizar la división después del final del bucle m. Por lo tanto, la cantidad de operaciones aritméticas que consumen mucho tiempo se puede reducir significativamente.

Véase también

Literatura

  • Bentley, John Louis . Escribir programas eficientes. ISBN 0-13-970251-2
  • Donald Knuth . El arte de la programación informática = El arte de la programación informática. - 3ra ed. - M .: Williams , 2006. - V. 1: Algoritmos básicos. — 720 s. - ISBN 0-201-89683-4 .
  • Donald Knuth . El arte de la programación informática = El arte de la programación informática. - 3ra ed. - M. : Williams , 2007. - V. 2: Algoritmos obtenidos. — 832 pág. — ISBN 0-201-89684-2 .
  • Donald Knuth . El arte de la programación informática = El arte de la programación informática. - 2ª ed. — M .: Williams , 2007. — V. 3: Clasificación y búsqueda. — 824 pág. - ISBN 0-201-89685-0 .
  • S. A. NEMNYUGIN Taller // Turbo Pascal. - 2ª ed. - San Petersburgo. : Pedro, 2007. - 268 p. - ISBN 5-94723-702-4 .
  • Chris Kaspersky . Técnica de optimización de programas. Uso eficiente de la memoria. - San Petersburgo. : BHV-Petersburg, 2003. - 464 p. — ISBN 5-94157-232-8 .

Enlaces