¿Vale la pena usar grupos de partículas en lenguajes administrados?

10

Iba a implementar un grupo de objetos para mi sistema de partículas en Java, luego encontré esto en Wikipedia. Para reformular, dice que no vale la pena usar agrupaciones de objetos en lenguajes administrados como Java y C #, porque las asignaciones requieren solo decenas de operaciones en comparación con cientos en lenguajes no administrados como C ++.

Pero como todos sabemos, cada instrucción puede afectar el rendimiento del juego. Por ejemplo, un grupo de clientes en un MMO: los clientes no entrarán ni saldrán del grupo demasiado rápido. Pero las partículas pueden renovarse decenas de veces en un segundo.

La pregunta es: ¿vale la pena usar un conjunto de objetos para partículas (específicamente, aquellas que mueren y se recrean rápidamente) en un lenguaje administrado?

Gustavo Maciel
fuente

Respuestas:

14

Sí lo es.

El tiempo de asignación no es el único factor. La asignación puede tener efectos secundarios, como inducir un pase de recolección de basura, que no solo puede afectar negativamente el rendimiento, sino que también puede afectar el rendimiento de manera impredecible. Los detalles de esto dependerán de su idioma y las opciones de plataforma.

La agrupación también generalmente mejora la localidad de referencia para los objetos en la agrupación, por ejemplo, manteniéndolos a todos en matrices contiguas. Esto puede mejorar el rendimiento mientras se itera el contenido del grupo (o al menos la parte activa del mismo) porque el siguiente objeto en la iteración tenderá a estar ya en el caché de datos.

La sabiduría convencional de tratar de evitar cualquier asignación en los bucles de juego más internos aún se aplica incluso en lenguajes administrados (especialmente en, por ejemplo, el 360 cuando se usa XNA). Las razones para esto solo difieren ligeramente.


fuente
+1 Sin embargo, no mencionó si valía la pena al usar estructuras: básicamente no lo es (al agrupar los tipos de valor no se logra nada); en su lugar, debe tener un solo (o posible conjunto de) matriz para administrarlos.
Jonathan Dickinson
2
No toqué el tema de la estructura ya que el OP mencionó el uso de Java y no estoy tan familiarizado con la forma en que operan los tipos / estructuras de valores en ese lenguaje.
No hay estructuras en Java, solo clases (siempre en el montón).
Brendan Long
1

Para Java no es tan útil agrupar objetos * ya que el primer ciclo de GC para los objetos que aún están alrededor los reorganizará en la memoria, sacándolos del espacio "Edén" y posiblemente perdiendo la localidad espacial en el proceso.

  • Siempre es útil en cualquier idioma agrupar recursos complejos que son muy caros de destruir y crear como hilos. Puede valer la pena agruparlos porque el gasto de crearlos y destruirlos no tiene casi nada que ver con la memoria asociada con el identificador de objeto del recurso. Sin embargo, las partículas no se ajustan a esta categoría.

Java ofrece una asignación rápida de ráfagas utilizando un asignador secuencial cuando asigna rápidamente objetos al espacio Eden. Esa estrategia de asignación secuencial es súper rápida, más rápida que mallocen C ya que solo agrupa la memoria ya asignada de manera secuencial directa, pero viene con la desventaja de que no puede liberar fragmentos individuales de memoria. También es un truco útil en C si solo desea asignar cosas súper rápido para, por ejemplo, una estructura de datos donde no necesita eliminar nada, simplemente agregue todo y luego utilícelo y bótelo todo más tarde.

Debido a este inconveniente de no poder liberar objetos individuales, el GC de Java, después de un primer ciclo, copiará toda la memoria asignada desde el espacio de Eden a nuevas regiones de memoria utilizando un asignador de memoria más lento y de uso general que permite que la memoria ser liberado en trozos individuales en un hilo diferente. Entonces puede tirar la memoria asignada en el espacio del Edén en su conjunto sin molestarse con objetos individuales que ahora se han copiado y viven en otro lugar en la memoria. Después de ese primer ciclo de GC, sus objetos pueden terminar fragmentados en la memoria.

