CKTIS / C++
Výkon, zložitosť a lokalita dát
Zložitosť opisuje, ako náklady rastú s veľkosťou vstupu, nie počet milisekúnd. AoS a SoA môžu mať rovnakú zložitosť, no odlišne využívať cache. Výber si vyžaduje merania so skutočným vzorom prístupu.
Verzia: C++23; repository compiler flag, production runtime not attested
Syntax
#include <vector>
// AoS
struct Particle {
int x, y;
};
std::vector<Particle> aos;
// SoA
struct Particles {
std::vector<int> x, y;
};
Particles soa;Časová alebo priestorová zložitosť opisuje, ako náklady rastú s veľkosťou vstupu n. O(n) označuje asymptotickú hornú hranicu s lineárnym rastom, nie presný čas. Požiadavky na zložitosť v štandardnej knižnici sú horné hranice. Amortizované náklady sa týkajú postupnosti operácií: pridávanie do std::vector má amortizovane konštantné náklady, ale jedno pridanie môže vyžadovať realokáciu a lineárnu prácu.
AoS, SoA a lokalita cache: AoS (array of structures) ukladá celé záznamy vedľa seba, napríklad v std::vector<Particle>. SoA (structure of arrays) oddeľuje polia do samostatných polí, napríklad v Particles. Prvky std::vector<T> sú súvislé v pamäti pre T iné ako bool; to neznamená, že Particle nemá vnútornú výplň. V SoA musia zodpovedajúce indexy označovať ten istý záznam a dĺžky polí musia zostať zhodné.
Priestorová lokalita znamená prístup k blízkym adresám. Pri čítaní iba x SoA zoskupuje potrebné hodnoty bez prekladania polí y, takže môže lepšie využiť riadky cache. AoS môže byť užitočné pri spracovaní viacerých polí jedného záznamu. Sú to predpoklady závislé od hardvéru, kompilátora a záťaže, nie záruky C++. Obidve ukážkové slučky vykonajú lineárny počet sčítaní a používajú konštantnú pomocnú pamäť.
Pred optimalizáciou overte správnosť a nájdite nákladné miesta pomocou profilera. Porovnávajte reprezentatívne údaje, nastavenia optimalizácie a opakované merania; oddeľte alokáciu a vstup/výstup od meranej práce a zachovajte pozorovateľný výsledok. Ukážka nie je benchmark. Tento záznam sa vzťahuje na C++23; samotný príznak kompilátora v repozitári nepotvrdzuje produkčné prostredie. Dodaný zdrojový kód je rozvíjaný návrh, nie zmrazené vydanie C++23.
Príklady
#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';
}
Výsledok
6 6
Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.