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 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 rcbool is_const;
int key;
char const *value;
struct tree *left, *right;
};
Si tratta di un ABR con due campi aggiunti: un reference count3 e un flag booleano. is_const
è gestito secondo le seguenti regole:
se
is_const
è vero, il nodo è immutabile. Cambiare campi che non sianorc
è 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 impostareis_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 (veditree_put
più avanti). Inoltre, se un nodo è il figlio condiviso di più genitori, e almeno un genitore è immutabile, allora deve essere lui stesso immutabile4 (importante per l’implementazione ditree_clone
).
Ecco qualche semplice funzione per creare, aumentare il reference count, e liberare i nodi:
struct tree *
(int k, char const *v, struct tree *l, struct tree *r)
tree_new{
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
(struct tree *t)
tree_hold{
if (atomic_fetch_add(&t->rc, 1) == 0)
(1);
exit}
void
(struct tree *t)
tree_free{
if (atomic_fetch_sub(&t->rc, 1) != 1)
return;
if (t->left)
(t->left);
tree_freeif (t->right)
(t->right);
tree_free
(t);
free}
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 *
(struct tree *t, int k)
tree_get{
while (t) {
if (t->key == k)
return t->value;
= k > t->key ? t->right : t->left;
t }
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 *
(struct tree *t)
tree_clone{
struct tree *res = malloc(sizeof(*res));
if (!res) return 0;
(res, t, sizeof(*t));
memcpy->rc = 1;
res->is_const = false;
res
if (res->left) tree_hold(res->left);
if (res->right) tree_hold(res->right);
if (t->is_const) {
if (t->left)
->left->is_const = true;
tif (t->right)
->right->is_const = true;
t}
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ì:
scendi giù per l’albero, scegliendo il figlio appropriato come in un ABR qualsiasi;
se il nodo corrente
t
è immutabile, crea una copia mutabile contree_clone
e mettila al posto dit
nel suo padre (stiamo cancellando un rifrimento at
, quindi chiamiamotree_free
);se viene trovato un nodo con chiave corrispondente a quella fornita, scrivi il valore desiderato in quel nodo e termina;
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 *
(struct tree *t, int k, char const *v)
tree_put{
struct tree *root = t;
struct tree **p = &root;
while (t) {
if (t->is_const) {
= tree_clone(t);
t if (!t) return 0;
(*p);
tree_free*p = t;
}
if (t->key == k) {
->value = v;
treturn root;
}
= k > t->key ? &t->right : &t->left;
p = *p;
t }
*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
(struct tree *t)
tree_persist{
->is_const = true;
t(t);
tree_hold}
Usare l’albero
Vediamo un esempio di utilizzo del nostro ABR transiente6:
struct tree *t = tree_new(0, "root", 0, 0);
= 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"); t
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
= tree_put(t, 0, "tree");
u (t == v); assert
Possiamo prendere uno snapshot persistente:
(t);
tree_persist= tree_put(t, 6, "pluto"); u
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:
= tree_put(u, -5, "car"); u
I nodi di u
che appartengono anche a t
sono immutabili, il resto è mutabile.
Ricordiamoci di non lasciare niente indietro:
(t);
tree_free(u); tree_free
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.
Giusto per essere chiari, questo non significa che le modifiche a
t
cambianov
: come vedete è necessario assegnare il valore dit
av
dopo il ciclo.↩︎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 qualificatoreconst
può essere rimosso se questo non è un problema nel vostro caso specifico.↩︎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.↩︎
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.↩︎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.↩︎Non sto controllando che il valore restituito da
tree_new
etree_put
non sia nullo, ma dovrei.↩︎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.