- Optimizaciones Globales
- Optimizaciones de Ciclo
- Optimizaciones 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. Se realiza reestructurando el código de tal forma que el nuevo código generado tenga mayores beneficios.
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 folding 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 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
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
Pre-calcular 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
- Eliminación secuencias nulas
- Reducción de potencia
- 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 instrucciones en ensamblador.
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
Elaborado por:
-Axel Gutiérrez de la Cruz
-Joseph Aldahir López Hernández
Referencias
Muñoz, E. (12 de Mayo de 2014). Tipos de Optimización.
Recuperado el 1 de Abril de 2022, de Prezi.com:
https://prezi.com/gls_boi1bbcx/tipos-de-optimizacion/
Rojas, M. J. (s.f.). Unidad
VII Optimización. Recuperado el 1 de Abril de 2022, de
http://dsc.itmorelia.edu.mx: http://dsc.itmorelia.edu.mx/~jcolivares/courses/ps207a/ps2_u7.pdf
Zunun, V. L. (18 de
Octubre de 2019). Tipos de Optimización. Obtenido de Blogger.com:
https://vilmalauramoraleszunun.blogspot.com/2019/10/tipos-de-optimizacion.html