Alocação dinâmica de memória e gerenciamento de memória

Em um jogo comum, existem centenas ou talvez milhares de objetos em cena. É completamente correto alocar memória para todos os objetos, incluindo tiros (balas), dinamicamente via padrão new () ?

Devo criar qualquer pool de memória para alocação dinâmica ou não há necessidade de se preocupar com isso? E se a plataforma de destino for um dispositivo móvel?

Há necessidade de um gerenciador de memória em um jogo para celular, por favor? Obrigado.

Idioma usado: C ++; Atualmente desenvolvido no Windows, mas planejado para ser portado mais tarde.

Em um jogo comum, existem centenas ou talvez milhares de objetos na cena. É completamente correto alocar memória para todos os objetos, incluindo tiros (balas), dinamicamente via padrão novo ()?

Isso realmente depende do que você quer dizer com "correto". Se você pegar o termo literalmente (e ignorar qualquer conceito de correção do design implícito), então sim, é perfeitamente aceitável. Seu programa irá compilar e executar bem.

Pode ter um desempenho abaixo do ideal, mas também pode ter um desempenho suficiente para ser um jogo divertido e entregável.

Devo criar qualquer pool de memória para alocação dinâmica ou não há necessidade de se preocupar com isso? E se a plataforma de destino for um dispositivo móvel?

Perfil e veja. No C ++, por exemplo, a alocação dinâmica no heap geralmente é uma operação "lenta" (na medida em que envolve percorrer o heap procurando um bloco de tamanho apropriado). Em C #, geralmente é uma operação extremamente rápida, pois envolve pouco mais que um incremento. Implementações de idiomas diferentes têm características de desempenho diferentes em relação à alocação de memória, fragmentação após o lançamento etc.

A implementação de um sistema de pool de memória certamente pode trazer ganhos de desempenho - e, como os sistemas móveis geralmente têm pouca potência em relação aos sistemas de desktop, você pode obter mais ganhos em uma plataforma móvel específica do que em um desktop. Mas, novamente, você teria que criar um perfil e ver - se, atualmente, seu jogo é lento, mas a alocação / liberação de memória não aparece no criador de perfil como um hot spot, implementando infraestrutura para otimizar a alocação e o acesso à memória, provavelmente vencidos ' Você não tem muito dinheiro para gastar.

Há necessidade de um gerenciador de memória em um jogo para celular, por favor? Obrigado.

Mais uma vez, perfil e veja. Seu jogo está funcionando bem agora? Então você pode não precisar se preocupar.

Todo esse discurso de advertência à parte, o uso de alocação dinâmica para tudo não é estritamente necessário e, portanto, pode ser vantajoso evitá-lo - por causa dos ganhos potenciais de desempenho e por alocar memória que você precisa rastrear e, eventualmente, liberar significa que você precisa acompanhar e eventualmente liberá-lo, possivelmente complicando seu código.

Em particular, no seu exemplo original, você citou "marcadores", que tendem a ser criados e destruídos com freqüência - porque muitos jogos envolvem muitas marcações, e as marchas se movem rapidamente e, assim, atingem o fim de sua vida útil rapidamente (e freqüentemente violentamente!). Portanto, implementar um alocador de pool para eles e objetos como eles (como partículas em um sistema de partículas) geralmente pode resultar em ganhos de eficiência e provavelmente seria o primeiro lugar para começar a usar a alocação de pool.

Não estou claro se você está considerando uma implementação de pool de memória distinta de um "gerenciador de memória" - um pool de memória é um conceito relativamente bem definido, por isso posso dizer com certeza que eles podem ser um benefício se você implementá-los . Um "gerenciador de memória" é um pouco mais vago em termos de sua responsabilidade, então eu teria que dizer que a necessidade ou não de um depende do que você acha que o "gerenciador de memória" faria.

