CKTIS / C++
Lokalnost predpomnilnika v C++: AoS in SoA
Razporeditev podatkov izberi glede na to, kaj program dejansko bere. AoS združuje polja enega zapisa, SoA pa vrednosti istega polja iz več zapisov.
Različica: ISO C++23; implementation support may vary
Sintaksa
// 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.Podatkovno usmerjeno načrtovanje izhaja iz najpogostejših operacij: katera polja se berejo skupaj, v kakšnem vrstnem redu in kako pogosto? Lokalnost predpomnilnika pomeni dostopanje do bližnjih lokacij v pomnilniku (prostorska lokalnost) ali hitro ponovno uporabo istih podatkov (časovna lokalnost). Razporeditev podatkov neposredno vpliva na prostorsko lokalnost.
Tabela struktur (AoS) zaporedne zapise hrani v neprekinjenem zaporedju; rows[i].score je polje zapisa i. Zaporedni polji score sta med seboj oddaljeni sizeof(Record) bajtov, vključno z morebitnimi polnilnimi bajti. Struktura tabel (SoA) hrani vrednosti vsakega polja v ločenem neprekinjenem stolpcu; cols.score[i] in cols.id[i] pripadata istemu logičnemu zapisu. Pri spreminjanju velikosti ali vrstnega reda ohrani usklajene indekse v vseh stolpcih.
Pri zaporednem prehodu samo po pogosto uporabljenem stolpcu score v SoA je lahko v vsaki vrstici predpomnilnika več uporabnih vrednosti, zato se lahko naloži manj neuporabljenih podatkov. AoS je lahko primernejši, kadar operacija hkrati uporablja veliko polj vsakega zapisa. C++23 zagotavlja neprekinjeno razporeditev elementov std::array, ne določa pa velikosti vrstice predpomnilnika in ne zagotavlja pohitritve.
Obe razporeditvi izmeri na ciljni strojni opremi z optimizirano gradnjo ter reprezentativnimi količinami podatkov in vzorci dostopa. Vključi strošek pretvorbe ali ga navedi ločeno: kopiranje in dodatni pomnilnik lahko izničita prednosti poznejših prehodov.
Primeri
#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';
}
Rezultat
AoS sum: 15 SoA sum: 15
Program prekopira obe polji iz `rows` v `cols`, nato v obeh razporeditvah sešteje samo vrednosti `score`. Obe vsoti sta 15. Primer prikazuje razporeditev podatkov in ne meri zmogljivosti.
Povezane lekcije
- C++ · Lekcija 21 · Napredna · Različica: 3