¿Cómo son los sistemas de entidad eficientes en caché?

Últimamente, he estado leyendo mucho sobre sistemas de entidades para implementar en mi motor de juego C ++ / OpenGL. Los dos beneficios clave que escucho constantemente sobre los sistemas de entidades son

1. la fácil construcción de nuevos tipos de entidades, debido a que no tienen que enredarse con complejas jerarquías de herencia, y
2. eficiencia de caché, que estoy teniendo problemas para entender.

La teoría es simple, por supuesto; cada componente se almacena de forma contigua en un bloque de memoria, por lo que el sistema que se preocupa por ese componente puede iterar sobre toda la lista, sin tener que saltar en la memoria y matar el caché. El problema es que realmente no puedo pensar en una situación en la que esto sea realmente práctico.

Primero, veamos cómo se almacenan los componentes y cómo se referencian entre sí. Los sistemas deben poder trabajar con más de un componente, es decir, tanto el sistema de representación como el físico deben acceder al componente de transformación. He visto varias implementaciones posibles que abordan esto, y ninguna de ellas lo hace bien.

Puede hacer que los componentes almacenen punteros a otros componentes, o punteros a entidades que almacenan punteros a componentes. Sin embargo, tan pronto como agregas punteros a la mezcla, ya estás matando la eficiencia del caché. Puede asegurarse de que cada matriz de componentes sea 'n' grande, donde 'n' es el número de entidades activas en el sistema, pero este enfoque desperdicia enormemente memoria; Esto hace que sea muy difícil agregar nuevos tipos de componentes al motor, pero aún desperdicia la eficiencia de la memoria caché, ya que está saltando de una matriz a la siguiente. Podría intercalar su matriz de entidades, en lugar de mantener matrices separadas, pero aún está desperdiciando memoria; por lo que resulta extremadamente costoso agregar nuevos componentes o sistemas, pero ahora con el beneficio adicional de invalidar todos sus niveles anteriores y guardar archivos.

Todo esto supone que las entidades se procesan linealmente en una lista, cada cuadro o marca. En realidad, este no suele ser el caso. Supongamos que usa un renderizador de sector / portal, o un octree, para realizar el sacrificio de oclusión. Es posible que pueda almacenar entidades de forma contigua dentro de un sector / nodo, pero va a saltar, le guste o no. Luego tiene otros sistemas, que podrían preferir entidades almacenadas en otro orden. AI podría estar de acuerdo con almacenar entidades en una lista grande, hasta que comience a trabajar con AI LOD; entonces, querrás dividir esa lista según la distancia al jugador, o alguna otra métrica LOD. La física va a querer usar ese octree. Las secuencias de comandos no les importa, necesitan ejecutarse, pase lo que pase.

Pude ver la división de componentes entre "lógica" (p. Ej., Ai, scripts, etc.) y "mundo" (p. Ej., Representación, física, audio, etc.) y la administración de cada lista por separado, pero estas listas aún tienen que interactuar entre sí. AI no tiene sentido, si no puede afectar el estado de transformación o animación utilizado para la representación de una entidad.

¿Cómo son los sistemas de entidad "eficientes en caché" en un motor de juego del mundo real? ¿Quizás hay un enfoque híbrido que todos usan, pero no hablan, como almacenar entidades en una matriz a nivel mundial y hacer referencia a ellas dentro del octree?

Los dos beneficios clave que escucho constantemente sobre los sistemas de entidades son 1) la fácil construcción de nuevos tipos de entidades debido a que no tienen que enredarse con las jerarquías de herencia complejas, y 2) la eficiencia de la memoria caché.

Tenga en cuenta que (1) es un beneficio del diseño basado en componentes , no solo ES / ECS. Puede usar componentes de muchas maneras que no tienen la parte de "sistemas" y funcionan bien (y muchos juegos independientes y AAA usan tales arquitecturas).

El modelo de objetos estándar de Unity (usando GameObjecty MonoBehaviourobjetos) no es un ECS, sino un diseño basado en componentes. La nueva característica de Unity ECS es un ECS real, por supuesto.

Los sistemas deben poder trabajar con más de un componente, es decir, tanto el sistema de representación como el físico deben acceder al componente de transformación.

Algunos ECS clasifican sus contenedores de componentes por ID de entidad, lo que significa que los componentes correspondientes en cada grupo estarán en el mismo orden.

Esto significa que si usted está linealmente iteración sobre gráficos componente que esté también linealmente interactuando sobre los componentes transformar correspondientes. Es posible que esté omitiendo algunas de las transformaciones (ya que puede tener volúmenes de activación física que no procesa o tal), pero dado que siempre está saltando hacia adelante en la memoria (y no por distancias particularmente grandes, generalmente) todavía va tener ganancias de eficiencia.

Esto es similar a la forma en que la Estructura de matrices (SOA) es el enfoque recomendado para HPC. La CPU y el caché pueden manejar múltiples arreglos lineales casi tan bien como pueden manejar un solo arreglo lineal, y mucho mejor de lo que pueden manejar un acceso aleatorio a la memoria.

