di  -  mercoledì 7 marzo 2012

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.

4 Commenti »

I commenti inseriti dai lettori di AppuntiDigitali non sono oggetto di moderazione preventiva, ma solo di eventuale filtro antispam. Qualora si ravvisi un contenuto non consono (offensivo o diffamatorio) si prega di contattare l'amministrazione di Appunti Digitali all'indirizzo info@appuntidigitali.it, specificando quale sia il commento in oggetto.

  • # 1
    banryu
     scrive: 

    Interessante, purtroppo mi son perso il talk all’EuroPython e pare che il video del talk non sia più raggiungibile (dal sito dell’EuroPython).

  • # 2
    Antonio Barba
     scrive: 

    Veramente una bella pensata, complimenti :-)

  • # 3
    floriano
     scrive: 

    quindi questa pseudo ottimizzazione che hanno effettuato i progettisti di python è a tutti gli effetti una regressione, mah preferisco i linguaggi che non cambiano così velocememtne senza motivo…

  • # 4
    Cesare Di Mauro (Autore del post)
     scrive: 

    Non si tratta di una “pseudo-ottimizzazione”.

    Con Python 3 si sono voluti togliere di mezzo alcuni aspetti del linguaggio e delle librerie che non erano “pythonici”, facendo un po’ di “pulizia” al linguaggio e ridefinendo alcuni aspetti.

    Non si tratta di un linguaggio completamente diverso, ovviamente, ma alcuni cambiamenti l’hanno reso incompatibile a livello sintattico coi predecessori (in realtà a partire da Python 2.6 è possibile, con alcune direttive, abilitare selettivamente alcuni di questi cambiamenti in modo da poter scrivere programmi che funzionino su 2.6/2.7 e su 3.0+).

    Uno di questi cambiamenti radicali è stato quello dell’unificazione dei tipi interi. Prima c’erano due tipi, gli interi corti e quelli lunghi; da Python 3.0 c’è solo quest’ultimo, che ha preso il posto degli interi.

    Le motivazioni sono nella filosofia che Python propugna da tempo:

    “There should be one– and preferably only one –obvious way to do it.”

    Con un tipo intero, quello lungo, si riesce a fare tutto. E così è stato.

    Anche perché Python viene spesso usato come linguaggio didattico. Ha fatto della semplicità e immediatezza il suo vessillo, e complicare il linguaggio con tipi diversi per fare la stessa cosa è, appunto, una complicazione ulteriore.

    In tutto ciò c’ha rimesso la velocità d’esecuzione, ma per il creatore del linguaggio questo non è un problema. Chi usa Python lo fa in maniera consapevole: sa che è un linguaggio che non nasce per essere veloce e competere con giganti del calibro di C, C++, ma anche Java.

    Ciò detto, la situazione attuale dipende… dall’implementazione attuale. Non è mica detto che l’esecuzione degli interi (ormai soltanto “lunghi”) debba rimanere così. Anzi.

    Intanto ci sono progetti come PyPy che grazie al compilatore JIT integrato migliorano la velocità d’esecuzione anche di 100 volte. Qualche tempo fa nella mailing list di PyPy è stato annunciato di voler supportare finalmente la versione 3 di Python, per cui i benefici del lavoro che hanno fatto arriveranno anche su quest’ultima versione del linguaggio.

    Poi ti assicuro che esistono diverse altre soluzioni per migliorare la velocità d’esecuzione di Python in generale, e degli interi, anche lunghi, in particolare senza ricorrere a compilatori JIT.

    Un’anticipazione è questa serie di articoli con la mia implementazione, che porta un modesto guadagno del 5-7%.

    Ma questa mia idea, combinata con una di queste ultime soluzioni “no-JIT” di cui parlavo, potrebbe tranquillamente non far rimpiangere gli interi corti. Anzi! 8-)

    @banryu: purtroppo ho visto che è rimasto soltanto il video del talk in italiano (scaricabile tramite torrent). Fortunatamente li ho scaricati entrambi.

    Comunque in questa serie di articoli penso di affrontare almeno le parti più importanti, in maniera più discorsiva e chiara.

Scrivi un commento!

Aggiungi il commento, oppure trackback dal tuo sito.

I commenti inseriti dai lettori di AppuntiDigitali non sono oggetto di moderazione preventiva, ma solo di eventuale filtro antispam. Qualora si ravvisi un contenuto non consono (offensivo o diffamatorio) si prega di contattare l'amministrazione di Appunti Digitali all'indirizzo info@appuntidigitali.it, specificando quale sia il commento in oggetto.