Località dei dati: perché std::vector è spesso più veloce

1. Perché “stessa O” non significa “stessa velocità”

Quando sentite parlare per la prima volta di Big‑O, può sembrare di avere un trucco per la realtà: “Se entrambe le operazioni sono O(N), allora sono ugualmente veloci”. Purtroppo è come dire: “Due persone camminano a piedi, quindi arriveranno insieme”, senza specificare che una cammina su strada piana e l’altra su una palude piena di buche e zanzare. Big‑O parla della crescita al variare di N, ma dice poco su quanta “micro‑sofferenza” sia nascosta in ogni passo.

In C++ i contenitori spesso danno la stessa Big‑O per la stessa operazione. Per esempio, un attraversamento lineare di vector, deque e list è ovunque O(N). Ma nella pratica vector spesso vince come se fosse “imbroglione”. La ragione non è magica né che std::list sia “cattivo”. La ragione è il modo in cui i dati sono disposti in memoria e il modo in cui la CPU li “consuma”.

Località dei dati: definizione senza pedanterie

La parola “località” suona come se stessimo per fare una lezione di geografia, ma no: parliamo di memoria. Per località dei dati si intende in genere l’idea semplice: se ora avete acceduto a un pezzo di memoria, con alta probabilità vi serviranno presto o i byte adiacenti (località spaziale), o gli stessi byte di nuovo (località temporale). Le CPU “sanno” questo e cercano di indovinare le vostre esigenze future più in fretta di quanto riusciate a dire: “non conserverò un puntatore grezzo a un elemento di vector”.

Perché questa previsione funzioni, i dati devono essere “comodi”. Ed è qui che vector spesso primeggia, perché memorizza gli elementi contigui e si adatta bene alla struttura delle cache CPU. Nello standard C++ esiste persino la categoria separata di contiguous iterators per contenitori come vector, array e string, che sottolinea la loro “contiguità” a livello del modello di iteratori.

2. Cosa succede sotto il cofano: cache e linee di cache

Se semplifichiamo molto (utile per i principianti), possiamo pensare che la CPU abbia diversi “livelli” di memoria: cache molto veloci e piccole e la memoria principale (RAM) più lenta. Quando leggete x = v[i], la CPU non porta necessariamente esattamente un singolo int. Di solito porta un blocco intero di byte adiacenti — la cosiddetta linea di cache.

Immaginate di andare in biblioteca per una pagina. Il bibliotecario non vi porta una sola pagina; vi porta l’intero libro e lo posa sul tavolo, perché è probabile che chiediate la pagina seguente. Questa è la località spaziale, solo che al posto delle pagine ci sono i byte.

Da qui deriva una conclusione chiave per il programmatore: quando gli elementi sono vicini (come in vector), la CPU entra spesso in una “modalità ideale”: carica la linea di cache e voi poi leggete gli elementi uno dopo l’altro quasi gratuitamente. Quando gli elementi sono sparsi (come in list), ogni passo può essere un “nuovo viaggio in biblioteca”.

3. Come i contenitori dispongono i dati in memoria

Adesso colleghiamo ciò che già sapete sui contenitori al modo in cui vivono in memoria. Qui non è importante memorizzare una “tabella di garanzie”, ma afferrare l’intuizione.

std::vector<T>: elementi contigui

vector memorizza gli elementi in un singolo blocco di memoria contiguo. Perciò l’iterazione su di esso generalmente si adatta bene alla cache e al prefetching — la CPU anticipa e carica le linee di cache successive mentre voi leggete gli elementi correnti.

Inoltre, vector fornisce data() — un modo per ottenere un puntatore al primo elemento, che sottolinea ancora la natura “array‑like” del contenitore.

std::list<T>: nodi e puntatori

list è un contenitore a nodi: ogni elemento risiede in un “nodo” separato, e i nodi sono collegati da puntatori. Questo è comodo per inserimenti/cancellazioni veloci in una posizione, ma spesso è pessimo per la cache: passare da un nodo all’altro significa “saltare” attraverso la memoria.

std::deque<T>: blocchi e compromesso

deque normalmente memorizza i dati in blocchi: ogni blocco è abbastanza contiguo per conto suo, ma il contenitore nel suo insieme è una collezione di blocchi. In pratica deque si colloca spesso tra vector e list: la località è migliore rispetto a una lista, ma peggiore rispetto a un vettore.

