di  -  mercoledì 14 marzo 2012

L’esperienza che ho maturato in trenta, lunghi, anni di programmazione si potrebbe racchiudere nella seguente massima: “32 bits ought to be enough for anybody“, parafrasando una massima che viene erroneamente attribuita a Bill Gates.

La stessa frase la si potrebbe riscrivere, senza alterarne il significato, cambiando 32 con 8 all’epoca d’oro dei microprocessori a 8 bit, con 16 per l’era dei 16 bit, e… con 64 visto che siamo già entrati in quella dei 64 bit (di macchine a 128 bit non credo che ne parlerò).

Tutto ciò ha senso perché i progressi della tecnologia ci hanno portato ad alzare via via l’asticella dei limiti che erano stati raggiunti in quel determinato periodo per le macchine che si contendevano la fetta di mercato maggiore (quella consumer e professionale; quindi non accademica o di particolari nicchie).

Da un punto di vista strettamente algoritmico il problema nemmeno si pone: i limiti sono strettamente legati all’algoritmo, a quello che deve calcolare effettivamente. Se avrà a che fare con quantità a 16 bit, il fatto di avere in quella macchina la possibilità di manipolare 64 bit alla volta non cambia assolutamente nulla; ci saranno i 48 bit alti che rimarranno sostanzialmente inutilizzati (sempre a zero, oppure a zero a “-1″ a seconda del segno del risultato; dipende tutto dall’implementazione dell’ISA).

Per una macchina a 8 bit ovviamente si porrà il problema della manipolazione di quantità a 16 bit, visto che si tratta di numeri che non riesce a gestire “nativamente” / direttamente, a causa dei limiti intrinseci della sua architettura. Di conseguenza si dovranno adottare delle tecniche o, più probabilmente, delle “librerie” per gestire questi casi.

Questa piccola introduzione serve a comprendere in che situazione ci si trova lavorando con gli interi e, in particolare, coi long di Python; in ultima analisi è proprio ciò che influenza le prestazioni della macchina virtuale quando si trova a processare il codice che gli diamo in pasto, ossia la concretizzazione degli algoritmi che ci sono serviti per risolvere il determinato problema.

Fino a Python 2.x esistono gli interi “corti” (a 32 o 64 bit) e quelli “lunghi” (limitati dalla memoria a disposizione). Un algoritmo che utilizza normalmente gli interi corti può passare automaticamente a quelli lunghi perché CPython quando si accorge che il risultato di un’operazione non è in grado di essere rappresentato coi primi.

In maniera similare, in CPython 3.x, che possiede soltanto gli interi lunghi, si passa dall’utilizzare uno o più “digit” (ho voluto semplificare il discorso senza tenere conto dello zero) a seconda di quanto spazio sia necessario per rappresentare il risultato.

I casi borderline in entrambe le versioni maggiori del linguaggio rimangono due: il passaggio dall’intero corto a quello lungo, oppure da un intero con un solo digit a uno con più digit.

Quest’ultimo ovviamente è presente anche in CPython 2.x, perché anch’esso mette a disposizione gli interi lunghi, ma concretamente si tratta di eventi molto rari (specialmente su macchine a 64 bit), proprio perché normalmente si lavora con gli interi corti, e a quelli lunghi si arriva a causa di sopraggiunti overflow nei primi; overflow che, per quanto detto, richiederanno sicuramente più di un digit per contenere il risultato finale.

Il nocciolo della questione è che risulta importante focalizzare l’attenzione su quello che capita realmente, più frequentemente, all’interno della macchina virtuale quando abbiamo a che fare con gli interi.

Cosa cambierebbe se la frase iniziale la riscrivessimo così:

31 bits ought to be enough for anybody

oppure così:

30 bits ought to be enough for anybody

Molto? Poco? Tantissimo? Per nulla?

Dipende tutto dagli algoritmi, dal codice che viene fatto girare, ma alla fine una decisione la si deve prendere, alcuni paletti vanno necessariamente fissati, altrimenti non avremmo avuto macchine a 8, 16, 32, e non saremmo arrivati ai famigerati 64 bit.

Esistono alcuni studi (di cui purtroppo ho perso i riferimenti) i quali dimostrano, su un ventaglio di algoritmi sufficientemente ampio, che la maggioranza dei valori interi manipolati ricade nel dominio dei 16 bit (con quelli a 8 bit a fare la parte del leone), e che la stragrande maggioranza non manipola più di 32 bit. Inoltre la maggior parte di essi riguarda quantità non negative (quindi i positivi, più lo zero).

Sono dati che, esperienza alla mano, sembrano ovvi, ma non per chi deve implementare una macchina virtuale con dei limiti precisi e che deve prendere decisioni che possono avere anche gravi ripercussioni sulle prestazioni generali.

Pensiamo un attimo al caching degli interi che è stato implementato in CPython. Come abbiamo visto, la virtual machine mantiene i valori da -5 a 256 in un’apposita tabella per evitare di allocare e deallocare continuamente strutture di tipo PyIntObject, restituendolo (quasi) immediatamente la relativa istanza quando il risultato di un’operazione è racchiuso in quest’intervallo.

