KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / C++

Prestaties, complexiteit en datalokaliteit

Complexiteit beschrijft hoe de kosten groeien met de invoergrootte, niet een aantal milliseconden. AoS en SoA kunnen dezelfde complexiteit hebben en de cache toch verschillend benutten. De keuze vereist metingen met het daadwerkelijke toegangspatroon.

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

Syntax

#include <vector>

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

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

Tijd- of ruimtecomplexiteit beschrijft hoe de kosten groeien met invoergrootte n. O(n) duidt een asymptotische bovengrens met lineaire groei aan, geen exacte tijdsduur. Complexiteitseisen van de standaardbibliotheek zijn bovengrenzen. Geamortiseerde kosten hebben betrekking op een reeks bewerkingen: toevoegen aan het einde van een std::vector heeft geamortiseerd constante kosten, maar één toevoeging kan herallocatie en lineair werk vereisen.

AoS, SoA en cachelokaliteit: AoS (array of structures) slaat volledige records naast elkaar op, zoals in std::vector<Particle>. SoA (structure of arrays) verdeelt velden over afzonderlijke arrays, zoals in Particles. Elementen van std::vector<T> zijn aaneengesloten voor T anders dan bool; dit betekent niet dat Particle geen interne opvulling heeft. Bij SoA moeten overeenkomstige indices hetzelfde record aanduiden en moeten de arraylengtes consistent blijven.

Ruimtelijke lokaliteit betekent toegang tot adressen die dicht bij elkaar liggen. Als alleen x wordt gelezen, groepeert SoA de benodigde waarden zonder y-velden ertussen; daardoor kunnen cachelijnen mogelijk beter worden benut. AoS kan nuttig zijn wanneer meerdere velden van één record worden verwerkt. Dit zijn verwachtingen die afhangen van hardware, compiler en werklast, geen C++-garanties. Beide voorbeeldlussen voeren een lineair aantal optellingen uit en gebruiken constante extra ruimte.

Controleer vóór optimalisatie de correctheid en vind duur werk met een profiler. Vergelijk representatieve gegevens, optimalisatie-instellingen en herhaalde metingen; houd allocatie en invoer/uitvoer gescheiden van het gemeten werk en behoud een waarneembaar resultaat. Het voorbeeld is geen benchmark. Dit artikel richt zich op C++23; een compileroptie in de repository alleen bevestigt de productieomgeving niet. De meegeleverde broncode is een evoluerend concept, geen bevroren C++23-editie.

Voorbeelden

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

Resultaat

6 6

De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.

Bronnen