Contenedores STL velocidad vs. matrices

Acabo de empezar a trabajar en un proyecto científico donde la velocidad realmente importa (HPC). Actualmente estoy diseñando las estructuras de datos. El núcleo del proyecto es una cuadrícula 3D de valores dobles, para resolver una ecuación diferencial parcial.

Dado que la velocidad aquí es probablemente una preocupación mayor que la simplicidad del código, me gustaría saber cómo funciona el STL en comparación con los arreglos de estilo C habituales. En mi caso, dado que es una cuadrícula 3D, estaba pensando en a) un vector unidimensional con indexación lineal b) un vector de 3 vectores o c) una matriz de estilo c unidimensional o d) un estilo c tridimensional formación.

Busqué preguntas más antiguas, pero solo encontré preguntas relacionadas con la construcción / destrucción (lo que no es importante aquí, ya que las estructuras de datos solo se crean una vez al inicio del progtwig; la indexación rápida y los cálculos son importantes) o la comparación de diferentes contenedores STL.

Gracias por la ayuda

Es difícil (o incluso imposible) decir de antemano cuáles serán las actuaciones relativas. Generalmente, en las máquinas modernas, el uso de un vector plano y el cálculo de los índices en él superarán a un vector de vector de vector; En máquinas antiguas, lo contrario era cierto. (En las máquinas modernas, la multiplicación suele ser más barata de lo que se pierde en la página debido a la mala ubicación. En las máquinas más antiguas, la multiplicación era costosa y no había cachés, por lo que la localidad no hacía una diferencia).

Además, dependiendo de la máquina y la implementación de la biblioteca, usar un std::vector para este vector plano puede ser más costoso que usar un simple puntero a la memoria (o puede que no lo sea, no se puede saber de antemano). Primero seguiría por el vector, envolvería todo con cuidado en una clase controladora y, si todavía existían problemas de rendimiento, cambia al puntero.

El diseño de memoria de los arreglos 1D y 3D será el mismo, y similar al diseño de memoria de un std::vector lineal. Tomaría ese enfoque: un vector unidimensional y una función en línea para asignar a la ubicación apropiada.

El vector de vectores, por otro lado, tiene un diseño completamente diferente, ya que los datos en el vector no se almacenan dentro del objeto, sino que se asignan y se referencian dinámicamente. Esto significa que dos filas diferentes en un std::vector> podrían estar en ubicaciones completamente no relacionadas en la memoria.

Un vector hará internamente lo que necesita hacer manualmente para manejar una matriz en bruto de tamaño individual, por lo tanto, siempre que se utilicen correctamente, los vectores deben realizar lo mismo que las matrices sin procesar que realizan la misma tarea.

Por ejemplo, el único vector debe realizar lo mismo que la matriz-c unidimensional, y el vector de los vectores debe realizar aproximadamente el mismo que si se usara una matriz de punteros sin procesar, cada elemento de los cuales apunta a una matriz.

Sin embargo, si la matriz 3D tiene tamaños de dimensión uniformes (es decir, no matrices irregulares), los vectores pagan un costo adicional para administrar individualmente sus tamaños (por ejemplo, tienen que almacenar sus tamaños individualmente). Si se conoce alguno de los tamaños de dimensión en el momento de la comstackción, sería mejor utilizar el contenedor ‘STL’ ‘std :: array , because it won't have that unnecessary overhead. You can even have multi-dimentional , because it won't have that unnecessary overhead. You can even have multi-dimentional std :: arrays`:

 template using Matrix = std::array,Rows>,Planes>; 

Aunque no es estrictamente necesario, debe ser el mismo que T arr[Planes][Rows][Cols]; , pero sin los problemas de c-arrays en bruto.

Un objeto de matriz estática (HPC) asignada dinámicamente (en términos de dimensiones inalterables después de la asignación) es la combinación de una matriz plana y un vector de dope. Básicamente, la idea es asignar una gran parte plana de memoria y luego construir un árbol de punteros en ella. Para matrices 2D, el árbol es solo una simple lista lineal de punteros al principio de cada fila. Para las matrices 3D, el árbol tiene dos niveles y cada uno de los elementos del segundo nivel apunta a una fila desde el sector 2D que corresponde al primer nivel. Colocar el árbol de vector de dopaje al comienzo de la memoria asignada le permite aplicar directamente el operador de indexación [] , por ejemplo, A[i][j][k] , pero se debe tener cuidado como &A[i] no sería El comienzo de la i -ª sección 2D.

Un problema de este enfoque es que el árbol vector de droga podría crecer mucho en tamaño. Por ejemplo, el tamaño de esta estructura de datos para una matriz de 1000x1000x1000 en una máquina de 64 bits es de 1000x1000x8 bytes o casi 8 MiB. Esto podría tomar un espacio de caché precioso para ciertos patrones de acceso a datos.