Alberi transienti in C
2021-09-03

Forse avrete già sentito parlare di strutture dati persistenti, ovvero strutture immutabili in cui ciascun cambiamento genera una nuova versione della struttura invece di modificarla direttamente.

Ultimamente ho iniziato a scrivere le basi di un editor di testo (che naturalmente non porterò mai a termine), e mi sono interessato alle strutture persistenti perché hanno un paio di proprietà utili in questo contesto:

• implementare l’undo è banale, basta conservare una lista di tutte le versioni della struttura usata per rappresentare il testo;

• sono accessibili in sicurezza da più thread, quindi su grandi file è possibile mantere il syntax highlighting senza bloccare la modifica del buffer semplicemente eseguendo la colorazione su un thread separato.

Lo svantaggio è che le operazioni persistenti richiedono allocazioni e copiature. Un’implementazione intelligente può ridurre l’impatto sulla performance condividendo parti della struttura tra le diverse versioni, ma si paga necessariamente un certo costo aggiuntivo rispetto alla modifica diretta. Per questo motivo è utile potersi liberare dal vincolo di immutabilità in determinate circostanze; in Clojure, questo è possibile tramite i transient.

In pseudocodice, l’utilizzo è il seguente:

let n = 1000000
let v = new persistent vector


// persisent

for i from 0 to n
    v = v.push(i)


// transient

t = v.transient()
for i from 0 to n
    t.push(i)
v = t.persistent()

ad ogni iterazione del primo ciclo viene creata una copia (leggera) di v, mentre nel secondo si modifica il vettore direttamente¹. Se l’operazione viene eseguita frequentemente la differenza nel tempo di esecuzione può diventare notevole. Naturalmente i transient non hanno le proprietà che ho menzionato prima (in particolare non sono thread-safe), quindi solitamente è desiderabile tornare alla versione persistente appena possibile.

Transienti come stato di default

L’approccio di Clojure è pensato per un contesto funzionale, ma ho pensato che “ribaltarlo” potrebbe renderlo più adatto ad un linguaggio imperativo.

L’idea è questa: trattiamo la struttura come mutabile, ma con la possibilità di ottenere degli snapshot persistenti, su cui le operazioni sono copy-on-write. Una struttura mutabile potrebbe avere sottoparti immutabili, ma questo viene gestito in modo trasparente dalle procedure di modifica.

Vediamo un esempio di implementazione pratica in C.

Un albero binario di ricerca (ABR) transiente

Questa è la definizione del nostro albero:

struct tree {
    atomic_int rc;
    bool is_const;

    int key;
    char const *value;

    struct tree *left, *right;
};

²

Si tratta di un ABR con due campi aggiunti: un reference count³ e un flag booleano. is_const è gestito secondo le seguenti regole:

• se is_const è vero, il nodo è immutabile. Cambiare campi che non siano rc è proibito, quindi per farlo è necessario creare una copia mutabile del nodo;

• is_const è propagato in maniera lazy, in modo che per rendere persistente un albero sia sufficiente impostare is_const sulla radice. Quando attraversiamo l’albero per aggiungere una foglia o modificare un valore, ogni volta che incontriamo un nodo il cui padre è immutabile dovremo assicurarci che quel nodo sia anch’esso immutabile (vedi tree_put più avanti). Inoltre, se un nodo è il figlio condiviso di più genitori, e almeno un genitore è immutabile, allora deve essere lui stesso immutabile⁴ (importante per l’implementazione di tree_clone).

Ecco qualche semplice funzione per creare, aumentare il reference count, e liberare i nodi:

struct tree *
tree_new(int k, char const *v, struct tree *l, struct tree *r)
{
    struct tree *t = malloc(sizeof(*t));
    if (!t) return 0;

    *t = (struct tree){
        .rc = 1,
        .key = k,
        .value = v,
        .left = l,
        .right = r
    };

    return t;
}

void
tree_hold(struct tree *t)
{
    if (atomic_fetch_add(&t->rc, 1) == 0)
        exit(1);
}

⁵

void
tree_free(struct tree *t)
{
    if (atomic_fetch_sub(&t->rc, 1) != 1)
        return;

    if (t->left)
        tree_free(t->left);
    if (t->right)
        tree_free(t->right);

    free(t);
}

Niente di interessante qui. I nodi vengono creati con is_const impostato a falso e rc a 1.

Per ottenere un valore conservato nell’albero si segue lo stesso procedimento di un normale ABR:

char const *
tree_get(struct tree *t, int k)
{
    while (t) {
        if (t->key == k)
            return t->value;

        t = k > t->key ? t->right : t->left;
    }

    return 0;
}

