di  -  mercoledì 13 maggio 2009

“Finalmente è finita”. Questa è la prima cosa che ho pensato alla chiusura della sessione di domande & risposte prevista al termine del talk di presentazione del mio progetto, come atto liberatorio dell’enorme tensione accumulata fino ad allora.

Stare “dall’altra parte” un’ora circa come oratore per uno che non si è mai cimentato in un’impresa del genere può essere fisicamente e psicologicamente molto pesante da sostenere.

A parte questo, come anticipato da Jacopo, lo scorso sabato ho tenuto un talk alla recente PyCon3 in cui ho parlato di una nuova implementazione di Python nella quale ho fatto convergere diverse mie idee su come ottimizzarla, e in particolare quella principale che riguarda l’uso di un nuovo modello di opcode, che ho chiamato wordcode

Riuscire a sintetizzare più di tre mesi di lavoro non era possibile già per un talk di un’ora, figuriamoci per un articolo di un blog tecnologico. Per cui, seguendo più o meno la stessa strada (che non è quella della sintesi, quanto della trattazione di precisi punti), toccherò alcuni argomenti chiave senza scendere nel dettaglio.

Tornando al nuovo modello di opcode, la scelta del nome “wordcode” non è casuale, visto che suona molto simile a bytecode. Infatti la rappresentazione sotto forma di bytecode è molto utilizzata nei linguaggi che fanno uso di virtual machine (il più famoso è Java), come appunto avviene attualmente anche per Python. Io ho scelto di “andare oltre”, proponendo l’uso di word (a 16 bit).

Ovviamente cambiamenti di questo tipo non vengono realizzati soltanto per proporre qualcosa di diverso, ma perché portano a dei guadagni tangibili in qualche area. Nello specifico il solo passaggio dal bytecode al wordcode ha permesso una riduzione in termini di spazio stimata fra il 22 e il 25% per la memorizzazione degli opcode delle istruzioni.

L’introduzione di opcode ad hoc per gestire alcuni casi comuni ha permesso di ridurre ulteriormente lo spazio occupato arrivando fino a un 30% circa, e al contempo anche il numero di istruzioni eseguite (che sostanzialmente in un colpo solo eseguivano lo stesso lavoro di due o più istruzioni).

Un punto molto importante è proprio quella riduzione del numero delle istruzioni eseguite. Questo perché in virtual machine di questo tipo un fattore che fa perdere tempo e, conseguentemente, prestazioni è il ciclo principale che si occupa di eseguire il fetch e la decodifica delle medesime.

Questo ciclo purtroppo deve effettuare necessariamente dei controlli (ad esempio per verificare la presenza di eventi che fossero eventualmente “scattati” durante l’esecuzione di un opcode, e che devono essere gestiti) che penalizzano un po’ le prestazioni. Meno si riesce a tornare a eseguire il loop, e più si guadagna in velocità.

Il modello a wordcode a cui ho pensato non serviva soltanto per recuperare spazio (cosa comunque utile), ma ciò che avevo in mente era la possibilità di implementare istruzioni più complesse che riuscissero a eseguire più lavoro riducendo pertanto il tempo che la CPU passa a eseguire le suddette operazioni “di servizio” nel ciclo principale.

Sia chiaro: implementare istruzioni più complesse era fattibile già col “vecchio” modello a bytecode, ma avrebbe saturato velocemente il numero opcode disponibili (ce ne sono soltanto 256), non potendo poi permettere di implementare tutte quelle necessarie a completare l’implementazione a cui pensavo.

Con le wordcode, invece, mi è stato possibile rifattorizzatore e raggruppare opportunamente le istruzioni, e ciò ha consentito di gestire con semplicità e notevole flessibilità l’introduzione di opcode che facessero uso di operazioni unarie e binarie, che sono fra le più usate e critiche per l’esecuzione di codice in Python.

Tutto ciò mi ha permesso di introdurre delle particolari “famiglie” di istruzioni che hanno reso la mia implementazione di Python simile a un modello a registri, comunemente usato in alcune virtual machine (ad esempio quella di LUA), pur mantenendo al contempo anche il modello a stack che era quello basato sulla vecchia versione. Insomma, un modello ibrido che cerca di sfruttare i pregi dell’una e dell’altra soluzione, senza stravolgere troppo il codice.

