Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

CKTIS / C++

Performances, complexité et localité des données

La complexité décrit l’évolution du coût avec la taille des données, et non un nombre de millisecondes. AoS et SoA peuvent avoir la même complexité tout en utilisant le cache différemment. Le choix nécessite des mesures avec le motif d’accès réel.

Version : C++23; repository compiler flag, production runtime not attested

Syntaxe

#include <vector>

// AoS
struct Particle {
    int x, y;
};
std::vector<Particle> aos;

// SoA
struct Particles {
    std::vector<int> x, y;
};
Particles soa;

La complexité en temps ou en espace décrit l’évolution du coût avec la taille d’entrée n. O(n) désigne une borne supérieure asymptotique à croissance linéaire, et non une durée exacte. Les exigences de complexité de la bibliothèque standard sont des bornes supérieures. Le coût amorti concerne une séquence d’opérations : ajouter à std::vector a un coût constant amorti, mais un ajout isolé peut nécessiter une réallocation et un travail linéaire.

AoS, SoA et localité du cache : AoS (array of structures) stocke des enregistrements complets côte à côte, comme dans std::vector<Particle>. SoA (structure of arrays) sépare les champs dans des tableaux distincts, comme dans Particles. Les éléments de std::vector<T> sont contigus pour tout T autre que bool ; cela ne signifie pas que Particle n’a aucun remplissage interne. En SoA, les indices correspondants doivent désigner le même enregistrement et les longueurs des tableaux doivent rester cohérentes.

La localité spatiale consiste à accéder à des adresses proches. Lorsqu’on ne lit que x, SoA regroupe les valeurs nécessaires sans entrelacer les champs y, ce qui peut mieux exploiter les lignes de cache. AoS peut être utile quand on traite plusieurs champs d’un même enregistrement. Ce sont des prévisions dépendant du matériel, du compilateur et de la charge de travail, pas des garanties de C++. Les deux boucles de l’exemple effectuent un nombre linéaire d’additions et utilisent un espace auxiliaire constant.

Avant d’optimiser, vérifiez la correction et repérez les opérations coûteuses avec un profileur. Comparez des données représentatives, des réglages d’optimisation et des mesures répétées ; séparez les allocations et les entrées/sorties du travail mesuré et conservez un résultat observable. L’exemple n’est pas un benchmark. Cette fiche vise C++23 ; un indicateur de compilation dans le dépôt ne suffit pas à attester l’environnement de production. Le code fourni est une ébauche en évolution, pas une édition C++23 figée.

Exemples

#include <iostream>
#include <vector>

struct Particle {
    int x;
    int y;
};

struct Particles {
    std::vector<int> x;
    std::vector<int> y;
};

int main() {
    const std::vector<Particle> aos{{1, 10}, {2, 20}, {3, 30}};
    const Particles soa{{1, 2, 3}, {10, 20, 30}};

    int aos_sum = 0;
    for (const auto& p : aos) {
        aos_sum += p.x;
    }

    int soa_sum = 0;
    for (int x : soa.x) {
        soa_sum += x;
    }

    std::cout << aos_sum << ' ' << soa_sum << '\n';
}

Résultat

6 6

Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.

Sources