Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C++

Performance, complexity, and data locality

Complexity describes how cost grows with input size, not a number of milliseconds. AoS and SoA layouts can have the same complexity while using caches differently. Choosing between them requires measurements for the actual access pattern.

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

Time or space complexity describes how cost grows with input size n. O(n) denotes an asymptotic upper bound with linear growth, not an exact duration. Standard-library complexity requirements are upper bounds. Amortized cost concerns a sequence of operations: appending to std::vector has amortized constant cost, but an individual append can require reallocation and linear work.

AoS, SoA and cache locality: AoS (array of structures) stores complete records next to one another, as in std::vector<Particle>. SoA (structure of arrays) separates fields into individual arrays, as in Particles. Elements of std::vector<T> are contiguous for T other than bool; this does not imply that Particle has no internal padding. In SoA, corresponding indices must identify the same record, and array lengths must be kept consistent.

Spatial locality means accessing nearby addresses. When reading only x, SoA groups the needed values without interleaving y fields, which may use cache lines more effectively. AoS may be useful when processing many fields of one record. These are predictions dependent on hardware, compiler, and workload, not C++ guarantees. Both example loops perform a linear number of additions and use constant auxiliary space.

Before optimizing, check correctness and locate expensive work with a profiler. Compare representative data, optimization settings, and repeated measurements; separate allocation and input/output from the measured work and preserve an observable result. The example is not a benchmark. This entry targets C++23; a repository compiler flag alone does not attest the production runtime. The supplied source is an evolving draft, not a frozen C++23 edition.

Examples

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

Result

6 6

The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.

Sources