En informática , la especialización de algoritmos en tiempo de ejecución es una metodología para crear algoritmos eficientes para tareas de cálculo costosas de cierto tipo. La metodología tiene su origen en el campo de la demostración automatizada de teoremas y, más específicamente, en el proyecto Vampire theorem prover .
La idea está inspirada en el uso de la evaluación parcial para optimizar la traducción de programas. Muchas operaciones básicas en los demostradores de teoremas presentan 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 . Por lo general, puede evitar algunas operaciones que tendría que realizar, 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 recursión, etc.
La diferencia clave entre la especialización en tiempo de ejecución y la evaluación parcial es que los valores de en los que se especializa 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 . Solo tenemos que imaginar cuándo 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 usar ningún método universal para especializar algoritmos, que suele ser el caso con la evaluación parcial. En cambio, tenemos que programar un procedimiento de especialización para cada algoritmo particular . Una ventaja importante de hacerlo es que podemos usar algunos trucos ad hoc poderosos 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 debe calcular sobre 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í puede optimizarse adicionalmente mediante transformaciones que preservan las respuestas y que se basan solo en la semántica de las instrucciones de la máquina abstracta.
Las instrucciones de la máquina abstracta se pueden representar normalmente como registros. Un campo de un registro de este tipo almacena una etiqueta de número entero que identifica el tipo de instrucción; otros campos se pueden utilizar para almacenar parámetros adicionales de la instrucción, por ejemplo, un puntero a otra instrucción que represente 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, una lista o un árbol.
La interpretación se realiza obteniendo instrucciones en un orden determinado, identificando su tipo y ejecutando las acciones asociadas a este tipo. En C o C++ podemos utilizar una sentencia switch para asociar algunas acciones con diferentes etiquetas de instrucción. Los compiladores modernos suelen compilar una sentencia switch con etiquetas de números enteros de un rango estrecho de forma bastante eficiente almacenando la dirección de la sentencia correspondiente a un valor en la celda -ésima de una matriz especial. Se puede aprovechar esto tomando valores para las etiquetas de instrucción 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 con diferentes en un orden impredecible. Por ejemplo, es posible que tengamos que comprobar primero, luego Failed to parse (SVG (MathML se puede habilitar mediante el complemento del navegador): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle \mathit{alg}(A_2,B_2)} , 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 especializada compacta 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 , destinada a hacer el mismo trabajo más rápido.