In un attraversamento lineare deque solitamente va bene: dentro ogni blocco gli elementi sono vicini e per la CPU è più semplice. Tuttavia i passaggi tra blocchi possono rompere il prefetching perfetto e rendere l’accesso un po’ meno “fluido” rispetto a vector.

Se vi servono frequenti push_front/pop_front, deque è una scelta sensata. Se invece volete il massimo delle prestazioni per un passaggio lineare su un grande array di dati, “più è vicino a un array puro, meglio è” — e qui vector solitamente è in vantaggio.

Per fissare visivamente il concetto, ecco uno schema (semplificato):

flowchart TB
    subgraph V[vector]
      v1["[0][1][2][3][4][5][6][7] (contigui)"]
    end

    subgraph D[deque]
      d1["[0][1][2] (blocco A)"]
      d2["[3][4][5] (blocco B)"]
      d3["[6][7] (blocco C)"]
    end

    subgraph L[list]
      l1["nodo: 0"] --> l2["nodo: 1"] --> l3["nodo: 2"] --> l4["nodo: 3"]
      l4 --> l5["..."]
    end

4. Mini‑esperimento: stampare gli indirizzi degli elementi

Probabilmente non volete ancora (e avete ragione) misurare le prestazioni “con il cronometro in mano”: è una disciplina a sé. Ma percepire la località è possibile con un trucco semplice: stampare gli indirizzi degli elementi.

Indirizzi in vector: di solito “in file ordinati”

Integriamo un piccolo frammento diagnostico nella nostra applicazione didattica TaskBox (per ipotesi: un manager di task in memoria). Supponiamo di avere un vettore delle durate dei task.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> minutes{10, 20, 30, 40};

    for (std::size_t i = 0; i < minutes.size(); ++i) {
        std::cout << static_cast<const void*>(&minutes[i]) << '\n';
    }
}

Vedrete che gli indirizzi saranno “quasi contigui” (differiranno della dimensione di un int, tipicamente 4 byte). Questa è la località spaziale in forma pura.

Indirizzi in list: spesso “sparsi”

Ora lo stesso esperimento per una lista:

#include <iostream>
#include <list>

int main() {
    std::list<int> minutes{10, 20, 30, 40};

    for (int& x : minutes) {
        std::cout << static_cast<const void*>(&x) << '\n';
    }
}

Gli indirizzi degli elementi di list spesso appaiono sparsi. È normale: ogni nodo viene allocato separatamente e “vicino” in memoria può esserci qualsiasi cosa — persino dati di un altro contenitore.

Ed ecco l’effetto: “formalmente sempre O(N), ma la CPU è triste”.

5. TaskBox: lo stesso algoritmo, contenitori diversi

Immaginiamo che in TaskBox conserviamo task e dobbiamo spesso calcolare il tempo totale dei task “attivi”. Per ora non tocchiamo file, multithreading o architetture complesse — lavoriamo onestamente con i contenitori.

Creiamo un modello di task quanto più semplice possibile (abbiamo già imparato struct, quindi lo usiamo):

#include <string>

struct Task {
    std::string title;
    int minutes = 0;
    bool done = false;
};

Somma su vector<Task>

#include <vector>

int sum_active_minutes(const std::vector<Task>& tasks) {
    int total = 0;
    for (const Task& t : tasks) {
        if (!t.done) total += t.minutes;
    }
    return total;
}

Il codice è semplice, leggibile e di solito veloce: i task sono contigui, procediamo linearmente, leggiamo i campi, la CPU è felice.

Lo stesso codice, ma con list<Task>

#include <list>

int sum_active_minutes(const std::list<Task>& tasks) {
    int total = 0;
    for (const Task& t : tasks) {
        if (!t.done) total += t.minutes;
    }
    return total;
}

Formalmente la complessità è la stessa: O(N). Ma nella pratica c’è una maggiore probabilità che ogni successivo t si trovi in una linea di cache diversa o addirittura in un’altra area di memoria. Quindi ogni iterazione potrebbe comportare attese extra.

Importante: questo non significa che list sia “cattiva”. Significa che list paga il costo della sua struttura (nodi e puntatori) in termini di velocità nell’attraversamento.

Perché vector vince anche sulle costanti

Quando memorizzate Task in una list, non memorizzate solo il Task, ma anche i “campi di servizio” del nodo: almeno i puntatori al nodo precedente e a quello successivo (di solito due puntatori). Inoltre ogni nodo richiede una singola allocazione — anche questo è lavoro.

