Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / C++

Prestazioni, complessità e località dei dati

La complessità descrive come cresce il costo con la dimensione dei dati, non un numero di millisecondi. AoS e SoA possono avere la stessa complessità ma usare la cache in modo diverso. La scelta richiede misurazioni con il modello di accesso effettivo.

Versione: C++23; repository compiler flag, production runtime not attested

Sintassi

#include <vector>

// AoS
struct Particle {
    int x, y;
};
std::vector<Particle> aos;

// SoA
struct Particles {
    std::vector<int> x, y;
};
Particles soa;

La complessità temporale o spaziale descrive come cresce il costo con la dimensione dell’input n. O(n) indica un limite superiore asintotico con crescita lineare, non una durata esatta. I requisiti di complessità della libreria standard sono limiti superiori. Il costo ammortizzato riguarda una sequenza di operazioni: aggiungere a std::vector ha costo costante ammortizzato, ma una singola aggiunta può richiedere una riallocazione e lavoro lineare.

AoS, SoA e località della cache: AoS (array of structures) memorizza record completi uno accanto all’altro, come in std::vector<Particle>. SoA (structure of arrays) separa i campi in array distinti, come in Particles. Gli elementi di std::vector<T> sono contigui per T diverso da bool; ciò non implica che Particle non abbia padding interno. In SoA, gli indici corrispondenti devono identificare lo stesso record e le lunghezze degli array devono restare coerenti.

La località spaziale consiste nell’accedere a indirizzi vicini. Quando si legge solo x, SoA raggruppa i valori necessari senza intercalarli con i campi y, e può così usare meglio le linee della cache. AoS può essere utile quando si elaborano molti campi di un record. Sono previsioni che dipendono da hardware, compilatore e carico di lavoro, non garanzie di C++. Entrambi i cicli dell’esempio eseguono un numero lineare di addizioni e usano spazio ausiliario costante.

Prima di ottimizzare, verifica la correttezza e individua le operazioni costose con un profiler. Confronta dati rappresentativi, impostazioni di ottimizzazione e misurazioni ripetute; separa allocazione e input/output dal lavoro misurato e mantieni un risultato osservabile. L’esempio non è un benchmark. Questa voce ha come riferimento C++23; un’opzione del compilatore nel repository, da sola, non attesta l’ambiente di produzione. Il codice fornito è una bozza in evoluzione, non un’edizione C++23 congelata.

Esempi

#include <iostream>
#include <vector>

struct Particle {
    int x;
    int y;
};

struct Particles {
    std::vector<int> x;
    std::vector<int> y;
};

int main() {
    const std::vector<Particle> aos{{1, 10}, {2, 20}, {3, 30}};
    const Particles soa{{1, 2, 3}, {10, 20, 30}};

    int aos_sum = 0;
    for (const auto& p : aos) {
        aos_sum += p.x;
    }

    int soa_sum = 0;
    for (int x : soa.x) {
        soa_sum += x;
    }

    std::cout << aos_sum << ' ' << soa_sum << '\n';
}

Risultato

6 6

Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.

Fonti