Gli interi sono il tipo di dato più diffuso nel campo della computazione, per cui è normale che vi si dedichi più attenzione e risorse cercando di ottimizzarne il più possibile l’uso.
Python non fa eccezione nel discorso generale, ma purtroppo abbiamo visto nella serie di articoli precedenti che a partire dalla versione 3 è sparita la rappresentazione più veloce (gli interi “corti”) a favore dell’unico tipo di dato intero che fa capo ai long (interi “lunghi”).
Questo ha portato a una generale perdita di prestazioni, specialmente alla luce del complesso meccanismo che sta alla base dell’implementazione attuale delle operazioni (non soltanto aritmetiche, grazie al polimorfismo degli operatori che questo ricco e flessibile linguaggio mette a disposizione).
Studiando e sperimentando con la macchina virtuale di Python è stato per me naturale pensare a qualche possibile ottimizzazione per migliorare la situazione attuale. Le idee che sono venute fuori non sono state tante (quel codice è vecchio di anni, ed è passato sotto lo sguardo di parecchia gente molto esperta), e spesso inconcludenti.
A inizio dello scorso anno, però, ne è affiorata una mentre analizzavo il codice degli interi, ed è quella che si è concretizzata col lavoro che ho poi portato qualche mese dopo all’EuroPython.
Non è un caso che sia emersa proprio studiando il modo di ottimizzare gli interi, perché nella mia mente cullavo il sogno di unire la flessibilità degli interi lunghi (con precisione illimitata, memoria permettendo) alla velocità di quelli corti.
I due tipi, però, hanno una struttura e una rappresentazione completamente diversa, per cui conciliare le due cose a prima vista non sembra possibile, come abbiamo visto nell’articolo in cui li metto a confronto.
Gli interi corti hanno una dimensione fissa e sfruttano un concetto che ha fatto la fortuna dell’informatica: la rappresentazione in complemento a due. Quelli lunghi hanno una dimensione variabile, e sono rappresentati da una tripletta: il numero di cifre, il segno, e le cifre vere e proprie, coi primi due che risultano “fusi” in un solo valore.
La soluzione che ho ideato trae origine dal confronto di alcuni casi che si somigliano molto, com’è possibile vedere dalla tabella presente alla fine dell’articolo di cui sopra.
In particolare il più importante è quello degli interi positivi (e quindi non nulli) la cui rappresentazione coincide sostanzialmente fra i due tipi nel caso in cui per gli interi lunghi sia necessario un solo digit per contenerne il valore, com’è evidente col numero 1000000 quando i long utilizzano digit a 30 bit.
Per lo zero la situazione è un po’ diversa, perché negli interi corti fa ovviamente parte del valore memorizzato nella struttura, mentre in quelli lunghi la sua presenza viene indicata soltanto dal numero di digit che è pari a zero (il cui significato è chiaro: non servono digit per contenerlo).
Il primo passo per avvicinare le due rappresentazioni è stato quindi quello di far rientrare questo caso in quello dei numeri positivi. E’ bastato forzare l’uso di almeno digit per qualunque valore per arrivare allo scopo. Infatti in questo modo lo zero viene viene conservato così com’è nel primo digit (ob_digit[0]) della struttura long, ovviamente con ob_size = 1 (un solo digit presente).
A questo punto possiamo dire che interi positivi e zero coincidono nei due diversi tipi, sempre supponendo che si utilizzi esattamente un digit per i long, mentre rimangono completamente fuori gli interi negativi, che hanno una forma di fatto inconciliabile col complemento a due utilizzato nei classici interi.
D’altra parte è bene ricordare che gli interi corti, che sono di gran lunga i più usati anche nella sola e più diffusa incarnazione a 32 bit, svolgono egregiamente il loro dovere pur essendo estremamente limitati rispetto ai long.
La seconda idea che è venuta fuori è stata, quindi, quella di cercare di fare qualcosa di simile con questi ultimi: accelerarne l’esecuzione nei casi più comuni, lasciando al codice più generale e lento tutti gli altri.
Da qui la decisione di memorizzare il segno nell’ultimo digit, quello più significativo. Questa mossa ha avuto una prima, importante, implicazione, poiché è stato riportato alla definizione originale il campo che conserva il numero di digit utilizzati (ob_size), di cui gli sviluppatori Python avevano abusato conservandovi il segno del numero per cercare di risparmiare spazio (come spiegato nell’articolo di cui ho fornito il link).
Il segno, però, non è stato memorizzato così com’è, cioè semplicemente settando un bit (ad esempio il 16° nel caso di digit a 16 bit, oppure il 31° o il 32° per quelli a 32 bit).
Il trucchetto, forse un po’ sporco ma funzionale e soprattutto prestazionale, è stato quello di memorizzare il digit più significativo, e solo questo, in complemento a due quando il numero intero è negativo.
Ricapitolando, questo significa che per i numeri positivi non cambia assolutamente nulla rispetto all’implementazione attuale usata in CPython, per lo zero c’è una piccola differenza (ob_size risulta 1 anziché 0, viene usato un digit anziché nessuno e il suo valore è esattamente zero).
I negativi, infine, sono abbastanza diversi perché hanno ob_size sempre positivo (mentre prima era l’esatto opposto) e l’ultimo digit è il complemento a due rispetto all’attuale codifica. A non cambiare sono tutti gli altri digit, che conservano esattamente lo stesso valore.
La seguente tabella, molto simile a quella presentata nel link di cui sopra, mostra gli esempi precedenti con la nuova rappresentazione:
Value ob_size ob_digit[0] ob_digit[1] Digit Size
0 1 0 Not used 30 bits
1000000 1 1000000 Not used 30 bits
-1000000 1 -1000000 Not used 30 bits
-10000000000 2 336323584 -9 30 bits
Com’è possibile vedere, per numeri interi rappresentabili da 30 bit (in realtà uno in meno: -2^30 viene escluso), che quindi fanno uso di un solo digit, il primo e unico digit conserva esattamente lo stesso valore degli interi corti utilizzati nelle versioni di CPython fino alla versione 2.7.
Nell’implementazione ho pensato di non perdere tempo con l’ottimizzazione del codice per i digit a 15, per cui ho deciso di supportare solamente quelli a 30 bit, che a mio avviso offrono i migliori vantaggi, come vedremo in un prossimo articolo in cui spiegherò meglio perché questa rappresentazione è preferibile alla precedente.