L’introduzione di queste famiglie di istruzioni ha permesso di compattare ulteriormente il codice (che adesso occupa mediamente il 44% dello spazio in meno), ma soprattutto di ridurre notevolmente il numero di istruzioni eseguite (mediamente il 38% in meno) da eseguire per portare a termine le stesse operazioni. Meno istruzioni vuol dire meno tempo della CPU passato nel loop della VM, coi vantaggi di cui parlavo prima.

Il modello a wordcode ha permesso anche di eliminare un collo di bottiglia del ciclo di principale, rappresentato dal fatto che per ogni opcode in precedenza era necessario controllare se fosse dotato o meno di argomento, ed eventualmente prelevarlo dalla sequenza di byte. Col nuovo modello concettualmente non esistono istruzioni non dotate di parametri: tutte ne hanno almeno uno, per cui tale controllo non è più necessario, evitando al processore di incappare in branch misprediction che capitano quando la suddetta verifica fallisce.

Un’altra cosa interessante è il fatto che, leggendo word e non byte, è possibile ottimizzare il numero di operazioni di load / store della CPU, consumando al contempo meno banda di memoria verso cache e memoria centrale.

Entrambe sono possibili perché la maggior parte delle istruzioni eseguite richiedono una sola word (2 byte), anziché i 3 byte della precedente implementazione. La word viene caricata in un colpo solo (con una sola load), mentre prima erano necessarie 3 distinte operazioni di load dei singoli byte.

Ho apportato poi diverse altre ottimizzazioni che hanno permesso di occupare meno spazio e ridurre il numero di istruzioni. Le aree toccate sono molte, per cui cito le principali: constant folding (più aggressivo, efficiente, e riconosce casi anche molto complessi), salti condizionati (ottimizzati), cicli (ci sono meno istruzioni), comprehension (meno istruzioni da eseguire nel ciclo di questi costrutti sintattici).

Ovviamente non posso trattare nel dettaglio tutto, perché Appunti Digitali non è un sito di divulgazione scientifica. Comunque ho creato un progetto su Google Code, in cui trovate i sorgenti, un pacchetto con l’eseguibile per Windows, e soprattutto le slide del talk.

Capisco che l’argomento non è dei più semplici, ma in ogni caso per qualunque dubbio, osservazione, chiarimenti, critiche (costruttive, ovviamente) sono a disposizione.

