Zig-ArrayList

ZIG - ArrayList e allocatori (cenni)

NB: capitolo scritto in ritardo e con estrema difficoltà perchè le cose relativamente a questo costrutto sono cambiate recentemente ... Kelley... what the heck...

In Zig un ArrayList è sostanzialmente una lista dinamica, una struttura che consiste in un array ridimensionabile automaticamente. Per trovare un parallelo potete pensare a Vec<T> del linguaggio Rust o al classico std::vector<T> del C++.
ArrayList si trova nella classica libreria standard ed è interessante perchè contiene 4 tipi di informazione:

il tipo T a cui appartengono i suoi elementi
la lunghezza corrente
la capacità allocata
un allocatore che useremo per espandere o ridimensionare la memoria

Come avrete capito gli elementi interni devono essere tutti dello stesso tipo ma è possibile aggirare questa limitazione se avete bisogno di una maggiore varietà e vedremo in questo stesso paragrafo come fare.

ALLOCATORI

Prima di analizzare questo costrutto però, dobbiamo soffermarci sull'importantissimo concetto di "allocatore". Davvero fondamentale. In questo linguaggio abbiamo detto non esistono "magie" e quindi, ad esempio una funzione che abbia bisogno di allocare qualcosa sullo heap deve in certo senso esserne autorizzato esplicitamente. Non ci possono essere allocazioni nascoste. Quindi non esiste il borrow-checker di Rust, non c'è il garbage collector di Java o C# che gestisce la soppressione di oggetti non più utilizzati, ovvero dello spazio da questi occupato. Zig getta nella mischia gli allocatori. In particolare questo pattern è chiamato Allocation Awareness (consapevolezza dell'allocazione). Il loro scopo è quello di:

allocare memoria
riallocare memoria
liberare memoria

Esiste una interfaccia base per gli allocatori:

std.mem.Allocator

in pratica una vtable che definisce come allocare, ridimensionare e liberare la memoria. Questa interfaccia presenta 4 operazioni fondamentali che vegono implementati da tutti gli allocatori disponibili:

allocator.alloc(T, n) // alloca n elementi di tipo T 

	allocator.free(slice) // libera la memoria 
allocator.create(T) // alloca 
	un singolo valore 
allocator.destroy(ptr) // libera un singolo valore

Vediamo ora quali sono gli allocatori principali disponibili ma tenete presente, come traspare anche dalle descrizioni, che la scelta dell'allocatore ideale per il vostro codice è tutto nelle vostre mani. Dovete scegliere voi.

Allocatori di uso generale
DebugAllocator (ex GeneralPurposeAllocator) — allocatore completo con rilevamento di leak, double-free e use-after-free. Ideale in sviluppo.
SmpAllocator — allocatore thread-safe ottimizzato per sistemi multicore (SMP = Symmetric MultiProcessing). È il nuovo allocatore "default" per applicazioni native.

Allocatori a scopo specifico
ArenaAllocator — alloca liberamente, ma libera tutto in un colpo solo. Perfetto per allocazioni temporanee con lifetime ben definito.
FixedBufferAllocator — alloca da un buffer statico pre-esistente, zero heap. Utile in contesti embedded o stack-only.
ThreadSafeAllocator — wrapper che aggiunge un mutex a qualsiasi allocatore non thread-safe.

Allocatori di basso livello / piattaforma
PageAllocator — alloca direttamente pagine di memoria dal SO (mmap/VirtualAlloc). Granularità grossa (tipicamente 4KB+).
SbrkAllocator — usa sbrk(), tipicamente per target WASI o sistemi molto minimali.
WasmAllocator — ottimizzato per WebAssembly, usa memory.grow.

Ce ne sono altri come ad esempio std.heap.c_allocator, std.heap.raw_c_allocator che useremo ad in concomitazitanza con l'uso di librerie scritte in C ma li vedremo all'opera ad un livello più avanzato.

Avremo varie occasioni per vedere all'opera questi allocatori e ne parleremo ancora, costituiscono la base della gestione della memoria e della sicurezza in questo linguaggio. Per ora vedetela come una panoramica generica quale in effetti è.

