Sommare due “long” non è così semplice in CPython

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.