CKTIS / C++
Výkon, složitost a lokalita dat
Složitost popisuje, jak náklady rostou s velikostí vstupu, nikoli kolik milisekund výpočet trvá. Uspořádání AoS a SoA mohou mít stejnou složitost, ale různě využívat mezipaměť. Při výběru je třeba měřit podle toho, jak program k datům skutečně přistupuje.
Verze: C++23; repository compiler flag, production runtime not attested
Syntaxe
#include <vector>
// AoS
struct Particle {
int x, y;
};
std::vector<Particle> aos;
// SoA
struct Particles {
std::vector<int> x, y;
};
Particles soa;Časová nebo paměťová složitost popisuje, jak náklady rostou s velikostí vstupu n. Zápis O(n) označuje asymptotickou horní mez s lineárním růstem, nikoli přesnou dobu běhu. Požadavky standardní knihovny na složitost udávají horní meze. Amortizované náklady se vztahují k posloupnosti operací: přidávání prvků na konec std::vector má amortizovaně konstantní náklady, ale jedno přidání může vyžadovat realokaci a množství práce úměrné počtu prvků.
AoS, SoA a lokalita dat v mezipaměti: AoS (array of structures, pole struktur) ukládá celé záznamy vedle sebe, například v std::vector<Particle>. SoA (structure of arrays, struktura polí) ukládá hodnoty jednotlivých členů do samostatných polí, jak ukazuje Particles. Pro T jiné než bool jsou prvky std::vector<T> uloženy souvisle v paměti; z toho neplyne, že Particle neobsahuje výplň mezi členy. V SoA musí stejný index ve všech polích označovat tentýž záznam a pole musí mít stejnou délku.
Prostorová lokalita znamená přístup k blízkým adresám v paměti. Při čtení pouze x jsou v SoA potřebné hodnoty uloženy vedle sebe a nejsou proloženy hodnotami y. To může vést k lepšímu využití řádků mezipaměti. AoS může být výhodné při zpracování více členů téhož záznamu. Jde o očekávání závislá na hardwaru, překladači a pracovní zátěži, nikoli o záruky jazyka C++. V obou smyčkách v ukázce roste počet sčítání lineárně s počtem prvků a množství pomocné paměti zůstává konstantní.
Před optimalizací ověřte správnost programu a pomocí profileru zjistěte, které části jsou nákladné. Použijte reprezentativní data, porovnejte různá nastavení optimalizace a měření opakujte. Oddělte alokaci a vstupně-výstupní operace od měřené části a zachovejte pozorovatelný výsledek. Ukázka neslouží jako benchmark. Tento záznam se vztahuje k C++23; samotná volba překladače uvedená v repozitáři nedokládá, v jakém prostředí program běží v produkci. Odkazovaný dokument je průběžně aktualizovaný pracovní návrh, nikoli neměnné vydání normy C++23.
Pří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ýsledek
6 6
Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí postupem zaznamenaným v dokladu o ověření této konkrétní verze.