База знанияИзпитен център
BGБългарски
Избери език13

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

Източници