Arrivati ai long (interi “lunghi”) sulla scia dei precedenti articoli sulla macchina virtuale di Python (CPython, quella maggiormente in uso finora), un articolo sull’implementazione della loro somma, a titolo anche di confronto con la medesima operazione per gli interi (corti), era inevitabile.
Il cuore di tutto sta nella funzione long_add, locata nel file longobject.c, che ovviamente riceve come parametri i due oggetti PyLongObject di cui si voglia effettuare la somma:
static PyObject *
long_add(PyLongObject *a, PyLongObject *b)
{
PyLongObject *z;
CHECK_BINOP(a, b);
if (ABS(Py_SIZE(a)) <= 1 && ABS(Py_SIZE(b)) <= 1) {
PyObject *result = PyLong_FromLong(MEDIUM_VALUE(a) +
MEDIUM_VALUE(b));
return result;
}
if (Py_SIZE(a) < 0) {
if (Py_SIZE(b) < 0) {
z = x_add(a, b);
if (z != NULL && Py_SIZE(z) != 0)
Py_SIZE(z) = -(Py_SIZE(z));
}
else
z = x_sub(b, a);
}
else {
if (Py_SIZE(b) < 0)
z = x_sub(a, b);
else
z = x_add(a, b);
}
return (PyObject *)z;
}
In apparenza il funzionamento non sembra complicato, presentando poco codice che, però, si trova per lo più celato all’interno di macro e funzioni che si predono carico rispettivamente delle azioni più frequenti (che, quindi, vanno velocizzate al massimo) o troppo complesse da poter essere “espanse” ogni volta.
Similmente a quanto abbiamo visto per gli interi, prima di procedere è necessario controllare che i due oggetti passati siano effettivamente dei PyLongObject, e ciò avviene tramite la macro CHECK_BINOP:
#define CHECK_BINOP(v,w) \
do { \
if (!PyLong_Check(v) || !PyLong_Check(w)) { \
Py_INCREF(Py_NotImplemented); \
return Py_NotImplemented; \
} \
} while(0)
L’idea è che se i due oggetti non sono quelli che ci si aspetta, viene restituito immediatamente come risultato dell’operazione binaria l’istanza dell’oggetto singleton Py_NotImplemented, in modo tale che Python sia in grado di tentare qualche azione per portarla a compimento, nel caso riuscisse a trovare il modo di “coniugare” i due oggetti.
Lo si capirà meglio in un prossimo articolo in cui descriverò il (complesso) meccanismo che sta alla base dell’operator overloading (e “coercizione” dei tipi).
Il controllo vero e proprio viene svolto da un’altra macro, PyLong_Check:
#define PyLong_Check(op) \ PyType_FastSubclass(Py_TYPE(op), Py_TPFLAGS_LONG_SUBCLASS)
Rispetto allo stesso che abbiamo visto per i PyIntObject, le differenze sono notevoli. Coi classici tipi interi, infatti, era sufficiente controllare che il tipo associato a questa istanza puntasse alla struttura PyInt_Type.
Con Python 3 questo controllo non è sufficiente, poiché il linguaggio è stato esteso in modo da permettere di sfruttare e applicare il lavoro di long_add anche per le istanze che discendono da PyLongObject. Infatti controllare che il tipo sia esattamente PyLong_Type non lo avrebbe permesso.
Per aggirare questa limitazione mantenendo una certa velocità di esecuzione si fa uso di una mappa di bit in tutti i discendenti di PyType (PyInt_Type, PyLong_Type, ecc.; tutte le classi / tipi, in sostanza) che specificano una serie di caratteristiche che possiede il tipo in questione.
Fra questi, c’è un bit che è riservato e impostato per tutte le istanze di PyLong_Type o di tutti i suoi discendenti, ed è esattamente ciò che controlla la macro PyType_FastSubclass tramite l’ulteriore macro PyType_HasFeature:
#define PyType_FastSubclass(t,f) PyType_HasFeature(t,f) #define PyType_HasFeature(t,f) (((t)->tp_flags & (f)) != 0)
Nonostante questo susseguirsi di scatole cinesi, alla fine l’operazione di controllo svolta si riduce al controllo del flag f (cioè Py_TPFLAGS_LONG_SUBCLASS) nel campo tp_flags della struttura PyType che definisce l’insieme di bit / caratteristiche associate a questo tipo.
Ricapitolando, si estrae il tipo (campo ob_type di qualunque oggetto Python, come abbiamo già visto), si prelevano i flag (campo tp_flags della struttura PyType che definisce il tipo di un oggetto), e si controlla il flag Py_TPFLAGS_LONG_SUBCLASS.
Superata la barriera del controllo del tipo dei due oggetti, si può passare dunque al calcolo vero e proprio. Nello specifico, si presentano due casi: quello più comune, in cui siamo in presenza di una somma di long costituiti da al più un digit (di 15 o 30 bit, come abbiamo visto nel precedente articolo), oppure quello più generale in cui i long sono costituiti da più di un digit per almeno uno dei due operandi.
Per discriminare fra i due casi serve un ulteriore controllo che fa capo al primo if presente nel codice. La macro Py_Size, che abbiamo già visto per le stringhe, recupera il numero di elementi (digit in questo caso, caratteri per le stringhe) contenuti nelle due istanze, e verifica che il valore assoluto sia 0 oppure 1.
L’applicazione del valore assoluto si rende necessaria perché, come visto nel precedente articolo, il campo ob_size (estratto da Py_Size) viene utilizzato impropriamente nei long per conservare anche il segno dell’intero.
Se entrambi i long si scopre essere “corti”, si procede col percorso veloce, che prevede l’estrazione dei rispettivi valori interi (intesi come tipi int del C), la somma, e la conversione del risultato nuovamente in PyLongObject, tramite la funzione PyLong_FromLong.
L’estrazione del valore intero avviene grazie alla macro MEDIUM_VALUE:
/* convert a PyLong of size 1, 0 or -1 to an sdigit */
#define MEDIUM_VALUE(x) \
(Py_SIZE(x) < 0 ? -(sdigit)(x)->ob_digit[0] : \
Py_SIZE(x) == 0 ? (sdigit)0 : \
(sdigit)(x)->ob_digit[0]))
Il funzionamento è molto semplice: se il numero è negativo, si preleva e cambia il segno all’unico digit presente; se è zero, si restituisce 0; infine, se è positivo, restituisce il digit così com’è.
Della funzione PyLong_FromLong ne parlerò in un apposito articolo, data la complessità del lavoro che svolge, mentre l’ultima parte del codice riguarda il caso generale di somma di due long di dimensione arbitraria e, al di là della relativa lunghezza (rispetto al percorso più semplice e veloce), risulta piuttosto semplice da capire.
Le funzioni x_add e x_sub si occupano rispettivamente di sommare e sottrare i digit dei due oggetti PyLongObject, non tenendo conto del loro segno, e restituendo un nuovo oggetto PyLongObject. Per la prima il long che ritorna è sempre positivo, mentre per la seconda può essere negativo (se, in valore assoluto, il secondo long è più grande del primo).
Tenendo conto di tutto ciò, risulta facile a questo punto capire il resto del codice, che si occupa semplicemente di considerare i quattro casi che si possono presentare a seconda del segno dei due numeri:
- se sono entrambi negativi, si esegue la somma regolare (dei valori assoluti), e se esiste il PyLongObject ed è diverso da zero, gli si cambia il segno;
- se il primo (a) è negativo e il secondo (b) non lo è, si calcola b – a (i numeri, lo ricordo ancora, sono sempre presi in valore assoluto);
- se il primo (a) è non negativo, e il secondo (b) è negativo, si calcola la normale sottrazione a – b;
- infine se sono entrambi non negativi, li si somma.
Niente di trascendentale insomma, tenendo però conto che la reale complessità dell’operazione di somma rimane racchiusa all’interno delle (grandi) funzioni utilizzate, ma serve a comprendere le notevoli differenze che è già possibile cogliere rispetto alla somma di due oggetti PyIntObject di cui abbiamo già parlato, e che ovviamente comportano un decadimento delle prestazioni.
Una cosa che mi incuriosisce e’ che, se la memoria non mi inganna, in un qualche commento di qualche articolo fa avevi scritto che Python e’ ormai usato molto anche dalla comunita’ matematica, e che molti lo preferiscono a Matlab per via delle molte librerie numeriche eccetera.
Pero’: se solo per sommare due interi bisogna fare ‘sto casotto inenarrabile, e come dicevi la scorsa volta c’e’ una perdita di prestazioni di piu’ di un ordine di grandezza rispetto alla somma di interi in HW (anzi, se ricordo bene c’e’ piu’ di un numero di grandezza di ISTRUZIONI in piu’, che e’ ancora peggio :) , cosi’ a naso sarebbe la mia ultima scelta per scrivere del codice di calcolo numerico. Matlab e’ si’ interpretato, ma usa tipi standard supportati dall’HW e le sue routine interne sono (che io sappia) compilate per andare alla massiam velocita’ (se fai delle operazioni matriciali, e’ piuttosto veloce).
L’unico vantaggio (non da poco, eh! anzi) che mi viene in mente e’ che Matlab bisogna pagarlo, e Python no… infatti ormai non lo uso quasi piu’, quando mi capito sfrutto quello che ho in ufficio.
Hai perfettamente ragione. Infatti gli scienziati non usano Python “nudo e crudo”, ma anche delle librerie che sono state sviluppate per effettuare velocemente calcoli con vettori e matrici.
NumPy, Scipy (che usa la precedente) e matplotlib sono GLI strumenti che non possono mancare per sostituire agevolmente Matlab. E ce ne sono altre per altri campi della scienza, come la bioinformatica, ad esempio.
Ovviamente si tratta di librerie scritte in C proprio per questioni di velocità, ma vale lo stesso per Mathlab & affini.
In questo modo si unisce la facilità e velocità di prototipazione tipica di Python (con in più una notevole leggibilità e manutenibilità del codice; al contrario di linguaggi come Perl che vengono definiti “write-only”) alla velocità di esecuzione necessaria quando c’è da manipolare grosse quantità di dati.
Azz… c’è un bel po’ di codice dietro delle (apparentemente) semplici operazioni aritmetiche. Inizio a pensare che un linguaggio più sia comodo da usare e “bello” stilisticamente, meno sia efficiente nel number crunching.
Probabilmente non lo userei mai per operazioni di calcolo o per lo sviluppo di applicazioni con forti requisiti prestazionali. Al massimo lo userei per la creazione di tools di sviluppo, script per automatizzare alcune cose, per sviluppare prototipi di algoritmi complessi (da reimplementare successivamente in linguaggi più adatti al calcolo pesante), ecc…
In effetti è così: la comodità si paga. In particolare in Python 3, dove gli interi sono diventati di dimensione variabile, al contrario di Python < 3, dove gli interi corti erano più efficienti. Comunque non mi pongo problemi per le prestazioni del codice Python che scrivo. Nella mia esperienza, difficilmente mi sono sentito limitato in tal senso. Eventualmente si può pensare a soluzioni algoritmiche, oppure usare strumenti com Cython ( http://cython.org/ ) oppure passare a PyPy ( http://speed.pypy.org/ ).
Insomma, gli strumenti ci sono per mantenere il codice elegante, compatto, e manutenibile con Python, se serve anche un occhio di riguardo alle prestazioni.
Poi è chiaro che se le prestazioni diventano IL problema, allora si passa ad altro. Python non ha la pretesa di coprire tutti i campi.
Sempre interessanti questi tuoi articoli, Cesare :)
Ho una curiosità sulla macro CHECK_BINOP: perchè il codice con cui viene espansa è racchiuso in un ciclo a singola iterazione (il do…while(0)) ?
@banryu: il do..while serve ad isolare il ramo dell’istruzione “if”.
Se non ci fosse tale ciclo, e la macro si trovasse dopo un if e prima di un else, potrebbe scombinare completamente il significato del programma (l’else non farebbe più riferimento al primo if, ma all’if contenuto nella macro) e causare un bug difficilissimo da scovare.
Per questo motivo sarebbe saggio usare le funzioni inline al posto delle macro che sono presenti anche nel C a partire dalla versione ANSI ISO C-99 :-)
Purtroppo il codice di CPython è volutamente ANSI C89, perché gira anche su sistemi che non hanno né un compilatore C99 né tanto meno uno C++.
@Antonio Barba: grazie del chiarimento.
@Cesare: peccato, con il C99 si potrebbe pulire parecchio il codice pur mantenendo inalterate le prestazioni.
Già. Purtroppo è il prezzo da pagare per aumentare il bacino d’utenza di Python.
Nello specifico, quali sarebbero le piattaforme tagliate fuori nel caso si switchasse al C99?
Immagino che tutte le piattaforme dotate di GCC non dovrebbero soffrire alcun problema, quindi rimangono veramente poche alternative…
Francamente non ne ho idea. So che se n’è parlato nella mailing list degli sviluppatori, ma non ricordo quali sistemi fossero C89-only.
E’ evidente come il progetto non sia spinto da logiche di mercato ma semplicemente da una community di appassionati, dato che GCC copre “virtualmente” qualsiasi cosa che abbia dentro una CPU, magari ci sono 11-12 persone nel mondo che compilano Python con qualche OS arcaico :-D
Diciamo che la comunità Python pensa prima di tutto al linguaggio e alla sua diffusione.
Al mercato ci pensa pure, ma non in maniera da intralciare i loro (sani, per me) principi. ;)
Comunque tanti vecchi sistemi sono stati eliminati col tempo, perché le risorse non sono infinite: http://www.python.org/dev/peps/pep-0011/
Magari col tempo spariranno anche quelle piattaforme che sono soltanto ANSI C89, per cui si potrà pensare a passare al C99 o, addirittura al C++.
Il problema, in questo caso, è che i compilatori esistenti non sono tutti fedeli agli standard, per cui le rogne ci sarebbero comunque. :|