Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / C++

Zmogljivost, zahtevnost in lokalnost podatkov

Zahtevnost opisuje, kako stroški naraščajo z velikostjo vhoda, ne števila milisekund. AoS in SoA imata lahko enako zahtevnost, vendar različno uporabljata predpomnilnik. Izbira zahteva meritve z dejanskim vzorcem dostopa.

Različica: C++23; repository compiler flag, production runtime not attested

Sintaksa

#include <vector>

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

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

Časovna ali prostorska zahtevnost opisuje, kako stroški naraščajo z velikostjo vhoda n. O(n) označuje asimptotično zgornjo mejo z linearno rastjo, ne natančnega trajanja. Zahteve standardne knjižnice glede zahtevnosti so zgornje meje. Amortizirani stroški se nanašajo na zaporedje operacij: dodajanje v std::vector ima amortizirano konstantne stroške, vendar lahko posamezno dodajanje zahteva ponovno alokacijo in linearno delo.

AoS, SoA in lokalnost predpomnilnika: AoS (array of structures) shranjuje celotne zapise enega ob drugem, kot v std::vector<Particle>. SoA (structure of arrays) loči polja v posamezne nize, kot v Particles. Elementi std::vector<T> so v pomnilniku zvezni za T, ki ni bool; to ne pomeni, da Particle nima notranje zapolnitve. Pri SoA morajo ustrezajoči si indeksi označevati isti zapis, dolžine nizov pa morajo ostati usklajene.

Prostorska lokalnost pomeni dostop do bližnjih naslovov. Pri branju samo x SoA združi potrebne vrednosti, ne da bi jih prepletal s polji y, zato lahko bolje izkoristi vrstice predpomnilnika. AoS je lahko uporaben pri obdelavi več polj enega zapisa. To so napovedi, odvisne od strojne opreme, prevajalnika in delovne obremenitve, ne jamstva jezika C++. Obe zanki v primeru izvedeta linearno število seštevanj in uporabljata konstanten dodatni prostor.

Pred optimizacijo preverite pravilnost in s profilnikom poiščite draga opravila. Primerjajte reprezentativne podatke, nastavitve optimizacije in ponovljene meritve; alokacijo ter vhod/izhod ločite od merjenega dela in ohranite opazen rezultat. Primer ni merilo zmogljivosti. Ta zapis se nanaša na C++23; zastavica prevajalnika v repozitoriju sama po sebi ne potrjuje produkcijskega okolja. Priložena izvorna koda je razvijajoči se osnutek, ne zamrznjena izdaja C++23.

Primeri

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

Rezultat

6 6

Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.

Viri