CKTIS / C++
Performanse, složenost i lokalnost podataka
Složenost opisuje kako trošak raste s veličinom ulaza, a ne broj milisekundi. AoS i SoA mogu imati istu složenost, ali različito koristiti predmemoriju. Odabir zahtijeva mjerenja sa stvarnim obrascem pristupa.
Verzija: C++23; repository compiler flag, production runtime not attested
Sintaksa
#include <vector>
// AoS
struct Particle {
int x, y;
};
std::vector<Particle> aos;
// SoA
struct Particles {
std::vector<int> x, y;
};
Particles soa;Vremenska ili prostorna složenost opisuje kako trošak raste s veličinom ulaza n. O(n) označava asimptotsku gornju granicu linearnog rasta, a ne točno trajanje. Zahtjevi standardne biblioteke za složenost gornje su granice. Amortizirani trošak odnosi se na niz operacija: dodavanje u std::vector ima amortizirano konstantan trošak, ali pojedino dodavanje može zahtijevati realokaciju i linearan rad.
AoS, SoA i lokalnost predmemorije: AoS (array of structures) pohranjuje cijele zapise jedan do drugoga, kao u std::vector<Particle>. SoA (structure of arrays) razdvaja polja u zasebne nizove, kao u Particles. Elementi std::vector<T> kontinuirani su u memoriji za T različit od bool; to ne znači da Particle nema unutarnje popunjavanje. U SoA-i odgovarajući indeksi moraju označavati isti zapis, a duljine nizova moraju ostati usklađene.
Prostorna lokalnost znači pristup obližnjim adresama. Pri čitanju samo x, SoA grupira potrebne vrijednosti bez ispreplitanja s poljima y, pa može bolje iskoristiti retke predmemorije. AoS može biti koristan pri obradi više polja jednog zapisa. To su predviđanja ovisna o hardveru, prevoditelju i radnom opterećenju, a ne jamstva jezika C++. Obje petlje u primjeru izvode linearan broj zbrajanja i koriste konstantan pomoćni prostor.
Prije optimizacije provjerite ispravnost i profilerom pronađite skupe dijelove. Usporedite reprezentativne podatke, postavke optimizacije i ponovljena mjerenja; odvojite alokaciju i ulaz/izlaz od mjerenog rada te sačuvajte opažljiv rezultat. Primjer nije benchmark. Ovaj se zapis odnosi na C++23; zastavica prevoditelja u repozitoriju sama po sebi ne potvrđuje produkcijsko okruženje. Dostavljeni izvorni kod radni je nacrt koji se razvija, a ne zamrznuto izdanje C++23.
Primjeri
#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';
}
Rezultat
6 6
Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.