CKTIS / C++
Производителност, сложност и локалност на данните
Сложността описва как разходите нарастват с размера на входа, а не брой милисекунди. AoS и SoA може да имат еднаква сложност, но да използват кеша различно. Изборът изисква измервания с действителния модел на достъп.
Версия: C++23; repository compiler flag, production runtime not attested
Синтаксис
#include <vector>
// AoS
struct Particle {
int x, y;
};
std::vector<Particle> aos;
// SoA
struct Particles {
std::vector<int> x, y;
};
Particles soa;Времевата или пространствената сложност описва как разходите нарастват с размера на входа n. O(n) означава асимптотична горна граница с линеен растеж, а не точно време. Изискванията на стандартната библиотека за сложност са горни граници. Амортизираната цена се отнася до поредица от операции: добавянето към std::vector има амортизирана константна цена, но отделно добавяне може да изисква преразпределяне на паметта и линейна работа.
AoS, SoA и локалност на кеша: AoS (array of structures) съхранява цели записи един до друг, както в std::vector<Particle>. SoA (structure of arrays) разделя полетата в отделни масиви, както в Particles. Елементите на std::vector<T> са разположени последователно в паметта за T, различно от bool; това не означава, че Particle няма вътрешно допълване. При SoA съответстващите индекси трябва да обозначават един и същ запис, а дължините на масивите трябва да се поддържат еднакви.
Пространствената локалност означава достъп до близки адреси. Когато се чете само x, SoA групира нужните стойности, без да ги преплита с полета y, което може да използва кеш линиите по-ефективно. AoS може да е полезен при обработка на много полета от един запис. Това са прогнози, зависещи от хардуера, компилатора и натоварването, а не гаранции на C++. Двата цикъла в примера извършват линеен брой събирания и използват константна допълнителна памет.
Преди оптимизация проверете коректността и открийте скъпите операции с профилиращ инструмент. Сравнявайте представителни данни, настройки за оптимизация и повторени измервания; отделяйте заделянето на памет и входа/изхода от измерваната работа и запазвайте наблюдаем резултат. Примерът не е бенчмарк. Този материал е за C++23; флагът на компилатора в хранилището сам по себе си не удостоверява производствената среда. Предоставеният изходен код е развиваща се чернова, а не замразено издание на C++23.
Примери
#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';
}
Резултат
6 6
Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.