Diseño orientado a datos: ¿poco práctico con más de 1-2 miembros de estructura?

El ejemplo habitual de diseño orientado a datos es con la estructura Ball:

struct Ball
{
  float Radius;
  float XYZ[3];
};

y luego hacen un algoritmo que itera un std::vector<Ball>vector.

Luego te dan lo mismo, pero implementado en Diseño orientado a datos:

struct Balls
{
  std::vector<float> Radiuses;
  std::vector<XYZ[3]> XYZs;
};

Lo cual es bueno y todo si va a recorrer primero todos los radios, luego todas las posiciones, etc. Sin embargo, ¿cómo mueves las bolas en el vector? En la versión original, si tiene un std::vector<Ball> BallsAll, puede mover cualquiera BallsAll[x]a cualquiera BallsAll[y].

Sin embargo, para hacer eso para la versión Orientada a datos, debe hacer lo mismo para cada propiedad (2 veces en el caso de Bola - radio y posición). Pero empeora si tienes muchas más propiedades. Tendrás que mantener un índice para cada "bola" y cuando trates de moverla, debes hacer el movimiento en cada vector de propiedades.

¿Eso no mata ningún beneficio de rendimiento del diseño orientado a datos?

Otra respuesta dio una excelente visión general sobre cómo encapsularía muy bien el almacenamiento orientado a filas y ofrecería una mejor vista. Pero como también pregunta sobre el rendimiento, permítame abordar eso: el diseño SoA no es una bala de plata . Es un valor predeterminado bastante bueno (para el uso de caché; no tanto para facilitar la implementación en la mayoría de los idiomas), pero no es todo lo que hay, ni siquiera en el diseño orientado a datos (lo que sea que eso signifique exactamente). Es posible que los autores de algunas introducciones que haya leído hayan perdido ese punto y presenten solo el diseño de SoA porque piensan que ese es el punto principal del DOD. Estarían equivocados, y afortunadamente no todos caen en esa trampa .

Como probablemente ya se haya dado cuenta, no todos los datos primitivos se benefician de ser extraídos en su propia matriz. Un diseño So es una ventaja cuando los componentes que divide en matrices separadas generalmente se acceden por separado. Pero no se accede a cada pieza pequeña de forma aislada, por ejemplo, un vector de posición casi siempre se lee y actualiza al por mayor, por lo que, naturalmente, no se divide ese. De hecho, ¡tu ejemplo tampoco hizo eso! Del mismo modo, si generalmente accedes a todas las propiedades de una Bola juntas, porque pasas la mayor parte del tiempo intercambiando bolas en tu colección de bolas, no tiene sentido separarlas.

Sin embargo, hay un segundo lado del DOD. No obtiene todas las ventajas de la memoria caché y la organización simplemente girando el diseño de su memoria 90 ° y haciendo lo mínimo para corregir los errores de compilación resultantes. Hay otros trucos comunes enseñados bajo este banner. Por ejemplo, "procesamiento basado en la existencia": si con frecuencia desactiva las bolas y las reactiva, no agregue una bandera al objeto de bola y haga que el bucle de actualización ignore las bolas con la bandera establecida en falso. Mueva la bola de una colección "activa" a una colección "inactiva" y haga que el ciclo de actualización solo inspeccione la colección "activa".

Más importante y relevante para su ejemplo: si pasa tanto tiempo barajando el conjunto de bolas, tal vez está haciendo algo mal. ¿Por qué importa el orden? ¿Puedes hacer que no importe? Si es así, obtendría varios beneficios:

• No necesita barajar la colección (el código más rápido es ningún código).
• Puede agregar y eliminar de manera más fácil y eficiente (cambiar al final, soltar último).
• El código restante puede ser elegible para otras optimizaciones (como el cambio de diseño en el que se enfoca).