Dado que los objetos pueden terminar fragmentados después de ese primer ciclo de GC, los beneficios de la agrupación de objetos cuando se trata principalmente de mejorar los patrones de acceso a la memoria (localidad de referencia) y reducir la sobrecarga de asignación / desasignación se pierden en gran medida ... tanto que obtendrá una mejor localidad de referencia, por lo general, simplemente asignando nuevas partículas todo el tiempo y usándolas mientras aún estén frescas en el espacio del Edén y antes de que se vuelvan "viejas" y potencialmente dispersas en la memoria. Sin embargo, lo que puede ser extremadamente útil (como obtener un rendimiento que rivalice con C en Java) es evitar el uso de objetos para sus partículas y agrupar datos primitivos simples y antiguos. Para un ejemplo simple, en lugar de:

class Particle
{
    public float x;
    public float y;
    public boolean alive;
}

Haz algo como:

class Particles
{
    // X positions of all particles. Resize on demand using
    // 'java.util.Arrays.copyOf'. We do not use an ArrayList
    // since we want to work directly with contiguously arranged
    // primitive types for optimal memory access patterns instead 
    // of objects managed by GC.
    public float x[];

    // Y positions of all particles.
    public float y[];

    // Alive/dead status of all particles.
    public bool alive[];
}

Ahora, para reutilizar la memoria de partículas existentes, puede hacer esto:

class Particles
{
    // X positions of all particles.
    public float x[];

    // Y positions of all particles.
    public float y[];

    // Alive/dead status of all particles.
    public bool alive[];

    // Next free position of all particles.
    public int next_free[];

    // Index to first free particle available to reclaim
    // for insertion. A value of -1 means the list is empty.
    public int first_free;
}

Ahora, cuando la nthpartícula muere, para permitir que se reutilice, empújela a la lista gratuita de esta manera:

alive[n] = false;
next_free[n] = first_free;
first_free = n;

Cuando agregue una nueva partícula, vea si puede resaltar un índice de la lista gratuita:

if (first_free != -1)
{
     int index = first_free;

     // Pop the particle from the free list.
     first_free = next_free[first_free];

     // Overwrite the particle data:
     x[index] = px;
     y[index] = py;
     alive[index] = true;
     next_free[index] = -1;
}
else
{
     // If there are no particles in the free list
     // to overwrite, add new particle data to the arrays,
     // resizing them if needed.
}

No es el código más agradable para trabajar, pero con esto debería poder obtener algunas simulaciones de partículas muy rápidas con el procesamiento secuencial de partículas siempre muy amigable con el caché, ya que todos los datos de partículas siempre se almacenarán contiguamente. Este tipo de representante de SoA también reduce el uso de memoria, ya que no tenemos que preocuparnos por el relleno, los metadatos del objeto para el despacho de reflexión / dinámica, y separa los campos calientes de los campos fríos (por ejemplo, no estamos necesariamente interesados ​​en los datos campos como el color de una partícula durante el paso de la física, por lo que sería un desperdicio cargarlo en una línea de caché solo para no usarlo y desalojarlo).

Para facilitar el trabajo con el código, puede valer la pena escribir sus propios contenedores redimensionables básicos que almacenan conjuntos de flotantes, conjuntos de enteros y conjuntos de booleanos. Nuevamente, no puede usar genéricos y ArrayListaquí (al menos desde la última vez que lo verifiqué) ya que eso requiere objetos administrados por GC, no datos primitivos contiguos. Queremos usar una matriz contigua de int, por ejemplo, matrices no administradas por GC, Integerque no necesariamente serán contiguas después de dejar el espacio de Eden.

Con matrices de tipos primitivos, siempre se garantiza que son contiguas, por lo que obtienes la localidad de referencia extremadamente deseable (para el procesamiento secuencial de partículas hace una gran diferencia) y todos los beneficios que la agrupación de objetos está destinada a proporcionar. Con una matriz de objetos, en cambio es algo análogo a una matriz de punteros que comienzan apuntando a los objetos de manera contigua, suponiendo que los asignó todos a la vez en el espacio del Edén, pero después de un ciclo GC, puede apuntar por todo el colocar en la memoria.


fuente
1
Este es un buen artículo sobre el tema, y ​​después de 5 años de codificación Java puedo verlo claramente; Java GC ciertamente no es tonto, tampoco fue hecho para la programación de juegos (ya que realmente no le importa la ubicación de los datos y esas cosas), por lo que es mejor que juguemos como quiera: P
Gustavo Maciel