Asignación dinámica de memoria y gestión de memoria

En un juego promedio, hay cientos o quizás miles de objetos en la escena. ¿Es completamente correcto asignar memoria para todos los objetos, incluidos los disparos (balas), dinámicamente a través de new () predeterminado ?

¿Debo crear un grupo de memoria para la asignación dinámica , o no hay necesidad de molestarse con esto? ¿Qué pasa si la plataforma objetivo son dispositivos móviles?

¿Es necesario un administrador de memoria en un juego móvil, por favor? Gracias.

Lenguaje utilizado: C ++; Actualmente desarrollado bajo Windows, pero planeado ser portado más tarde.

En un juego promedio, hay cientos o quizás miles de objetos en la escena. ¿Es completamente correcto asignar memoria para todos los objetos, incluidos los disparos (balas), dinámicamente a través de new ()?

Eso realmente depende de lo que quieres decir con "correcto". Si toma el término literalmente (e ignora cualquier concepto de corrección del diseño implícito), entonces sí, es perfectamente aceptable. Su programa compilará y funcionará bien.

Puede funcionar de manera subóptima, pero aún puede funcionar lo suficientemente bien como para ser un juego divertido y transportable.

¿Debo crear un grupo de memoria para la asignación dinámica, o no hay necesidad de molestarse con esto? ¿Qué pasa si la plataforma objetivo son dispositivos móviles?

Perfil y ver. En C ++, por ejemplo, la asignación dinámica en el montón suele ser una operación "lenta" (ya que implica caminar por el montón buscando un bloque de tamaño apropiado). En C #, generalmente es una operación extremadamente rápida porque implica poco más que un incremento. Las diferentes implementaciones de lenguaje tienen diferentes características de rendimiento con respecto a la asignación de memoria, fragmentación tras el lanzamiento, etc.

La implementación de un sistema de agrupación de memoria ciertamente puede generar ganancias de rendimiento, y dado que los sistemas móviles generalmente tienen poca potencia en comparación con los sistemas de escritorio, es posible que obtenga más ganancias en una plataforma móvil en particular que en un escritorio. Pero, de nuevo, tendrías que hacer un perfil y ver si, en la actualidad, tu juego es lento pero la asignación / liberación de memoria no aparece en el generador de perfiles como un punto caliente, la implementación de infraestructura para optimizar la asignación de memoria y el acceso probablemente ganó ' No te daré mucho por tu dinero.

¿Es necesario un administrador de memoria en un juego móvil, por favor? Gracias.

Nuevamente, perfila y mira. ¿Tu juego funciona bien ahora? Entonces es posible que no necesite preocuparse.

Dejando a un lado todo ese discurso de advertencia, el uso de la asignación dinámica para todo no es estrictamente necesario, por lo que puede ser ventajoso evitarlo, tanto por las posibles ganancias de rendimiento como por la asignación de memoria que necesita rastrear y eventualmente liberar. significa que tienes que rastrearlo y eventualmente liberarlo, posiblemente complicando tu código.

En particular, en su ejemplo original, citó "balas", que tienden a ser algo que se crea y destruye con frecuencia, porque muchos juegos involucran muchas balas, y las balas se mueven rápido y, por lo tanto, llegan al final de su vida rápidamente (y a menudo ¡violentamente!). Por lo tanto, implementar un asignador de grupo para ellos y objetos como ellos (como partículas en un sistema de partículas) generalmente puede generar ganancias de eficiencia y probablemente sea el primer lugar para comenzar a considerar el uso de la asignación de grupo.

No estoy claro si está considerando que una implementación de grupo de memoria sea distinta de un "administrador de memoria": un grupo de memoria es un concepto relativamente bien definido, por lo que puedo decir con certeza que pueden ser beneficiosos si los implementa . Un "administrador de memoria" es un poco más vago en términos de su responsabilidad, por lo que tendría que decir que si se requiere o no depende de lo que usted piense que haría el "administrador de memoria".

Por ejemplo, si considera que un administrador de memoria es algo que solo intercepta llamadas a new / delete / free / malloc / lo que sea y proporciona diagnósticos sobre la cantidad de memoria que asigna, lo que pierde, etc., eso puede ser útil herramienta para el juego mientras está en desarrollo para ayudarlo a depurar fugas y ajustar los tamaños óptimos de su grupo de memoria, y así sucesivamente.

No tengo mucho que agregar a la excelente respuesta de Josh, pero comentaré sobre esto:

¿Debo crear un grupo de memoria para la asignación dinámica, o no hay necesidad de molestarse con esto?

