Nel precedente articolo abbiamo visto a grandi linee in che modo viene eseguita una somma fra due interi “lunghi” (long) di CPython (il codice riguardava la versione 3.2, per la precisione), puntando l’attenzione sul caso migliore (che dovrebbe anche essere il più comune).
Dalla discussione era rimasta fuori la funzione PyLong_FromLong, che si occupa di convertire il risultato dell’operazione dal tipo long del C al PyLongObject col quale lavora la macchina virtuale, ma a causa della complessità ho preferito trattarla separatamente.
/* Create a new long int object from a C long int */
PyObject *
PyLong_FromLong(long ival)
{
PyLongObject *v;
unsigned long abs_ival;
unsigned long t; /* unsigned so >> doesn't propagate sign bit */
int ndigits = 0;
int sign = 1;
CHECK_SMALL_INT(ival);
if (ival < 0) {
/* negate: can't write this as abs_ival = -ival since that
invokes undefined behaviour when ival is LONG_MIN */
abs_ival = 0U-(unsigned long)ival;
sign = -1;
}
else {
abs_ival = (unsigned long)ival;
}
/* Fast path for single-digit ints */
if (!(abs_ival >> PyLong_SHIFT)) {
v = _PyLong_New(1);
if (v) {
Py_SIZE(v) = sign;
v->ob_digit[0] = Py_SAFE_DOWNCAST(
abs_ival, unsigned long, digit);
}
return (PyObject*)v;
}
#if PyLong_SHIFT==15
/* 2 digits */
if (!(abs_ival >> 2*PyLong_SHIFT)) {
v = _PyLong_New(2);
if (v) {
Py_SIZE(v) = 2*sign;
v->ob_digit[0] = Py_SAFE_DOWNCAST(
abs_ival & PyLong_MASK, unsigned long, digit);
v->ob_digit[1] = Py_SAFE_DOWNCAST(
abs_ival >> PyLong_SHIFT, unsigned long, digit);
}
return (PyObject*)v;
}
#endif
/* Larger numbers: loop to determine number of digits */
t = abs_ival;
while (t) {
++ndigits;
t >>= PyLong_SHIFT;
}
v = _PyLong_New(ndigits);
if (v != NULL) {
digit *p = v->ob_digit;
Py_SIZE(v) = ndigits*sign;
t = abs_ival;
while (t) {
*p++ = Py_SAFE_DOWNCAST(
t & PyLong_MASK, unsigned long, digit);
t >>= PyLong_SHIFT;
}
}
return (PyObject *)v;
}
Al solito, suddividendo il codice in parti risulta molto più semplice comprenderne le funzionalità. Il concetto rimane sempre lo stesso: partire dai casi più comuni da trattare velocemente, fino ad arrivare a quello più complesso e generale.
Questo si traduce nel ricorso alla macro CHECK_SMALL_INT quale prima “istruzione” eseguita in assoluto, e dal codice si capisce bene il perché:
#define CHECK_SMALL_INT(ival) \
do if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) { \
return get_small_int((sdigit)ival); \
} while(0)
Anche per gli oggetti long, come per gli interi “corti” di Python <= 2.7, si fa ricorso a una cache che conserva quelli più comunemente usati (fra -5 e 256) e che risultano, pertanto, già allocati e immediatamente utilizzabili.
E’ sufficiente controllare che il valore del long rientri fra questi fortunati valori, per restituire eventualmente l’istanza tramite la chiamata alla funzione get_small_int:
static PyLongObject small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
static PyObject *
get_small_int(sdigit ival)
{
PyObject *v = (PyObject*)(small_ints + ival + NSMALLNEGINTS);
Py_INCREF(v);
return v;
}
small_ints è il vettore che mantiene tutte le istanze pre-allocate, per cui basta convertire il valore nel corrispondente indice per recuperare l’oggetto a cui siamo interessati. Prima di restituirlo serve, comunque, aumentare il contatore per il reference count.
Se non rientriamo in questo caso, bisogna sicuramente allocare un nuovo oggetto PyLongObject, e memorizzarvi opportunamente il valore long, per cui si provvede inizialmente a estrarne separatamente segno e valore assoluto (dicendo addio al complemento a due), in modo da lavorare più velocemente su queste entità quando sarà necessario.
L’altro caso molto comune riguarda la presenza di un solo digit da memorizzare, e per questo si controlla se il valore assoluto appena estratto non superi 2^15 – 1 oppure 2^30 – 1, a seconda della dimensione del digit.
Questo controllo (!(abs_ival >> PyLong_SHIFT)) a mio avviso risulta inefficiente, per cui nella mia implementazione dei long ho provveduto a fornirne una versione alternativa (in realtà ho riscritto l’intera funzione), che mostrerò in qualche articolo dedicato al talk che ho tenuto all’ultima EuroPython.
In ogni caso, se rientriamo in questa condizione il codice è di gran lunga semplificato. Infatti basta allocare un nuovo oggetto con un solo digit (facendo uso della funzione interna _PyLong_New), conservando il segno nel campo ob_size (tramite la macro Py_SIZE) della struttura PyLongObject che conserva il numero di digit (ricordo che, per ottimizzare lo spazio occupato, il segno risulta memorizzato assieme al numero di digit), e infine ricopiando il valore assoluto nel primo e unico digit a disposizione.
Prima di passare a quello più generale, è presente un’ulteriore specializzazione di quest’ultimo scenario, che riguarda le compilazioni di CPython facenti uso di digit a 15 bit. Se il valore assoluto copre due digit, viene allocato un PyLongObject contenente due digit, appunto, memorizzando in ob_size il segno moltiplicato per 2, e infine copiando nei due digit rispettivamente i primi 15 bit (quelli più “bassi”) e i 15 successivi.
L’ultimo è ovviamente il caso più complesso e che richiede più attenzione. Per prima cosa bisogna tenere conto del fatto che non sappiamo qual è la dimensione di un long in termini di bit, e quindi il massimo numero di digit che è possibile utilizzare per conservare un qualunque valore long. In realtà con un po’ di lavoro in fase di compilazione lo si può determinare e agire di conseguenza (ed è quello che ho fatto nella mia implementazione).
Il principio di funzionamento del primo ciclo while serve proprio a determinare quanti digit sono necessari per poter conservare il valore assoluto del valore, che ogni volta viene fatto scorrere a destra del numero di bit allocati per ogni digit, fino a quando non diventa zero.
Una volta noto il numero di digit, si alloca un oggetto PyLongObject di dimensione adeguata, e si memorizzano sia il numero di digit che il segno (per quanto detto in precedenza).
A questo punto si procede con un ciclo while simile al precedente, ma il cui scopo è quello che di estrarre ogni volta un numero di bit pari alla dimensione di un digit, conservandoli via via nei digit allocati per questa struttura.
E’ chiaro che questo scenario è quello molto più lento, ma fortunatamente anche quello meno comune, per cui generalmente non verrà mai eseguito. Anche di questo ho fornito una versione appositamente ottimizzata nel mio lavoro, che presenterò a tempo debito.
