Eseguire una semplice somma in CPython si sta rivelando più complicato di quel che si poteva immaginare, principalmente a causa del diverso “modello” dei dati manipolati rispetto al linguaggio C (col quale è implementata la macchina virtuale).
CPython, come già detto, gestisce qualunque dato facendo uso di una gerarchia che discende dall’oggetto (struttura in C) PyObject, che si specializza poi in base al tipo (classe) di oggetto modellato.
Ritornando al codice della somma, una volta appurato che entrambi gli oggetti siano di tipo intero (puntatori a strutture PyIntObject per la precisione), è possibile procedere allo svolgimento dell’effettiva operazione, di cui riporto soltanto le righe di codice essenziali:
/* INLINE: int + int */ register long a, b, i; a = PyInt_AS_LONG(v); b = PyInt_AS_LONG(w); i = a + b; if ((i^a) < 0 && (i^b) < 0) goto slow_add; x = PyInt_FromLong(i);
Come anticipato dal titolo dell’articolo, il primo problema che si presenta è quello di passare dal “mondo Python” a quello del C. La VM di per sé manipola soltanto PyObject, ma alla fine è pur sempre implementata in C, ed è usando questo linguaggio che si devono implementare tutte le operazioni che supporta la gerarchia dei suoi dati.
Nello specifico, un PyIntObject consente di effettuare operazioni con interi a 32 o 64 bit, a seconda dell’architettura del processore. La sua struttura l’abbiamo già vista ed è molto semplice:
typedef struct {
Py_ssize_t ob_refcnt;
struct _typeobject *ob_type;
long ob_ival;
} PyIntObject;
ob_ival rappresenta ovviamente l’intero in questione.
A questo punto passare da Python a C tramite l’uso della macro PyInt_AS_LONG, come si può intuire, risulta essere abbastanza semplice:
#define PyInt_AS_LONG(op) (((PyIntObject *)(op))->ob_ival)
Si tratta banalmente di estrarre proprio il campo ob_ival di entrambi gli oggetti Python, e copiarlo nelle variabili a e b definite all’interno del blocco.
A questo punto la somma si ottiene immediatamente, come si può vedere dalla riga successiva, ma ottenuto il risultato “grezzo” (memorizzato nella variabile i) si pone il problema di ritornare nel mondo di Python creando un opportuno oggetto che lo rappresenti correttamente.
In teoria sarebbe anch’essa un’operazione semplice: basterebbe creare un nuovo oggetto PyIntObject, e memorizzare nel campo ob_val il valore appena calcolato. In realtà ciò non è immediatamente possibile per un paio di motivi.
Il primo e più importante è che l’operazione avrebbe potuto generare un overflow (o underflow), poiché il tipo long del C non è in grado di rappresentare interi di grandezza arbitraria, ma soltanto quelli consentiti dall’architettura su cui gira la VM (interi a 32 o 64 bit, come già detto).
L’istruzione if serve proprio allo scopo: verificare se ricadiamo in questo caso (che risulta abbastanza raro, per la verità: 32 bit sono sufficienti per la stragrande maggioranza delle operazioni, come c’insegna l’esperienza) e saltare all’etichetta slow_add che si occupa di eseguire il codice più generico che gestisce operator overloading e “promozione” dei risultati (in particolare quelli numerici).
E’ bene sottolineare che questa verifica assume per buona una pratica molto diffusa, ma non standardizzata dal comitato ANSI & ISO: il fatto che un overflow o underflow comporti un cambio di segno del risultato di un’operazione binaria. Questo ha provocato di recente problemi con le ultime versioni del compilatore GCC (sembra soltanto su OS X), com’è stato riportato, e ha richiesto l’aggiunta di un’apposita opzione di compilazione che forza tale assunzione.
A questo punto (e arriviamo al secondo motivo di cui parlavo) se il risultato non ha generato un overflow (quindi un long è sufficiente per rappresentarlo), possiamo finalmente convertirlo in un oggetto PyIntObject facendo uso della funzione PyInt_FromLong che si occupa proprio di effettuare quest’operazione.
Finora abbiamo visto che in CPython vengono utilizzate numerose macro per velocizzare operazioni comuni. Questa volta si fa ricorso a una funzione (definita nel file intobiect.c, che si occupa di gestire gli oggetti PyIntObject), e non a caso:
#define NSMALLNEGINTS 5
#define NSMALLPOSINTS 257
static PyIntObject *small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
PyObject *PyInt_FromLong(long ival)
{
register PyIntObject *v;
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
v = small_ints[ival + NSMALLNEGINTS];
Py_INCREF(v);
return (PyObject *) v;
}
#endif
if (free_list == NULL) {
if ((free_list = fill_free_list()) == NULL)
return NULL;
}
/* Inline PyObject_New */
v = free_list;
free_list = (PyIntObject *)Py_TYPE(v);
PyObject_INIT(v, &PyInt_Type);
v->ob_ival = ival;
return (PyObject *) v;
}
Non spiegherò riga per riga come funziona, limitandomi a una trattazione di massima, ma comunque sufficiente a comprendere bene i meccanismi che scattano quando c’è da convertire un intero in un PyIntObject.
La definizione delle macro NSMALLNEGINTS e NSMALLPOSINTS, oltre che del successivo vettore small_ints, serve a gestire una cache di PyIntObject già istanziati per rappresentare tutti gli interi compresi fra -5 (NSMALLNEGINTS) e 256 (NSMALLPOSINTS – 1) inclusi, poiché si tratta di valori utilizzati molto spesso e il caching consente di velocizzare l’operazione di conversione in intero, oltre che ottimizzare l’uso della memoria (grazie al riutilizzo degli stessi oggetti facendo ricorso al meccanismo del reference counting).
La parte iniziale di PyIntObject serve proprio a questo: controllare se il risultato (passato come unico parametro) ricade in quest’intervallo, e in tal caso prelevare l’oggetto PyIntObject corrispondente, incrementarne il reference count tramite l’apposita macro Py_INCREF, e restituire immediatamente tale oggetto.
Al contrario se la condizione non è verificata, sarà necessario ricorrere all’apposita trafila prevista per il caso peggiore: allocare memoria per un oggetto di tipo PyIntObject, inizializzare la struttura di base PyObject (quindi i campi ob_ref e ob_type che si occupano rispettivamente di tenere conto del reference counting e del tipo / classe dell’oggetto stesso), memorizzare il valore desiderato e infine restituirlo.
Preciso che tutte queste operazioni sono svolte da una funzione già esistente, PyObject_New, ma per evitare una chiamata a funzione (e ritorno) il suo codice è stato “inglobato” in PyInt_FromLong, sempre per il solito mantra della maggior velocità di esecuzione che permea la VM.
Nel prossimo articolo dedicato a CPython vedremo a grandi linee anche il codice che si occupa di “sommare” (concatenare) due stringhe, e la finalizzazione del codice relativo al bytecode BINARY_ADD.
Ciao Cesare, ho due curiosità! :-)
1) come hanno determinato che gli interi più utilizzati sono compresi nel range -5..257? Mi piacerebbe sapere perchè proprio -5 e non -6 o -4… Ne sai qualcosa?
2) Nel caso in cui l’intero non sia nella “cache dei piccoli” e bisogna istanziare un nuovo oggetto entra in ballo free_list: qual’è il suo scopo? In particolare prima di utilizzarla si controlla se è NULL e in tal caso c’è un ulteriore controllo sul buon fine di un’operazione che la vede coinvolta (fill_free_list).
A che serve quell’operazione? In che occasioni può andare storto qualcosa?
Articolo interssante, come i precedenti (e finalmente si entra nei dettagli) :-D
Prima o poi dovevamo arrivarci. :P
Allora:
1) Credo che abbiano effettuato delle simulazioni con delle applicazioni reali, tenendo traccia delle varie allocazioni e disallocazioni.
Personalmente ho fatto lo stesso, ma per monitorare quale costanti intere erano utilizzate all’interno dei bytecode, e la tendenza è proprio quella: in quel range si trovano i valori più frequenti.
2) free_list è una lista di oggetti PyIntObject che sono stati precedentemente utilizzati, e inseriti in questa lista quando sarebbero dovuti essere allocati.
In questo modo anziché deallocare memoria per poi allocarla quando serve nuovamente, il sistema tiene traccia di tutti gli oggetti PyIntObject già allocati e che sono liberi di essere usati nuovamente (basta sovrascrivere il ob_ival col nuovo valore, e rimettere a posto ob_type che internamente viene usato per concatenare la lista, sempre per il solito matra delle prestazioni e, questa volta, dello spazio).
Il controllo all’inizio serve per capire se siamo nella condizionale iniziale, cioè se l’interprete non ha ancora allocato alcun intero. In questo caso siamo alla prima allocazione, per cui la lista va riempita con alcuni elementi allocando un blocco di memoria di una certa dimensione, calcolando quante strutture di tipo PyIntObject può “ospitare”, e infine inizializzando opportunamente tutti questi nuovi elementi.
Poiché l’allocazione del grosso blocco di memoria di memoria può non andare a buon fine, c’è quell’ulteriore controllo.
Una volta che siamo sicuri che la lista contiene almeno un elemento da cui attingere, lo si preleva e si inizializza impostando il campo ob_type e ob_ival.
In effetti ci siamo parecchio addentrati nella VM. :)
Capito, un’altro dei maccanismi di caching della VM, a scopo di efficienza. Sospettavo qualcosa del genere, ma le tue spiegazioni sono state illuminanti.
Solo un’altro paio di cose: ma free_list non viene proprio mai deallocata dall VM? Sospetto il contrario… magari al superamento di una certa dimensione? Entrano in gioco anche considerazioni circa il garbage collector, forse?
Di che dimensioni stiamo parlando, circa il blocco di memoria riservata alla sua inizializzazione?
All’incirca 1K.
Come avevi intuito, ogni tanto (quando viene eseguito un clean-up “pesante”) il garbage collector richiama una funzione (PyInt_ClearFreeList) di intobject.c per liberare quanta più memoria allocata possibile.
Noto che ci sono delle direttive che permettono di non considerare il codice per gli interi “piccoli”.
Perché ci sono queste direttive? Può dare dei problemi quel codice in talunne particolari condizioni?
PS. A volte ho l’impressione che in C il nome delle variabili siano poco intuitive. Tipo, ob_ival io l’avrei chiamata, come in Javese, integerValue.
Io l’avrei chiamata Value (tanto sappiamo che già è un intero), in pascalese. :D
Riguardo alle domande che poni, penso che l’introduzione del caching degli interi sia avvenuto dopo la normale implementazione, e si sia voluto lasciare comunque la possibilità di far funzionare CPython alla vecchia maniera.
Il motivo non lo so, ma posso azzardare qualche ipotesi. La prima è per una questione semantica, perché il caching di questi valori di fatto cambia la semantica del linguaggio.
Ti faccio un piccolo esempio:
>>> i = 1
>>> j = 1
>>> i is j
3: True
>>> i = 257
>>> j = 257
>>> i is j
4: False
Il primo risultato è True proprio perché il valore 1 è condiviso (quando possibile, cioè spesso), mentre il secondo è False perché l’operatore is si trova di fronte a due puntatori a due istanze PyIntObject diverse, sebbene conservino poi lo stesso valore.
Infatti:
>>> i == j
5: True
L’uguaglianza non mente. ;)
La seconda ipotesi è che magari si potrebbe adattare CPython per qualche sistema embedded in cui l’occupazione di memoria dev’essere minima e l’implementazione viene customizzata in modo da tagliare ove possibile lo spazio occupato.
Magari si farà poco uso di interi (nel senso: in un determinato momento in esecuzione ci saranno sempre poche istanze di numeri interi utilizzate), per cui si preferisce privilegiare la riduzione dello spazio a scapito delle prestazioni (il continuo allocare e disallocare istanze all’occorrenza).
azz questa cosa del caching mi fa storcere parecchio il naso :-/
Non ho mai visto di buon occhio i linguaggi puramente ad oggetti, proprio perchè si è costretti a ricorrere a questi “trucchi” per superare l’overhead della modellazione ad oggetti perfino dei tipi elementari come un intero.
Secondo te, trattare gli interi come tipi primitivi (quindi senza check sul tipo, senza ref counting, ma semplicemete mappando 1:1 con gli int del C) quale svantaggio porterebbe in un sistema a tipizzazione dinamica come Python?
E’ una cosa a cui avevo pensato anch’io, ma non esattamente così. Immaginavo di mappare un intero a 31 o 63 bit (a seconda dell’architettura) infilandolo nel puntatore, ma shiftato a sinistra di 1 e forzando il bit 0 sempre a 1 per distinguere il puntatore usato come intero da un puntatore normale (che avrebbe avuto il bit 0 sempre a 0).
Però avrei incasinato la VM parecchio, e non so se alla fine questa porcata avrebbe migliorato realmente le prestazioni globali di CPython.
Poi qualche mese fa, studiandomi gli interi per il mio talk per l’EuroPython, ho scoperto il seguente commento all’inizio del file intobject.c:
“(Using odd pointers to represent integers would save much space but require extra checks for this special case throughout the code.)”
Per cui qualcun altro v’aveva già pensato ed era arrivato alle stesse conclusioni, quindi mi sono fatto passare la voglia di farmi il mazzo soltanto per vedere se la mia idea fosse buona. :D
Comunque coi linguaggi dinamici non c’è alternativa a una gerarchia di tipi come quella usata in CPython, perché non puoi sapere a priori il tipo di dato di un oggetto che ti viene passato da qualche parte. Infatti anche LUA, che è il linguaggio dinamico più veloce in assoluto, utilizza qualcosa di simile (anche se più “primitivo”, avendo pochi tipi di dati da manipolare).
Se parlassimo di linguaggi statici, non ci sarebbe alcun problema: conoscendo già a priori il tipo dei dati che si stanno manipolando, subentrerebbero apposite ottimizzazioni e non avremmo bytecode “generici” come BINARY_ADD che si occupa di effettuare la “somma” qualunque siano i tipi di dati passati, ma avremmo apposite istruzioni (INT_ADD, FLOAT_ADD, STRING_ADD, ecc.).
Al solito, la dinamicità ha un prezzo salato da pagare. Ma fortunatamente se servono le prestazioni ormai da anni sono stati sviluppati compilatori JIT che riducono di molto la forbice coi linguaggi staticamente tipati (Java è molto vicino al C ormai).
[OT]
@Cesare: interessantissime queste tue ultime considerazioni; so che divagano un po’ troppo dal tema stretto dell’articolo ed è carino che almeno vengano fuori grazie/nei commenti.
Per quanto possibile ti esorto a inserire eventuali *chicche* del genere anche in occasione dei prossimi articoli, perchè questi “aneddoti” sono interessantissimi e possono venire fuori solo da chi si è veramente “sporcato le mani” (o rotto la testa, se vuoi) con la virtual machine…
Cesare, quando dici
“E’ bene sottolineare che questa verifica assume per buona una pratica molto diffusa, ma non standardizzata dal comitato ANSI & ISO: il fatto che un overflow o underflow comporti un cambio di segno del risultato di un’operazione binaria.”
ti stai riferendo al fatto che lo standard C specifica il wrap-around per interi unsigned, ma non signed?
Esattamente.
@banryu: ti ringrazio, ma, come vedi, gli spunti arrivano principalmente da voi lettori. Difficilmente avrei pensato di parlarne altrimenti, ma siete giustamente esigenti e molto attenti, per cui mi fa piacere che certe cose saltino fuori. :)
io avrei fatto un uso dei puntatori piu’ intenso questo avrebbe evitato il goto oltre ad altre cose…ma sopratutto avrei utilizzato un algoritmo unico per la gestione degli interi completamente staccato dalla tipologia di gestione del C degli interi…….virtualizzando al meglio la gestione della ram e dei signal….un po’ come si fa con il kernel di OS….ibm è maestra in questo modo di programare….basta vedere le emulazioni dei server I series….con processore power7……..
questo renderebbe python anche meno dipendente dall’OS ospite…
e sopratutto meno interprete e piu’ virtual machine….
Potresti farmi qualche esempio dei tre casi che hai citato all’inizio? Come puoi immaginare, l’argomento m’interessa particolarmente. :P
Cosi’ a naso mi pare che avere un algoritmo unico per la gestione degli interi sarebbe molto piu’ lento. Quel codice usa la somma nativa a 32 (64?) bit della macchina per la maggior parte dei casi, che e’ la cosa piu’ veloce che si puo’ fare, e usa l’algoritmo lento “slow_add” per i casi particolari — il che e’ esattamente quello che la legge di Amdahl dice di fare per accelerare l’esecuzione dei programmi :)
Inoltre non capisco tutta questa animosita’ nei confronti del goto. Ovvio che abusarne crea uno “spaghetti-code” assolutamente ingestibile, ma credo ci siano occasioni in cui un uso giudizioso sia una buona soluzione. O almeno questo e’ quello che dice Knuth :) e io mi fido:
http://pplab.snu.ac.kr/courses/adv_pl05/papers/p261-knuth.pdf
L’articolo e’ un po’ vecchiotto (37 anni fa :) ma certe cose non cambiano mai :)
L’opinione, infatti, è quella.
Personalmente nelle applicazioni che ho sviluppato ho sempre evitato i goto. Soltanto lavorando con la VM di Python m’è capitato di incontrarne parecchi, e a volte ho dovuto ricorrevi pure io per le motivazioni che ho addotto prima (per evitare i goto avrei dovuto duplicare porzioni di codice e/o introdurre altre variabili, peggiorando le prestazioni).
Considerato che la VM è un po’ diversa da una normale applicazione, per lo meno per i requisiti di efficienza che si porta dietro, ci può anche stare e si fa di necessità virtù.
Sull’implementazione degli interi concordo. Comunque lavorando al talk della scorsa EuroPython m’è venuta in mente un’implementazione leggermente diversa della VM di Python che dovrebbe gestire in maniera più efficiente le operazioni che finirebbero nel caso “slow_add”, avvicinando di molto le prestazioni al caso veloce di interi e stringhe. Al momento rimane un’idea, anche perché non ho tempo per implementarla, ma in particolare perché mi sto arrovellando sulla sua possibile brevettabilità, visto che sarebbe una trovata abbastanza generale da essere implementata in VM di linguaggi dinamici (senza ricorrere a compilatori JIT o sistemi con tracing-JIT).
“”Al momento rimane un’idea, anche perché non ho tempo per implementarla, ma in particolare perché mi sto arrovellando sulla sua possibile brevettabilità, visto che sarebbe una trovata abbastanza generale da essere implementata in VM di linguaggi dinamici (senza ricorrere a compilatori JIT o sistemi con tracing-JIT).””
Sbav, sbav… Non puoi lanciare il sasso e poi nascondere la mano in questo modo!! Prima ci affami e poi ci lasci a bocca asciutta! B******o! :D
Se ti dicessi che ne ho un’altra (per la quale sono combattuto allo stesso modo) per accelerare la chiamata ai metodi dei tipi standard sempre per VM di linguaggi dinamici, mi vieni a cercare a casa con la mazza chiodata? :D
Poi ne spunta fuori un’altra per migliorare l’esecuzione del codice delle inner function / method, e devo prenotare un posto al campo santo… O:-)
A parte gli scherzi, avendo messo le mani sulla VM, mi sono venute fuori tantissime idee per velocizzarne l’esecuzione (molte implementate in WPython, per cui ne parlerò. Promesso!).
Queste che ho citato sono soltanto le ultime 3 “di spessore” (nel senso che “a naso” mi aspetto sensibili aumenti di prestazioni), ma in questi anni ne ho collezionato (e appuntato) un discreto numero.
P.S. Ho dovuto moderare quel termine, perché la policy di AD è molto rigida. ;)
Maledetto sadico -_-‘
Ma prima o poi ce ne parlerai, ah, giuro che lo farai!
Ti becco alla EuroPython l’anno prossimo e ti torchio di brutto :D
A meno che, per quella data, non arrivi pronto con l’asso nella manica e ci cali un talk da chilo al riguardo!
Uomo avvisato…
Non so se parteciperò alla prossima EuroPython. Sono cambiate molto cose. Vedremo.
Comunque materiale di cui discutere in queste pagine ce ne sarà. ;)