27 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
    cla
     scrive: 

    Che dire… da utente python (anche se lo ammetto, non molto evoluto) trovo la cosa estremamente interessante!

    Domanda: e’ una proposta di implementazione?
    Potremmo vederla in python ufficialmente oppure e’ progetto a se stante?

    Il BDFL che dice? :)

  • # 2
    Cesare Di Mauro
     scrive: 

    Non è una proposta di implementazione: è un’implementazione alternativa e praticamente completa (ci sono soltanto dei bug da fixare nella libreria di test; quindi il codice di produzione funziona).

    Non so ancora se verrà tutto o in parte integrato nella versione ufficiale. Il BDFL non c’è ancora pronunciato, mentre al momento ho ricevuto feedback molto positivi degli altri sviluppatori “ufficiali”, che mi hanno anche chiesto di effettuare un backport su Python 3 (attualmente funziona solo su Python 2.6.1).

    Per adesso ho un paio di release in programma per fixare qualche problemino, e poi passerò al backport.

    Poi si vedrà cosa ne pensa Guido.

  • # 3
    The3D
     scrive: 

    E in tre mesi hai fatto un lavorone del genere? Ma per lavoro (quindi hai sfruttato le ore lavorative) o per hobby?

    Complimenti

  • # 4
    Cesare Di Mauro
     scrive: 

    Sì, lavorando più che altro la notte e, quando possibile, qualche fine settimana.

    L’ho fatto per hobby, se negli hobby includiamo anche le pratiche masochisto-autolesionistiche. :D

    Grazie comunque. :)

  • # 5
    The3D
     scrive: 

    allora complimenti doppi…avessi io questa costanza, dopo che ho programmato 9 e passa ore nn ho nemmeno voglia di guardare una riga di codice da lontano :D

    Comunque, visto che hai parlato delle fasi di fetch-decode e della loro criticità in quanto overhead, hai pensato a qualche meccanismo di prefetching da implementare?

  • # 6
    Cesare Di Mauro
     scrive: 

    Sostanzialmente sono due le soluzioni che ho implementato.

    La prima è di considerare tutte le istruzioni dotate di parametro, in modo da evitare branch misprediction e, quindi, non avere cali di prestazioni quando si deve eseguire il loop.

    La seconda è quella di realizzare “macroistruzioni”, cioé istruzioni che eseguono più compiti, in modo da ridurre l’uso di istruzioni (che vengono sostanzialmente accorpate).

    Ovviamente c’è un limite a tutto ciò: non posso creare macroistruzioni per qualunque caso, e questo per due motivi.
    Il primo è che la tabella degli opcode è limitata al massimo a 256 valori. :D
    Il secondo è che si complicherebbe notevolmente il codice del peephole optimizer, e inoltre il codice della virtual machine diventerebbe troppo grande, costringendo a eseguire flush della cache del codice.

    P.S. Non hai idea di quante volte m’è capitato di addormentarmi davanti alla tastiera. :D Ma volevo a tutti i costi arrivare alla PyCon con la mia implementazione funzionante.
    Per il momento la notte finalmente riesco a dormire un bel po’ di ore. :D :D :D

  • # 7
    Giullo
     scrive: 

    complimenti cesare, per uno cui non piace il c ne devi aver smazzato parecchio in sti 3 mesi ;)

  • # 8
    Giulio
     scrive: 

    Cesare, non conosco bene python ma ho intenzione di impararlo, in ogni caso complimenti per il lavoro che stai facendo.

  • # 9
    Cesare Di Mauro
     scrive: 

    @Giullo: diciamo che è stato una tortura. Tra l’altro lavorare a basso livello mi ha portato nuovamente a pensare di fare delle schifezze immonde sul codice (tipo usare goto).

    @Giulio: te lo consiglio perché è un ottimo linguaggio. Semplice, veloce da imparare, e col quale impieghi poco tempo per risolvere problemi.

    Grazie a tutti. :)

  • # 10
    Marco
     scrive: 

    Complimenti! Ottimo lavoro!!!

  • # 11
    Medicina
     scrive: 

    Complimenti Cesare per il lavoro. Vedrò di provare il tutto, al momento però ci sono dei problemi con l’archivio per Windows che hai pubblicato sul sito, dove python.exe non risulta eseguibile. Proverò a compilarlo più tardi.

  • # 12
    Cesare Di Mauro
     scrive: 

    Strano, perché ho scaricato il pacchetto, l’ho scompattato, e sono riuscito a eseguirlo:

    C:\tmp\Python-2.6.1 BIN>python
    WPython “CISCy” 2.6.1 (r261:67515, May 1 2009, 15:13:54) [MSC v.1500 32 bit (Intel)] on win32
    Type “help”, “copyright”, “credits” or “license” for more information.

  • # 13
    Medicina
     scrive: 

    Ok, se c’è installato Python per Windows funziona, altrimenti spunta fuori un messaggio di sistema che invita a reinstallare il software. Sai, usando Cygwin…

    Sto provando a compilarlo su Linux, qui il problema è che l’include Python_ast.h non viene generato per qualche motivo con la dichiarazione di Const_kind, e quindi la compilazione viene interrotta.

  • # 14
    Cesare Di Mauro
     scrive: 

    L’ho scaricato su un portatile in cui non c’è installato Python e ha funzionato. :|

    Su Linux, dopo averlo configuratoro (con ./configure immagino), copia il mio file Python_ast.h su quello che è stato generato automaticamente.

  • # 15
    The3D
     scrive: 

    Devo dire che basandomi solo sull’articolo non avevo capito al 100% la risposta che mi avevi dato sul prefetching. Sono andato a leggermi le dispense e ora ho tutto + chiaro! In realtà quindi non hai usato un’intera word per gli opcode (cosa che mi era sembrata di leggere dall’articolo, anche se leggendolo + attentamente e dopo aver letto le slides si capisce anche da li) ma in realtà hai usato un byte per gli opcode + 1 byte per operando fisso. Dalla prima (superficiale) lettura mi era parso invece di aver capito che avessi usato una intera word come opcode per andare oltre il limite delle 255 istruzioni, e oltre alla word per l’opcode ogni istruzione avesse un parametro obbligatorio per evitare il salto condizionato nel loop principale. Comunque quando intendevo prefetching mi riferivo a un qualche meccanismo di pipelining interno alla VM per velocizzare. Che so, la butto lì: usare 2 worker thread separati per fetch ed execute, in modo da implementare una rudimentale pipeline a 2 stadi.

    Comunque consiglio a tutti di leggere le diapositive, sono illuminanti :)

  • # 16
    Cesare Di Mauro
     scrive: 

    No, di pipeline non se ne parla e non si può implementare questo modello. L’esecuzione purtroppo è strettamente sequenziale.

    Sulla wordcode è esattamente come hai capito: la word è divisa in due parti, col primo byte che contiene l’opcode vero e proprio da eseguire, e il secondo byte il suo parametro obbligatorio.

    In questo modo, come dicevo, ogni opcode ha SEMPRE un parametro a 8 bit (estendibile poi a 16 o 32 bit con un’apposito opcode), quindi si evita appunto la branch misprediction che in precedenza era dovuta al fatto di dover distinguere fra opcode con e senza parametri.

    Ovviamente anche qui gli opcode possono essere al massimo 256, ma il vantaggio è rappresentato dal fatto che tutti gli opcode con operatori unari, binari, ternari, che manipolano lo stack, che manipolano lo stack e possono sollevare eccezioni, e infine quelli “senza parametro” che fanno operazioni particolari (es: ritornare dalla funzione, eseguire il break di un loop, ecc.) sono tutti racchiusi in 6 opcode speciali.

    Quindi c’è un netto risparmio di spazio nella opcode table, perché tutti questi casi sono gestiti da 6 soli opcode. Inoltre se ci fosse la necessità di aggiungere altre istruzioni dello stesso tipo (sempre senza parametro), basterebbe estendere la sub-opcode table associata.

    In sostanza con questa implementazione è possibile avere 6 * 256 = fino a 1536 istruzioni senza parametri.

    Poi ovviamente ci sono sempre le 250 entry per tutti gli altri opcode con parametro vero e proprio.

    Sì, dalle slide si capisce meglio. Qui nell’articolo non ho potuto approfondire, causa mancanza di spazio.

  • # 17
    Medicina
     scrive: 

    L’ho eseguito su Linux e ho fatto alcuni piccoli benchmark, operazioni semplici tipo aggiungere un elemento a un set e a un dizionario, risultano rispettivamente circa 25% e 4,7% più veloci sul mio Barton. Il Pybench mi restituisce risultati sensibilmente più bassi (dictWithFloatKeys: -6,4%, ListSlicing: -0,83%, SimpleFloatArithmetic: -48,2%, SimpleIntFloatArithmetic: -52,1%). Ben fatto Cesare. Speriamo che il tutto regga all’esame e venga presto resa ufficiale. :)

  • # 18
    Medicina
     scrive: 

    “rispettivamente circa 25% e 4,7% più veloci sul mio Barton.”

    Non ho fermato in tempo l’invio del post. Dovevo scrivere: 12% e 6%.

  • # 19
    Cesare Di Mauro
     scrive: 

    Fantastico: mi serviva proprio un test su Linux, sei il primo che s’è cimentato con successo. :D

    Da quel che ho potuto vedere i guadagni maggiori sono sulle macchine vecchie. Le slide portano i risultati di un vecchio Athlon64 2800+ socket 754 con 2GB di memoria DDR400.

    Il tuo Barton è il modello “precedente”, se mi passi il termine (e l’ultimo della famiglia Athlon; il top di gamma tra l’altro :D), quindi leggermente più vecchio, e conferma il trend che ho rilevato.

    Non ho ancora provato su architetture ARM usate per i sistemi embedded, smarthphone e palmari. Sarebbe bello avere qualche dato anche per questi. Sperando in una conferma del trend, questa versione potrebbe rivelarsi il candidato ideale per questi sistemi. :)

    Grazie per i test!!!

  • # 20
    Franci
     scrive: 

    Cesare, grazie per il lavoro.
    Cosa ne pensi di Ruby e del notevole salto prestazionale della versione 1.9x (che dai test in rete supera quelle di Python, anche se forse non quelle della combinata Python+Psyco)?

  • # 21
    Cesare Di Mauro
     scrive: 

    Il salto prestazionale di Ruby 1.9 deriva più che altro dall’ottimizzazione effettuata per quanto riguarda la chiamata a funzioni, che è stata pesantemente riscritta.

    In questo caso (che comunque è molto frequente, sia chiaro), Python rimane abbastanza indietro.
    Questo complice anche la volontà da parte degli sviluppatori Python, e in particolare di Guido, di NON implementare ottimizzazioni nel caso di tail recursion.

    In ogni caso Python si mostra mediamente superiore. Se prendiamo la famosa suite di benchmark “Computer Language Shootout”, notiamo che il trend è proprio questo: http://shootout.alioth.debian.org/u32q/benchmark.php?test=all&lang=python&lang2=yarv&box=1

    Su 11 test Ruby “vince” soltanto su 4 per quanto riguarda il tempo di calcolo; 3 ne “vince” per quanto riguarda la memoria consumata, mentre per altri 3 il consumo è “pari”.

    Non è un caso che nei test che girano in rete vengano utilizzati “guarda caso” funzioni ricorsive. :D

    Ma la realtà, come puoi vedere, è ben diversa, e mostra ancora una predominanza di Python.

    Poi all’appello manca la mia soluzione, che non è specializzata sulle chiamate a funzioni, ma che contribuisce globalmente a migliorare ancora di più il quadro in favore di Python. :D :D :D

  • # 22
    Franci
     scrive: 

    Grazie per i chiarimenti.
    Detto questo, mi pare che Python sia adatto e piu’ efficiente del php come linguaggio open source lato server siti web: perche’ allora si continua a insistere sul Php e non Python come P di LAMP?

  • # 23
    Cesare Di Mauro
     scrive: 

    Perché PHP ha il vantaggio d’essere “partito per primo” su un mercato sostanzialmente vergine (quello delle pagine web dinamiche).

    Per PHP esistono montagne di framework e librerie. Inutile negarlo. E questo va a suo favore.

    Fortunatamente col tempo anche Python s’è “arricchito” in questo settore dell’informatica, ma riuscire a rosicchiare mercato al PHP richiede notevoli sforzi e tempo, grazie al vantaggio che ha saputo costruire.

    Oggi se chiedi uno spazio per la tua applicazione web, trovi miriade di provider che ti offrono PHP e MySQL. Trovarne qualcuno che fa hosting per Python è raro (e non parliamo poi di engine SQL diversi da MySQL: per FireBird, ad esempio, non ne ho ancora trovati).

  • # 24
    catonano
     scrive: 

    Cesare,

    ciao, ci siamo incontrati al PyCon, io sono Adriano di Infomedia, ti abbiamo chiesto di scrivere qualcosa su questo tuo lavoro, previa indicazione da parte nostra su cosa coprire.

    Poi però abbiamo realizzato di non avere il tuo contatto :-(

    Adesso ritrovo questo post: fantastico ! ;-)

    Una cosa già l’hai chiarita: hai fatto questa cosa per hobby e non per lavoro !

    Accipicchia, hai avuto una determinazione invidiabile ! Complimenti !

    La mia email presso Infomedia è:

    catonano chiocciola infomedia punto it

    Grazie !
    Ciao
    Adriano

  • # 25
    Medicina
     scrive: 

    Penso che a qualcuno possa interessare la versione aggiornata del progetto:

    http://code.google.com/p/wpython2/

    C’era un thread sul forum ma non riesco più a trovarlo…

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

    Il thread lo trovi qui: http://www.hwupgrade.it/forum/showthread.php?t=1981141

    Comunque a breve rilascerò la versione 1.1 di wpython, sempre nel sito di cui hai riportato il link. :)

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

    Ieri sera ho rilasciato la versione 1.1 del progetto.

    Al solito, lo trovate qui http://code.google.com/p/wpython2/downloads/list oppure sul repository Mercurial.

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.