Hay un punto medio entre los grupos de memoria y la invocación newde cada asignación. Por ejemplo, puede asignar un número establecido de objetos en una matriz, luego establecer una bandera en ellos para 'destruirlos' más tarde. Cuando necesite asignar más, puede sobrescribir las que tengan el conjunto de banderas destruidas. Este tipo de cosas es solo un poco más complejo de usar que new / delete (ya que tendría 2 funciones nuevas para ese propósito), pero es simple de escribir y puede brindarle grandes ganancias.

¿Es completamente correcto asignar memoria para todos los objetos, incluidos los disparos (balas), dinámicamente a través de new ()?

No claro que no. No hay asignación de memoria correcta para todos los objetos. El operador new () es para asignación dinámica , es decir, es apropiado solo si necesita que la asignación sea dinámica, ya sea porque la vida útil del objeto es dinámica o porque el tipo de objeto es dinámico. Si el tipo y la vida útil del objeto se conocen estáticamente, debe asignarlo estáticamente.

Por supuesto, cuanta más información tenga sobre sus patrones de asignación, más rápido se pueden hacer estas asignaciones a través de asignadores especializados, como grupos de objetos. Pero, estas son optimizaciones y solo debe hacerlas si se sabe que son necesarias.

Es una especie de eco de la sugerencia de Kylotan, pero recomendaría resolver esto en el nivel de estructura de datos cuando sea posible, no en el nivel inferior del asignador si puede ayudarlo.

Aquí hay un ejemplo simple de cómo puede evitar asignar y liberar Foosrepetidamente utilizando una matriz con agujeros con elementos unidos (resolviendo esto en un nivel de "contenedor" en lugar de un nivel de "asignador"):

struct FooNode
{
    explicit FooNode(const Foo& ielement): element(ielement), next(-1) {}

    // Stores a 'Foo'.
    Foo element;

    // Points to the next foo available; either the
    // next used foo or the next deleted foo. Can
    // use SoA and hoist this out if Foo doesn't 
    // have 32-bit alignment.
    int next;
};

struct Foos
{
    // Stores all the Foo nodes.
    vector<FooNode> nodes;

    // Points to the first used node.
    int first_node;

    // Points to the first free node.
    int free_node;

    Foos(): first_node(-1), free_node(-1)
    {
    }

    const FooNode& operator[](int n) const
    {
         return data[n];
    }

    void insert(const Foo& element)
    {
         int index = free_node;
         if (index != -1)
         {
              // If there's a free node available,
              // pop it from the free list, overwrite it,
              // and push it to the used list.
              free_node = data[index].next;
              data[index].next = first_node;
              data[index].element = element;
              first_node = index;
         }
         else
         {
              // If there's no free node available, add a 
              // new node and push it to the used list.
              FooNode new_node(element);
              new_node.next = first_node;
              first_node = data.size() - 1;
              data.push_back(new_node);
         }
    }

    void erase(int n)
    {
         // If the node being removed is the first used
         // node, pop it from the used list.
         if (first_node == n)
              first_node = data[n].next;

         // Push the node to the free list.
         data[n].next = free_node;
         free_node = n;
    }
};

Algo en este sentido: una lista de índice individualmente vinculada con una lista libre. Los enlaces de índice le permiten omitir los elementos eliminados, eliminar elementos en tiempo constante y también reclamar / reutilizar / sobrescribir elementos libres con inserción de tiempo constante. Para recorrer la estructura, debes hacer algo como esto:

for (int index = foos.first_node; index != -1; index = foos[index].next)
    // do something with foos[index]

Y puede generalizar el tipo anterior de estructura de datos de "matriz vinculada de agujeros" utilizando plantillas, colocación de invocación de dtor nueva y manual para evitar el requisito de asignación de copia, hacer que invoque destructores cuando se eliminan elementos, proporcionar un iterador directo, etc. I elegí mantener el ejemplo muy parecido a C para ilustrar más claramente el concepto y también porque soy muy vago.

Dicho esto, esta estructura tiende a degradarse en la localidad espacial después de eliminar e insertar muchas cosas desde / hacia el medio. En ese punto, los nextenlaces podrían hacer que camine de un lado a otro a lo largo del vector, recargando datos anteriormente desalojados de una línea de caché dentro del mismo recorrido secuencial (esto es inevitable con cualquier estructura de datos o asignador que permita la eliminación en tiempo constante sin barajar elementos mientras reclama espacios desde el medio con inserción de tiempo constante y sin usar algo como un bitset paralelo o unremoved bandera). Para restaurar la compatibilidad con el caché, puede implementar un copiador y un método de intercambio como este:

Foos(const Foos& other)
{
    for (int index = other.first_node; index != -1; index = other[index].next)
        insert(foos[index].element);
}