Gli allocatori sono parte fondamentale per capire ed usare i nostri ArrayList. In particolare nelle ultime versioni del linguaggio gli allocatori sono fuori dalla definizione e devono essere specificati, come vedremo, per ogni operazione, anche quella banale definita tramite la funzione append. In altre versioni precedenti del linguaggio se ricordo bene, gli allocatori erano integrati ma Zig vuole essere quanto più esplicito possibile.

Vediamo un esempio per partire con i nostri ArrayList:

Esempio 18.1

const std = @import("std");

pub fn main() !void {
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();
    const allocator = arena.allocator();

    var numeri: std.ArrayList(i32) = .empty;
    defer numeri.deinit(allocator);

    try numeri.append(allocator, 10);
    try numeri.append(allocator, 20);
    try numeri.append(allocator, 30);
    for (numeri.items) |n| {
        std.debug.print("{}\n", .{n});
    }
}

spieghiamolo riga per riga;

var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator); - è una istruzione molto complessa ed interessante.

var arena - è la consueta definizione di un elemento variabile
std.heap - è il namespace
ArenaAllocator - è la struct che implementa l'ArenaAllocator, ovviamente
init - è il costruttore. Non esiste la keyword new in Zig e si usa init che restituisce una istanza per valore
std.heap.page_allocator - argomento passato a init, uso una allocatore già pronto, in pratica è fornitore di memoria all'allocatore.

defer arena.deinit(); - defer esegue questa istruzione quando la funzione termina (qualunque sia il motivo). Qui distrugge l'arena e libera tutta la memoria allocata al suo interno. È il pattern idiomatico di Zig per la gestione delle risorse. Abbiamo già visto poco sopra che Arena libera tutta la memoria in un unico passaggio. Ricordiamo che defer in Zig serve a posticipare l'esecuzione di un'istruzione fino all'uscita dallo scope corrente. E' in pratica l'equivalente di drop in Rust o finally in Java e C#. Viene eseguito anche in caso di errore.

const allocator = arena.allocator(); - otteniamo in pratica l'interfaccia allocator da arena. Questa interfaccia servirà per allocare o deallocare memoria.

var numeri: std.ArrayList(i32) = .empty; - qui evidentemente nn facciamo altro che creare una lista di interi vuota

defer numeri.deinit(allocator); - quando la funzione termina, chiama deinit sulla lista passando l'allocatore, così viene liberata la memoria interna dell'array dinamico. Il defer garantisce che avvenga sempre, anche in caso di errore.

try numeri.append(allocator, 10);
try numeri.append(allocator, 20);
try numeri.append(allocator, 30);
qui popoliamo la lista con i n umeri 10, 20 e 30. Poichè append può fallire dobbiamo premettere try che in caso di errore lo riporta al chiamante (il main nel caso specifico). La cosa che è interessante notare è che l'allocatore è passato ad ogni singola istruzione, quindi non direttamente al costruttore dell'array dinamico. E' una scelta di design per avere chiara l'allocazione ad ogni singolo step.

Segue una normale istruzione di stampa.

Possiamo fare un esempio usando anche l'allocatore generico:

Esempio 18.2

const std = @import("std");

pub fn main() !void {
    var gpa = std.heap.DebugAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var numeri: std.ArrayList(i32) = .empty;
    defer numeri.deinit(allocator);

    try numeri.append(allocator, 10);
    try numeri.append(allocator, 20);
    try numeri.append(allocator, 30);

    for (numeri.items) |n| {
        std.debug.print("{}\n", .{n});
    }
}

Il risultato non cambia ma l'allocatore merita una spiegazione:

var gpa = std.heap.DebugAllocator(.{}){}; - in particolare osserviamo la parte destra. std.heap.DebugAllocator è una funzione che restituisce un tipo. E' un generatore di tipi e restiuisce una struct. in dettaglio:

DebugAllocator(.{}) → tipo

DebugAllocator(.{}){} → istanza di quel tipo

