CKTIS / C++
Локалност на кеша в C++: AoS и SoA
Избирай подредбата според данните, които програмата действително чете. AoS групира полетата на един запис, а SoA групира стойностите на едно и също поле от много записи.
Версия: ISO C++23; implementation support may vary
Синтаксис
// AoS: one contiguous array of records
std::array<Record, N> rows; // access: rows[i].score
// SoA: one contiguous array per field
struct Columns {
std::array<int, N> score;
std::array<int, N> id;
};
Columns cols; // access: cols.score[i]
// Record and N must be defined; initialize values before reading.Проектирането, ориентирано към данните, започва от най-честите операции: кои полета се четат заедно, в какъв ред и колко често? Локалност на кеша означава достъп до близки адреси в паметта (пространствена локалност) или скорошно повторно използване на същите данни (времева локалност). Подредбата на данните влияе пряко върху пространствената локалност.
Масив от структури (AoS) съхранява последователните записи в непрекъсната област от паметта; rows[i].score е поле на записа i. Последователните полета score са на разстояние sizeof(Record) байта, включително евентуалните байтове за подравняване. Структура от масиви (SoA) съхранява стойностите на всяко поле в отделна непрекъсната колона; cols.score[i] и cols.id[i] принадлежат на един и същ логически запис. При промяна на размера или реда запазвай съответствието на индексите във всички колони.
При последователно обхождане само на често използваната колона score в SoA в един кеш ред могат да се поберат повече полезни стойности и да се заредят по-малко неизползвани данни. AoS може да е по-подходящо, когато операцията използва заедно много полета от всеки запис. C++23 гарантира, че елементите на std::array са разположени непрекъснато, но не определя размера на кеш реда и не гарантира ускорение.
Измери и двете подредби с представителни обеми данни и модели на достъп, като използваш оптимизирана компилация на целевия хардуер. Включи разхода за преобразуване или го отчети отделно: копирането и допълнителната памет могат да заличат ползата от следващите обхождания.
Примери
#include <array>
#include <cstddef>
#include <iostream>
struct Record {
int score;
int id;
};
template<std::size_t N>
struct Columns {
std::array<int, N> score;
std::array<int, N> id;
};
int main() {
const std::array<Record, 3> rows{Record{3, 101}, Record{5, 102}, Record{7, 103}};
Columns<3> cols{};
for (std::size_t i = 0; i < rows.size(); ++i) {
cols.score[i] = rows[i].score;
cols.id[i] = rows[i].id;
}
int aos_sum = 0;
for (const Record& row : rows) {
aos_sum += row.score;
}
int soa_sum = 0;
for (int score : cols.score) {
soa_sum += score;
}
std::cout << "AoS sum: " << aos_sum << '\n'
<< "SoA sum: " << soa_sum << '\n';
}
Резултат
AoS sum: 15 SoA sum: 15
Програмата копира и двете полета от `rows` в `cols`, след което сумира само стойностите на `score` при двете подредби. И двете суми са 15. Примерът показва подредбата на данните, а не измерва производителността.
Свързани уроци
- C++ · Урок 21 · Напреднало · Версия: 3