di  -  mercoledì 16 novembre 2011

Visto che l’appetito vien mangiando, esaminiamo ora le azioni che sono necessarie in CPython (che ricordo essere la macchina virtuale “ufficiale” / “mainstream” di Python) per portare a compimento un’altra operazione molto comune, la concatenazione di due stringhe, che risulta “mappata” anch’essa sull’operatore di addizione/somma (il classico simbolo “+“).

Se Python s’è diffuso molto, infatti, è anche merito della semplicità di manipolazione delle stringhe che l’ha caratterizzato fin dall’inizio, e fra queste operazioni la più diffusa rimane quella oggetto di quest’articolo.

Riprendendo parte del codice del bytecode BINARY_ADD di cui abbiamo parlato in uno dei precedenti articoli di questa serie

else if (PyString_CheckExact(v) && PyString_CheckExact(w)) {
  x = string_concatenate(v, w, f, next_instr);
  /* string_concatenate consumed the ref to v */
  goto skip_decref_vx;
}

notiamo che sono poche le azioni eseguite. Intanto il doveroso controllo che il tipo dei due operandi sia quello che ci si aspetta (entrambe istanze della “classe” / struttura PyString), affidato alla solita macro:

#define PyString_CheckExact(op)  (Py_TYPE(op) == &PyString_Type)

dove PyString_Type è la struttura che definisce il tipo/classe di questi oggetti. Si tratta di un pattern molto comune, che s’incontra spesso fra le righe del codice della VM di cui stiamo parlando.

Poiché nel corpo dell’if è presente soltanto una chiamata a funzione, e un successivo goto che si occupa della “finalizzazione” del codice di BINARY_ADD, è ovvio che il lavoro vero e proprio venga svolto all’interno di string_concatenate, che si presenta così:

static PyObject *
string_concatenate(PyObject *v, PyObject *w,
  PyFrameObject *f, unsigned char *next_instr)
{
  /* This function implements 'variable += expr' when both arguments
      are strings. */
  Py_ssize_t v_len = PyString_GET_SIZE(v);
  Py_ssize_t w_len = PyString_GET_SIZE(w);
  Py_ssize_t new_len = v_len + w_len;
  if (new_len < 0) {
    PyErr_SetString(PyExc_OverflowError,
      "strings are too large to concat");
    return NULL;
  }

  if (v->ob_refcnt == 2) {
    /* In the common case, there are 2 references to the value
     * stored in 'variable' when the += is performed: one on the
     * value stack (in 'v') and one still stored in the
     * 'variable'.  We try to delete the variable now to reduce
     * the refcnt to 1.
     */

    switch (*next_instr) {
    case STORE_FAST:
    {
      int oparg = PEEKARG();
      PyObject **fastlocals = f->f_localsplus;
      if (GETLOCAL(oparg) == v)
        SETLOCAL(oparg, NULL);
      break;
    }
    case STORE_DEREF:
    {
      PyObject **freevars = (f->f_localsplus +
                 f->f_code->co_nlocals);
      PyObject *c = freevars[PEEKARG()];
      if (PyCell_GET(c) == v)
        PyCell_Set(c, NULL);
      break;
    }
    case STORE_NAME:
    {
      PyObject *names = f->f_code->co_names;
      PyObject *name = GETITEM(names, PEEKARG());
      PyObject *locals = f->f_locals;
      if (PyDict_CheckExact(locals) &&
        PyDict_GetItem(locals, name) == v) {
        if (PyDict_DelItem(locals, name) != 0) {
          PyErr_Clear();
        }
      }
      break;
    }
    }
  }

  if (v->ob_refcnt == 1 && !PyString_CHECK_INTERNED(v)) {
    /* Now we own the last reference to 'v', so we can resize it
     * in-place.
     */
    if (_PyString_Resize(&v, new_len) != 0) {
      /* XXX if _PyString_Resize() fails, 'v' has been
       * deallocated so it cannot be put back into
       * 'variable'.  The MemoryError is raised when there
       * is no value in 'variable', which might (very
       * remotely) be a cause of incompatibilities.
       */
      return NULL;
    }

    /* copy 'w' into the newly allocated area of 'v' */
    memcpy(PyString_AS_STRING(v) + v_len,
           PyString_AS_STRING(w), w_len);
    return v;
  }

  else {
    /* When in-place resizing is not an option. */
    PyString_Concat(&v, w);
    return v;
  }
}