Por exemplo, se você considera um gerenciador de memória algo que apenas intercepta chamadas para new / delete / free / malloc / o que quer que seja e fornece diagnósticos sobre quanta memória você aloca, o que você vaza, etc. - isso pode ser útil ferramenta para o jogo enquanto estiver em desenvolvimento para ajudá-lo a depurar vazamentos e ajustar os tamanhos ideais de pool de memória, etc.

Não tenho muito a acrescentar à excelente resposta de Josh, mas vou comentar sobre isso:

Devo criar qualquer pool de memória para alocação dinâmica ou não há necessidade de se preocupar com isso?

Há um meio termo entre os pools de memória e a chamada newem cada alocação. Por exemplo, você pode alocar um número definido de objetos em uma matriz e definir um sinalizador para "destruí-los" posteriormente. Quando você precisar alocar mais, poderá substituir aqueles com o sinalizador destruído definido. Esse tipo de coisa é apenas um pouco mais complexo de usar do que new / delete (como você teria duas novas funções para esse fim), mas é simples de escrever e pode proporcionar grandes ganhos.

É completamente correto alocar memória para todos os objetos, incluindo tiros (balas), dinamicamente via padrão new ()?

Não, claro que não. Nenhuma alocação de memória está correta para todos os objetos. O operador new () é para alocação dinâmica , ou seja, é apropriado apenas se você precisar que a alocação seja dinâmica, porque o tempo de vida do objeto é dinâmico ou porque o tipo do objeto é dinâmico. Se o tipo e a vida útil do objeto forem conhecidos estaticamente, você deverá alocá-lo estaticamente.

Obviamente, quanto mais informações você tiver sobre seus padrões de alocação, mais rapidamente essas alocações poderão ser feitas por meio de alocadores especializados, como conjuntos de objetos. Porém, essas são otimizações e você deve fazê-las somente se forem necessárias.

Tipo de eco da sugestão de Kylotan, mas eu recomendaria resolver isso no nível da estrutura de dados quando possível, e não no nível mais baixo do alocador, se você puder ajudá-lo.

Aqui está um exemplo simples de como você pode evitar alocar e liberar Foosrepetidamente usando uma matriz com furos com elementos vinculados (resolvendo isso no nível "contêiner" em vez de no nível "alocador"):

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 para esse efeito: uma lista de índice vinculada individualmente com uma lista gratuita. Os links de índice permitem pular os elementos removidos, remover elementos em tempo constante e também recuperar / reutilizar / substituir elementos livres com inserção em tempo constante. Para percorrer a estrutura, faça algo assim:

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

E você pode generalizar o tipo acima de estrutura de dados de "matriz de furos vinculados" usando modelos, posicionando a chamada de dtor novo e manual para evitar o requisito de atribuição de cópia, fazer com que invoque destruidores quando elementos são removidos, forneça um iterador direto etc. optou por manter o exemplo muito parecido com o C para ilustrar mais claramente o conceito e também porque sou muito preguiçoso.

Dito isto, essa estrutura tende a se degradar na localidade espacial depois que você remove e insere muitas coisas de / para o meio. Nesse ponto, os nextlinks podem fazer com que você ande de um lado para o outro ao longo do vetor, recarregando dados anteriormente despejados de uma linha de cache dentro do mesmo percurso seqüencial (isso é inevitável com qualquer estrutura ou alocador de dados que permita a remoção em tempo constante sem embaralhar elementos durante a recuperação) espaços do meio com inserção em tempo constante e sem usar algo como um conjunto de bits paralelo ou um removedsinalizador). Para restaurar a facilidade de cache, você pode implementar um método de cópia e troca 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);

Agora, a nova versão é compatível com cache novamente. Outro método é armazenar uma lista separada de índices na estrutura e classificá-los periodicamente. Outra é usar um conjunto de bits para indicar quais índices são usados. Você sempre terá que percorrer o conjunto de bits em ordem sequencial (para fazer isso de forma eficiente, verifique 64 bits de cada vez, por exemplo, usando FFS / FFZ). O conjunto de bits é o mais eficiente e não invasivo, exigindo apenas um bit paralelo por elemento para indicar quais são usados ​​e quais são removidos em vez de exigir nextíndices de 32 bits , mas o mais demorado para escrever bem (não será necessário). seja rápido na passagem se estiver verificando um bit de cada vez - é necessário que o FFS / FFZ encontre um bit definido ou desmarcado imediatamente entre 32 ou mais bits de cada vez para determinar rapidamente os intervalos de índices ocupados).