E’ chiaro che la scelta dei due limiti, -5 e 256, è stata fatta in maniera opportuna, quale miglior compromesso raggiungibile sulla scorta degli studi di cui sopra e dei risultati ottenuti effettuando dei tentativi e profilandone l’esecuzione.

Se gli sviluppatori della VM avessero tenuto conto soltanto degli studi statistici, avrebbero potuto benissimo pensare di estendere il caching all’intero intervallo dei numeri a 16 bit (da -32768 a 32767; e magari portare quest’ultimo fino a 65535), essendo sicuri di coprire la maggior parte dei casi.

Alla fine, a conti fatti, quanto sarebbe costato tutto ciò? Poco. Per un’architettura 32 bit un PyIntObject occupa (generalmente) 12 byte (4 byte per il reference count, 4 per il puntatore al tipo / classe a cui appartiene, e 4 per il valore vero e proprio), e 24 byte per un’architettura a 64 bit. Supponendo di allineare i risultati a 16 byte per ogni istanza, servirebbero 16 e 32 byte rispettivamente; non molto, insomma.

65536 istanze di PyIntObject necessarie per coprire l’intero range dei 16 bit richiederebbero, quindi, 1 e 2MB di memoria per le architetture a 32 e 64 bit. Una miseria, visto che la memoria si misura ormai in termini di GB da diversi anni.

Estendere la cache a tutti questi valori, però, non è affatto detto che avrebbe portato a un miglioramento generale delle prestazioni. Infatti mentre adesso 262 (257 + 5) valori occupano circa 4 e 8KB di memoria ed è presumibile che si trovino tutti all’interno della cache L1 della CPU, 1 e 2MB comporterebbero un eccessivo “trashing” delle linee di cache L1, che dovrebbero essere continuamente rimpiazzate a seconda degli interi (o dell’intero) manipolati in quel preciso momento.

Altri studi dimostrano (mi spiace, ma anche qui ho perso il link alla pubblicazione) che il numero di valori interi distinti utilizzati in un ben preciso momento (immaginiamo di “fotografare” lo stato della VM) è generalmente piccolo, per cui una strategia come quella prima esposta non è conveniente anche dal punto di vista dello spazio occupato (che ad esempio è importantissimo in un server che deve far girare centinaia e anche migliaia di istanze della stessa VM, oppure in sistemi embedded dove la memoria scarseggia).

Il compromesso migliore, quindi, è quello di avere una cache piccola per i valori più comuni, e un pool di strutture PyIntObject “vuote” (inutilizzate) dal quale attingere quando serve memorizzare un intero che non si trova in cache (e, viceversa, “liberare” un intero che non serve più; quindi senza deallocarne la struttura). Il classico colpo al cerchio e alla botte.

Ricapitolando, una VM come quella di Python (e altri linguaggi) ha a che fare con due limiti “strutturali”: il range di interi rappresentabili nell’unità di misura adottata (tipo long del C a 32/64 bit per quelli “corti”; digit per quelli lunghi) e il numero di istanze contemporaneamente presenti / gestibili.

Vedremo in un prossimo articolo qualche esempio pratico delle conseguenze relative ad alcune scelte fattibili per il primo dei due limiti strutturali.

7 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
    Antonio Barba
     scrive: 

    […] un pool di strutture PyIntObject “vuote” (inutilizzate) dal quale attingere quando serve memorizzare un intero che non si trova in cache (e, viceversa, “liberare” un intero che non serve più; quindi senza deallocarne la struttura) […]

    Si chiama Object Caching, o anche Object Pool Allocator, ed è una tecnica fondamentale. L’ho usata estensivamente sui miei giochi Nintendo DS (che ha solo 4MB di Ram totali) per eliminare il problema dei memory leaks e della frammentazione della memoria.

    :-)

  • # 2
    banryu
     scrive: 

    Altro articolo interessante Cesare, grazie :-)

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

    E’ un piacere. :)

    @Antonio: purtroppo faccio a pugni coi nomi. Posso applicare pattern grazie all’esperienza che mi porta a modellare il software in un certo modo, ma da lì a dargli un nome per me è un grosso problema. -_-

  • # 4
    dave
     scrive: 

    giusto per spaccare i maroni…

    32 bits “should be” enough for anybody :)

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

    La conoscevo anch’io in quella forma, ma tempo fa cercando qualche fonte sembra che la versione “più corretta” (lo metto tra virgolette perché comunque parliamo di una leggenda metropolitana) sembra quella che ho messo nell’articolo.

    Comunque una vale l’altra. :P

  • # 6
    Antonio Barba
     scrive: 

    @Cesare: i nomi sono utili “relativamente”. Se entrambi conosciamo com’è fatto un gatto, e io dico “Gatto”, ci capiamo all’istante.
    Se invece stai spiegando il gatto a dei marziani, puoi tranquillamente chiamarlo “essere vivente a base di carbonio che fa miaaao” :-D

    In questo specifico caso i marziani siamo noi, ma vabbè il concetto è lo stesso! :D

    La tua spiegazione del funzionamento di un Pool Allocator la trovo corretta, semplice e chiara (a patto di avere un’infarinatura di programmazione ovviamente), e questa è la cosa più importante.

  • # 7
    Gendo Ikari
     scrive: 

    Articolo interessantissimo, come sempre.

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.