il blog di dalz

chi sonogeminienglishicona di feed RSS

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:

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 direttamente1. 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;
};

2

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

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);
}

5

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:

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 transiente6:

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:

Albero iniziale

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:

t u

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

Condivisione strutturale dopo una modifica

Se continiuamo a modificare u, i due divergereanno gradualmente:

u = tree_put(u, -5, "car");
Condivisione strutturale dopo un’altra modifica

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 statici7, ma questo è C: la soluzione è pensare di più, ed avere tanta pazienza.


  1. Giusto per essere chiari, questo non significa che le modifiche a t cambiano v: come vedete è necessario assegnare il valore di t a v dopo il ciclo.↩︎

  2. Dal momento che il campo value è un puntatore, altre parti del codice potrebbero modificare il valore a cui punta senza chiamare le nostre procedure. Questo significa che i cambiamenti del valore non rispetterebbero la persistenza dell’albero. Il qualificatore const può essere rimosso se questo non è un problema nel vostro caso specifico.↩︎

  3. Non strettamente necessario; si può rimpiazzare con un garbage collector, o semplicemente ignorando la gestione della memoria se l’intenzione è di tenere in memoria tutti gli snapshot per l’intera esecuzione del programma.↩︎

  4. Se non è chiaro il perché, prendete questo esempio: C è figlio del nodo mutabile A e di quello immutabile B. Se modifichiamo C proveniendo da B lo vedremo come immutabile (dal momento che dovremo propagare is_const), ma se facessimo lo stesso venendo da A lo tratteremmo come mutabile. Ovviamente C non può essere contemporaneamente mutabile e immutabile.↩︎

  5. Se quando tree_hold viene chiamato il reference count è 0, l’albero sta venendo liberato e mantenerlo in memoria non è possibile. Un programma serio potrebbe provare a gestire questa situazione, ma qui mi limiterò a terminare l’esecuzione.↩︎

  6. Non sto controllando che il valore restituito da tree_new e tree_put non sia nullo, ma dovrei.↩︎

  7. Che permetterebbe ad esempio di avere tipi diversi per i nodi mutabili e non.↩︎



Domande, dubbi, incertezze, carenze affettive? Manda tutto a blog@alsd.eu!
Torna alla lista degli articoli.