Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / C++

Localidade da cache em C++: AoS e SoA

Escolhe a disposição dos dados em função do que o programa realmente lê. AoS agrupa os campos de um registo; SoA agrupa os valores do mesmo campo de vários registos.

Versão: ISO C++23; implementation support may vary

Sintaxe

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

A conceção orientada aos dados parte das operações mais frequentes: que campos são lidos em conjunto, por que ordem e com que frequência? A localidade da cache consiste em aceder a posições de memória próximas (localidade espacial) ou em reutilizar os mesmos dados pouco depois (localidade temporal). A disposição dos dados afeta diretamente a localidade espacial.

Um array de estruturas (AoS) armazena os registos consecutivos numa sequência contígua; rows[i].score é um campo do registo i. Os campos score consecutivos estão separados por sizeof(Record) bytes, incluindo eventuais bytes de preenchimento. Uma estrutura de arrays (SoA) armazena cada campo na sua própria coluna contígua; cols.score[i] e cols.id[i] pertencem ao mesmo registo lógico. Mantém os índices sincronizados em todas as colunas ao redimensionar ou reordenar.

Em SoA, percorrer sequencialmente apenas a coluna score, usada com frequência, pode permitir colocar mais valores úteis em cada linha de cache e reduzir o carregamento de dados não utilizados. AoS pode ser mais adequado quando uma operação usa em conjunto muitos campos de cada registo. C++23 garante a contiguidade dos elementos de std::array, mas não fixa a dimensão das linhas de cache nem garante ganhos de velocidade.

Mede ambas as disposições com volumes de dados e padrões de acesso representativos, numa compilação otimizada e no hardware de destino. Inclui o custo da conversão ou apresenta-o em separado: a cópia e o espaço adicional podem anular os ganhos das passagens seguintes.

Exemplos

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

Resultado

AoS sum: 15
SoA sum: 15

O programa copia ambos os campos de `rows` para `cols` e soma apenas `score` em cada disposição. Ambas as somas dão 15. O exemplo demonstra a disposição dos dados, mas não mede o desempenho.

Lições relacionadas

  • C++ · Lição 21 · Avançado · Versão: 3

Fontes