Tipos De Optimización
3.1.- Tipos De Optimización
Tipos de optimización:
Optimizaciones Globales
Optimizaciones de Ciclo
Optimización de Mirilla
Optimizaciones Locales
• La optimización es un proceso que tiene a minimizar o maximizar alguna variable
de rendimiento, generalmente tiempo, espacio, procesador, etc.
• La optimización se realiza reestructurando el código de tal forma que el nuevo
código generado tenga mayores beneficios.
Optimización Local
• Las optimizaciones locales se realizan sobre el bloque básico
• Optimizaciones locales
– Folding
– Propagación de constantes
– Reducción de potencia
– Reducción de subexpresiones comunes
Bloque Básico
• Un bloque básico es un fragmento de código que tiene una única entrada y salida, y cuyas
instrucciones se ejecutan secuencialmente. Implicaciones:
– Si se ejecuta una instrucción del bloque se ejecutan todas en un orden conocido en tiempo de
compilación.
• La idea del bloque básico es encontrar partes del programa cuyo análisis necesario para la
optimización sea lo más simple posible.
Ensamblamiento (Folding)
• El ensamblamiento es remplazar las expresiones por su resultado cuando se pueden evaluar en
tiempo de compilación (resultado constante).
– Ejemplo: A=2+3+A+C -> A=5+A+C
• Estas optimizaciones permiten que el programador utilice cálculos entre constantes
representados explícitamente sin introducir ineficiencias.
Implementación del Folding
• Implementación del floding durante la generación de código realizada conjuntamente con el
análisis sintáctico.
– Se añade el atributo de constante temporal a los símbolos no terminales y a las variables de la
tabla de símbolos.
– Se añade el procesamiento de las constantes a las reglas de análisis de expresiones.
– Optimiza: 2+3+b -> 5+b
• Hay una suma de constantes (2+3)+b
– No optimiza: 2+b+3 -> 2+b+3
• No hay una suma de constantes (2+b)+3
Implementación del Folding
• Implementación posterior a la generación de código
– Buscar partes del árbol donde se puede aplicar la propiedad conmutativa:
• Sumas/restas: como la resta no es conmutativa se transforma en sumas: a+b-c+d -> a+b+(-c)+d
• Productos/divisiones: como la división no es conmutativa se transforma en productos: a*b/c*e ->
a*b*(1/c)*e
– Buscar las constantes y operarlas
– Reconstruir el árbol.
Propagación de constantes
• Desde que se asigna a una variable un valor constante hasta la siguiente asignación, se
considera a la variable equivalente a la constante.
• Ejemplo: Propagación Ensamblamiento
PI=3.14 -> PI=3.14 -> PI=3.14
G2R=PI/180 -> G2R=3.14/180 -> G2R=0.017
PI y G2R se consideran constantes hasta la próxima asignación.
• Estas optimizaciones permiten que el programador utilice variables como constantes sin
introducir ineficiencias. Por ejemplo en C no hay constantes y será lo mismo utilizar
– Int a=10;
– #define a 10
Con la ventaja que la variable puede ser local.
• Actualmente en C se puede definir const int a=10;
implementación de la Propagación de Constantes
• Separar el árbol en bloques básicos
– Cada bloque básico será una lista de expresiones y asignaciones
• Para cada bloque básico
– Inicializar el conjunto de definiciones a conjunto vacío.
• Definición: (variable,constante)
– Procesar secuencialmente la lista de expresiones y asignaciones
– Para expresión y asignación
• Sustituir las apariciones de las variables que se encuentran en el conjunto de definiciones por
sus constantes asociadas.
– Para asignaciones
• Eliminar del conjunto de definiciones la definición de la variable asignada
• Añadir la definición de la variable asignada si se le asigna una constante.
3.1.1 Locales
LOCALES
La optimización local se realiza sobre módulos del programa. En la mayoría de las ocasiones a
través de funciones, métodos, procedimientos, clases, etc.
Las características de las optimizaciones locales es que solo se ven reflejados en dichas
secciones. La optimización local sirve cuando un bloque de programa o sección es crítico por
ejemplo: la E/S, la concurrencia, la rapidez y confiabilidad de un conjunto de instrucciones.
EJEMPLOS:
1- Ejecución en tiempo de compilación
Precalcular expresiones constantes (con constantes o variables cuyo valor no cambia).
3!i=5
j=4
f = j + 2.5
!
j=4
f = 6.5
2- Reutilización de expresiones comunes
a=b+c
d=a-d
e=b+c
f=a-d
!
a=b+c
d=a-d
e=a
f=a–d
3- Propagación de copias
Ante instrucciones f=a, sustituir todos los usos de f por a.
a=3+i
f=a
b=f+c
d=a+m
m=f+d
!
a=3+i
b=a+c
d=a+m
m=a+d
4- Eliminación redundancias en acceso matrices
Localizar expresiones comunes en cálculo direcciones de matrices.
5- Transformaciones algebraicas:
Aplicar propiedades matemáticas para simplificar expresiones
o Eliminación secuencias nulas
o Reducción de potencia
o Reacondicionamiento de operandos
3.1.2 Ciclos
Los ciclos son una de las partes más esenciales en el rendimiento de un programa dado que
realizan acciones repetitivas, y si dichas acciones están mal realizadas, el problema se hace N
veces más grandes. La mayoría de las optimizaciones sobre ciclos tratan de encontrar elementos
que no deben repetirse en un ciclo.
El problema de la optimización en ciclos y en general radica en que es muy difícil saber el uso
exacto de algunas instrucciones. Así que no todo código de proceso puede ser optimizado. Otro
uso de la optimización puede ser el mejoramiento de consultas en SQL o en aplicaciones remotas
(sockets, E/S, etc.).
El problema de la optimización en ciclos y en general radica es que muy difícil saber el uso exacto
de algunas instrucciones. Así que no todo código de proceso puede ser optimizado.
3.1.3 Globales
La optimización global se da con respecto a todo el código.
• Este tipo de optimización es más lenta pero mejora el desempeño general de todo programa.
• Las optimizaciones globales pueden depender de la arquitectura de la máquina.
Optimización global
• En algunos casos es mejor mantener variables globales para agilizar los procesos (el proceso
de declarar variables y eliminarlas toma su tiempo) pero consume más memoria.
• Algunas optimizaciones incluyen utilizar como variables registros del CPU,
utilizar instrucción es enensamblador.
3.1.4 De Mirilla
La optimización de mirilla trata de estructurar de manera eficiente el flujo del programa, sobre todo
en instrucciones de bifurcación como son las decisiones, ciclos y saltos de rutinas. La idea es
tener los saltos lo más cerca de las llamadas, siendo el salto lo más pequeño posible.
Ideas básicas:
• Se recorre el código buscando combinaciones de instrucciones que pueden ser
reemplazadas por otras equivalentes más eficientes.
• Se utiliza una ventana de n instrucciones y un conjunto de patrones de
transformación (patrón, secuencias, remplazan).
• Las nuevas instrucciones son reconsideradas para las futuras optimizaciones.
Ejemplos:
• Eliminación de cargas innecesarias
• Reducción de potencia
• Eliminación de cadenas de saltos
7.2 Costos
Los costos son el factor más importante a tomar en cuenta a la hora de optimizar ya que en ocasiones
la mejora obtenida puede verse no reflejada en el programa final, pero si ser perjudicial para el
equipo de desarrollo.
• La optimización de una pequeña mejora tal vez tenga una pequeña ganancia en tiempo o en espacio,
pero sale muy costosa en tiempo en generarla.
• Pero en cambio si esa optimización se hace por ejemplo en un ciclo, la mejora obtenida puede ser
N veces mayor por lo cual el costo se minimiza y es benéfico la mejora.
• Por ejemplo: for (int i=0; i < 10000; i++); si la ganancia es de 30 ms 300s.
7.2.1 Costo de ejecución (Memoria,
Registro, Pilas).
Los costos de ejecución son aquellos que vienen implícitos al ejecutar el programa.
• En algunos programas se tiene un mínimo para ejecutar el programa, por lo que el espacio y la
velocidad del microprocesadores son elementos que se deben optimizar para tener un mercado
potencial más amplio. Costos de ejecución
• Las aplicaciones multimedias como los videojuegos tienen un costo de ejecución alto por lo cual
la optimización de su desempeño es crítico, la gran mayoría de las veces requieren de
procesadores rápidos (e.g. tarjetas de vídeo) o de mucha memoria.
• Otro tipo de aplicaciones que deben optimizarse son las aplicaciones para dispositivos móviles.
Costos de ejecución
• Los dispositivos móviles tiene recursos más limitados que un dispositivo de cómputo convencional
razón por la cual, el mejor uso de memoria y otros recursos de hardware tiene mayor rendimiento.
• En algunos casos es preferible tener la lógica del negocio más fuerte en otros dispositivos y hacer
uso de arquitecturas descentralizadas como cliente/servidor o P2P.
7.2.2 Criterios para mejorar el código
La mejor manera de optimizar el código es hacer ver a los programadores que optimicen su código
desde el inicio, el problema radica en que el costo podría ser muy grande ya que tendría que
codificar más y/o hacer su código mas legible.
• Los criterios de optimización siempre están definidos por el compilador Criterios de optimización
• Muchos de estos criterios pueden modificarse con directivas del compilador desde el código o de
manera externa.
• Este proceso lo realizan algunas herramientas del sistema como los ofuscadores para código móvil
y código para dispositivos móviles.
7.2.3 Herramientas para el análisis
del flujo de datos
• Existen algunas herramientas que permiten el análisis de los flujos de datos, entre ellas
tenemos los depuradores y desambladores.
• La optimización al igual que la programación es un arte y no se ha podido sistematizar del todo.