Entonces, en lugar de arrojar a ciegas SoA a todo, piense en sus datos y cómo los procesa. Si descubre que procesa las posiciones y las velocidades en un bucle, luego revise las mallas y luego actualice los puntos de vida, intente dividir el diseño de su memoria en estas tres partes. Si encuentra que accede a los componentes x, y, z de la posición de forma aislada, tal vez convierta sus vectores de posición en un SoA. Si te encuentras barajando datos más que realmente haciendo algo útil, quizás dejes de barajarlos.

Mentalidad Orientada a Datos

El diseño orientado a datos no significa aplicar SoAs en todas partes. Simplemente significa diseñar arquitecturas con un enfoque predominante en la representación de datos, específicamente con un enfoque en el diseño eficiente de la memoria y el acceso a la memoria.

Eso podría conducir a repeticiones de SoA cuando sea apropiado así:

struct BallSoa
{
   vector<float> x;        // size n
   vector<float> y;        // size n
   vector<float> z;        // size n
   vector<float> r;        // size n
};

... esto a menudo es adecuado para la lógica de bucle vertical que no procesa los componentes y el radio de un vector de centro de esfera simultáneamente (los cuatro campos no están simultáneamente calientes), sino uno a la vez (un bucle a través del radio, otros 3 bucles a través de componentes individuales de centros de esfera).

En otros casos, podría ser más apropiado usar un AoS si los campos se acceden con frecuencia juntos (si su lógica de bucle está iterando a través de todos los campos de bolas en lugar de individualmente) y / o si se necesita acceso aleatorio de una bola:

struct BallAoS
{
    float x;
    float y;
    float z;
    float r;
};
vector<BallAoS> balls;        // size n

... en otros casos, podría ser adecuado utilizar un híbrido que equilibre ambos beneficios:

struct BallAoSoA
{
    float x[8];
    float y[8];
    float z[8];
    float r[8];
};
vector<BallAoSoA> balls;      // size n/8

... incluso puede comprimir el tamaño de una pelota a la mitad usando medias flotantes para ajustar más campos de pelota en una línea / página de caché.

struct BallAoSoA16
{
    Float16 x2[16];
    Float16 y2[16];
    Float16 z2[16];
    Float16 r2[16];
};
vector<BallAoSoA16> balls;    // size n/16

... quizás ni siquiera se accede al radio con tanta frecuencia como al centro de la esfera (quizás su base de código a menudo los trata como puntos y solo raramente como esferas, por ejemplo). En ese caso, puede aplicar una técnica de división de campo caliente / frío adicional.

struct BallAoSoA16Hot
{
    Float16 x2[16];
    Float16 y2[16];
    Float16 z2[16];
};
vector<BallAoSoA16Hot> balls;     // size n/16: hot fields
vector<Float16> ball_radiuses;    // size n: cold fields

La clave para un diseño orientado a datos es considerar todos estos tipos de representaciones temprano en la toma de decisiones de diseño, para no quedar atrapado en una representación subóptima con una interfaz pública detrás.

Pone de relieve los patrones de acceso a la memoria y los diseños que los acompañan, lo que los convierte en una preocupación significativamente más fuerte de lo habitual. En cierto sentido, incluso puede derribar algunas abstracciones. Descubrí que al aplicar esta mentalidad más de lo que ya no miro std::deque, por ejemplo, en términos de sus requisitos algorítmicos, tanto como la representación de bloques contiguos agregados que tiene y cómo funciona el acceso aleatorio a nivel de memoria. De alguna manera, se está enfocando en los detalles de implementación, pero los detalles de implementación que tienden a tener tanto o más impacto en el rendimiento como la complejidad algorítmica que describe la escalabilidad.

Optimización prematura

Gran parte del enfoque predominante del diseño orientado a datos aparecerá, al menos de un vistazo, como peligrosamente cerca de la optimización prematura. La experiencia a menudo nos enseña que tales micro optimizaciones se aplican mejor en retrospectiva y con un perfilador en la mano.

Sin embargo, quizás un mensaje fuerte para tomar del diseño orientado a datos es dejar espacio para tales optimizaciones. Eso es lo que una mentalidad orientada a datos puede ayudar a permitir:

