Estoy trabajando en un lenguaje intermedio y una máquina virtual para ejecutar un lenguaje funcional, con un par de propiedades "problemáticos":¿Cuáles son algunas optimizaciones obvias para una máquina virtual que implementa un lenguaje funcional?
espacios de nombres- léxicas (cierres)
- dinámicamente creciente pila de llamadas
- Un tipo entero lento (bignums)
El lenguaje intermedio se basa en la pila, con una tabla hash simple para el espacio de nombres actual. Sólo para que pueda obtener una idea de lo que parece, aquí está la función McCarthy91:
# McCarthy 91: M(n) = n - 10 if n > 100 else M(M(n + 11))
.sub M
args
sto n
rcl n
float 100
gt
.if
.sub
rcl n
float 10
sub
.end
.sub
rcl n
float 11
add
list 1
rcl M
call-fast
list 1
rcl M
tail
.end
call-fast
.end
El "lazo grande" es sencillo:
- extraer una instrucción
- incremento del puntero de instrucción (o contador de programa)
- evaluar la instrucción
Junto con sto, rcl y mucho más, hay tres instrucciones para llamadas de función:
callcopia el espacio de nombres (en profundidad) y empuja el puntero de instrucción en la pila de llamadascall-fastes el mismo, pero sólo crea una copia superficialtailes básicamente un 'Goto'
La aplicación es muy sencillo. Para darle una mejor idea, aquí es sólo un fragmento de azar de la mitad del "bucle grande" (actualizado, véase más adelante)
} else if inst == 2 /* STO */ {
local[data] = stack[len(stack) - 1]
if code[ip + 1][0] != 3 {
stack = stack[:len(stack) - 1]
} else {
ip++
}
} else if inst == 3 /* RCL */ {
stack = append(stack, local[data])
} else if inst == 12 /* .END */ {
outer = outer[:len(outer) - 1]
ip = calls[len(calls) - 1]
calls = calls[:len(calls) - 1]
} else if inst == 20 /* CALL */ {
calls = append(calls, ip)
cp := make(Local, len(local))
copy(cp, local)
outer = append(outer, &cp)
x := stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
ip = x.(int)
} else if inst == 21 /* TAIL */ {
x := stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
ip = x.(int)
El problema es el siguiente: Llamada McCarthy91 16 veces con un valor de -10000 toma , cerca, como no hace ninguna diferencia, 3 segundos (después de optimizar la copia profunda, que agrega casi un segundo).
Mi pregunta es: ¿Cuáles son algunas técnicas comunes para optimizar la interpretación de este tipo de lenguaje? ¿Hay alguna fruta baja?
Usé rodajas para mis listas (argumentos, varias pilas, porción de mapas para los espacios de nombres, ...), así que hago este tipo de cosas por todos lados: call_stack[:len(call_stack) - 1]. En este momento, realmente no tengo ni idea de qué partes de código hacen que este programa sea lento. Cualquier consejo será apreciado, aunque principalmente estoy buscando estrategias generales de optimización.
Aparte:
puedo reducir el tiempo de ejecución de un poco eludiendo mis convenciones de llamada. La instrucción list <n> obtiene n argumentos de la pila y vuelve a colocar una lista de ellos en la pila, la instrucción args aparece en esa lista y vuelve a colocar cada elemento en la pila. Esto es, en primer lugar, comprobar que las funciones se invocan con el número correcto de argumentos y, en segundo lugar, que se pueden llamar funciones con listas de argumentos variables (es decir,(defun f x:xs)). Quitando eso, y también agregando una instrucción sto* <x>, que reemplaza sto <x>; rcl <x>, puedo bajarlo a 2 segundos. Todavía no es brillante, y tengo que tener este negocio list/args de todos modos. :)
Otro lado (esta es una pregunta larga que sé, lo siento):
perfilar el programa con pprof me habló muy poco (soy nuevo en ir en caso de que no es obvio) :-). Estos son los 3 mejores artículos según ha informado pprof:
16 6.1% 6.1% 16 6.1% sweep pkg/runtime/mgc0.c:745
9 3.4% 9.5% 9 3.4% fmt.(*fmt).fmt_qc pkg/fmt/format.go:323
4 1.5% 13.0% 4 1.5% fmt.(*fmt).integer pkg/fmt/format.go:248
Estos son los cambios que he hecho hasta ahora:
- Quité la tabla hash. En cambio, ahora paso solo punteros a las matrices, y solo copio de manera eficiente el alcance local cuando tengo que hacerlo.
- Reemplacé los nombres de las instrucciones con códigos de operación enteros. Antes, he perdido bastante tiempo comparando cadenas.
- La instrucción
call-fastse ha ido (el aumento de velocidad no era medible más después de los otros cambios) - En lugar de tener "int", "flotar" y las instrucciones "STR", sólo tienen uno
evaly evaluar las constantes en tiempo de compilación (compilación del bytecode que es). Entonces,evalsimplemente empuja una referencia a ellos. - Después de cambiar la semántica de
.if, podría deshacerme de estas pseudo-funciones. ahora es.if,.elsey.endif, con implosivos gotos y semántica de bloques similar a.sub. (some example code)
Después de implementar el analizador léxico, analizador, y el compilador de código de bytes, la velocidad se redujo un poco, pero no mucho. Al calcular MC (-10000) 16 veces, se evalúan 4,2 millones de instrucciones de código de bytes en 1,2 segundos. Aquí está a sample of the code it generates (desde this).
¡No utilice hashtables ni ningún otro tipo de búsqueda de nombres para los idiomas de ámbito léxico! No tiene ningún sentido en absoluto. Su compilador puede asignar registros estáticamente. Es muy fácil inferir el entorno capturado para cada abstracción lambda. –
Realmente no entiendo a qué te refieres todavía. ¿Podría armar un pequeño ejemplo, digamos "rcl" y "sto"? –
Use las ranuras numéricas para los argumentos, las variables y las variables de cierre. Introduzca códigos de operación como 'ldarg N', 'starg N', 'ldloc N', 'stloc N', 'ldenv N', 'stenv N'. Resuelva los nombres de las variables en los números al compilar. Construya las listas de variables capturadas mediante la comparación de las listas de variables libres y vinculadas para cada punto de abstracción lambda. Introduzca una instrucción especial para construir una instancia de cierre (debería ser similar a una llamada con una lista de variables para capturar). Es la forma en que se implementan la mayoría de los lenguajes funcionales (tanto VM como nativos). Puede ser muy eficiente. –