CKTIS / C++
Leistung, Komplexität und Datenlokalität
Komplexität beschreibt, wie die Kosten mit der Eingabegröße wachsen, nicht eine Anzahl von Millisekunden. AoS und SoA können dieselbe Komplexität haben, den Cache aber unterschiedlich nutzen. Die Wahl erfordert Messungen mit dem tatsächlichen Zugriffsmuster.
Version: 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;Zeit- oder Speicherkomplexität beschreibt, wie die Kosten mit der Eingabegröße n wachsen. O(n) bezeichnet eine asymptotische obere Schranke mit linearem Wachstum, keine genaue Dauer. Komplexitätsanforderungen der Standardbibliothek sind obere Schranken. Amortisierte Kosten beziehen sich auf eine Folge von Operationen: Das Anhängen an std::vector hat amortisiert konstante Kosten, doch ein einzelnes Anhängen kann eine Reallokation und linearen Aufwand erfordern.
AoS, SoA und Cache-Lokalität: AoS (array of structures) speichert vollständige Datensätze nebeneinander, etwa in std::vector<Particle>. SoA (structure of arrays) trennt Felder in einzelne Arrays, etwa in Particles. Elemente von std::vector<T> liegen für T außer bool zusammenhängend im Speicher; das bedeutet nicht, dass Particle kein internes Padding hat. Bei SoA müssen entsprechende Indizes denselben Datensatz bezeichnen und die Array-Längen übereinstimmen.
Räumliche Lokalität bedeutet den Zugriff auf benachbarte Adressen. Wird nur x gelesen, gruppiert SoA die benötigten Werte, ohne sie mit y-Feldern zu verschachteln; dadurch können Cache-Zeilen möglicherweise besser genutzt werden. AoS kann vorteilhaft sein, wenn viele Felder eines Datensatzes verarbeitet werden. Das sind von Hardware, Compiler und Arbeitslast abhängige Erwartungen, keine C++-Garantien. Beide Beispielschleifen führen eine lineare Anzahl von Additionen aus und verwenden konstanten zusätzlichen Speicher.
Prüfe vor der Optimierung die Korrektheit und finde mit einem Profiler die aufwendigen Stellen. Vergleiche repräsentative Daten, Optimierungseinstellungen und wiederholte Messungen; trenne Allokation sowie Ein-/Ausgabe von der gemessenen Arbeit und erhalte ein beobachtbares Ergebnis. Das Beispiel ist kein Benchmark. Dieser Eintrag zielt auf C++23; ein Compiler-Flag im Repository allein bestätigt nicht die Produktionsumgebung. Der bereitgestellte Quelltext ist ein weiterentwickelter Entwurf, keine eingefrorene C++23-Ausgabe.
Beispiele
#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';
}
Ergebnis
6 6
Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.