Non sempre “big is better”: l’importanza della scelta dei tipi di dati – Un esempio con CPython

Da quando ho iniziato, nel lontano 1982, la mia avventura coi computer (poi sfociata in passione e infine in professione) posso dire di avere avuto la gioia nonché il privilegio di veder passare davanti a me, come pure toccare con mano, i progressi di questa meravigliosa tecnologia (i quali si sono succeduti abbastanza rapidamente, se guardiamo bene ai tempi).

In principio erano gli 8 bit (almeno per me: altri hanno avuto la fortuna di assaporare anche i 4 bit, ad esempio), si potrebbe parafrasare, perché i microprocessori utilizzati negli home computer dell’epoca (i più diffusi nonché abbordabili per la massa) manipolavano agevolmente dati di quella dimensione (e molto meno agevolmente dati più grandi, che richiedevano più istruzioni eseguite allo scopo, impattando considerevolmente sulle prestazioni).

La fame di potenza di calcolo, nonché la disponibilità di sempre più transistor impacchettati nella ridotta area dei chip, ha portato col tempo al fiorire di sistemi a 16 bit, poi a 32 bit e, negli ultimi anni, naturalmente a quelli a 64 bit (i quali sono gli unici a essere supportati ormai nei sistemi mainstream).

E’ facile, quindi, comprendere come nell’immaginario collettivo si sia radicata l’idea che “più bit = più potente” (come abbiamo trattato in un vecchio, ma ancora attuale, articolo sull’argomento: Dal mito dei Mhz a quello dei bit…), per cui l’hardware si è evoluto verso la manipolazione di dati sempre più grandi e, conseguentemente, il software è stato adattato o scritto per utilizzarli.

Tutto magnifico, considerando il livello di complessità raggiunto dal software, il che ha consentito di avvicinare sempre più persone alla tecnologia, in maniera via via più semplice e comoda, estendendone i benefici praticamente all’intera collettività.

D’altra parte anche per i programmatori la transizione è stata semplice e veloce: per sfruttare dati di dimensioni sempre più grandi è stato sufficiente utilizzare l’apposito (magari nuovo) tipo di dato.

Oppure non muovere un dito e lasciare al compilatore tutto l’onere. Ad esempio in C (come pure in Pascal e altri linguaggi), il tipo dati intero (int) non ha una dimensione precisa, ma è definito dalla piattaforma (ABI) e/o dal compilatore stesso. Usualmente nei sistemi a 8 bit era a 16 bit, in quelli a 16 o 32 bit poteva essere a 16 o 32 bit, e infine 32 o 64 bit in quelli a 64 bit.

Il rovescio della medaglia è, però, rappresentato dal fatto che dati più grandi richiedono ovviamente più spazio per essere memorizzati in qualunque dispositivo (dalle memorie ai sistemi di archiviazione), che in un sistema si traducono inevitabilmente anche in un maggior uso di banda verso la memoria (in generale, verso l’intera gerarchia: dalla RAM fino alle cache L3/L2/L1).

Ciò non è stato un grosso problema se consideriamo che i progressi tecnologici hanno ormai messo a disposizione enormi quantitativi di memoria e archiviazione, come pure delle relative bande per accedervi, ma l’avvento di processori prima, e schede video poi, aventi parecchi core integrati affamati di banda hanno messo in luce problemi di condivisione e fruizione di questa preziosa risorsa.

Complice anche il rallentamento di tali progressi (checché se ne dica, la famigerata Legge di Moore è destinata ad avere una fine, e vi ci stiamo avvicinando), il problema si è fatto e si farà sempre più rilevante.

Sorge, pertanto, la necessità di sfruttare nel miglior modo possibile le risorse che abbiamo, senza strafare in eccessi che sono stati incoraggiati dall’esplosione di loro sempre maggiori quantità.

Uso della memoria in (C)Python