_{El diseño orientado a datos puede dejar espacio para respirar para explorar representaciones más efectivas. No se trata necesariamente de lograr la perfección del diseño de la memoria de una vez, sino más bien de hacer las consideraciones apropiadas de antemano para permitir representaciones cada vez más óptimas.}

Diseño granular orientado a objetos

Muchas discusiones de diseño orientadas a datos se enfrentarán a las nociones clásicas de programación orientada a objetos. Sin embargo, ofrecería una forma de ver esto que no es tan duro como para descartar por completo la POO.

_{La dificultad con el diseño orientado a objetos es que a menudo nos tentará a modelar interfaces a un nivel muy granular, dejándonos atrapados con una mentalidad escalar, uno a la vez, en lugar de una mentalidad masiva paralela.}

Como un ejemplo exagerado, imagine una mentalidad de diseño orientada a objetos aplicada a un solo píxel de una imagen.

class Pixel
{
public:
    // Pixel operations to blend, multiply, add, blur, etc.

private:
    Image* image;          // back pointer to access adjacent pixels
    unsigned char rgba[4];
};

Esperemos que nadie realmente haga esto. Para hacer que el ejemplo sea realmente asqueroso, almacené un puntero posterior a la imagen que contiene el píxel para que pueda acceder a los píxeles vecinos para algoritmos de procesamiento de imágenes como el desenfoque.

El puntero posterior de la imagen agrega inmediatamente una sobrecarga deslumbrante, pero incluso si lo excluimos (haciendo que la interfaz pública de píxeles proporcione operaciones que se aplican a un solo píxel), terminamos con una clase solo para representar un píxel.

Ahora no hay nada de malo con una clase en el sentido indirecto inmediato en un contexto de C ++ además de este puntero de retroceso. Los compiladores optimizadores de C ++ son excelentes para tomar toda la estructura que construimos y eliminarla en pedazos.

La dificultad aquí es que estamos modelando una interfaz encapsulada a un nivel de píxel demasiado granular. Eso nos deja atrapados con este tipo de diseño granular y datos, con potencialmente una gran cantidad de dependencias de clientes que los acoplan a esta Pixelinterfaz.

Solución: elimine la estructura orientada a objetos de un píxel granular y comience a modelar sus interfaces en un nivel más grueso que se ocupa de una gran cantidad de píxeles (en el nivel de imagen).

Al modelar a nivel de imagen masiva, tenemos mucho más espacio para optimizar. Podemos, por ejemplo, representar imágenes grandes como mosaicos combinados de 16x16 píxeles que encajan perfectamente en una línea de caché de 64 bytes, pero permiten un acceso vertical vecino eficiente de píxeles con una zancada típicamente pequeña (si tenemos varios algoritmos de procesamiento de imágenes que necesita acceder a los píxeles vecinos de forma vertical) como un ejemplo orientado a datos hardcore.

Diseñando a un nivel más grueso

El ejemplo anterior de interfaces de modelado a nivel de imagen es un ejemplo obvio ya que el procesamiento de imágenes es un campo muy maduro que se ha estudiado y optimizado hasta la muerte. Sin embargo, menos obvio podría ser una partícula en un emisor de partículas, un sprite frente a una colección de sprites, un borde en un gráfico de bordes, o incluso una persona frente a una colección de personas.

La clave para permitir optimizaciones orientadas a datos (en previsión o en retrospectiva) a menudo se reducirá al diseño de interfaces a un nivel mucho más grueso, a granel. La idea de diseñar interfaces para entidades individuales se reemplaza por el diseño de colecciones de entidades con grandes operaciones que las procesan en masa. Esto apunta especialmente e inmediatamente a los bucles de acceso secuenciales que necesitan acceder a todo y no pueden evitar tener una complejidad lineal.

El diseño orientado a datos a menudo comienza con la idea de fusionar datos para formar datos de modelado de agregados en masa. Una mentalidad similar se hace eco de los diseños de interfaz que la acompañan.

