CKTIS / C++
Rendimiento, complejidad y localidad de datos
La complejidad describe cómo crece el coste con el tamaño de los datos, no un número de milisegundos. AoS y SoA pueden tener la misma complejidad y utilizar la caché de forma diferente. La elección requiere mediciones con el patrón de acceso real.
Versión: C++23; repository compiler flag, production runtime not attested
Sintaxis
#include <vector>
// AoS
struct Particle {
int x, y;
};
std::vector<Particle> aos;
// SoA
struct Particles {
std::vector<int> x, y;
};
Particles soa;La complejidad temporal o espacial describe cómo crece el coste con el tamaño de entrada n. O(n) denota una cota superior asintótica de crecimiento lineal, no una duración exacta. Los requisitos de complejidad de la biblioteca estándar son cotas superiores. El coste amortizado se refiere a una secuencia de operaciones: añadir a std::vector tiene un coste constante amortizado, pero una inserción individual puede requerir realocación y trabajo lineal.
AoS, SoA y localidad de caché: AoS (array of structures) almacena registros completos uno junto a otro, como en std::vector<Particle>. SoA (structure of arrays) separa los campos en arrays individuales, como en Particles. Los elementos de std::vector<T> son contiguos para T distinto de bool; esto no implica que Particle carezca de relleno interno. En SoA, los índices correspondientes deben identificar el mismo registro y las longitudes de los arrays deben mantenerse coherentes.
La localidad espacial consiste en acceder a direcciones cercanas. Al leer solo x, SoA agrupa los valores necesarios sin intercalar campos y, lo que puede aprovechar mejor las líneas de caché. AoS puede ser útil al procesar muchos campos de un registro. Son previsiones que dependen del hardware, el compilador y la carga de trabajo, no garantías de C++. Ambos bucles del ejemplo realizan un número lineal de sumas y usan espacio auxiliar constante.
Antes de optimizar, comprueba la corrección y localiza el trabajo costoso con un perfilador. Compara datos representativos, opciones de optimización y mediciones repetidas; separa la asignación y la entrada/salida del trabajo medido y conserva un resultado observable. El ejemplo no es un benchmark. Esta ficha se refiere a C++23; una opción del compilador en un repositorio no acredita por sí sola el entorno de producción. El código proporcionado es un borrador en evolución, no una edición fija de C++23.
Ejemplos
#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
El código mostrado y el resultado declarado se verificaron en un entorno aislado mediante el método registrado en la evidencia de verificación de esta versión exacta.