Essa solução vinculada geralmente é a mais fácil de implementar e não intrusiva (não requer modificação Foopara armazenar algum removedsinalizador), o que é útil se você deseja generalizar esse contêiner para trabalhar com qualquer tipo de dados, se você não se importa que 32 bits sobrecarga por elemento.

Devo criar qualquer pool de memória para alocação dinâmica ou não há necessidade de se preocupar com isso? E se a plataforma de destino for um dispositivo móvel?

necessidade é uma palavra forte e sou tendenciosa trabalhando em áreas muito críticas de desempenho, como traçado de raios, processamento de imagens, simulações de partículas e processamento de malha, mas é relativamente caro alocar e liberar objetos pequeninos usados ​​para processamento muito leve, como balas e partículas individualmente contra um alocador de memória de tamanho variável e de uso geral. Dado que você deve ser capaz de generalizar a estrutura de dados acima em um dia ou dois para armazenar o que quiser, acho que seria uma troca interessante para eliminar esses custos de alocação / desalocação de heap de serem pagos por cada coisa pequenina. Além de reduzir os custos de alocação / desalocação, você obtém uma melhor localidade de referência atravessando os resultados (menos falhas de cache e falhas de página, por exemplo).

Quanto ao que Josh mencionou sobre o GC, não estudei a implementação de GC do C # tão de perto quanto o Java, mas os alocadores de GC geralmente têm uma alocação inicialisso é muito rápido porque está usando um alocador seqüencial que não pode liberar memória do meio (quase como uma pilha, você não pode excluir coisas do meio). Em seguida, paga pelos custos dispendiosos que permitem remover objetos individuais em um thread separado, copiando a memória e eliminando a memória anteriormente alocada como um todo (como destruir a pilha inteira de uma só vez, enquanto copia os dados para algo mais parecido com uma estrutura vinculada), mas, como é feito em um encadeamento separado, não necessariamente paralisa os encadeamentos do aplicativo. No entanto, isso acarreta um custo oculto muito significativo de um nível adicional de indireção e a perda geral de LOR após um ciclo inicial de GC. É outra estratégia para acelerar a alocação - torne mais barato no segmento de chamada e faça o trabalho caro em outro. Para isso, você precisa de dois níveis de indireção para referenciar seus objetos em vez de um, pois eles acabarão ficando embaralhados na memória entre o tempo que você alocou inicialmente e após o primeiro ciclo.

Outra estratégia semelhante é um pouco mais fácil de aplicar em C ++: não se preocupe em liberar seus objetos em seus threads principais. Basta continuar adicionando e adicionando e adicionando ao final de uma estrutura de dados que não permite remover coisas do meio. No entanto, marque as coisas que precisam ser removidas. Então, um encadeamento separado pode cuidar do trabalho dispendioso de criar uma nova estrutura de dados sem os elementos removidos e depois trocar atomicamente o novo com o antigo, por exemplo, grande parte do custo dos elementos de alocação e liberação pode ser repassado para um thread separado se você puder assumir que a solicitação para remover um elemento não precisa ser satisfeita imediatamente. Isso não apenas torna a liberação mais barata no que diz respeito aos seus tópicos, mas também a alocação, pois você pode usar uma estrutura de dados muito mais simples e mais burra, que nunca precisa lidar com casos de remoção do meio. É como um contêiner que precisa apenas de umpush_backfunção de inserção, uma clearfunção para remover todos os elementos e swaptrocar conteúdo por um novo contêiner compacto, excluindo os elementos removidos; é isso no que diz respeito à mutação.