In breve, il fatto che le coppie di graffe non abbiano nulla all'interno vuol dire che il compilatore deve assegnare il default. Il discorso non è semplicissimo e sugli allocatori dovremo tornarci. Per adesso sappiamo più o meno come lavorare per studiare i nostri ArrayList.

Abbiamo visto come inizializzare un ArrayList tramite append, comodo ma un po' (tanto) laborioso. La cosa non è così banale in prima battuta. Supponiamo di avere uno slice già predefinito. Possiamo usarlo come segue nel listato 18.3:

Esempio 18.3

const std = @import("std");

pub fn main() !void {
    var gpa = std.heap.DebugAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();
    const buffer = try allocator.dupe(i32, &[_]i32{ 10, 20, 30 });
    var numeri = std.ArrayList(i32).fromOwnedSlice(buffer);
    defer numeri.deinit(allocator);
    for (numeri.items) |n| {
        std.debug.print("{}\n", .{n});
    }
}

che ci dà ovviamente:

10
20
30

Qui entra in gioco però un concetto interessante e molto importante. Nel momento in cui utilizziamo
fromOwnedSlice
trasferiamo a numeri la proprietà (ownership, come in Rust laddove però il compilatore ti protegge da queste situazioni) di quella zona di memoria prima puntata dalla slice. In questo modo buffer punta ancora a quella zona ma ogno cambiamento su di esso eventuale si rifletterebbe anche sul contenuto dell'array (e viceversa). Inoltre non potremmo più usare quello stesso buffer in particolare in caso di riallocazione dell'ArrayList, avremmo un segfault dovuto ad un use-after-free, un simpatico dangling pointer O meglio potremmo averlo. Insomma, per farla breve è ottima norma non usare più la slice dopo averne attribuito il contenuto ad un ArrayList. Qui si vede la differenza rispetto a Rust: meno controllo più responsabilità per chi programma, ma anche più libertà. Avrete notato l'istruzione

allocator.dupe

la quale alloca nuova memoria e ci copia dentro il contenuto di uno slice esistente — è sostanzialmente un clone di uno slice. Dal momento che alloca memoria può fallire da qui il consueto try. Equivale a fare manualmente

const copia = try allocator.alloc(i32, originale.len); @memcpy(copia, originale);

Vediamo adesso un secondo metodo

Esempio 18.4

const std = @import("std");

pub fn main() !void {
    var gpa = std.heap.DebugAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();
    var numeri: std.ArrayList(i32) = .empty;
    defer numeri.deinit(allocator);
    try numeri.appendSlice(allocator, &[_]i32{ 10, 20, 30 });
    for (numeri.items) |n| {
        std.debug.print("{}\n", .{n});
    }
}

Questo esempio funziona in modo opposto rispetto al precedente. La infatti l'ArrayList si "impadroniva" di una zona di memoria già allocata (con relativi rischi) qui invece effettua una copia di una slice. Questo sistema è più sicuro perchè non può condurre a dangling pointer, cioè al problema visto nell'esempio 18.3

E se ad esempio volessimo una lista che contenga 100 volte un certo numero? Il metodo più tranquillo è forse il seguente:

Esempio 18.5

const std = @import("std");

pub fn main() !void {
    var gpa = std.heap.DebugAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();
    var numeri: std.ArrayList(i32) = .empty;
    defer numeri.deinit(allocator);
    try numeri.appendNTimes(allocator, 3, 100);
    for (numeri.items) |n| {
        std.debug.print("{}\n", .{n});
    }
}

Questo fa uso di appendNTimes (molto intuitiva come funzione) che aggiunge elementi finchè necessario e in particolare inserisce gli elementi che indichiamo, in questo caso il numero 3.
Un altro sistema prevede un resize e il successivo riempimento della memoria tramite una funzione builtin:

Esempio 18.6

const std = @import("std");

pub fn main() !void {
    var gpa = std.heap.DebugAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();
    var numeri: std.ArrayList(i32) = .empty;
    defer numeri.deinit(allocator);
    try numeri.resize(allocator, 100);
    @memset(numeri.items, 7);
    for (numeri.items) |n| {
        std.debug.print("{}\n", .{n});
    }
}