Reduce dal puntuale appuntamento con la Pycon italiana (conferenza di appassionati di questo meraviglioso linguaggio) e dalle mie passate esperienze (WPython) con la versione più diffusa / mainstream (CPython) di Python, mi è venuta voglia di rispolverare una vecchia idea e descrivere una possibile ottimizzazione per i sistemi a 64 bit, dopo aver partecipato ad alcune presentazioni che parlavano di reference count e GIL.

Senza dilungarmi troppo, possiamo dire che qualunque dato in Python (CPython per l’esattezza: d’ora in poi mi riferirò sempre a questa implementazione, che è la più diffusa e quella che usiamo praticamente tutti) è costituito da una struttura (struct, in C) base, a prescindere dal particolare tipo di dato, la cui definizione è sostanzialmente riconducibile a questa:

struct {
    Py_ssize_t ob_refcnt;
    PyTypeObject *ob_type;
} PyObject;

Anche qui ho voluto semplificare molto, togliendo di mezzo parecchi dettagli tecnici che non sono rilevanti per lo scopo dell’articolo. Ciò che è realmente importante è comprendere che il mattoncino base di qualunque oggetto (perché, in questo linguaggio, ogni dato è un oggetto) Python è costituito da due informazioni chiave: il numero di volte (ob_refcnt) che tale oggetto viene referenziato (da un altro oggetto. Perché è contenuto in una lista, ad esempio) e il suo tipo (ob_type). Qualunque altro oggetto, infatti, avrà sempre questi due elementi alla sua base, a cui eventualmente potrà aggiungerne altri di propri.

In memoria la sua rappresentazione sarà la seguente per un sistema a 32 bit:

mentre in un sistema a 64 bit sarà (senza grosse sorprese) questa:

D’altra parte i puntatori sono raddoppiati come dimensione passando da 32 a 64 bit, e la stessa cosa è avvenuta col tipo (Py_ssize_t) che consente di specificare la dimensione massima (in byte) per gli interi che vengono utilizzati in questo caso (e che normalmente sono della stessa dimensione dei puntatori). Address/Offset ovviamente si riferisce all’indirizzo dove si trova in memoria quel particolare elemento, a partire dall’inizio della struttura.

Apparentemente non v’è nulla che possa essere cambiato, e ciò riflette il discorso che è stato fatto in precedenza: passando ad architetture che manipolano dati più grandi, aumentano di conseguenza le dimensioni dei tipi di dati utilizzati, che si riflette sull’occupazione di memoria (e della relativa banda per accedervi).