Quando memorizzate Task in un vector, invece, memorizzate quasi soltanto i task, uno dopo l’altro. Sì, il vector ha size()/capacity() e talvolta riallocazioni, ma durante un singolo attraversamento i costi aggiuntivi sono minimi.

Vale la pena ricordare che la libreria standard distingue tra contenitori i cui dati risiedono fisicamente in modo contiguo: è un concetto importante dei contenitori, non una “opzione da smanettoni”.

6. Ottimizzazione invisibile: stile di attraversamento dei dati

Esiste una piccola trappola mentale: sembra che la località sia “bassa livello”. In realtà avete già fatto passi in questa direzione scegliendo semplici attraversamenti lineari senza salti inutili.

Per esempio, questo codice per vector è leggibile e in genere performante:

#include <vector>

int sum_all(const std::vector<int>& v) {
    int total = 0;
    for (int x : v) total += x;
    return total;
}

Invece questo “equivalente logico”, ma più faticoso per la CPU reale (soprattutto se usate indicizzazione complessa e branching), può essere peggiore:

#include <vector>

int sum_all_weird(const std::vector<int>& v) {
    int total = 0;
    for (std::size_t i = 0; i < v.size(); i += 2) {
        total += v[i];
        if (i + 1 < v.size()) total += v[i + 1];
    }
    return total;
}

Non è “rotto”, ha solo più condizioni, più controlli ed è meno simile a un regolare “treno” che scorre sulla memoria. Le ottimizzazioni reali del compilatore possono attenuare questo, ma come stile — soprattutto per i principianti — è meglio preferire attraversamenti semplici e prevedibili.

7. Come la località influenza la scelta del contenitore

Quando scegliete un contenitore, guardate prima il profilo delle operazioni (inserimenti, cancellazioni, accesso per indice, operazioni sulle estremità). Ma se il profilo ammette più opzioni, la località spesso diventa l’argomento decisivo.

Un pensiero molto pratico da ricordare: se percorrete spesso i dati “dall’inizio alla fine” e svolgete calcoli semplici, volete che i dati siano il più compatti possibile. Per questo motivo vector spesso “vince di default”.

E non è solo un “consiglio da forum”. In C++ il modello degli iteratori sottolinea con la categoria separata di contiguous iterators che vector (come array, string) fornisce accesso di memoria contiguo.

8. Errori tipici quando si prova a ottimizzare per la località

Errore n.1: scegliere std::list “perché l’inserimento è O(1)”, e poi fare milioni di attraversamenti lineari.
I principianti sentono parlare di “inserimento O(1)” e pensano che list sia una versione migliorata di vector. Ma list paga con nodi e puntatori, e negli attraversamenti spesso perde. La domanda corretta è: “Sto davvero inserendo continuamente nel mezzo, o percorro il contenitore più spesso?”

Errore n.2: cercare di dimostrare la località con una singola stampa di indirizzi e trarne conclusioni assolute.
Se avete stampato gli indirizzi e avete visto “quasi contigui”, è una buona intuizione, ma non è un contratto valido per tutti gli allocator e tutte le piattaforme. È importante capire il modello: in vector gli elementi sono contigui; in list i nodi sono separati.

Errore n.3: “ottimizzare” i contenitori senza avere un problema reale.
A volte si vuole sostituire tutto con vector perché “è più veloce”. Ma se il vostro scenario richiede spesso push_front o cancellazioni per iteratore nel mezzo senza ricostruire la struttura, pagherete in spostamenti di elementi. Il contenitore va scelto in base alle operazioni; la località è il secondo livello di criterio.

Errore n.4: mettere oggetti pesanti nel contenitore e poi stupirsi che “la località non ha aiutato”.
Se dentro Task ci sono stringhe grandi e fate continue copie o create/cancellate elementi frequentemente, il collo di bottiglia può essere un’altra parte del programma. La località aiuta quando leggete/elaborate dati già creati, non quando state continuamente facendo “feste di allocazione”.

Errore n.5: concludere “dato che vector è contiguo, posso memorizzare riferimenti/puntatori agli elementi e andarci tranquillo”.
Anche se gli elementi sono contigui, vector può riallocare la memoria quando cresce, e tutti i riferimenti precedenti diventano discutibili. La località riguarda la velocità di accesso, non l’“immortalità” dei riferimenti. Se la sicurezza dei riferimenti è importante, dovete rispettare le regole di invalidamento (ne abbiamo già parlato nel corso).