Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C++

Wydajność, złożoność i lokalność danych

Złożoność opisuje wzrost kosztu wraz z rozmiarem danych, a nie liczbę milisekund. Układy AoS i SoA mogą mieć tę samą złożoność, lecz inaczej wykorzystywać pamięć podręczną. Wybór wymaga pomiarów dla rzeczywistego sposobu dostępu.

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

Składnia

#include <vector>

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

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

Złożoność czasowa lub pamięciowa opisuje, jak koszt rośnie wraz z rozmiarem wejścia n. O(n) oznacza asymptotyczne ograniczenie górne o wzroście liniowym, nie dokładny czas. Wymagania złożoności biblioteki standardowej są ograniczeniami górnymi. Koszt zamortyzowany dotyczy sekwencji operacji: dopisywanie do std::vector ma zamortyzowany koszt stały, ale pojedyncze dopisanie może wymagać realokacji i liniowej pracy.

AoS, SoA and cache locality: AoS (array of structures) przechowuje całe rekordy obok siebie, jak std::vector<Particle>. SoA (structure of arrays) rozdziela pola na osobne tablice, jak Particles. Elementy std::vector<T> są ciągłe w pamięci dla T innego niż bool; nie oznacza to braku dopełnienia wewnątrz Particle. W SoA odpowiadające sobie indeksy muszą oznaczać ten sam rekord, a długości tablic trzeba utrzymywać zgodne.

Lokalność przestrzenna oznacza dostęp do pobliskich adresów. Przy odczycie wyłącznie x układ SoA grupuje potrzebne wartości bez przeplatania ich polami y, co może lepiej wykorzystywać linie pamięci podręcznej. AoS może być korzystny przy przetwarzaniu wielu pól jednego rekordu. To przewidywania zależne od sprzętu, kompilatora i obciążenia, a nie gwarancje C++. Obie pętle przykładu wykonują liniową liczbę dodawań i używają stałej dodatkowej pamięci.

Przed optymalizacją sprawdź poprawność i znajdź kosztowne miejsca profilerem. Porównuj reprezentatywne dane, ustawienia optymalizacji i powtarzane pomiary; oddziel alokację oraz wejście/wyjście od mierzonej pracy i zachowaj obserwowalny wynik. Przykład nie jest benchmarkiem. Zakres wpisu to C++23; sam znacznik kompilatora w repozytorium nie potwierdza środowiska produkcyjnego. Podane źródło jest rozwijanym szkicem, nie zamrożonym wydaniem C++23.

Przykłady

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

Wynik

6 6

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła