di  -  mercoledì 12 Ottobre 2011

All’ultima EuroPython tenutasi a Firenze ho avuto la possibilità di presentare un talk riguardo a un mio lavoro di ricerca sulla macchina virtuale di Python (chiamata CPython, essendo scritta in C) che trattava di alcune ottimizzazioni possibili sugli interi.

Penso sia interessante capire in che modo lavora internamente, per essere coscienti del peso che possono avere operazioni anche banali, come la classica somma di due numeri, ad esempio, di cui parlerò in questo articolo.

Preciso che parlerò dell’implementazione di CPython 2.6, ma il discorso è di carattere generale e rimane valido anche per la versione 2.7 (l’ultima del ramo 2.x), e per le precedenti. Comunque a grandi linee è applicabile anche ad altre virtual machine (d’ora in poi VM) basate sul concetto di stack.

Python è un linguaggio compilato in una forma astratta chiamata usualmente bytecode anziché in linguaggio macchina, come avviene invece in linguaggi come il C, Delphi, ecc..

In comune c’è comunque la compilazione, cioè la fase che prevede la lettura del sorgente e la generazione di un codice oggetto (che potrebbe anche essere un altro sorgente!), di cui però non ci occuperemo in questa fase per semplificare la trattazione.

Supponendo che il compilatore abbia già fatto il lavoro di compilazione di una semplice funzione che esegue la somma di due parametri:

def f(x, y):
  return x + y

vediamo come si presenta l’equivalente in bytecode:

 2 0 LOAD_FAST 0 (x)
 3   LOAD_FAST 1 (y)
 6   BINARY_ADD
 7   RETURN_VALUE

Al momento non ci addentreremo nei dettagli di più basso livello di questa rappresentazione (ci saranno altre occasioni), ma ci soffermeremo sulle sole istruzioni che vengono eseguite, per vedere concretamente quali passi sono necessari alla VM per portare a compimento quanto le abbiamo chiesto.

La prima istruzione LOAD_FAST serve per prelevare il valore della variabile locale x (cioè il primo parametro della funzione; tutti i parametri vengono inseriti nelle variabili locali, come in altri linguaggi) e inserirlo in cima allo stack utilizzato per la valutazione delle espressioni, che si presenterà così:

 -------
2|  x  | <---
 -------
1|  y  |
 -------
0|  x  |
 -------

La cima dello stack (contrassegnata con una freccia) è rappresentata dall’elemento di offset 2, cioè quello appena inserito. Gli altri due elementi rappresentano i due parametri passati alla funzione, che vengono conservati in due variabili locali.

CPython utilizza lo stesso vettore per memorizzare sia le variabili locali che i risultati delle espressioni; ciò si spiega il risultato appena mostrato.

Com’è facile intuire, eseguendo la seconda LOAD_FAST viene prelevato il valore della variabile locale y e inserito in cima allo stack, che assume di conseguenza la seguente forma:

 -------
3|  y  | <---
 -------
2|  x  |
 -------
1|  y  |
 -------
0|  x  |
 -------

con l’offeset 3 che adesso ne rappresenta la cima.

A questo punto lo stack contiene tutto ciò che serve, ed eseguendo la successiva operazione, BINARY_ADD, vengono prelevati i due valori dallo stack, sommati, e il risultato infine inserito sempre in cima allo stack:

 -------
2| x+y | <---
 -------
1|  y  |
 -------
0|  x  |
 -------

A questo punto l’ultima istruzione, RETURN_VALUE, altro non fa che prendere la cima dello stack e restituirla al chiamante, concludendo quindi l’esecuzione della funzione, e lasciando lo stack com’era all’inizio dell’esecuzione della funzione:

 -------
1|  y  | <---
 -------
0|  x  |
 -------

Sembra tutto molto semplice, ma questa, alla fine, rimane pur sempre un’astrazione, cioè una rappresentazione di più alto livello di quello che era scritto nel sorgente originale, per cui risulta ben lontana dalle operazioni che verranno poi effettivamente svolte dalla macchina, che sono decisamente numerose a fronte di istruzioni all’apparenza così semplici.

