CKTIS / C++
Datagericht ontwerp: AoS, SoA en cachelokaliteit
Stem de geheugenindeling af op het datagebruik van het programma: vergelijk volledige records met losse kolommen en meet het effect bij een representatieve werklast.
Versie: ISO C++23; implementation support may vary
Syntax
// ISO C++23 — alternative layouts for N records
// T and U are field types; N is a compile-time element count.
#include <array>
#include <cstddef>
template<class T, class U>
struct Record { T x; U y; };
template<class T, class U, std::size_t N>
using AoS = std::array<Record<T, U>, N>;
template<class T, class U, std::size_t N>
struct SoA {
std::array<T, N> x;
std::array<U, N> y;
};
// Record i: aos[i].x and aos[i].y, or soa.x[i] and soa.y[i].Bij datagericht ontwerp kies je de gegevensrepresentatie op basis van de bewerkingen die het programma uitvoert. Begin bij de belangrijkste lussen: welke velden lezen of schrijven ze, in welke volgorde en hoe vaak? AoS en SoA zijn geheugenindelingen, geen sleutelwoorden of aparte voorzieningen in C++23.
Een array van structs (AoS) slaat volledige records aaneengesloten op: aos[i].energy en aos[i].id horen bij hetzelfde object. Een struct van arrays (SoA) slaat elk veld in een eigen aaneengesloten array op: soa.energy[i] en soa.id[i] beschrijven hetzelfde logische record. Zorg dat de kolommen even lang zijn en dezelfde recordvolgorde houden, ook bij sorteren, invoegen en verwijderen.
De cachelokaliteit verbetert als opeenvolgende toegangen gegevens gebruiken die al in de cache zijn geladen. Leest een lus alleen de vaak gebruikte (warme) kolom energy, dan passen bij SoA mogelijk meer nuttige waarden in één cachelijn en worden mogelijk minder ongebruikte gegevens opgehaald. AoS kan gunstiger zijn als een bewerking meestal de meeste velden van elk record samen nodig heeft.
Geen van beide indelingen garandeert snelheidswinst. De omzetting kopieert hier beide velden van elk record; beide indelingen bijhouden kost extra geheugen en vereist dat wijzigingen gelijk blijven lopen. Vergelijk geoptimaliseerde builds op de doelhardware met representatieve gegevensgroottes en toegangspatronen. Meet de omzetting mee als die bij de werkelijke werklast hoort.
Voorbeelden
#include <array>
#include <cstddef>
#include <iostream>
struct Particle {
int energy;
int id;
};
struct ParticleColumns {
std::array<int, 3> energy;
std::array<int, 3> id;
};
int main() {
const std::array<Particle, 3> aos{{{2, 101}, {4, 102}, {6, 103}}};
ParticleColumns soa{};
for (std::size_t i = 0; i < aos.size(); ++i) {
soa.energy[i] = aos[i].energy;
soa.id[i] = aos[i].id;
}
int aosSum = 0;
for (const Particle& particle : aos) {
aosSum += particle.energy;
}
int soaSum = 0;
for (int energy : soa.energy) {
soaSum += energy;
}
std::cout << "AoS sum: " << aosSum << '\n'
<< "SoA sum: " << soaSum << '\n';
}Resultaat
AoS sum: 12 SoA sum: 12
Beide lussen tellen alleen `energy` op en drukken `12` af voor hun eigen indeling. De gelijke uitkomst toont dezelfde bewerking op twee indelingen, geen snelheidsvoordeel.
Gerelateerde lessen
- C++ · Les 21 · Gevorderd · Versie: 3