La parte problematica è, ovviamente, l’inserimento. Avremo bisogno di una funzione di appoggio che crea una copia superficiale mutabile di un nodo:

struct tree *
tree_clone(struct tree *t)
{
    struct tree *res = malloc(sizeof(*res));
    if (!res) return 0;

    memcpy(res, t, sizeof(*t));
    res->rc = 1;
    res->is_const = false;

    if (res->left) tree_hold(res->left);
    if (res->right) tree_hold(res->right);

    if (t->is_const) {
        if (t->left)
            t->left->is_const = true;
        if (t->right)
            t->right->is_const = true;
    }

    return res;
}

Un paio di dettagli degni di nota:

• copiando t creaimo nuovi riferimenti ai suoi figli, per cui è necessario incrementare i loro reference count;

• come già detto, se il nodo originale era immutabile allora is_const deve essere propagato ai figli (vedi ancora ⁴).

Ora siamo pronti per definire tree_put. Funziona così:

1. scendi giù per l’albero, scegliendo il figlio appropriato come in un ABR qualsiasi;

2. se il nodo corrente t è immutabile, crea una copia mutabile con tree_clone e mettila al posto di t nel suo padre (stiamo cancellando un rifrimento a t, quindi chiamiamo tree_free);

3. se viene trovato un nodo con chiave corrispondente a quella fornita, scrivi il valore desiderato in quel nodo e termina;

4. altrimenti, quando viene raggiunta una foglia aggiungi un nuovo nodo come suo figlio con la coppia chiave-valore fornita.

Qualcuno avrà notato che questi passi richiedono la modifica dei nodi. Tuttavia, il secondo punto stabilisce la seguente invariante:

All’inizio di ogni iterazione, il padre di t è mutabile.

Questo garantisce che il secondo e quarto passo sono validi. Inoltre, il terzo è eseguito dopo il secondo, quindi in quel momento anche t è mutabile e cambiare il suo campo value è consentito.

Il valore restituito da tree_put è l’albero in input se è mutabile, una sua copia mutabile se non lo è.

Segue il codice:

struct tree *
tree_put(struct tree *t, int k, char const *v)
{
    struct tree *root = t;
    struct tree **p = &root;

    while (t) {
        if (t->is_const) {
            t = tree_clone(t);
            if (!t) return 0;

            tree_free(*p);
            *p = t;
        }

        if (t->key == k) {
            t->value = v;
            return root;
        }

        p = k > t->key ? &t->right : &t->left;
        t = *p;
    }

    *p = tree_new(k, v, 0, 0);
    if (!*p) return 0;

    return root;
}

Manca un ultimo componente: abbiamo bisogno di un modo per rendere l’albero persistente. Questo è molto facile grazie alla propagazione lazy di is_const:

void
tree_persist(struct tree *t)
{
    t->is_const = true;
    tree_hold(t);
}

Usare l’albero

Vediamo un esempio di utilizzo del nostro ABR transiente⁶:

struct tree *t = tree_new(0, "root", 0, 0);

t = tree_put(t, -10, "foo");
t = tree_put(t, -5, "bar");
t = tree_put(t, 10, "baz");
t = tree_put(t, 5, "fizz");
t = tree_put(t, 15, "buzz");
t = tree_put(t, 7, "pippo");

Questo crea l’albero seguente:

Al momento l’albero è ancora interamente mutabile, quindi il valore restituito da tree_put è il t passato in input:

struct tree *u

u = tree_put(t, 0, "tree");
assert(t == v);

Possiamo prendere uno snapshot persistente:

tree_persist(t);
u = tree_put(t, 6, "pluto");

Ora abbiamo questo:

Ma la parte interessante è che t e u condividono parte della loro struttura (t a sinistra, u a destra):

Se continiuamo a modificare u, i due divergereanno gradualmente:

u = tree_put(u, -5, "car");

I nodi di u che appartengono anche a t sono immutabili, il resto è mutabile.

Ricordiamoci di non lasciare niente indietro:

tree_free(t);
tree_free(u);

Conclusioni

Prima di tutto, il codice è disponibile per intero su Codeberg: dalz/transient-tree.

Non l’ho mostrato, ma dopo aver chiamato tree_persist su un albero, si può passare quell’albero tra thread senza problemi.

Rendere transiente un ABR è piuttosto semplice, ma lo stesso non si può dire per strutture più elaborate che hanno molteplici procedure di aggiornamento complesse (invece di un singolo tree_put). In tal caso tenere traccia di immutabilità e riferimenti a mente comincia ad essere una faticaccia. Si potrebbe risolvere con un sistema dei tipi robusto con più controlli statici⁷, ma questo è C: la soluzione è pensare di più, ed avere tanta pazienza.