Un’ultima considerazione la merita lo stack. Guardandolo fin dalla prima rappresentazione e, soprattutto, focalizzando l’attenzione sulla seconda, appare evidente che, anche senza le due LOAD_FAST, esso contenga comunque i due elementi che servono per effettuarne materialmente la somma. Anche questa osservazione ha contribuito alla realizzazione del mio progetto WPython, di cui parlerò in futuro.

Nel prossimo articolo, invece, verranno analizzati “al microscopio” i dettagli interni (in C) di questi bytecode, per comprendere meglio le azioni eseguite e cominciando, quindi, a prendere confidenza col mondo della VM.

15 Commenti »

I commenti inseriti dai lettori di AppuntiDigitali non sono oggetto di moderazione preventiva, ma solo di eventuale filtro antispam. Qualora si ravvisi un contenuto non consono (offensivo o diffamatorio) si prega di contattare l'amministrazione di Appunti Digitali all'indirizzo info@appuntidigitali.it, specificando quale sia il commento in oggetto.

  • # 1
    abral
     scrive: 

    Secondo te, quale garantisce maggiori performance tra una virtual machine stack-based e una register-based su un’architettura come x86 o ARM?

  • # 2
    Antonio Barba (TheKaneB)
     scrive: 

    bella, mi sintonizzo per le prossime puntate :-)

  • # 3
    RickTheSnake
     scrive: 

    Recentemente ho dato un’occhiata molto superficiale a python per fare la conoscenza con questi “strani” linguaggi interpretati di alto livello, curiosità nata in larga parte proprio grazie agli articoli di cesare sull’argomento, e ne sono rimasto estremamente impressionato. i miei studi universitari mi impongono il C/C++, quindi per me il salto è notevole, una bella serie di articoli “sotto il cofano” è proprio la ciliegina sulla torta che ci voleva :D

  • # 4
    Cesare Di Mauro (Autore del post)
     scrive: 

    Spero di non allontanare gente, però. Il rischio è che, vedendo quante cose sono eseguite per una banale operazione come la somma, nemmeno si provi questo linguaggio o lo si abbandoni. :-/

    @abral: generalmente sono quelle register-based a offrire le migliori prestazioni.

    Quelle stack-based, però, sono molto semplici da implementare, ed è per questo che sono diffuse. A maggior se poi si farà uso di un compilatore JIT, che si occuperà di tirar fuori codice binario più o meno ottimizzato per l’architettura su cui si gira.

    Poi ci sono le “ibride”, come WPython, che cercano di prendere il meglio dai due mondi. Ma ne parlerò più avanti, dopo aver completato la panoramica su CPython.

  • # 5
    Andrea Del Bene
     scrive: 

    @abral
    Una differenza sostanziale di prestazioni si dovrebbe notare tra diverse architetture più che tra diersi tipi di virtual machine.
    I processori ARM di ultima generazione dispongono di una modalità chiamata ThumbEE che è stata ideata proprio per rendere più performante l’esecuzione di linguaggi compilati in bytecode e con un compilatore JIT.

  • # 6
    Mirco Tracolli
     scrive: 

    Interessantissimo argomento, non vedo l’ora di approfondire ancora la mia conoscenza di python :D

  • # 7
    Jena Plisskin
     scrive: 

    @6: lo stò imparando mooooolto lentamente. Un bel linguaggio di alto livello, lo vorrei usare per gli script in HPUX. E ti dirò è pure divertente :-)

  • # 8
    Cesare Di Mauro (Autore del post)
     scrive: 

    HP-UX è supportato: divertiti. :)

    Penso, inoltre, che sia azzeccatissimo come termine. Dopo tantissimi anni di programmazione con svariati linguaggi, dal bassissimo livello a quello alto, posso dire che da quando ho incontrato Python mi è tornato il sano divertimento di giocare, sperimentare, divertirmi appunto, con un questo fantastico linguaggio.

    @Andrea Del Bene: ThumbEE è applicabile ugualmente bene a entrambi i tipi di VM.

    Comunque giusto qualche giorno fa un utente ha postato un link in un mio precedente articolo in cui parlavo proprio di questa ISA. E’ una mail di un dipendente Google in cui parla delle difficoltà di farne uso nella VM di Android. In sostanza, bisognerebbe riscriverla da zero con ThumbEE in mente.

  • # 9
    pietro
     scrive: 

    Concordo con Cesare, dopo 10 C#, vb, c, js, …. , scoprire Python ti “ringiovanisce”, straordinario, efficiente, uno ottimo Framework e una quantità di librerie davvero notevole ed infine una vasta ed estremamente professionale community.
    Ultimamente sto portando avanti un progetto il cui core è interamente realizzato in Python con Cassandra e devo dire che i risultati sono davvero incoraggianti! ;)

    Una volta “scoperto” difficilmente lo si lascia!

  • # 10
    abral
     scrive: 

    @Cesare: ero sempre io che ho pubblicato quel link :D
    Volevo vedere cosa ne pensavi, soprattutto riguardo al fatto dell’interoperabilità con il normale codice ARM.
    Ultimamente mi sto interessando al campo delle virtual machine e dei compilatori. Volevo sapere se avevi qualche articolo/libro tecnico che potrei leggere a riguardo (naturalmente anche in inglese, non c’è problema). Ho alcuni libri sull’argomento, ma sono o molto molto complicati o molto formali o entrambi (ad esempio, Aho A.V.,Lam M.S.,Sethi R.,Ullman J. – Compilers principles techniques and tools).
    Ho anche un libro che a prima vista sembrava più pratico (Modern Compiler Implementation in C – Andrew W. Appel), ma non mi piace per niente com’è scritto.
    Grazie ;)

    P.S.: a chi piace Python ed è interessato all’argomento dei compilatori, consiglio questo video: https://blip.tv/pycon-us-videos-2009-2010-2011/pycon-2010-how-to-compile-python-x86-assembly-the-python-way-3283367
    Mi ha fatto capire molte cose (anche se non comprendo benissimo l’inglese parlato).

  • # 11
    Cesare Di Mauro (Autore del post)
     scrive: 

    @abral:

    @Cesare: ero sempre io che ho pubblicato quel link :D

    Ma LOL. Che gaffe. :D Purtroppo ho difficoltà a ricordare nomi, ma i contenuti di ciò che leggo in genere godono di una sorte migliore. :P

    Volevo vedere cosa ne pensavi, soprattutto riguardo al fatto dell’interoperabilità con il normale codice ARM.

    Bisognerebbe vedere di preciso il contesto. A naso direi che si tratta di un non-problema, perché a mio avviso si potrebbe realizzare una VM che venga eseguita interamente in modalità ThumbEE, inclusi i plugin scritti in C.

    Sì, li compilerei direttamente per ThumbEE; quindi assumendo questa modalità attiva. Al limite soltanto per qualche porzione critica i plugin potrebbero internamente passare ad ARM o Thumb-2.

    Se, invece, si fa ricorso a un compilatore JIT, non si pone il problema, perché potrebbe girare tutto in modalità ARM o, meglio ancora, Thumb-2 (si ottengono circa il 98% delle prestazioni del codice ARM, col 30% in meno di spazio).

    Ultimamente mi sto interessando al campo delle virtual machine e dei compilatori. Volevo sapere se avevi qualche articolo/libro tecnico che potrei leggere a riguardo (naturalmente anche in inglese, non c’è problema). Ho alcuni libri sull’argomento, ma sono o molto molto complicati o molto formali o entrambi (ad esempio, Aho A.V.,Lam M.S.,Sethi R.,Ullman J. – Compilers principles techniques and tools).

    Questo è considerato “la bibbia” e non può mancare nella libreria di un appassionato di parser, anche soltanto come riferimento.

    Ho anche un libro che a prima vista sembrava più pratico (Modern Compiler Implementation in C – Andrew W. Appel), ma non mi piace per niente com’è scritto.
    Grazie ;)

    Lo conosco di nome, ma non so com’è fatto.

    Personalmente dopo anni di YACC et similia da quando ho trovato ANTLR ( http://www.antlr.org/ ) sono arrivato al punto di non ritorno. Parafrasando il ritornello di un famosissimo gioco per Amiga: “Parsing was never been so much fun”. :D

    Ho fatto comprare il libro dell’autore all’azienda perché in alcuni progetti m’è capitato di dover scrivere velocemente dei parser, e l’ho trovato estremamente chiaro e ben fatto (non l’ho ancora finito di leggere, ma gli ho già dato un’occhiata generale, e l’impressione è che sarà lo stesso anche per la parte rimanente).

    Nel sito è citato anche Guido van Rossum (“I’m actually really liking ANTLR! I have a pretty darn good velocity with…”), che l’ha usato per il progetto Google App Engine.
    Non ti nascondo che ho pensato che sarebbe stato interessante scrivere un compilatore Python facendo uso di ANTLR: sarebbe di gran lunga più semplice e manutenibile dell’attuale implementazione.

    Tra l’altro il tool che è stato realizzato, ANTLRWorks, è FE-NO-ME-NA-LE per scrivere parser. Una goduria immensa. Se vedi già soltanto gli screenshot… |-Q________

    Ultima cosa e chiudo (che siamo pure OT), con la stessa sintassi (e sorgenti, eventualmente) ti permette di scrivere lexer, parser, e visitatore di Abstract Syntax Tree.

    P.S.: a chi piace Python ed è interessato all’argomento dei compilatori, consiglio questo video: https://blip.tv/pycon-us-videos-2009-2010-2011/pycon-2010-how-to-compile-python-x86-assembly-the-python-way-3283367

    Sono circa 3 ore, e al momento il tempo scarseggia. Comunque me lo segno, grazie. :P

    Mi ha fatto capire molte cose (anche se non comprendo benissimo l’inglese parlato).

    Purtroppo è così anche per me: non parlando inglese ho difficoltà di comprensione. Il tizio che parla nel filmato comunque si capisce abbastanza bene, se si guarda il video (e quindi i movimenti delle labbra).

  • # 12
    abral
     scrive: 

    @Cesare: ti ringrazio per le info :D
    Oltre ai parser, hai altre info riguardo gli altri argomenti “cari” alla compilazione? (code generation, ottimizzazioni, JIT)

    Il parser l’ho iniziato a scrivere a mano (per questioni di prestazioni), però questo ANTLR mi sembra molto potente. E soprattutto permette di concentrarsi sulle parti più importanti, mantenendo il codice semplice (come sottolineavi tu).

  • # 13
    Cesare Di Mauro (Autore del post)
     scrive: 

    Personalmente le prestazioni le valuterei dopo aver implementato il parser, per cui generalmente implemento il parser con ANTLR, che mi permette di arrivare velocemente a un prodotto funzionante (e con pochi sbattimenti di testa). A meno che la “velocità massima” non sia uno stretto requisito del progetto.

    Sugli altri argomenti francamente non ti so dire, perché l’esperienza me la sono fatta leggendo articoli, studiando emulatori (ad esempio WinUAE, che è stato uno dei primi a utilizzare il JIT 680×0 -> x86), smanettando con VM, ecc., quindi non ti saprei dare qualche testo di riferimento.

  • # 14
    abral
     scrive: 

    Grazie Cesare. Sto facendo qualche piccolo esperimento con Python per ora, usando il parser PLY. Mi hai aperto gli occhi, perché in effetti svilupparsi il parser a mano è una perdita di tempo e non permette di concentrarsi si parti ben più importanti.
    Vi farò sapere quando avrò qualche risultato da mostrare ;)

  • # 15
    Cesare Di Mauro (Autore del post)
     scrive: 

    Non avevo capito che conoscessi Python, altrimenti t’avrei consigliato di provare PLY, appunto, che è “meno traumatico” rispetto a un tradizionale generatore di parser.

    Ottimo, e condivido ovviamente la scelta: anche per me è importantissimo arrivare prima al prodotto, per poterlo testare (e giocarci un po’: coi parser questo è il “minimo sindacale” :D).

Scrivi un commento!

Aggiungi il commento, oppure trackback dal tuo sito.

I commenti inseriti dai lettori di AppuntiDigitali non sono oggetto di moderazione preventiva, ma solo di eventuale filtro antispam. Qualora si ravvisi un contenuto non consono (offensivo o diffamatorio) si prega di contattare l'amministrazione di Appunti Digitali all'indirizzo info@appuntidigitali.it, specificando quale sia il commento in oggetto.