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.