Otra estrategia utilizada en algunas implementaciones de ECS, incluido Unity ECS, es asignar componentes en función del arquetipo de su entidad correspondiente. Esto es, todas las entidades con precisión el conjunto de componentes ( PhysicsBody, Transform) serán asignados por separado de las entidades con las diferentes componentes (por ejemplo PhysicsBody, Transform, y Renderable ).

Los sistemas en tales diseños funcionan encontrando primero todos los Arquetipos que coinciden con sus requisitos (que tienen el conjunto requerido de Componentes), iterando esa lista de Arquetipos e iterando los Componentes almacenados dentro de cada Arquetipo coincidente. Esto permite un acceso de componente O (1) completamente lineal y verdadero dentro de un Arquetipo y permite a los Sistemas encontrar Entidades compatibles con una sobrecarga muy baja (buscando una pequeña lista de Arquetipos en lugar de buscar potencialmente cientos de miles de Entidades).

Puede hacer que los componentes almacenen punteros a otros componentes, o punteros a entidades que almacenan punteros a componentes.

Los componentes que hacen referencia a otros componentes en la misma entidad no necesitan almacenar nada. Para hacer referencia a componentes en otras entidades, simplemente almacene el ID de la entidad.

Si se permite que un componente exista más de una vez para una sola entidad y necesita hacer referencia a una instancia en particular, almacene el ID de la otra entidad y un índice de componente para esa entidad. Sin embargo, muchas implementaciones de ECS no permiten este caso, específicamente porque hace que estas operaciones sean menos eficientes.

Puede asegurarse de que cada matriz de componentes sea 'n' grande, donde 'n' es el número de entidades activas en el sistema

Use manejadores (por ejemplo, índices + marcadores de generación) y no punteros y luego puede cambiar el tamaño de las matrices sin temor a romper referencias de objetos.

También puede usar un enfoque de "matriz fragmentada" (una matriz de matrices) similar a muchas std::dequeimplementaciones comunes (aunque sin el tamaño de fragmento lamentablemente pequeño de dichas implementaciones) si desea permitir punteros por alguna razón o si ha medido problemas con rendimiento de cambio de tamaño de matriz.

En segundo lugar, todo esto supone que las entidades se procesan linealmente en una lista cada cuadro / tic, pero en realidad este no suele ser el caso

Depende de la entidad. Sí, para muchos casos de uso, no es cierto. De hecho, esta es la razón por la que enfatizo la diferencia entre el diseño basado en componentes (bueno) y el sistema de entidad (una forma específica de CBD).

Algunos de sus componentes sin duda serán fáciles de procesar linealmente. Incluso en casos de uso normalmente "pesados ​​en árboles", definitivamente hemos visto un aumento en el rendimiento del uso de matrices muy compactas (principalmente en casos que involucran un N de unos cientos como máximo, como agentes de IA en un juego típico).

Algunos desarrolladores también han descubierto que las ventajas de rendimiento del uso de estructuras de datos orientadas linealmente y orientadas a datos superan la ventaja de rendimiento del uso de estructuras basadas en árboles "más inteligentes". Todo depende del juego y los casos de uso específicos, por supuesto.

Supongamos que utiliza un renderizador de sector / portal o un octree para realizar el sacrificio de oclusión. Es posible que pueda almacenar entidades de forma contigua dentro de un sector / nodo, pero va a saltar de un lado a otro, le guste o no.

Te sorprendería lo mucho que la matriz todavía ayuda. Estás saltando en una región de memoria mucho más pequeña que "en cualquier lugar" e incluso con todos los saltos, es mucho más probable que termines en algo en la memoria caché. Con un árbol de cierto tamaño o menos, es posible que pueda precargar todo en la memoria caché y nunca perder un caché en ese árbol.

También hay estructuras de árboles que están construidas para vivir en matrices muy compactas. Por ejemplo, con su octree, puede usar una estructura similar a un montón (padres antes que hijos, hermanos uno al lado del otro) y asegurarse de que incluso cuando "profundice" el árbol siempre esté iterando hacia adelante en la matriz, lo que ayuda la CPU optimiza los accesos de memoria / búsquedas de caché.

Lo cual es un punto importante que hacer. Una CPU x86 es una bestia compleja. La CPU está ejecutando efectivamente un optimizador de microcódigo en su código de máquina, dividiéndolo en microcódigo más pequeño y reordenando instrucciones, prediciendo patrones de acceso a la memoria, etc. Los patrones de acceso a datos importan más de lo que puede ser evidente si todo lo que tiene es una comprensión de alto nivel de cómo funciona la CPU o el caché.

Luego tiene otros sistemas, que podrían preferir entidades almacenadas en otro orden.

Podrías almacenarlos varias veces. Una vez que elimine sus matrices hasta los mínimos detalles mínimos, es posible que realmente ahorre memoria (ya que ha eliminado sus punteros de 64 bits y puede usar índices más pequeños) con este enfoque.

Podría intercalar su matriz de entidades en lugar de mantener matrices separadas, pero aún está desperdiciando memoria

Esto es antitético al buen uso de caché. Si lo único que le importa son las transformaciones y los datos gráficos, ¿por qué hacer que la máquina dedique tiempo a obtener todos esos otros datos para física e inteligencia artificial, entrada y depuración, etc.?

