CKTIS / C++
Cachelokaliteit in C++: AoS en SoA
Kies de gegevensindeling op basis van wat het programma daadwerkelijk leest. AoS groepeert de velden van één record; SoA groepeert de waarden van hetzelfde veld uit meerdere records.
Versie: ISO C++23; implementation support may vary
Syntax
// 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.Datagericht ontwerpen begint bij de bewerkingen die het vaakst plaatsvinden: welke velden worden samen gelezen, in welke volgorde en hoe vaak? Cachelokaliteit houdt in dat je dicht bij elkaar gelegen geheugenlocaties benadert (ruimtelijke lokaliteit) of dezelfde gegevens snel opnieuw gebruikt (temporele lokaliteit). De gegevensindeling heeft direct invloed op de ruimtelijke lokaliteit.
Een array van structuren (AoS) slaat opeenvolgende records aaneengesloten op; rows[i].score is een veld van record i. Tussen opeenvolgende score-velden zit sizeof(Record) bytes, inclusief eventuele opvulbytes. Een structuur van arrays (SoA) slaat elk veld op in een eigen aaneengesloten kolom; cols.score[i] en cols.id[i] horen bij hetzelfde logische record. Houd de indices in alle kolommen op elkaar afgestemd wanneer je de grootte of volgorde wijzigt.
Door in SoA alleen de veelgebruikte kolom score opeenvolgend te doorlopen, passen er mogelijk meer nuttige waarden in elke cachelijn en worden er mogelijk minder ongebruikte gegevens opgehaald. AoS kan beter passen als een bewerking veel velden van elk record samen gebruikt. C++23 garandeert dat de elementen van std::array aaneengesloten zijn, maar legt geen cachelijngrootte vast en garandeert geen snelheidswinst.
Meet beide indelingen met representatieve gegevensvolumes en toegangspatronen, in een geoptimaliseerde build op de doelhardware. Neem de conversiekosten mee of rapporteer ze apart: kopiëren en extra opslag kunnen de winst van latere iteraties tenietdoen.
Voorbeelden
#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';
}
Resultaat
AoS sum: 15 SoA sum: 15
Het programma kopieert beide velden van `rows` naar `cols` en telt in beide indelingen alleen `score` op. Beide sommen zijn 15. Het voorbeeld toont de indeling en meet geen prestaties.
Gerelateerde lessen
- C++ · Les 21 · Gevorderd · Versie: 3