Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

Lokalnost predmemorije u C++-u: AoS i SoA

Odaberi raspored podataka prema tome što program doista čita. AoS grupira polja jednog zapisa, a SoA grupira vrijednosti istog polja iz više zapisa.

Verzija: ISO C++23; implementation support may vary

Sintaksa

// 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.

Oblikovanje usmjereno na podatke polazi od najčešćih operacija: koja se polja čitaju zajedno, kojim redoslijedom i koliko često? Lokalnost predmemorije znači pristupanje bliskim memorijskim lokacijama (prostorna lokalnost) ili skoru ponovnu uporabu istih podataka (vremenska lokalnost). Raspored podataka izravno utječe na prostornu lokalnost.

Niz struktura (AoS) pohranjuje uzastopne zapise u neprekinutom području memorije; rows[i].score je polje zapisa i. Uzastopna polja score udaljena su sizeof(Record) bajtova, uključujući eventualne bajtove ispune. Struktura nizova (SoA) pohranjuje vrijednosti svakog polja u zasebnom neprekinutom stupcu; cols.score[i] i cols.id[i] pripadaju istom logičkom zapisu. Pri promjeni veličine ili redoslijeda zadrži usklađene indekse u svim stupcima.

Pri sekvencijalnom prolasku samo kroz često korišten stupac score u SoA u jednu liniju predmemorije može stati više korisnih vrijednosti pa se može učitati manje neiskorištenih podataka. AoS može bolje odgovarati operacijama koje koriste mnogo polja svakog zapisa zajedno. C++23 jamči neprekinut raspored elemenata std::array, ali ne propisuje veličinu linije predmemorije niti jamči ubrzanje.

Izmjeri oba rasporeda s reprezentativnim količinama podataka i obrascima pristupa, u optimiziranoj verziji programa na ciljnom hardveru. Uključi trošak pretvorbe ili ga prikaži odvojeno: kopiranje i dodatna memorija mogu poništiti dobitak naknadnih prolazaka.

Primjeri

#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';
}

Rezultat

AoS sum: 15
SoA sum: 15

Program kopira oba polja iz `rows` u `cols`, a zatim u oba rasporeda zbraja samo vrijednosti `score`. Oba zbroja iznose 15. Primjer prikazuje raspored podataka, a ne mjeri brzinu izvođenja.

Povezane lekcije

  • C++ · Lekcija 21 · Napredno · Verzija: 3

Izvori