Al solito, la lunghezza del codice può impressionare a prima vista, ma in realtà i casi da gestire sono pochi e di semplice comprensione. Ho aggiunto delle righe appositamente per separarli e trattarli singolarmente (senza la spiegazione di ogni riga di codice).

Intanto è importante comprendere il significato dei parametri passati a questa funzione, che non sono soltanto le due istanze da concatenare, come si ci poteva aspettare, ma ne vengono passati altri due.

Il terzo, f, punta al cosiddetto “frame“, che rappresenta il corrente “ambiente di esecuzione”. Con ciò s’intende l’insieme di tutte le informazioni necessarie alla corretta esecuzione dei bytecode: frame precedente (se esiste; usato nel caso di più chiamate a funzioni / oggetti “eseguibili”), elenco dei bytecode da eseguire, elenco delle variabili globali / built-in / “generali”, ecc.

Il quarto, next_instr, rappresenta semplicemente il puntatore alla prossima istruzione / bytecode da eseguire.

Vedremo meglio dopo perché sono indispensabili e quali informazioni sono importanti per completare l’operazione.

Il primo controllo da effettuare riguarda la dimensione della stringa finale, e lo si fa molto facilmente prelevando la dimensione delle due stringhe, anche qui facendo ricorso a delle macro:

#define PyString_GET_SIZE(op)  Py_SIZE(op)
#define Py_SIZE(ob)  (((PyVarObject*)(ob))->ob_size)

Servono due macro perché la prima è dedicata esclusivamente alle stringhe, mentre la seconda è quella che si occupa di recuperare effettivamente la lunghezza prelevandola dal campo ob_size.

Questo perché al momento le stringhe sono derivate dalla struttura PyVarObject  che Python utilizza per rappresentare gli oggetti “sequenza”, cioè che rappresentano un array di informazioni (il cui tipo al momento non c’interessa):

