Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

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

Źródła