¿Cómo beneficiarse de la caché de la CPU en un motor de juego de sistema de componentes de entidad?

A menudo leo en el motor del juego ECS las documentaciones que son una buena arquitectura para usar el caché de la CPU con prudencia.

Pero no puedo entender cómo podemos beneficiarnos del caché de la CPU.

Si los componentes se guardan en una matriz (o en un grupo), en memoria contigua, es una buena manera de usar el caché de la CPU PERO solo si leemos los componentes de forma secuencial.

Cuando usamos sistemas, necesitan una lista de entidades que son una lista de entidades que tienen componentes con tipos específicos.

Pero estas listas dan los componentes de forma aleatoria, no secuencialmente.

Entonces, ¿cómo diseñar un ECS para maximizar el golpe de caché?

EDITAR:

Por ejemplo, un sistema Físico necesita una lista de entidades para la entidad que tiene los componentes RigidBody y Transform (hay un grupo para RigidBody y un grupo para componentes Transform).

Entonces su ciclo para actualizar entidades será así:

for (Entity eid in entitiesList) {
    // Get rigid body component
    RigidBody *rigidBody = entityManager.getComponentFromEntity<RigidBody>(eid);

    // Get transform component
    Transform *transform = entityManager.getComponentFromEntity<Transform>(eid);

    // Do something with rigid body and transform component
}

El problema es que el componente RigidBody de la entidad1 puede estar en el índice 2 de su grupo y el componente Transformar de la entidad1 en el índice 0 de su grupo (porque algunas entidades pueden tener algunos componentes y no el otro y por agregar / eliminar entidades / componentes al azar).

Entonces, incluso si los componentes son contiguos en la memoria, se leen al azar y, por lo tanto, tendrá más pérdida de caché, ¿no?

¿A menos que haya una forma de buscar previamente los siguientes componentes en el bucle?

El artículo de Mick West explica el proceso de linealización de los datos de los componentes de la entidad, en su totalidad. Funcionó para la serie Tony Hawk, hace años, en un hardware mucho menos impresionante que el que tenemos hoy, para mejorar en gran medida el rendimiento. Básicamente, utilizó matrices globales preasignadas para cada tipo distinto de datos de entidad (posición, puntaje y demás) y hace referencia a cada matriz en una fase distinta de su update()función en todo el sistema . Puede suponer que los datos para cada entidad estarían en el mismo índice de matriz en cada una de estas matrices globales, por lo que, por ejemplo, si el reproductor se crea primero, podría tener sus datos [0]en cada matriz.

Aún más específico para la optimización de caché, las diapositivas de Christer Ericsson para C y C ++.

Para dar un poco más de detalle, debe intentar utilizar bloques de memoria contiguos (asignados más fácilmente como matrices) por cada tipo de datos (por ejemplo, posición, xy y z), para garantizar una buena localidad de referencia, utilizando cada uno de esos bloques de datos en distintas update()fases por el bien de la localidad temporal, es decir, para garantizar que la memoria caché no se vacíe a través del algoritmo LRU del hardware antes de que haya reutilizado los datos que pretende reutilizar, dentro de una update()llamada determinada . Como ha implicado, lo que no desea hacer es asignar sus entidades y componentes como objetos discretos new, ya que los datos de diferentes tipos en cada instancia de entidad se intercalarán, reduciendo la localidad de referencia.

Si tiene interdependencias entre los componentes (datos) de tal manera que no puede permitirse el lujo de separar algunos datos de sus datos asociados (por ejemplo, Transformar + Física, Transformar + Renderer), entonces puede optar por replicar los datos de Transformar en las matrices de Física y Renderer. , asegurando que todos los datos pertinentes se ajusten al ancho de línea de caché para cada operación crítica de rendimiento.

Recuerde también que la memoria caché L2 y L3 (si puede asumir esto para su plataforma de destino) hacen mucho para aliviar los problemas que puede sufrir la memoria caché L1, como un ancho de línea restrictivo. Entonces, incluso en una falla L1, estas son redes de seguridad que a menudo evitarán llamadas a la memoria principal, que es un orden de magnitud más lento que las llamadas a cualquier nivel de caché.

Nota sobre la escritura de datos La escritura no llama a la memoria principal. De forma predeterminada, los sistemas actuales tienen habilitado el almacenamiento en caché de reescritura: escribir un valor solo lo escribe en la memoria caché (inicialmente), no en la memoria principal, por lo que no se verá afectado por esto. Solo cuando los datos se solicitan desde la memoria principal (no sucederá mientras esté en la memoria caché) y está obsoleto, la memoria principal se actualizará desde la memoria caché.