typedef struct {
  Py_ssize_t ob_refcnt;
  struct _typeobject *ob_type;
  Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;

che ho espanso qui per comodità.

I primi due campi, ob_refcnt e ob_type, li conosciamo già, mentre il terzo, ob_size, conserva, appunto, la lunghezza della sequenza.

Py_SIZE si occupa di prelevare questo campo, e PyString_GET_SIZE fa uso di questa macro allo scopo, ma è bene utilizzare sempre PyString_GET_SIZE, perché in futuro la rappresentazione delle stringhe potrebbe cambiare, per cui usando Py_SIZE ci sarebbero non poche difficoltà a cambiare poi tutte le parti del codice che hanno bisogno di recuperare la lunghezza della stringa.

Recuperate le due lunghezze le si somma e si controlla se è stato superato il massimo intero positivo rappresentabile col tipo Py_ssize_t (già visto per ob_refcnt, che è sostanzialmente un intero con segno), col solito trucchetto già visto nel codice relativo alla somma dei due interi, cioè controllando che il segno del risultato sia cambiato (diventato negativo, nel nostro caso).

Se siamo andati oltre la quantità massima rappresentabile, si solleva un’opportuna eccezione e si esce, altrimenti si prosegue effettuando alcuni controlli per vedere se ci troviamo in uno dei casi frequenti che meritano di essere velocizzati.

Nello specifico, il caso è uno soltanto, e riguarda la seguente possibilità: la prima stringa della concatenazione ha soltanto 2 riferimenti, e il successivo bytecode si occupa soltanto di memorizzare il risultato della suddetta concatenazione.

Il perché di questo caso particolare è presto detto, e un semplice esempio di poche righe lo spiegherà meglio di mille parole:

s = ''
for i in range(10):
  s = s + str(i)

Si tratta di un pattern molto ricorrente in Python (ma anche in altri linguaggi), in cui si costruisce una stringa appendendogli man mano altre stringhe.

Il primo controllo è fondamentale per capire se rientriamo in questo caso (ed è ben spiegato nel commento, peraltro): se la prima stringa ha 2 riferimenti, vuol dire che uno dei due si trova nello stack (ci stiamo proprio lavorando in questo momento!) e l’altro si trova memorizzato nella variabile.

A questo punto se la successiva istruzione da eseguire riguarda la memorizzazione (STORE) della concatenazione in una variabile, e precisamente in quella variabile che contiene il riferimento in questione, ci troviamo esattamente nel caso di cui stiamo parlando.

Una piccola spiegazione è necessaria per lo switch e quei 3 bytecode STORE. Sono 3 perché una variabile può essere:

  • locale (FAST)
  • “cella” (CELL; sono tali le variabili di una funzione che vengono referenziate in una funzione annidata)
  • “generale” (NAME; è una qualunque variabile che non rientra nei due casi precedenti, quindi una variabile globale del modulo corrente oppure appartenente allo spazio dei built-in, cioè visibile in tutta l’applicazione)

Senza dilungarci troppo, come si può vedere dal codice il parametro f serve proprio per controllare se effettivamente la variabile che riceverà il valore della concatenazione contiene il riferimento al nostro primo operando v. Se la condizione è soddisfatta, si provvede a eliminare questo riferimento, in modo da ridurre il numero totale dei riferimenti a uno (soltanto quello presente nello stack).

Quest’operazione potrebbe sembrare non lecita, perché la concatenazione non è stata ancora effettuata, e stiamo lavorando sui dati della successiva istruzione che, però, non è stata ancora eseguita. In realtà tutte le operazioni di STORE “scartano” (dereferenziano) il vecchio valore prima di memorizzare il nuovo, per cui diciamo che in questa parte di codice ci siamo presi una libertà che ci possiamo permettere, perché in ogni caso dopo la concatenazione quel valore farebbe esattamente la stessa fine (buttato via).

Finiti questi “giochi di prestigio”, è necessario un ulteriore controllo per verificare se siamo finalmente in possesso dell’unico riferimento alla variabile v. Questo, però, non è sufficiente, perché bisogna stare attenti anche al fatto che questa stringa non sia “interned“, non appartenga cioè a quelle stringhe che per qualche motivo Python ha reso “interne” e che, quindi, non si devono toccare in alcun modo.

Questo lo si capisce subito guardando il successivo blocco di codice. Se, infatti, tutte le condizioni sono soddisfatte, lo spazio occupato dalla stringa presente nella variabile v viene aumentato fino a poter contenere un numero di caratteri pari alla dimensione della stringa concatenata.

Se l’operazione di ridimensionamento riesce, si procede banalmente a ricopiare tutti i caratteri della seconda stringa (w) alla fine della prima, tramite la classica funzione memcpy presente nella libreria standard del C.

La macro PyString_AS_STRING, come si può intuire dall’uso che se ne fa, serve a recuperare il puntatore al primo carattere della stringa:

#define PyString_AS_STRING(op) (((PyStringObject *)(op))->ob_sval)

Dove ob_sval rappresenta il vettore che conserva tutti i caratteri, come si può notare dalla definizione della struttura PyStringObject:

typedef struct {
  Py_ssize_t ob_refcnt;
  struct _typeobject *ob_type;
  Py_ssize_t ob_size; /* Number of items in variable part */
  long ob_shash;
  int ob_sstate;
  char ob_sval[1];
} PyStringObject;

Da notare che ob_sval viene definito come vettore di un solo carattere, ma in realtà, quando si alloca spazio per PyStringObject, alla dimensione della struttura qui definita viene aggiunto anche lo spazio per il numero di caratteri che la stringa dovrà contenere, in modo da “espandere” artificiosamente il vettore (un’operazione che si trova facilmente nel codice C di tanti altri progetti).

A questo punto l’operazione di concatenazione è completa per questo caso particolare, e abbiamo imparato anche un’altra cosa importante: sì, le stringhe sono oggetti immutabili in Python, ma soltanto sulla carta. La VM, in particolari condizioni, può tranquillamente alternarne il contenuto, se serve.

In questo caso serve sicuramente, perché senza il particolare codice per gestire questo pattern comune, le prestazioni ne risentirebbero parecchio, poiché le operazioni di concatenazione non avrebbero più un tempo lineare (relativamente alla lunghezza delle singole stringhe concatenate), ma quadratico, in quanto il processore spenderebbe parecchio tempo a ricopiare, per ogni concatenazione, tutti i caratteri del primo operando (mentre con l’ottimizzazione di cui sopra vengono copiati ogni volta soltanto quelli del secondo operando).

Senza contare, poi, lo spreco di risorse dovuto alla continua allocazione e deallocazione degli oggetti stringa, che comporta inoltre la frammentazione della memoria del processo (per cui è facile trovarsi con un processo che abbia una quantità spropositata di memoria virtuale, quando lo spazio realmente occupato è poco).

Infine, se non rientriamo in questo caso la concatenazione viene eseguita dalla funzione PyString_Concat, che si occupa di gestire, oltre al caso generale, anche le operazioni di concatenazione fra stringhe normali ed eventuali stringhe unicode (in Python esistono due tipi di stringhe, infatti: quelle “grezze” / byte-oriented, e quelle unicode).

Rimane la parte finale del bytecode BINARY_ADD:

Py_DECREF(v);
skip_decref_vx:
Py_DECREF(w);
SET_TOP(x);
if (x != NULL) continue;
break;

che si occupa di eliminare il riferimento agli oggetti utilizzati. Ricordo che l’istruzione LOAD_FAST, esaminata in precedenza, aggiunge un riferimento all’oggetto nel momento in cui preleva un’istanza e la deposita nello stack. Riferimento che va, appunto, eliminato dopo che l’oggetto è stato utilizzato e rimosso dallo stack.

Da notare che per le stringhe il goto porta all’etichetta skip_decref_vx, in quanto il riferimento alla variabile v viene rimosso dal codice presente all’interno della funzione string_concatenate (come in parte abbiamo visto), e quindi non si deve assolutamente dereferenziare nuovamente (pena prevedibili problemi da doppia deallocazione, che attanagliano i programmatori C/C++).

A questo punto il risultato dell’operazione (somma per gli interi, concatenazione per le stringhe, oppure altro nel caso in cui ci siano tipi diversi che supportano quest’operatore) viene piazzato in cima allo stack (in modo da essere disponibile per le successive istruzioni), e se non si è verificato alcun errore il controllo ritorna al ciclo principale della VM per eseguire la successiva istruzione…

4 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
    Pluto
     scrive: 

    Questo articolo l’ho capito solo in parte, perché ci sono troppi riferimenti a cose che non conosco. Bisognerebbe che avessi un background più preciso su come è implementata la VM.

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

    Se fai un elenco dei dubbi vedo se posso risponderti qui, oppure preparare un apposito articolo (se ci fosse troppa roba di cui discutere).

  • # 3
    homero
     scrive: 

    devo dire che analizzare una virtual machine come quella di python è realmente interessante, sopratutto per comprendere a fondo il linguaggio.
    mi farebbe piacere che si parlasse in uno dei prossimi articoli di come si sincronizzano i timing tra l’hosts e il guest, in modo che il codice python giri piu’ o meno allo stesso modo su sistemi diversi.

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

    Gli spunti sono sempre interessanti, e se rientra nelle mie conoscenze cercherò di accontentarti (anche perché adoro parlare della VM di Python), ma non mi è chiaro quello che chiedi. Potresti fare magari un esempio? Grazie.

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.