Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

Performanse, složenost i lokalnost podataka

Složenost opisuje kako trošak raste s veličinom ulaza, a ne broj milisekundi. AoS i SoA mogu imati istu složenost, ali različito koristiti predmemoriju. Odabir zahtijeva mjerenja sa stvarnim obrascem pristupa.

Verzija: 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;

Vremenska ili prostorna složenost opisuje kako trošak raste s veličinom ulaza n. O(n) označava asimptotsku gornju granicu linearnog rasta, a ne točno trajanje. Zahtjevi standardne biblioteke za složenost gornje su granice. Amortizirani trošak odnosi se na niz operacija: dodavanje u std::vector ima amortizirano konstantan trošak, ali pojedino dodavanje može zahtijevati realokaciju i linearan rad.

AoS, SoA i lokalnost predmemorije: AoS (array of structures) pohranjuje cijele zapise jedan do drugoga, kao u std::vector<Particle>. SoA (structure of arrays) razdvaja polja u zasebne nizove, kao u Particles. Elementi std::vector<T> kontinuirani su u memoriji za T različit od bool; to ne znači da Particle nema unutarnje popunjavanje. U SoA-i odgovarajući indeksi moraju označavati isti zapis, a duljine nizova moraju ostati usklađene.

Prostorna lokalnost znači pristup obližnjim adresama. Pri čitanju samo x, SoA grupira potrebne vrijednosti bez ispreplitanja s poljima y, pa može bolje iskoristiti retke predmemorije. AoS može biti koristan pri obradi više polja jednog zapisa. To su predviđanja ovisna o hardveru, prevoditelju i radnom opterećenju, a ne jamstva jezika C++. Obje petlje u primjeru izvode linearan broj zbrajanja i koriste konstantan pomoćni prostor.

Prije optimizacije provjerite ispravnost i profilerom pronađite skupe dijelove. Usporedite reprezentativne podatke, postavke optimizacije i ponovljena mjerenja; odvojite alokaciju i ulaz/izlaz od mjerenog rada te sačuvajte opažljiv rezultat. Primjer nije benchmark. Ovaj se zapis odnosi na C++23; zastavica prevoditelja u repozitoriju sama po sebi ne potvrđuje produkcijsko okruženje. Dostavljeni izvorni kod radni je nacrt koji se razvija, a ne zamrznuto izdanje C++23.

Primjeri

#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

Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.

Izvori