Quali strategie spedizione codice operativo vengono utilizzati nella interpreti efficienti?

Question

Quali tecniche promuovere efficiente invio codice operativo per fare un interprete veloce? Ci sono alcune tecniche che funzionano bene solo su hardware moderno e altri che non funzionano bene più a causa di progressi hardware? Quali compromessi devono essere effettuate tra facilità di implementazione, la velocità, e la portabilità?

Sono contento che l'attuazione di Python C sta finalmente muovendo al di là di una semplice implementazione per switch (opcode) {...} codice operativo spedizione verso filettatura indiretta come un'opzione di compilazione, ma sono meno contento che ci sono voluti 20 anni per arrivarci. Forse se ci documentiamo queste strategie sul StackOverflow la lingua successiva sarà ottenere velocemente più velocemente.

Answer 1

Ci sono una serie di articoli su diversi tipi di spedizione:

M. Anton Ertl e David Gregg, Ottimizzazione indiretta Precisione Branch Prediction in Interpreti Virtual Machine , in Atti del Convegno ACM SIGPLAN 2003 sulla progettazione linguaggio di programmazione e attuazione (PLDI 03), pp. 278-288, San Diego, California, giugno 2003.

M. Anton Ertl e David Gregg, Il comportamento di interpreti di macchine virtuali efficienti sulla moderno architetture , in Atti della Conferenza europea 7 ° calcolo parallelo (Europar 2001), pp. 403-412, LNCS 2150, Manchester, agosto 2001.

Un eccellente sommario è fornito da Yunhe Shi nella sua tesi di dottorato .

Inoltre, qualcuno ha scoperto una nuova tecnica a pochi anni fa, che è valida ANSI C.

Answer 2

Befor di iniziare qualsiasi cosa, controllare Lua .

E 'piccolo (150Kb), puro ANSI C, funziona su qualsiasi cosa abbia compilatore C. Molto veloce.

E, cosa più importante - il codice sorgente è pulito e leggibile. Vale la pena di verificare.

Answer 3

threading indiretta è una strategia in cui ogni applicazione ha un proprio codice operativo JMP al successivo codice operativo. La patch per l'interprete Python simile a questa:

add:
    result = a + b;
    goto *opcode_targets[*next_instruction++];

opcode_targets Mappe l'istruzione in bytecode del linguaggio per la locazione di memoria di attuazione codice operativo. Questo è più veloce perché predizione delle diramazioni del processore può fare una previsione diversa per ogni bytecode, in contrasto con un switch dichiarazione che ha una sola istruzione di salto.

Il compilatore deve supportare avanzamento calcolato per questo lavoro, che significa principalmente gcc.

threading diretto è simile, ma nella filettatura diretta matrice di codici operativi viene sostituito con puntatori ai implentations codice operativo in questo modo:

goto *next_opcode_target++;

Queste tecniche sono utili solo perché processori moderni sono pipeline e devono eliminare le condotte (lenta) su un ramo pronosticate male. I progettisti dei processori messi in branch prediction per evitare di dover cancellare il gasdotto come spesso, ma branch prediction funziona solo per i rami che sono più propensi a prendere un particolare percorso.

Answer 4

Just-in-time di compilazione è uno.

Answer 5

Una grande vittoria è per memorizzare il codice sorgente in una forma intermedia, anziché rifare analisi lessicale e analisi durante l'esecuzione.

Questo può variare tutta la strada da solo memorizzare i gettoni, per Forth codice di stile filettato e alla compilazione JIT.

Answer 6

Il benchmarking è una buona tecnica a fare qualsiasi cosa veloce sulla data piattaforma (s). Test, affinare, prova ancora una volta, a migliorare.

Non credo che si può ottenere qualsiasi risposta migliore. Ci sono molte tecniche per rendere interpreti. Ma ti do un consiglio, non fare compromessi, basta scegliere quello che si ha realmente bisogno e perseguire tali obiettivi.

Answer 7

Ho trovato un post sul blog sull'attuazione interprete filettato che è stato utile.

L'autore descrive GCC threading label-based e anche il modo di fare questo in Visual Studio utilizzando assembler inline.

http://abepralle.wordpress.com/2009/01/25/how-not-to-make-a-virtual-machine-label-based-threading/

I risultati sono interessanti. Lo riferisce il miglioramento delle prestazioni del 33% quando si usa GCC ma sorprendentemente l'attuazione assembly inline Visual Studio è 3 volte più lento!

Answer 8

La questione è un po 'vago. Ma, a quanto pare si sta chiedendo di scrivere un interprete.

Gli interpreti in genere utilizzano componenti di analisi tradizionali: lexer, parser, e l'albero di sintassi astratta (AST). Questo permette al progettista di leggere e interpretare sintassi valida e costruire una struttura ad albero di comandi con gli operatori associati, parametri, ecc.

Una volta in forma AST, l'intero ingresso viene token e l'interprete può iniziare l'esecuzione attraversando l'albero.

Ci sono molte opzioni, ma recentemente ho usato ANTLR come un generatore di parser che può costruire parser in vari bersaglio lingue, tra cui C / C ++ e C #.