In questo esempio resize predispone un spazio non inizializzato, @memset è una builtin function di Zig (ricordiamo che le builtin iniziano tutte con @) che riempie uno slice con un valore uniforme, in questo caso il numero 7. Se non usaste @memset, potete provare, otterrete con ogni porobabilità un valore da cui potrete capire che abbiamo una memoria non inizializzata.

Vediamo adesso, come di consueto, alcune operazioni utili per lavorare con i nostri ArrayList, potete riprendere il codice degli esempi precedenti ad aggiungere quegli spezzoni che vediamo di seguito:

conteggiare gli elementi
const len = numeri.items.len; std.debug.print("elementi: {}\n", .{len});

modificare un elemento
numeri.items[2] = 999;
si usa insomma il classico operatore items[indice]

cancellare un elemento - dipende anche da dove lo si vuole cancellare:

// In coda — O(1)
_ = numeri.pop();

// In testa — O(n), shifta 
	tutto
numeri.orderedRemove(0);

// In mezzo — O(n), mantiene 
	l'ordine
numeri.orderedRemove(3);

// In mezzo — O(1), NON mantiene 
	l'ordine (sostituisce con l'ultimo elemento)
numeri.swapRemove(3);

avrete notato che abbiamo indicato anche la complessità computazionale.
Qui ci vuole un esempio:

Esempio 18.7

const std = @import("std");

pub fn main() !void {
    var gpa = std.heap.DebugAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();
    var numeri: std.ArrayList(i32) = .empty;
    defer numeri.deinit(allocator);
    try numeri.appendSlice(allocator, &[_]i32{ 1, 2, 3, 4, 5, 6, 7, 8, 9 });
    _ = numeri.pop();
    for (numeri.items) |n| {
        std.debug.print("{}\n", .{n});
    }
    std.debug.print("\n", .{});
    _ = numeri.orderedRemove(0);
    for (numeri.items) |n| {
        std.debug.print("{}\n", .{n});
    }
    std.debug.print("\n", .{});
    _ = numeri.orderedRemove(3);
    for (numeri.items) |n| {
        std.debug.print("{}\n", .{n});
    }
    std.debug.print("\n", .{});
    _ = numeri.swapRemove(3);
    for (numeri.items) |n| {
        std.debug.print("{}\n", .{n});
    }
}

Aggiungere un elemento è abbastanza semplice, potete modificare facilmente l'esempio precedente:
// In coda — O(1) try numeri.append(allocator, 42); // In testa — O(n), shifta tutto try numeri.insert(allocator, 0, 42); // In mezzo — O(n) try numeri.insert(allocator, 3, 42);

