Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / C++

Lokalnost predpomnilnika v C++: AoS in SoA

Razporeditev podatkov izberi glede na to, kaj program dejansko bere. AoS združuje polja enega zapisa, SoA pa vrednosti istega polja iz več zapisov.

Različica: 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.

Podatkovno usmerjeno načrtovanje izhaja iz najpogostejših operacij: katera polja se berejo skupaj, v kakšnem vrstnem redu in kako pogosto? Lokalnost predpomnilnika pomeni dostopanje do bližnjih lokacij v pomnilniku (prostorska lokalnost) ali hitro ponovno uporabo istih podatkov (časovna lokalnost). Razporeditev podatkov neposredno vpliva na prostorsko lokalnost.

Tabela struktur (AoS) zaporedne zapise hrani v neprekinjenem zaporedju; rows[i].score je polje zapisa i. Zaporedni polji score sta med seboj oddaljeni sizeof(Record) bajtov, vključno z morebitnimi polnilnimi bajti. Struktura tabel (SoA) hrani vrednosti vsakega polja v ločenem neprekinjenem stolpcu; cols.score[i] in cols.id[i] pripadata istemu logičnemu zapisu. Pri spreminjanju velikosti ali vrstnega reda ohrani usklajene indekse v vseh stolpcih.

Pri zaporednem prehodu samo po pogosto uporabljenem stolpcu score v SoA je lahko v vsaki vrstici predpomnilnika več uporabnih vrednosti, zato se lahko naloži manj neuporabljenih podatkov. AoS je lahko primernejši, kadar operacija hkrati uporablja veliko polj vsakega zapisa. C++23 zagotavlja neprekinjeno razporeditev elementov std::array, ne določa pa velikosti vrstice predpomnilnika in ne zagotavlja pohitritve.

Obe razporeditvi izmeri na ciljni strojni opremi z optimizirano gradnjo ter reprezentativnimi količinami podatkov in vzorci dostopa. Vključi strošek pretvorbe ali ga navedi ločeno: kopiranje in dodatni pomnilnik lahko izničita prednosti poznejših prehodov.

Primeri

#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 prekopira obe polji iz `rows` v `cols`, nato v obeh razporeditvah sešteje samo vrednosti `score`. Obe vsoti sta 15. Primer prikazuje razporeditev podatkov in ne meri zmogljivosti.

Povezane lekcije

  • C++ · Lekcija 21 · Napredna · Različica: 3

Viri