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.