Trovare un elemento
Qui non esiste un metodo diciamo canonico e si ricorre a std.mem. Possiamo seguire due strade, valide per i tipi scalari (quindi non se gli elementi all'interno dell'ArrayList sono delle stringhe:
indexOf (che cerca una sottosequenza)
indexOfScalar (che cerca il singolo elemento)
vediamo un esempio che contiene esntrambe queste funzioni:

Esempio 18.8

const std = @import("std");

pub fn main() !void {
    var gpa = std.heap.DebugAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();
    var numeri: std.ArrayList(i32) = .empty;
    defer numeri.deinit(allocator);
    try numeri.appendSlice(allocator, &[_]i32{ 1, 2, 3, 4 });
    const idx = std.mem.indexOfScalar(i32, numeri.items, 42);
    if (idx) |i| {
        std.debug.print("trovato all'indice {}\n", .{i});
    } else {
        std.debug.print("non trovato\n", .{});
    }
    const idx2 = std.mem.indexOfScalar(i32, numeri.items, 2);
    if (idx2) |i| {
        std.debug.print("trovato all'indice {}\n", .{i});
    } else {
        std.debug.print("non trovato\n", .{});
    }
}

Nel caso di stringhe è necessario procedere con un confronto manuale scrivendo una funzione ad hoc. La vedremo nella sezione esempi

Copiare un ArrayList
Anche in questo caso dobbiamo stare attenti al contenuto dell'ArrayList che dobbiamo copiare. Il caso più semplice si ha quando abbiamo dei dati che appartengono a tipi primitivi, interi, bool, ecc... in questo caso attaverso clone() possiamo fare una deep copy dell'ArrayList. Rifacendoci agli esempi precedenti:

const copia = try numeri.clone(allocator); defer copia.deinit(allocator);

allochiamo nuova memoria e copiamo tutti i valori. Per i tipi primitivi è perfetto perché i valori sono autocontenuti. Come al solito le complicazioni nasconto con i tipi più strutturati come le nostre beneamate stringhe. Se ad esempio quindi abbiamo un ArrayList([]const u8) (lista di stringhe), clone copia i puntatori ma non le stringhe a cui puntano. Questo significa che avremo una shallow copy, per cui ogni variazione effettuata sull'ArrayList originale avrà effetto anche sulla copia e viceversa. In questo caso per avere una deep copy è necessario procedere manualmente con codice tipo:

var copia = std.ArrayList([]const u8).init(allocator); for (nomi.items) |s| { try copia.append(allocator, try allocator.dupe(u8, s)); }

In pratica, non ci sono automatismi ma è il programmatore che deve sapere su cosa sta operando.

Altre funzioni utili che vanno conosciute:

initCapacity - Crea un ArrayList preallocando subito una certa capacità e quindi ci evita inutili e dispendiose riallocazioni se sappiamo in anticipo quanti elementi avremo:

var numeri = try std.ArrayList(i32).initCapacity(allocator, 10); defer numeri.deinit(allocator); // len = 0, capacity = 10 — pronto per append senza riallocare try numeri.append(allocator, 42);

initBuf - Crea un ArrayList che usa un buffer già esistente sullo stack — zero allocazioni heap: e pertanto risulta molto utile quando sappiamo che la lista sarà piccola e vogliamo evitare l'heap del tutto, lo stack è sempre la scelta più efficiente.

var buf: [10]i32 = undefined; var numeri = std.ArrayList(i32).initBuf(&buf); // nessun allocatore necessario try numeri.append(allocator, 42); // se supera 10 elementi però rialloca sullo heap

toOwnedSlice - come si può intuire fa l'opposto di fromOwnedSlice, ovvero trasferisce il contenuto di un ArrayList ad una slice.

var numeri = std.ArrayList(i32).init(allocator); try numeri.append(allocator, 10); try numeri.append(allocator, 20); const slice = try numeri.toOwnedSlice(allocator); defer allocator.free(slice); // numeri è ora vuoto, slice contiene { 10, 20 }

questo codice è interessante in quanto ribadisce una volta di più la necessità di deallocare esplicitamente la memoria che viene allocata dinamicamente. Sulla gestione della memoria torneremo ma tenete presente questo concetto. Usando la funzione toOwnedSlice in pratica abbiamo questa sequenza di azioni:

toOwnedSlice alloca nuova memoria
copia gli elementi dell’ArrayList
svuota l’ArrayList
ti restituisce la slice
trasferisce la proprietà al programmatore

ensureTotalCapacity - Garantisce che la capacità sia almeno N — alloca se necessario, non fa nulla se la capacità è già sufficiente:

var numeri = std.ArrayList(i32).init(allocator); defer numeri.deinit(allocator); try numeri.ensureTotalCapacity(allocator, 100); // len = 0, capacity >= 100 // ora usiamo appendAssumeCapacity senza rischio di riallocazione numeri.appendAssumeCapacity(42);

Dopo aver usato ensureTotalCapacity siamo certi che la capacità non sarà essere < 100. Questo nell'ottica di ridurre al massimo le costose, in termini di risorse, riallocazioni.

Come avrete capito manca la parte di collaborazione, chiamiamola così, tra ArrayList e funzioni. Quando affronteremo il corposo capitolo dedicato a queste ultime avremo modo di colmare questa lacuna.