di  -  mercoledì 23 novembre 2011

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.

10 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
    banryu
     scrive: 

    Interessante questa analisi fatta osservando il numero di istruzioni per riga di codice eseguito. Già solo capire a spanne l’ordine di grandezza in gioco (10:1) è utile a farsi un’idea; poi c’è da considerare l’uso della memoria.

    In effetti, alla luce di questo secondo articolo mi pare ancora più chiara l’utilità della cache dei “piccoli interi”.

    Avendo perso il talk sono piuttosto incuriosito circa la tua soluzione che hai presentato alla scorsa EuroPython.

    “”
    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.
    “”
    Interessante, questo mi ricorda la lazy evaluation tipica di certi linguaggi funzionali (ho in mente Haskell), oppure una sorta di iteratore “intelligente” che invece di iterare su una lista, genera lui stesso il nuovo valore da restituire al chiamante ad ogni invocazione (beh, immagino sia così che funziona un generatore?).

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

    Infatti, è esattamente così. Ho parlato di generatore perché effettivamente i valori vengono generati uno alla volta.

    Invece il termine iteratore in genere viene usato quando c’è da processare una sequenza (restituendone un’altra, ad esempio).

    Della mia soluzione ne parlerò approfonditamente più avanti. Sarà utile anche per capire il passaggio ai long, che da Python 3 sono l’unico tipo di dati intero con cui un programmatore ha a che fare.

  • # 3
    Antonio Barba (TheKaneB)
     scrive: 

    beh, un’espansione 10:1 sulle operazioni di number crunching non mi sembra troppo grave. Sicuramente chi sviluppa in Python lo fa per avere buoni risultati con tempi di sviluppo brevi.

    Se una certa applicazione dovesse avere come requisito un’elevata efficienza di calcolo, bisogna per forza di cose rinunciare a linguaggi evoluti come Python e puntare su linguaggi di più basso livello. Oppure, in alternativa, si possono realizzare librerie in C/C++ contenenti gli algoritmi ottimizzati, e interfacciare poi il tutto con il resto dell’applicazione in Python (si può fare, no?) :-)

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

    Certo. Python è molto diffuso anche grazie al fatto che consente abbastanza facilmente sia l’embedding (vedi Civilization 4, ad esempio, che è interamente scriptato in Python) che l’extending (realizzando quindi moduli / librerie in altri linguaggi, da importare semplicemente in Python).

    Comunque c’è una cosa che ho dimenticato di dire: nel computo non è incluso il costo del ciclo principale di valutazione della VM. Non sono molte istruzioni, però ci sono, ma la loro presenza non fa certo aumentare di un ordine di grandezza il costo.

  • # 5
    banryu
     scrive: 

    @Antonio Barba:

    beh, un’espansione 10:1 sulle operazioni di number crunching non mi sembra troppo grave.

    Si ma si parla degli interi, immagino che per le applicazioni “number crunching intensive” sia più rilevante andare a vedere i costi associati alla manipolazione dei floating point.

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

    Certamente. C’è anche da dire che con la VM di Python si può eseguire una somma di interi (ma anche di valori in virgola mobile) prelevandola dallo stack e basta, mentre un compilatore statico per altri linguaggi può generare codice ottimizzato a suo piacimento, sfruttando anche estensioni SIMD et similia.

    Le differenze, quindi, possono essere molto più rilevanti (penso si possa aggiungere un altro ordine di grandezza con le SIMD).

    P.S. Per le citazioni si deve usare il tag XML blockquote. ;)

  • # 7
    banryu
     scrive: 

    P.S. Per le citazioni si deve usare il tag XML blockquote. ;)

    Many tanks ;)

  • # 8
    Antonio Barba (TheKaneB)
     scrive: 

    a maggior ragione si evidenzia quello che dicevo prima, cioè l’utilizzo di moduli esterni con algoritmi ottimizzati (e compilati in codice macchina) per quelle applicazioni che necessitano calcoli pesanti :-)

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

    Si potrebbe provare anche PyPy: http://speed.pypy.org/ ;)

  • # 10
    Antonio Barba
     scrive: 

    Jit compiler, fico :-D

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.