Sto lavorando su un linguaggio intermedio e di una macchina virtuale per eseguire un linguaggio funzionale con un paio di proprietà "problematici":Quali sono alcune ovvie ottimizzazioni per una macchina virtuale che implementa un linguaggio funzionale?
namespace- lessicali (chiusure)
- dinamicamente crescente stack di chiamate
- A tipo intero lento (bignums)
La lingua intermedia è basata sullo stack, con una semplice tabella hash per lo spazio dei nomi corrente. Solo così si ottiene un idea di quello che sembra, ecco la funzione 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
Il "grande anello" è semplice:
- recuperare un'istruzione
- incremento del puntatore di istruzioni (o program counter)
- valutare le istruzioni
Insieme con sto, rcl e molto di più, ci sono tre istruzioni per la funzione chiamate:
callcopie del namespace (copia completa) e spinge il puntatore all'istruzione nello stack delle chiamatecall-fastè la stessa, ma solo di creare una copiatailè fondamentalmente un 'goto'
L'implementazione è davvero semplice. Per darvi un'idea migliore, qui è solo un frammento casuale dalla metà del "grande anello" (aggiornato, vedi sotto)
} 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)
Il problema è questo: Calling McCarthy91 16 volte con un valore di -10000 prende , vicino come non fa differenza, 3 secondi (dopo aver ottimizzato via la copia profonda, che aggiunge quasi un secondo).
La mia domanda è: quali sono alcune tecniche comuni per ottimizzare l'interpretazione di questo tipo di linguaggio? C'è del frutto a bassa attaccatura?
Ho usato le fette per le mie liste (argomenti, i vari stack, una porzione di mappe per gli spazi dei nomi, ...), quindi faccio questo genere di cose dappertutto: call_stack[:len(call_stack) - 1]. In questo momento, non ho idea di quali parti di codice rendano questo programma lento. Tutti i suggerimenti saranno apprezzati, anche se sono principalmente alla ricerca di strategie generali di ottimizzazione.
parte:
posso ridurre il tempo di esecuzione di un bel po 'per eludere le mie convenzioni di chiamata. L'istruzione list <n> recupera gli argomenti dello stack e inserisce nuovamente un elenco di essi nello stack, l'istruzione args si spegne da tale elenco e inserisce nuovamente ogni elemento nello stack. In primo luogo, è necessario verificare che le funzioni siano chiamate con il numero corretto di argomenti e, in secondo luogo, essere in grado di chiamare funzioni con elenchi di argomenti variabili (ad es.(defun f x:xs)). Rimuovendolo, e aggiungendo anche un'istruzione sto* <x>, che sostituisce sto <x>; rcl <x>, posso ridurlo a 2 secondi. Ancora non brillante, e devo avere questo business list/args comunque. :)
Un'altra parte (questa è una domanda lunga lo so, mi spiace):
Profiling il programma con pprof mi ha detto molto poco (Sono nuovo di andare in caso che non è ovvio) :-). Questi sono i primi 3 articoli come riportate da 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
Questi sono i cambiamenti che ho fatto finora:
- ho rimosso la tabella hash. Invece sto passando solo dei puntatori agli array e, quando necessario, copio in modo efficiente lo scope locale.
- Ho sostituito i nomi delle istruzioni con codici opzionali interi. Prima, ho perso un bel po 'di tempo a confrontare le stringhe.
- L'istruzione
call-fastè andato (l'aumento di velocità non era misurabile più dopo le altre modifiche) - Invece di avere "int", "galleggiare" e le istruzioni "STR", Ho solo una
evale valutare le costanti al momento della compilazione (compilazione del bytecode). Quindi loevalinvia semplicemente un riferimento ad essi. - Dopo aver modificato la semantica di
.if, ho potuto eliminare queste pseudo-funzioni. è ora.if,.elsee.endif, con gotos implicito e blocco-semantica simile a.sub. (some example code)
Dopo aver implementato il lexer, il parser e il compilatore bytecode, la velocità è diminuita leggermente, ma non così terribilmente. Calcolando MC (-10000) per 16 volte si valuta 4,2 milioni di istruzioni bytecode in 1,2 secondi. Ecco lo a sample of the code it generates (dal this).
Si prega di non utilizzare le hashtables e altri tipi di ricerca di nomi per le lingue con scope lessicale! Non ha alcun senso. Il compilatore può allocare i registri in modo statico. È molto facile dedurre il set di ambienti catturati per ogni astrazione lambda. –
Non capisco ancora cosa intendi. Potresti fare un breve esempio, per "rcl" e "sto"? –
Utilizzare gli slot numerici per gli argomenti, le variabili e le variabili di chiusura. Introduci codici opzionali come 'ldarg N', 'starg N', 'ldloc N', 'stloc N', 'ldenv N', 'stenv N'. Risolvi i nomi delle variabili nei numeri durante la compilazione. Costruire gli elenchi di variabili catturate confrontando gli elenchi di variabili libere e rilegate per ciascun punto di astrazione lambda. Introdurre un'istruzione speciale per creare un'istanza di chiusura (dovrebbe essere simile a una chiamata con un elenco di variabili da catturare). È come viene implementata la maggior parte dei linguaggi funzionali (sia VM che nativi). Può essere molto efficiente. –