Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / C++

Desempenho, complexidade e localidade dos dados

A complexidade descreve como o custo aumenta com a dimensão dos dados, não um número de milissegundos. AoS e SoA podem ter a mesma complexidade, mas utilizar a cache de formas diferentes. A escolha exige medições com o padrão de acesso real.

Versão: C++23; repository compiler flag, production runtime not attested

Sintaxe

#include <vector>

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

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

A complexidade temporal ou espacial descreve como o custo aumenta com a dimensão da entrada n. O(n) indica um limite superior assintótico de crescimento linear, não uma duração exata. Os requisitos de complexidade da biblioteca padrão são limites superiores. O custo amortizado diz respeito a uma sequência de operações: acrescentar a std::vector tem custo constante amortizado, mas um único acrescento pode exigir realocação e trabalho linear.

AoS, SoA e localidade da cache: AoS (array of structures) guarda registos completos lado a lado, como em std::vector<Particle>. SoA (structure of arrays) separa os campos em arrays individuais, como em Particles. Os elementos de std::vector<T> são contíguos para T diferente de bool; isto não significa que Particle não tenha preenchimento interno. Em SoA, os índices correspondentes têm de identificar o mesmo registo e os comprimentos dos arrays têm de se manter coerentes.

A localidade espacial consiste em aceder a endereços próximos. Ao ler apenas x, SoA agrupa os valores necessários sem intercalar campos y, o que pode aproveitar melhor as linhas da cache. AoS pode ser útil ao processar vários campos de um registo. São previsões dependentes do hardware, do compilador e da carga de trabalho, não garantias de C++. Ambos os ciclos do exemplo fazem um número linear de adições e usam espaço auxiliar constante.

Antes de otimizar, verifica a correção e localiza o trabalho dispendioso com um profiler. Compara dados representativos, definições de otimização e medições repetidas; separa a alocação e a entrada/saída do trabalho medido e mantém um resultado observável. O exemplo não é um benchmark. Esta entrada tem como referência C++23; uma opção do compilador no repositório, por si só, não certifica o ambiente de produção. O código fornecido é um rascunho em evolução, não uma edição C++23 congelada.

Exemplos

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

Resultado

6 6

O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.

Fontes