Esta es la lección más valiosa que he tomado del diseño orientado a datos, ya que no soy lo suficientemente experto en arquitectura de computadoras para encontrar el diseño de memoria más óptimo para algo en mi primer intento. Se convierte en algo hacia lo que itero con un perfilador en la mano (y, a veces, con algunas fallas en el camino donde no pude acelerar las cosas). Sin embargo, el aspecto del diseño de interfaz del diseño orientado a datos es lo que me deja espacio para buscar representaciones de datos cada vez más eficientes.

La clave es diseñar interfaces a un nivel más grueso de lo que generalmente estamos tentados a hacer. Esto a menudo también tiene beneficios secundarios, como mitigar la sobrecarga de despacho dinámica asociada con funciones virtuales, llamadas de puntero de función, llamadas dylib y la imposibilidad de que estén en línea. La idea principal de sacar de todo esto es analizar el procesamiento de forma masiva (cuando corresponda).

Lo que ha descrito es un problema de implementación. El diseño OO no se refiere expresamente a las implementaciones.

Puede encapsular su contenedor Ball orientado a columnas detrás de una interfaz que expone una vista orientada a filas o columnas. Puede implementar un objeto Ball con métodos como volumey move, que simplemente modifican los valores respectivos en la estructura subyacente en forma de columna. Al mismo tiempo, su contenedor Ball podría exponer una interfaz para operaciones eficientes en columnas. Con las plantillas / tipos apropiados y un inteligente compilador en línea, puede usar estas abstracciones con un costo de tiempo de ejecución cero.

¿Con qué frecuencia accederá a los datos en columnas en lugar de modificarlos en filas? En los casos de uso típicos para el almacenamiento de columnas, el orden de las filas no tiene ningún efecto. Puede definir una permutación arbitraria de las filas agregando una columna de índice separada. Cambiar el orden solo requeriría intercambiar valores en la columna de índice.

La adición / eliminación eficiente de elementos podría lograrse con otras técnicas:

• Mantenga un mapa de bits de filas eliminadas en lugar de elementos de desplazamiento. Compacte la estructura cuando se vuelva demasiado escasa.
• Agrupe las filas en trozos del tamaño apropiado en una estructura tipo B-Tree para que la inserción o eliminación en posiciones arbitrarias no requiera modificar toda la estructura.

El código del cliente vería una secuencia de objetos Ball, un contenedor mutable de objetos Ball, una secuencia de radios, una matriz Nx3, etc. no tiene que preocuparse por los detalles feos de esas estructuras complejas (pero eficientes). Eso es lo que te compra la abstracción de objetos.

Respuesta corta: tienes toda la razón, y artículos como este no tienen este punto.

La respuesta completa es: el enfoque de "Estructura de matrices" de sus ejemplos puede tener ventajas de rendimiento para algún tipo de operaciones ("operaciones de columna") y "Arreglos de estructuras" para otro tipo de operaciones ("operaciones de fila" ", como las que mencionaste anteriormente). El mismo principio ha influido en las arquitecturas de bases de datos, hay bases de datos orientadas a columnas frente a las bases de datos orientadas a filas clásicas

Entonces, la segunda cosa a considerar para elegir un diseño es qué tipo de operaciones necesita más en su programa, y ​​si se beneficiarán de la diferente disposición de la memoria. Sin embargo, lo primero que debe considerar es si realmente necesita ese rendimiento (creo que en la programación de juegos, de donde proviene el artículo anterior, a menudo tiene este requisito).

La mayoría de los lenguajes OO actuales utilizan un diseño de memoria "Array-Of-Struct" para objetos y clases. Obtener las ventajas de OO (como crear abstracciones para sus datos, encapsulación y más alcance local de funciones básicas), generalmente está vinculado a este tipo de diseño de memoria. Por lo tanto, mientras no haga computación de alto rendimiento, no consideraría SoA como el enfoque principal.