CKTIS / C++
Lokalność pamięci podręcznej w C++: AoS i SoA
Dobieraj układ danych do tego, co program faktycznie odczytuje. AoS grupuje pola rekordu, a SoA grupuje wartości tego samego pola z wielu rekordów.
Wersja: ISO C++23; implementation support may vary
Składnia
// 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.Projektowanie zorientowane na dane zaczyna się od najczęściej wykonywanych operacji: które pola są odczytywane razem, w jakiej kolejności i jak często? Lokalność pamięci podręcznej polega na korzystaniu z danych znajdujących się blisko siebie w pamięci (lokalność przestrzenna) lub na ponownym używaniu tych samych danych w krótkim czasie (lokalność czasowa). Układ danych wpływa bezpośrednio na lokalność przestrzenną.
Tablica struktur (AoS) przechowuje kolejne rekordy w jednym ciągłym obszarze; rows[i].score to pole rekordu i. Odstęp między kolejnymi polami score wynosi sizeof(Record), z uwzględnieniem ewentualnego dopełnienia. Struktura tablic (SoA) przechowuje każde pole w osobnej, ciągłej kolumnie; cols.score[i] i cols.id[i] należą logicznie do tego samego rekordu. Przy zmianie rozmiaru lub kolejności trzeba zachować zgodność indeksów we wszystkich kolumnach.
Sekwencyjny odczyt tylko często używanej kolumny score w SoA może zmieścić więcej potrzebnych wartości w jednej linii pamięci podręcznej i ograniczyć pobieranie nieużywanych danych. AoS może być korzystniejszy, gdy operacja korzysta z wielu pól każdego rekordu naraz. C++23 gwarantuje ciągłość elementów std::array, ale nie określa rozmiaru linii pamięci podręcznej ani nie gwarantuje przyspieszenia.
Zmierz oba układy na reprezentatywnych rozmiarach danych i przy rzeczywistych wzorcach dostępu, w zoptymalizowanej kompilacji na docelowym sprzęcie. Uwzględnij albo osobno zmierz koszt konwersji: kopiowanie i dodatkowe miejsce mogą zniwelować zysk z późniejszych przebiegów.
Przykłady
#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';
}
Wynik
AoS sum: 15 SoA sum: 15
Program kopiuje oba pola z `rows` do `cols` i sumuje tylko `score` w obu układach. Obie sumy wynoszą 15. To przykład układu danych, nie test wydajności.
Powiązane lekcje
- C++ · Lekcja 21 · Zaawansowany · Wersja: 3