In realtà e conoscendo la struttura di altri tipi di dati definiti in Python, nonché il modo in cui questi sono utilizzati abitualmente, si può pensare a una soluzione diversa che consente di risparmiare un po’ di memoria e banda per i sistemi a 64 bit (per cui saranno necessarie alcune #ifdef in questo caso, che per semplicità ometterò dagli esempi che seguono).

Ridefinire PyObject & co.

Per raggiungere l’obiettivo è necessario, in primo luogo, definire due nuovi tipi di dati:

che, come da descrizione, vanno utilizzati rispettivamente per il tipo relativo a ob_refcnt, e per quello (usato in altri tipi di dati, come vedremo più avanti) che indica la lunghezza di una stringa o, in generale, il numero di elementi contenuti in sequenze (liste, tuple, insiemi, ecc.) o simili (dizionari, …).

A questo punto il tipo base PyObject diventerebbe:

struct {
    Py_refcnt_t ob_refcnt;
    PyTypeObject *ob_type;
} PyObject;

che in memoria sarebbe rappresentato come:

Adesso la situazione sembrerebbe persino peggiorata, in quanto si è creato un “buco” in mezzo alla struttura (necessario per allineare il puntatore ob_type alla sua naturale dimensione, che è di 8 byte) che, quindi, risulta inutilizzato.

Inoltre usando un intero con segno a 32 bit per ob_refcnt si è pure ridotta enormemente la possibilità di referenziare gli oggetti, in quanto si è passati da 8 miliardi di miliardi (2⁶³) a circa 2 miliardi (2³¹) numero massimo di riferimenti. Ma di questo ne parleremo meglio più avanti.

La cosa più semplice e immediata da fare è cercare di utilizzare in qualche modo questo spazio vuoto, ad esempio per indicare la lunghezza di una stringa, o il numero di elementi di una sequenza, ecc., oppure, in generale, lasciarlo come campo a 32 bit a disposizione per altri tipi di dati.

Una nuova definizione di PyObject potrebbe, quindi, essere la seguente:

struct {
    Py_refcnt_t ob_refcnt;
    union {
       Py_seq_len_t ob_size; /* Number of items in variable part */
       Py_seq_len_t ob_user_data; /* Free for other data types */
    };
    PyTypeObject *ob_type;
} PyObject;

la cui rappresentazione in memoria sarebbe:

A questo punto il vantaggio risulta già evidente, avendo guadagnato un ulteriore campo pur mantenendo lo stesso spazio occupato in memoria: siamo riusciti a impacchettare tre informazioni molto importanti in Python, ma in soli 16 byte.

Invece l’attuale implementazione per gli oggetti che sono dotati della proprietà / attributo “lunghezza”, che in genere fa capo al tipo PyVarObject:

struct {
    PyObject ob_base;
    Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;

richiede almeno 24 byte:

In realtà, e come si vede, lo spazio occupato è di 32 byte, perché la memoria allocata ha una granularità di 16 byte. Per cui lo spazio effettivamente occupato da PyVarObject risulta il doppio rispetto alla nuova implementazione proposta, che a questo punto diventa semplicemente:

typedef struct PyObject PyVarObject;

quindi un banale alias di PyObject.

Il primo erede di PyVarObject: PyTupleObject

Questi cambiamenti si riflettono immediatamente in tutti gli oggetti che derivano da PyVarObject. Ce ne sono diversi in Python, ma ne prenderemo in considerazione soltanto alcuni, esclusivamente per mostrare situazioni in cui ci sono benefici da questa nuova struttura e altri dove non si traggono vantaggi.

Ad esempio, le tuple, che sono fra gli oggetti / sequenze più utilizzati in Python, si trasformano in questo modo (semplificando ancora una volta la struttura a scopo puramente didattico):

struct {
    PyVarObject ob_base;
    /* ob_item contains space for 'ob_size' elements.
       Items must normally not be NULL, except during construction when
       the tuple is not yet visible outside the function that builds it. */
    PyObject *ob_item[1];
} PyTupleObject;

Essendo un oggetto dinamico, la cui dimensione è stabilita dagli elementi che contiene, anche lo spazio occupato varia di conseguenza, proporzionalmente al loro numero. Ad esempio, la tupla vuota (che non ha alcun elemento) coincide con PyVarObject (quindi c’è un risparmio con la nuova struttura), mentre quella con un solo elemento ha la seguente rappresentazione in memoria:

quindi occupa lo stesso spazio dell’attuale implementazione di Python. Mentre con due elementi:

questa volta con un risparmio. E così via. Per cui c’è un vantaggio soltanto per tuple aventi un numero di elementi pari.

Adesso tocca a PyListObject

Un tipo estremamente utilizzato che, invece, presenta sempre vantaggi con la nuova struttura è la lista:

struct {
    PyVarObject ob_base;
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_seq_len_t allocated;
} PyListObject;

Questo perché, pur essendo un oggetto dinamico (a causa degli elementi che contiene), la sua struttura base è sempre la stessa e non cambia mai. In memoria viene rappresentata come:

L’attuale implementazione in Python richiede, invece, 48 byte (anziché i 32 della nuova!).

Le stringhe sono più complicate!

Un altro tipo usatissimo dove è possibile ottenere molto spesso vantaggi grazie alla nuova rappresentazione sono le stringhe, che però sono gestite internamente da Python usando tre tipi / strutture diverse (sebbene siano ciascuna un’estensione della precedente). Partendo dalla più semplice (nonché comune!), che diventerebbe:

struct {
    PyVarObject ob_base;
    Py_hash_t hash;             /* Hash value; -1 if not set */
    struct {
        /* If interned is non-zero, the two references from the
           dictionary to this object are *not* counted in ob_refcnt.
           The possible values here are:
               0: Not Interned
               1: Interned
               2: Interned and Immortal
               3: Interned, Immortal, and Static
           This categorization allows the runtime to determine the right
           cleanup mechanism at runtime shutdown. */
        unsigned int interned:2;
        /* Character size:

           - PyUnicode_1BYTE_KIND (1):

             * character type = Py_UCS1 (8 bits, unsigned)
             * all characters are in the range U+0000-U+00FF (latin1)
             * if ascii is set, all characters are in the range U+0000-U+007F
               (ASCII), otherwise at least one character is in the range
               U+0080-U+00FF

           - PyUnicode_2BYTE_KIND (2):

             * character type = Py_UCS2 (16 bits, unsigned)
             * all characters are in the range U+0000-U+FFFF (BMP)
             * at least one character is in the range U+0100-U+FFFF

           - PyUnicode_4BYTE_KIND (4):

             * character type = Py_UCS4 (32 bits, unsigned)
             * all characters are in the range U+0000-U+10FFFF
             * at least one character is in the range U+10000-U+10FFFF
         */
        unsigned int kind:3;
        /* Compact is with respect to the allocation scheme. Compact unicode
           objects only require one memory block while non-compact objects use
           one block for the PyUnicodeObject struct and another for its data
           buffer. */
        unsigned int compact:1;
        /* The string only contains characters in the range U+0000-U+007F (ASCII)
           and the kind is PyUnicode_1BYTE_KIND. If ascii is set and compact is
           set, use the PyASCIIObject structure. */
        unsigned int ascii:1;
        /* The object is statically allocated. */
        unsigned int statically_allocated:1;
        /* Padding to ensure that PyUnicode_DATA() is always aligned to
           4 bytes (see issue #19537 on m68k). */
        unsigned int :24;
    } state;
} PyASCIIObject;

che in memoria sarebbe rappresentata come:

Anche qui utilizzando 32 byte anziché i 48 dell’attuale implementazione.

Il successivo tipo usato per le stringhe, che è basato su questo, diverrebbe quindi:

struct {
    PyASCIIObject _base;
    Py_seq_len_t utf8_length;    /* Number of bytes in utf8, excluding the
                                 * terminating \0. */
    char *utf8;                 /* UTF-8 representation (null-terminated) */
} PyCompactUnicodeObject;

e in memoria verrebbe rappresentato come:

In questo caso occuperebbe lo stesso spazio (48 byte) dell’attuale implementazione. Mentre il tipo successivo, invece, ne trarrebbe vantaggio:

struct {
    PyCompactUnicodeObject _base;
    union {
        void *any;
        Py_UCS1 *latin1;
        Py_UCS2 *ucs2;
        Py_UCS4 *ucs4;
    } data;                     /* Canonical, smallest-form Unicode buffer */
} PyUnicodeObject;

Infatti la sua rappresentazione in memoria sarebbe:

Ossia sempre 48 byte di spazio occupato, contro i 64 dell’attuale versione presente in Python.

E’ il turno dei dizionari: PyDictObject

Infine, un altro oggetto che vanta un vastissimo utilizzo, anche internamente, è certamente il dizionario, il quale otterrebbe anch’esso benefici dalla nuova implementazione:

struct {
    PyVarObject ob_base;
    PyDictKeysObject *ma_keys;

    /* If ma_values is NULL, the table is "combined": keys and values
       are stored in ma_keys.

       If ma_values is not NULL, the table is split:
       keys are stored in ma_keys and values are stored in ma_values */
    PyDictValues *ma_values;
} PyDictObject;

Infatti in memoria sarebbe rappresentato come:

Quindi 32 byte anziché i 48 richiesti dall’attuale implementazione.

Altre considerazioni

Mi fermo qui per non allungare eccessivamente l’articolo, ma il concetto esposto dovrebbe essere sufficiente chiaro nonché applicabile a diversi altri tipi di oggetti (anche agli interi che, ad esempio, diventerebbero molto simili alle tuple) utilizzati sia in Python sia nelle innumerevoli librerie esterne che sono state realizzate.

Un ragionamento simile si potrebbe fare anche per altri tipi di dati basilari che sono impiegati in diversi oggetti, come Py_hash_t che viene usato per i valori hash. Con codice a 64 bit viene utilizzato un intero di tale dimensione per il loro calcolo, ma bisognerebbe chiedersi se tale scelta produca degli effettivi benefici.

La domanda da chiedersi sarebbe, in questo caso, se l’uso di hash a 64 bit consentirebbe di distribuire molto meglio i valori delle strutture dati che ne facciano uso, rispetto ad hash a 32 bit. Perché se gli hash a 32 bit sono sufficienti, allora potrebbero essere adottati anche in sistemi a 64 bit, in modo da liberare altro spazio.

E’ bene sottolineare, in questo contesto, che utilizzare tipi di dati più piccoli non è di per sé sufficiente a ridurre la dimensione delle attuali strutture dati. Infatti, e com’è possibile verificare partendo già dai tipi PyObject e PyVarObject, è fondamentale cercare di incastrare bene i tipi di dimensione minore, così da sfruttare sapientemente gli spazi vuoti lasciati dalla riduzione effettuata e, quindi, far quadrare i conti mettendo a posto i pezzi del “puzzle”.

Serve, quindi, anche una buona visione e conoscenza degli oggetti e un occhio più attento ai dettagli di basso livello. Infatti molte cose sono state omesse per semplificare la discussione, ma i campi delle strutture utilizzate non sono sempre gli stessi, in quanto ne vengono aggiunti e/o rimossi altri a seconda di alcuni flag di compilazione (ad esempio per il debug o per la profilazione del codice).

L’importante, in ogni caso, è che le nuove modifiche apportate siano poi effettive per il codice generato per la versione “mainstream” (quella finale; di produzione, insomma), per ovvi motivi.

Un modello “Large“ per Python

Tutto ciò può portare a quello che, facendo un parallelo col codice generabile per l’architettura x86, si potrebbe definire come modello “large” (mentre quello attuale, di conseguenza, come modello “huge“) per Python, in quanto esistono più limiti e limitazioni su quello che si può fare con questo nuovo modello rispetto a quello che è disponibile adesso e che, ovviamente, non ne ha.

Il nocciolo della questione rimane, pertanto, quello di stabilire se i nuovi limiti così ristretti siano tollerabili rispetto ai già evidenziati vantaggi in termini di risparmio di memoria e di relativa banda per l’accesso, oppure siano troppo pesanti e affliggano in maniera insostenibile la normale esecuzione.

Per comprenderlo, però, è necessario distaccarsi dai freddi numeri (la teoria) e vedere come si comporterebbe il nuovo modello nel mondo reale (la pratica), con alcuni esempi concreti.

Cominciamo con quello che parrebbe il più odioso, ovvero la limitazione sul reference count, che passerebbe da più 8 miliardi di miliardi a circa 2 miliardi: una differenza a dir poco abissale! Eppure ciò significherebbe avere ben 2 miliardi di oggetti che referenzino quello specifico oggetto. Oppure, per fare un altro paragone, sarebbe come avere una lista (o una tupla. O altro) che contenga due miliardi di volte lo stesso oggetto.

E’ chiaro che trattasi di scenari assolutamente realistici, ma quanto comuni possano essere (e, quindi, quanto possano far desistere dall’applicare il nuovo modello di memoria) risulta, a mio avviso, tutto un altro paio di maniche.

Infatti avere 2 miliardi di oggetti contemporaneamente in memoria significa che, prendendo quello che occupa di meno (ad esempio il singleton None), essi occuperanno 2 miliardi * 16 byte = ben 32 GB di memoria solo per loro!

Una quantità impressionante, sebbene assolutamente realistica e alla portata dei computer moderni, ma bisogna considerare che stiamo parlando esclusivamente di oggetti che referenzino esattamente e soltanto lo stesso oggetto. Dubito che esistano applicazioni nel mondo reale che facciano soltanto questo…

Considerazioni analoghe si possono fare anche per l’altro limite, cioè quello del massimo numero di elementi che possono essere contenuti in sequenze (liste, tuple, …) o stringhe, che passa sempre dai circa 8 miliardi di miliardi a 4 miliardi (4Gi meno uno, per la precisione).

Questo significa porre un tetto di 4GB meno un carattere a una singola stringa, oppure avere liste in grado di ospitare al massimo 4 miliardi di elementi, per fare un altro esempio. Entrambe, però, non sono delle grosse limitazioni.

Prendendo l’esempio della lista, significherebbe che una contenente 4 miliardi di elementi richiederebbe, già soltanto per lei, 4G * 8 byte (ogni puntatore all’elemento referenziato occupa 8 byte) = circa 32GB di memoria. A cui si devono aggiungere almeno altri 4G * 16 byte = 64GB circa per lo spazio occupato dagli oggetti veri e propri, nell’ipotesi che questi occupino il minor spazio possibile (16 byte, per l’appunto).

Riguardo le stringhe parliamo comunque di 4 miliardi di caratteri, quindi si va da un minimo di 4G * 1 byte = 4GB circa per stringhe ASCII (dove un carattere richiede soltanto un byte) fino a 4G * 6 byte = 24GB circa per quelle codificate in formato UTF-8. Parliamo, comunque, di un limite applicabile a una singola stringa, ma ovviamente se ne possono avere di gran lunga di più e ognuna di esse con potenzialmente lo stesso limite / capacità.

D’altra parte questi limiti si riflettono, per l’appunto, su un singolo oggetto, ma durante l’esecuzione di un’applicazione Python ve ne possono anche miliardi, e in grado consumare non soltanto la memoria fisica a disposizione, ma anche l’intero spazio d’indirizzamento virtuale del processore.

Conclusioni

Mi sembra chiaro, quindi, che i limiti imposti dal nuovo modello “Large” non portino effettivamente grossi problemi, ma che, al contrario, si sposino molto bene con i tipici scenari in cui vengono eseguite le applicazioni Python più variegate.

Ovviamente sarebbe sempre possibile compilare Python col modello di memoria attuale (“Huge“) per il ristretto numero di quelle che abbiano bisogno di superare questi limiti. Parliamo, però, di applicazioni scientifiche di un certo calibro la cui diffusione nonché ridotto utilizzo non giustificano, a mio modesto avviso, l’attuale maggior consumo di memoria e di relativa banda d’accesso che vengono fatti pesare anche su tutti gli altri casi d’uso di gran lunga più comuni.

D’altra parte se è vero che i progressi tecnologici ci hanno fornito parecchia memoria e banda, è altrettanto vero che non sarà sempre così in futuro (causa tramonto della summenzionata Legge di Moore), oltre al fatto che non tutti i sistemi ne sono dotati e, quindi, vengono penalizzati dalle attuali scelte.

Sarebbe auspicabile, pertanto, che gli sviluppatori di Python tengano conto di queste considerazioni e implementino questo nuovo modello, in modo da estenderne i benefici alla maggior parte degli utenti, che non hanno certo bisogno di poter utilizzare o referenziare un così elevato numero di oggetti che rimarrebbe sempre e soltanto un dato puramente teorico per loro e mai nemmeno lontanamente fruito.