Ese es el punto que generalmente se hace a favor de los objetos de juego ECS vs monolíticos (aunque en realidad no es aplicable cuando se compara con otras arquitecturas basadas en componentes).

Por lo que vale, la mayoría de las implementaciones de ECS de "grado de producción" de las que estoy al tanto usan almacenamiento intercalado. El enfoque de Arquetipo popular que mencioné anteriormente (usado en Unity ECS, por ejemplo) está construido de manera muy explícita para usar almacenamiento intercalado para Componentes asociados con un Arquetipo.

La IA no tiene sentido si no puede afectar el estado de transformación o animación utilizado para la representación de una entidad.

El hecho de que la IA no pueda acceder de manera eficiente a los datos de transformación de forma lineal no significa que ningún otro sistema pueda usar esa optimización de diseño de datos de manera efectiva. Puede usar una matriz empaquetada para transformar datos sin impedir que los sistemas de lógica de juegos hagan las cosas de la manera ad hoc que los sistemas de lógica de juegos suelen hacer.

También estás olvidando el código de caché . Cuando utiliza el enfoque de sistemas de ECS (a diferencia de una arquitectura de componentes más ingenua), está garantizando que está ejecutando el mismo pequeño bucle de código y no saltando de un lado a otro a través de tablas de funciones virtuales a una variedad de Updatefunciones aleatorias esparcidas por todas partes tu binario Entonces, en el caso de AI, realmente desea mantener todos sus diferentes componentes de AI (¡porque ciertamente tiene más de uno para poder componer comportamientos!) En cubos separados y procesar cada lista por separado para obtener el mejor uso de caché de código.

Con una cola de eventos demorada (donde un sistema genera una lista de eventos pero no los envía hasta que el sistema termine de procesar todas las entidades), puede asegurarse de que su caché de código se use bien mientras se mantienen los eventos.

Con un enfoque en el que cada sistema sabe qué colas de eventos leer para el marco, incluso puede hacer que la lectura de eventos sea rápida. O más rápido que sin, al menos.

Recuerde, el rendimiento no es absoluto. No necesita eliminar hasta el último fallo de caché para comenzar a ver los beneficios de rendimiento de un buen diseño orientado a datos.

Todavía hay una investigación activa para hacer que muchos sistemas de juego funcionen mejor con la arquitectura ECS y los patrones de diseño orientados a datos. De manera similar a algunas de las cosas sorprendentes que hemos visto con SIMD en los últimos años (por ejemplo, analizadores JSON), estamos viendo más y más cosas hechas con la arquitectura ECS que no parece intuitiva para las arquitecturas de juegos clásicos, pero ofrece una serie de beneficios (velocidad, subprocesamiento múltiple, capacidad de prueba, etc.).

O tal vez hay un enfoque híbrido que todos usan pero nadie está hablando de

Esto es lo que he defendido en el pasado, especialmente para las personas que son escépticas de la arquitectura ECS: use buenos enfoques orientados a datos para componentes donde el rendimiento es crítico. Utilice una arquitectura más simple donde la simplicidad mejore el tiempo de desarrollo. No calce cada componente en una estricta sobredefinición de componente como propone ECS. Desarrolle su arquitectura de componentes de tal manera que pueda usar fácilmente enfoques similares a ECS donde tengan sentido y usar una estructura de componentes más simple donde el enfoque similar a ECS no tenga sentido (o tenga menos sentido que una estructura de árbol, etc.) .

Personalmente, soy un converso relativamente reciente al verdadero poder de ECS. Aunque para mí, el factor decisivo fue algo que rara vez se menciona sobre ECS: hace que las pruebas de escritura para sistemas de juegos y lógica sean casi triviales en comparación con los diseños basados ​​en componentes cargados de lógica estrechamente acoplados con los que he trabajado en el pasado. Dado que las arquitecturas de ECS ponen toda la lógica en los Sistemas, que solo consumen Componentes y producen actualizaciones de Componentes, construir un conjunto "falso" de Componentes para probar el comportamiento del Sistema es bastante fácil; Debido a que la mayoría de la lógica del juego debe vivir únicamente dentro de los Sistemas, eso significa que probar todos sus Sistemas proporcionará una cobertura de código bastante alta de la lógica de su juego. Los sistemas pueden usar dependencias simuladas (por ejemplo, interfaces GPU) para pruebas con mucha menos complejidad o impacto en el rendimiento que usted '

Como comentario aparte, puede observar que mucha gente habla de ECS sin comprender realmente qué es. Veo que la Unidad clásica se conoce como ECS con una frecuencia deprimente, lo que ilustra que muchos desarrolladores de juegos equiparan "ECS" con "Componentes" e ignoran por completo la parte del "Sistema de entidades". Se ve mucho amor en ECS en Internet cuando una gran parte de las personas realmente defiende el diseño basado en componentes, no el ECS real. En este punto, es casi inútil discutirlo; ECS se ha corrompido de su significado original a un término genérico y bien podría aceptar que "ECS" no significa lo mismo que "ECS orientado a datos". : /