Alla fine quanto costa una somma in CPython?

Dopo gli articoli che hanno approfondito i meccanismi che scattano quando si utilizza l’operatore + in CPython (fino alla versione 2.7. Dalla 3.0 in poi si è verificato un cambio sostanziale, che analizzeremo in seguito), il dubbio espresso è legittimo.

Le operazioni di somma di interi (e di concatenazione di stringhe) sono quelle più diffuse e per le quali è stata posta particolare attenzione dagli sviluppatori della macchina virtuale di CPython, ma bisogna distinguere i casi che possono verificarsi.

Gli interi sono in assoluto il tipo di dati più utilizzato, e che ha quindi goduto di un trattamento “di favore” da chi ha lavorato alla VM. Infatti abbiamo visto che il primo controllo sul tipo di dati di entrambi gli operatori è riservato proprio a loro.

Restringendo il dominio ai soli interi, i casi possibili che si verificano generalmente sono tre:

  • somme di interi “piccoli”
  • somme di interi qualunque
  • somme di interi che generano “long

Quest’ultimo caso è piuttosto raro nella pratica comune (“32 bits should be enough for anybody“), ma riveste un ruolo fondamentale in Python 3.0 e successori, poiché gli interi di cui abbiamo parlato finora sono spariti, rimpiazzati dai cosiddetti “long“, cioè interi lunghi, ovvero a dimensione variabile e che possono rappresentare qualunque valore, limitatamente alla memoria a disposizione e alla capacità di calcolo a disposizione.

Ovviamente c’è un costo salato da pagare, e infatti le prestazioni di Python 3 hanno subito un sensibile calo (del 30% circa, se la memoria non m’inganna), che Guido van Rossum (il “papà” di Python) e collaboratori hanno ritenuto giustificato dai vantaggi ottenuti nell’avere un solo tipo di dato intero da gestire.

Delle differenze fra gli attuali interi e i long ne parlerò più approfonditamente in futuro, discutendo del lavoro che ha presentato alla scorsa EuroPython, in cui ho presentato una soluzione ad hoc che cercasse di sfruttare i pregi di entrambi nell’ottica del codice comunemente eseguito.

Infatti questo rientra nei primi due casi (estremi) citati, o al più in entrambi, a seconda della “mistura” di interi manipolati da un particolare pezzo di codice. Non tutti gli interi sono utilizzati allo stesso modo e con la stessa frequenza, e ciò ha portato appunto al caching di un range di valori che va da -5 a 256, come abbiamo visto in precedenza.

Grossolanamente possiamo affermare che la manipolazione di quantità senza segno a 8 bit è stata di gran lunga privilegiata, in quanto si tratta di valori che si usano e s’incontrano molto spesso, ad esempio nella comunissima esecuzione di piccoli cicli (che magari fanno uso di indici per referenziare gli elementi di una tupla o lista).

Il codice eseguito, tenendo conto del fatto di essere soltanto in questo caso, risulta essere il seguente:

w = POP(); // 2
v = TOP();  // 1
if (PyInt_CheckExact(v) && PyInt_CheckExact(w)) // 6
/* INLINE: int + int */
register long a, b, i;
a = PyInt_AS_LONG(v); // 1
b = PyInt_AS_LONG(w); // 1
i = a + b; // 1
if ((i^a) < 0 && (i^b) < 0) // 6
x = PyInt_FromLong(i); // 3
Py_DECREF(v); // 4
Py_DECREF(w); // 4
SET_TOP(x); // 1
if(x != NULL) // 2
continue; // 0

Ho eliminato le righe di codice non eseguite, mantenendo gli if soltanto per sottolineare la valutazione dell’espressione (che va fatta a prescindere, ovviamente)

Aggiungendo anche il codice effettivamente eseguito dalla funzione PyInt_FromLong:

#define NSMALLNEGINTS		5
#define NSMALLPOSINTS		257
static PyIntObject *small_ints[NSMALLNEGINTS + NSMALLPOSINTS];

PyObject *PyInt_FromLong(long ival)
{
  register PyIntObject *v;
  if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) // 4
  v = small_ints[ival + NSMALLNEGINTS]; // 1
  Py_INCREF(v); // 3
  return (PyObject *) v; // 2
}

anche qui con la riga dell’if lasciata soltanto per tenere conto dell’espressione valutata.

Volendo fare una valutazione volutamente semplicistica (cioè senza tenere conto né dell’ISA né della particolare implementazione) assegnando un certo numero di istruzioni eseguite per ogni riga, tutto sommato il quadro non risulta malvagio: 42 istruzioni eseguite, quando in C probabilmente ne sarebbero servite 4 (due load, una somma, uno store), pari a circa un ordine di grandezza di differenza.

Prendendo il caso più generale, cioè quello della somma di due interi il cui risultato non sia un intero “corto”, cambia soltanto il codice eseguito dalla funzione PyInt_FromLong:

PyObject *PyInt_FromLong(long ival)
{
  register PyIntObject *v;
  if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) // 4
  if (free_list == NULL) // 3
	/* Inline PyObject_New */
  v = free_list; // 1
  free_list = (PyIntObject *)Py_TYPE(v); // 2
  PyObject_INIT(v, &PyInt_Type); // 4
  v->ob_ival = ival; // 2
  return (PyObject *) v; // 2
}

Con le stesse considerazioni di prima, abbiamo un totale di 50 istruzioni eseguite, assumendo pure che la lista di interi già allocati non sia vuota (capita soltanto alla prima esecuzione del codice oppure dopo un’operazione di pulizia “pesante” del garbage collector).

Non sembra un grosso peggioramento (parliamo di circa il 20% in più di istruzioni eseguite rispetto al caso degli interi piccoli), ma bisogna anche tener conto del fatto che la memoria consumata in questo caso risulta maggiore (per ogni intero utilizzato deve esistere un’apposita struttura allocata).

Questo fa capire quanto sia importante anche la scelta di alcuni costrutti sintattici e/o algoritmi utilizzati in alcuni casi. Un esempio classico è quello del ciclo for che scorre un indice intero fino a un certo valore.

Spesso in Python si vede codice come questo:

for i in range(n):
  print i

La funzione built-in range genera un’intera lista di valori interi che vanno da 0 a n – 1, e soltanto dopo che la lista è stata costruita viene passata al costrutto for che ne scorre gli elementi uno alla volta. Alla fine del costrutto l’intera lista generata da range viene distrutta, perché non risulta più utile.

A parte il costo dell’allocazione e deallocazione della lista, che potremmo anche trascurare, non si può certo chiudere un occhio per tutti gli interi generati.

Finché si tratta di interi “corti”, abbiamo visto che non c’è alcun problema, perché vengono riciclati grazie al meccanismo di caching. Diversamente CPython impiegherà parecchio tempo e, soprattutto, memoria per tutti gli altri interi.

Usando la funzione xrange al posto di range si ottiene lo stesso risultato, ma al for non viene passata la lista intera, quanto un generatore, cioè un oggetto che genera un elemento alla volta ogni volta che serve al for, limitando drasticamente l’uso di memoria e le operazioni di allocazione e deallocazione, oltre che di inizializzazione delle nuove istanze.

E’ soltanto un esempio di come la scelta di una soluzione piuttosto che un’altra possa cambiare anche radicalmente l’uso delle risorse della macchina, alla luce del modo in cui CPython ha implementato la gestione del tipo di dati intero.

Press ESC to close