En informática , la especialización de algoritmos en tiempo de ejecución es una metodología para crear algoritmos eficientes para tareas informáticas costosas de ciertos tipos. La metodología se origina en el campo de la demostración automatizada de teoremas y, más específicamente, en el proyecto de demostración del teorema Vampiro .
La idea se inspira en el uso de la evaluación parcial para optimizar la traducción de programas. Muchas operaciones centrales en los demostradores de teoremas exhiben el siguiente patrón. Supongamos que necesitamos ejecutar algún algoritmo en una situación en la que un valor de es fijo para potencialmente muchos valores diferentes de . Para hacer esto de manera eficiente, podemos intentar encontrar una especialización de para cada fijo , es decir, un algoritmo tal , que ejecutar sea equivalente a ejecutar .
El algoritmo especializado puede ser más eficiente que el genérico, ya que puede explotar algunas propiedades particulares del valor fijo . Normalmente, se pueden evitar algunas operaciones que tendrían que realizarse si se sabe que son redundantes para este parámetro en particular . En particular, a menudo podemos identificar algunas pruebas que son verdaderas o falsas para , desenrollar bucles y recursividad, etc.
La diferencia clave entre la especialización en tiempo de ejecución y la evaluación parcial es que los valores de on en los que está especializado no se conocen estáticamente, por lo que la especialización tiene lugar en tiempo de ejecución .
También hay una diferencia técnica importante. La evaluación parcial se aplica a algoritmos representados explícitamente como códigos en algún lenguaje de programación. En tiempo de ejecución, no necesitamos ninguna representación concreta de . Sólo nos queda imaginar cuando programamos el procedimiento de especialización. Todo lo que necesitamos es una representación concreta de la versión especializada . Esto también significa que no podemos utilizar ningún método universal para especializar algoritmos, como suele ocurrir con la evaluación parcial. En cambio, tenemos que programar un procedimiento de especialización para cada algoritmo en particular . Una ventaja importante de hacerlo es que podemos utilizar algunos poderosos trucos ad hoc que explotan las peculiaridades de y la representación de y , que están más allá del alcance de cualquier método de especialización universal.
El algoritmo especializado debe representarse de una forma que pueda interpretarse. En muchas situaciones, generalmente cuando se van a calcular muchos valores seguidos, podemos escribirlo como un código de una máquina abstracta especial , y a menudo decimos que está compilado . Luego, el código en sí se puede optimizar adicionalmente mediante transformaciones que preserven la respuesta y que se basen únicamente en la semántica de las instrucciones de la máquina abstracta.
Las instrucciones de la máquina abstracta normalmente se pueden representar como registros. Un campo de dicho registro almacena una etiqueta de número entero que identifica el tipo de instrucción; se pueden usar otros campos para almacenar parámetros adicionales de la instrucción, por ejemplo, un puntero a otra instrucción que representa una etiqueta, si la semántica de la instrucción requiere un salto. Todas las instrucciones de un código se pueden almacenar en una matriz, lista o árbol.
La interpretación se realiza buscando instrucciones en algún orden, identificando su tipo y ejecutando las acciones asociadas con este tipo. En C o C++ podemos usar una declaración de cambio para asociar algunas acciones con diferentes etiquetas de instrucciones. Los compiladores modernos generalmente compilan una declaración de cambio con etiquetas de números enteros de un rango estrecho de manera bastante eficiente al almacenar la dirección de la declaración correspondiente a un valor en la celda -ésima de una matriz especial. Se puede aprovechar esto tomando valores para etiquetas de instrucciones de un pequeño intervalo de números enteros.
Hay situaciones en las que muchas instancias de están destinadas al almacenamiento a largo plazo y las llamadas de ocurren de forma diferente en un orden impredecible. Por ejemplo, es posible que tengamos que comprobar primero, luego , luego , y así sucesivamente. En tales circunstancias, la especialización a gran escala con compilación puede no ser adecuada debido al uso excesivo de memoria. Sin embargo, a veces podemos encontrar una representación compacta especializada para cada , que se puede almacenar con o en lugar de . También definimos una variante que funciona en esta representación y cualquier llamada a se reemplaza por , con la intención de hacer el mismo trabajo más rápido.
