In Python raramente mi è capitato di avere a che fare con gli interi “lunghi”, cioè quegli interi che, non potendo essere rappresentati dai classici 32 o 64 bit (a seconda dell’architettura del processore), necessitano di un nuovo tipo di dati in grado di ottemperare a questo requisito.
Naturalmente un programmatore è molto attento nella manipolazione delle quantità di interi (in base al dominio del problema da risolvere), per cui un overflow dovuto a qualche operazione aritmetica che porti il risultato a essere trasformato da int a long è quasi sicuramente attribuibile a un bug.
A partire da Python 3.0, come già affermato in qualche precedente articolo sulla macchina virtuale di Python, non esistono più i vecchi interi “corti”, ma la VM espone un modello unico e omogeneo, che trova nel tipo long l’unico modello di riferimento per questa tipologia di dati.
Siamo passati, quindi, dalla seguente struttura:
typedef struct {
Py_ssize_t ob_refcnt;
struct _typeobject *ob_type;
long ob_ival;
} PyIntObject;
a questa:
typedef struct _longobject PyLongObject;
/* Revealed in longintrepr.h */
struct _longobject {
Py_ssize_t ob_refcnt;
struct _typeobject *ob_type;
Py_ssize_t ob_size;
digit ob_digit[1];
};
E’ bene notare che, a differenza di PyIntObject, PyLongObject è definito come alias del tipo _longobject, che si trova definito in un apposito file (longintrepr.h). Non si tratta di scatole cinesi, ma di una sorta di definizione “privata” della struttura che implementa effettivamente questo tipo di dati.
L’obiettivo è di mettere in chiaro che l’implementazione attuale non è definitiva, e quindi in futuro potrebbe benissimo cambiare se se ne presentasse l’esigenza. Chi ha la necessità di accedere alle informazioni contenute in questa struttura lo può fare, ma deve ricorrere alle apposite API esposte, in modo da controllarne l’accesso e garantire la compatibilità con le future implementazioni.
Tornando alle due strutture, a parte i primi due campi che, come già visto ampiamente in precedenza, rappresentano la base comune (PyObject) di tutti gli oggetti gestiti dalla VM, appare evidente che “non si somigliano per niente”.
La prima è statica (ha sempre la stessa dimensione), mentre la seconda è dinamica, in quanto il terzo campo (ob_size) fa parte del terzetto che definisce ogni tipo di dato che è classificabile come “sequenza” (PyVarObject), ossia una sorta di “vettore” (consentitemi la semplificazione) di una certa dimensione e il cui numero di elementi (che non sono necessariamente omogenei) è racchiuso in ob_size, appunto.
I dati sono conservati in modo completamente diverso. PyIntObject ha a disposizione soltanto il campo ob_ival allo scopo, mentre PyLongObject fa ricorso a un vettore conservato nel campo ob_digit, che però risulta di un solo elemento. Questo trucchetto si è reso necessario perché con le vecchie versioni del C non si può definire una struttura senza (zero) elementi. Sarà poi al momento dell’allocazione di memoria che la struttura verrà dimensionata correttamente, tenendo conto dello spazio che serve effettivamente.
Il tipo di ogni elemento è definito come digit:
typedef unsigned int digit;
cioè un intero senza segno. Quindi il vettore contiene una sequenza di interi. In realtà non tutto lo spazio che un int mette a disposizione viene utilizzato, perché in un digit viene conservata soltanto una quantità pari a 15 o 30 bit, a seconda di un’impostazione di compilazione:
#define PyLong_SHIFT 15 /* or 30 in Python >= 3.0 */
L’idea che sta alla base dei long appare molto semplice e intuitiva. Un intero di una certa dimensione viene “spezzettato” in tanti piccoli interi che conservano soltanto una certa quantità dell’informazione totale, pari a 15 o 30 bit, partendo dai bit meno significativi a quelli più significativi.
Il tipo digit, però, è stato definito come senza segno, mentre i long che possiamo manipolare potrebbero anche essere dotati di segno. La soluzione adottata è un po’ strana e fa parte del novero dei numerosi hack presenti nella VM sempre per questioni di spazio e/o velocità.
I digit conservano tutti quantità intere senza segno, perché di fatto nel vettore ob_digit viene conservato il valore assoluto del valore intero che si vuole rappresentare.
Il segno, che pure dev’essere memorizzato da qualche parte, si trova infatti nel campo ob_size. Più precisamente, se ob_size contiene un valore maggiore di zero, ob_digit rappresenta un intero positivo; se è zero, ob_digit non conserva nulla e il numero rappresentato risulta essere zero; infine, se ob_size è negativo, così sarà anche l’intero che viene conservato dalla struttura.
Si tratta di una pezza molto sporca, che mi ha fatto storcere il naso, ma che si rivela funzionale e necessaria per non aggiungere un altro campo della struttura, facendo aumentare ulteriormente lo spazio occupato.
Alcuni esempi mostrano immediatamente le differenze fra i due tipi di struttura nell’atto di rappresentare stessi valori:
Value ob_size ob_digit[0] ob_digit[1] Digit Size
0 0 Not used Not used Any
1000000 2 16960 30 15 bits
1000000 1 1000000 Not used 30 bits
-1000000 -1 1000000 Not used 30 bits
-10000000000 -2 336323584 9 30 bits
Com’è facile intuire, anche le operazioni sono implementate in maniera molto diversa, come vedremo in un prossimo articolo.
Anni per arrivare al complemento a due, e un attimo per buttarlo nella spazzatura :)
E’ la prima cosa che ho pensato. :P
Però ci sono delle ragioni precise per lavorare coi valori assoluti e il segno separati. Gli algoritmi più complessi, in particolare, lo richiedono per manipolare agevolmente quantità indefinite di cifre.
Come ci pure delle motivazioni per avere cifre di 15 o 30 bit, anziché 16 o 32 per sfruttare il più possibile lo spazio a disposizione all’interno di un intero senza segno.
P.S. Comunque la soluzione a cui ho lavorato per l’EuroPython fa rientrare in parte il complemento a due. :P
Immagino che i 15 bit servono perche’ cosi’ puoi sommare due valori a 15 bit ed essere sicuro di starci dentro uno da 16 bit (e poi metterlo a posto dopo), no? Ma il 30? Perche’ non 31? E’ una semplificazione (30 e’ il doppio di 15)?
Sì, anch’io sono curioso e vorrei sapare quale è la ragione dietro quel 30 e non 31… immagino che, come sempre, dietro questa scelta ci siano ragioni di ottimizzazione, in un modo o nell’altro…
P.S.: Dopo aver letto la serie di articoli sui branch predictor (grazie pleg) resto con la curiosità di vedere che succede se togli quel famoso if che controlla che la variabile locale di un metodo non sia “unbounded”… Spero che tu possa fare la prova in un futuro sufficientemente vicino per poterci raccontare l’esito in uno di questi articoli sulla vm di Python :)
Vediamo come sono messo col lavoro. Lo farò penso il prossimo anno, appena avrò un momento di respiro.
La motivazione alla scelta di quei 2 valori per i numero di bit per singolo digit arriva da qui:
Che, assieme ad altri vincoli, portano a 15 o 30 la scelta. Io ho proposto anche 60 nel mio talk, con alcuni “magheggi”. :P
Umm.. interessante :)
Ma io ho tovato anche questo (stessa fonte, sospetto :P )
– the marshal code currently expects that PyLong_SHIFT is a multiple of 15
Le scelte effettuate per marshal.c sono ininfluenti quando si devono effettuare scelte come queste, perché si tratta del modulo di marshalling, il cui formato / protocollo può variare (e lo fa! :P) tranquillamente nel tempo.
Tanto per essere chiari, il formato del bytecode memorizzato su filesystem (i famigerati file .pyc, che vengono generati usando, appunto, marshal.c) è cambiato parecchie volte, generalmente almeno una volta per ogni major version, e addirittura anche più volte in revisioni minori o in sviluppo. ;)
Ah, ok, grazie del chiarimento. Dunque il tuo 60 non l’avevi pensato per rispettare anche questo vincolo, io invece avevo pensato di sì. Comunque interessante anche questo articolo, Cesare.
Mi piace parlare di queste cose. :)
Il 60 l’avevo pensato per soddisfare gli altri requisiti, non quello di marshalling (che peraltro ho cambiato nella mia implementazione, portandolo a 30). Non essendoci processori a 65 bit, ho optato per il multiplo di 5 inferiore. O:-)