CKTIS / C++
Località della cache in C++: AoS e SoA
Scegli la disposizione dei dati in base a ciò che il programma legge davvero. AoS raggruppa i campi di un record; SoA raggruppa i valori dello stesso campo tra più record.
Versione: ISO C++23; implementation support may vary
Sintassi
// AoS: one contiguous array of records
std::array<Record, N> rows; // access: rows[i].score
// SoA: one contiguous array per field
struct Columns {
std::array<int, N> score;
std::array<int, N> id;
};
Columns cols; // access: cols.score[i]
// Record and N must be defined; initialize values before reading.La progettazione orientata ai dati parte dalle operazioni più frequenti: quali campi vengono letti insieme, in quale ordine e con quale frequenza? La località della cache consiste nell'accedere a posizioni di memoria vicine (località spaziale) o nel riutilizzare a breve gli stessi dati (località temporale). La disposizione dei dati influenza direttamente la località spaziale.
Un array di strutture (AoS) memorizza i record consecutivi in una sequenza contigua; rows[i].score è un campo del record i. Due campi score consecutivi distano sizeof(Record) byte, compreso l'eventuale riempimento. Una struttura di array (SoA) memorizza ogni campo in una colonna contigua distinta; cols.score[i] e cols.id[i] appartengono allo stesso record logico. Quando ridimensioni o riordini i dati, mantieni sincronizzati gli indici di tutte le colonne.
In SoA, scorrere in sequenza solo la colonna score, usata di frequente, può far entrare più valori utili in ogni linea di cache e ridurre il caricamento di dati inutilizzati. AoS può essere più adatto quando un'operazione usa insieme molti campi di ogni record. C++23 garantisce la contiguità degli elementi di std::array, ma non stabilisce le dimensioni delle linee di cache né garantisce un aumento di velocità.
Misura entrambe le disposizioni con volumi di dati e schemi di accesso rappresentativi, usando una build ottimizzata sull'hardware di destinazione. Includi il costo della conversione o riportalo separatamente: la copia e lo spazio aggiuntivo possono annullare i vantaggi delle scansioni successive.
Esempi
#include <array>
#include <cstddef>
#include <iostream>
struct Record {
int score;
int id;
};
template<std::size_t N>
struct Columns {
std::array<int, N> score;
std::array<int, N> id;
};
int main() {
const std::array<Record, 3> rows{Record{3, 101}, Record{5, 102}, Record{7, 103}};
Columns<3> cols{};
for (std::size_t i = 0; i < rows.size(); ++i) {
cols.score[i] = rows[i].score;
cols.id[i] = rows[i].id;
}
int aos_sum = 0;
for (const Record& row : rows) {
aos_sum += row.score;
}
int soa_sum = 0;
for (int score : cols.score) {
soa_sum += score;
}
std::cout << "AoS sum: " << aos_sum << '\n'
<< "SoA sum: " << soa_sum << '\n';
}
Risultato
AoS sum: 15 SoA sum: 15
Il programma copia entrambi i campi da `rows` a `cols`, poi somma solo `score` in entrambe le disposizioni. Le due somme valgono 15. L'esempio illustra la disposizione dei dati, non misura le prestazioni.
Lezioni correlate
- C++ · Lezione 21 · Avanzato · Versione: 3