void Foos::swap(Foos& other)
{
     nodes.swap(other.nodes):
     std::swap(first_node, other.first_node);
     std::swap(free_node, other.free_node);
}

// ... then just copy and swap:
Foos(foos).swap(foos);

Ahora la nueva versión es compatible con la caché nuevamente para atravesar. Otro método es almacenar una lista separada de índices en la estructura y ordenarlos periódicamente. Otra es usar un conjunto de bits para indicar qué índices se usan. Eso siempre tendrá que atravesar el conjunto de bits en orden secuencial (para hacer esto de manera eficiente, verifique 64 bits a la vez, por ejemplo, usando FFS / FFZ). El conjunto de bits es el más eficiente y no intrusivo, ya que solo requiere un bit paralelo por elemento para indicar cuáles se utilizan y cuáles se eliminan en lugar de requerir 32 bits.next índices de , pero es más lento escribir bien (no Sea rápido para el recorrido si está comprobando un bit a la vez: necesita FFS / FFZ para encontrar un bit establecido o no establecido inmediatamente entre más de 32 bits a la vez para determinar rápidamente los rangos de los índices ocupados).

Esta solución vinculada es generalmente la más fácil de implementar y no intrusiva (no requiere modificación Foopara almacenar algún removedindicador), lo cual es útil si desea generalizar este contenedor para que funcione con cualquier tipo de datos si no le importa ese 32 bits gastos generales por elemento.

¿Debo crear un grupo de memoria para la asignación dinámica, o no hay necesidad de molestarse con esto? ¿Qué pasa si la plataforma objetivo son dispositivos móviles?

necesitar es una palabra fuerte y estoy predispuesto a trabajar en áreas muy críticas para el rendimiento como el trazado de rayos, el procesamiento de imágenes, las simulaciones de partículas y el procesamiento de malla, pero es relativamente muy costoso asignar y liberar objetos pequeños utilizados para el procesamiento muy ligero como balas y partículas individualmente contra un asignador de memoria de tamaño variable de uso general. Dado que debería poder generalizar la estructura de datos anterior en un día o dos para almacenar lo que quiera, creo que sería un intercambio valioso para eliminar tales costos de asignación / desasignación del montón directamente por pagar por cada cosa pequeña. Además de reducir los costos de asignación / desasignación, obtiene una mejor localidad de referencia que atraviesa los resultados (menos errores de caché y fallas de página, es decir).

En cuanto a lo que Josh mencionó sobre GC, no he estudiado la implementación de GC de C # tan de cerca como la de Java, pero los asignadores de GC a menudo tienen una asignación inicialeso es muy rápido porque está usando un asignador secuencial que no puede liberar memoria del medio (casi como una pila, no puede eliminar cosas del medio). Luego paga los costos costosos para permitir realmente eliminar objetos individuales en un hilo separado copiando la memoria y purgando la memoria anteriormente asignada como un todo (como destruir la pila completa de una vez mientras se copian los datos en algo más como una estructura vinculada), pero debido a que se realiza en un hilo separado, no necesariamente detiene tanto los hilos de su aplicación. Sin embargo, eso conlleva un costo oculto muy significativo de un nivel adicional de indirección y la pérdida general de LOR después de un ciclo inicial de GC. Sin embargo, es otra estrategia para acelerar la asignación: hacerlo más barato en el hilo de llamadas y luego hacer el trabajo costoso en otro. Para eso, necesita dos niveles de indirección para hacer referencia a sus objetos en lugar de uno, ya que terminarán siendo barajados en la memoria entre el tiempo asignado inicialmente y después de un primer ciclo.

Otra estrategia en una línea similar que es un poco más fácil de aplicar en C ++ es simplemente no molestarse en liberar sus objetos en sus hilos principales. Simplemente agregue y agregue y agregue al final de una estructura de datos que no permite eliminar cosas del medio. Sin embargo, marque las cosas que deben eliminarse. Luego, un subproceso separado podría encargarse del costoso trabajo de crear una nueva estructura de datos sin los elementos eliminados y luego intercambiar atómicamente el nuevo con el anterior, por ejemplo, gran parte del costo de asignar y liberar elementos se puede transferir a un hilo separado si puede suponer que solicitar eliminar un elemento no tiene que satisfacerse de inmediato. Eso no solo hace que la liberación sea más barata en lo que respecta a sus hilos, sino que también hace que la asignación sea más barata, ya que puede usar una estructura de datos mucho más simple y más tonta que nunca tiene que manejar casos de eliminación desde el medio. Es como un contenedor que solo necesita unpush_backfunción para inserción, una clearfunción para eliminar todos los elementos y swappara intercambiar contenidos con un contenedor nuevo y compacto que excluya los elementos eliminados; eso es todo en cuanto a la mutación.