Python: dagli interi “corti” a quelli “lunghi”

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.

Press ESC to close