CKTIS / C++
Localité du cache en C++ : AoS et SoA
Choisissez la disposition des données selon ce que le programme lit réellement. AoS regroupe les champs d’un enregistrement ; SoA regroupe les valeurs d’un même champ entre enregistrements.
Version : ISO C++23; implementation support may vary
Syntaxe
// 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.La conception orientée données part des opérations les plus fréquentes : quels champs sont lus ensemble, dans quel ordre et à quelle fréquence ? La localité du cache consiste à accéder à des emplacements mémoire proches (localité spatiale) ou à réutiliser rapidement les mêmes données (localité temporelle). La disposition des données influe directement sur la localité spatiale.
Un tableau de structures (AoS) stocke les enregistrements à la suite dans une zone contiguë ; rows[i].score est un champ de l’enregistrement i. Deux champs score successifs sont espacés de sizeof(Record) octets, éventuels octets de bourrage compris. Une structure de tableaux (SoA) stocke chaque champ dans sa propre colonne contiguë ; cols.score[i] et cols.id[i] appartiennent au même enregistrement logique. Gardez les indices synchronisés entre toutes les colonnes lors d’un redimensionnement ou d’une réorganisation.
En SoA, un parcours séquentiel de la seule colonne score, fréquemment utilisée, peut placer davantage de valeurs utiles par ligne de cache et réduire le chargement de données inutilisées. AoS peut être préférable lorsqu’une opération utilise ensemble de nombreux champs de chaque enregistrement. C++23 garantit la contiguïté des éléments de std::array, mais ne fixe pas la taille des lignes de cache et ne promet aucun gain de vitesse.
Mesurez les deux dispositions avec des volumes de données et des profils d’accès représentatifs, dans une version optimisée sur le matériel cible. Incluez le coût de conversion ou présentez-le à part : la copie et le stockage supplémentaire peuvent annuler les gains des parcours suivants.
Exemples
#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';
}
Résultat
AoS sum: 15 SoA sum: 15
Le programme copie les deux champs de `rows` vers `cols`, puis additionne uniquement les valeurs de `score` dans les deux dispositions. Les deux sommes valent 15. Cet exemple illustre la disposition des données, sans mesurer les performances.
Leçons associées
- C++ · Leçon 21 · Avancé · Version : 3