Como se beneficiar do cache da CPU em um mecanismo de jogo do sistema de componentes da entidade?

15

Costumo ler as documentações do mecanismo de jogo do ECS, que são uma boa arquitetura para usar o cache da CPU com sabedoria.

Mas não consigo descobrir como podemos nos beneficiar do cache da CPU.

Se os componentes forem salvos em uma matriz (ou pool), na memória contígua, é uma boa maneira de usar o cache da CPU, MAS apenas se lermos os componentes sequencialmente.

Quando usamos sistemas, eles precisam de uma lista de entidades, que é uma lista de entidades que possuem componentes com tipos específicos.

Mas essas listas fornecem os componentes de maneira aleatória, não sequencial.

Então, como projetar um ECS para maximizar o acerto do cache?

EDIT:

Por exemplo, um sistema Physic precisa de uma lista de entidades para entidades que possuam os componentes RigidBody e Transform (existe um pool para RigidBody e um pool para componentes Transform).

Portanto, seu loop para atualizar entidades será assim:

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
}

O problema é que o componente RigidBody da entidade1 pode estar no índice 2 do seu pool e o componente Tranform da entidade1 no índice 0 do seu pool (porque algumas entidades podem ter alguns componentes e não o outro e devido à adição / exclusão de entidades / componentes aleatoriamente).

Portanto, mesmo que os componentes sejam contíguos na memória, eles são lidos aleatoriamente e, portanto, haverá mais falta de cache, não?

A menos que haja uma maneira de pré-buscar os próximos componentes no loop?

Johnmph
fonte
você pode nos mostrar como está alocando cada componente?
precisa
Com um alocador de pool simples e um gerenciador de Handle para ter referência de componente para gerenciar a realocação de componentes no pool (para manter os componentes contíguos na memória).
Johnmph
Seu loop de exemplo presume que as atualizações de componentes são intercaladas por entidade. Em muitos casos, é possível atualizar componentes em massa por tipo de componente (por exemplo, atualize todos os componentes do corpo rígido primeiro, atualize todas as transformações com os dados finais do corpo rígido e atualize todos os dados de renderização com as novas transformações ...) - isso pode melhorar o cache use para cada atualização de componente. Eu acho que esse tipo de estrutura é o que Nick Wiggill está sugerindo abaixo.
DMGregory
É o meu exemplo que é ruim; na verdade, é mais o sistema "atualizar todas as transformações com os dados do corpo rígido finalizado" do que o sistema Physic. Mas o problema permanece o mesmo: nesses sistemas (atualização transformada com corpo rígido, atualização renderizada com transformação, ...), precisaremos ter mais de um tipo de componente ao mesmo tempo.
Johnmph
Não tem certeza se isso também pode ser relevante? gamasutra.com/view/feature/6345/…
DMGregory

Respostas:

13

O artigo de Mick West explica o processo de linearização completa dos dados dos componentes da entidade. Ele trabalhou para a série Tony Hawk, anos atrás, em um hardware muito menos impressionante do que temos hoje, para melhorar significativamente o desempenho. Ele basicamente usou matrizes globais pré-alocadas para cada tipo distinto de dados da entidade (posição, pontuação e outros enfeites) e faz referência a cada matriz em uma fase distinta de sua update()função em todo o sistema . Você pode supor que os dados de cada entidade estariam no mesmo índice de matriz em cada uma dessas matrizes globais; portanto, se o player for criado primeiro, ele poderá ter seus dados [0]em cada matriz.

Ainda mais específico para a otimização do cache, os slides da Christer Ericsson para C e C ++.

Para dar um pouco mais de detalhes, você deve tentar usar blocos de memória contíguos (mais facilmente alocados como matrizes) para cada tipo de dados (por exemplo, posição, xy e z), para garantir uma boa localidade de referência, utilizando cada um desses blocos de dados em distintos update()fases por uma questão de localidade temporal, ou seja, para garantir que o cache não seja liberado pelo algoritmo LRU do hardware antes de você reutilizar os dados que pretende reutilizar, em uma determinada update()chamada. Como você sugeriu, o que você não quer fazer é alocar suas entidades e componentes como objetos discretos new, pois dados de tipos diferentes em cada instância de entidade serão intercalados, reduzindo a localidade de referência.

Se você tiver interdependências entre componentes (dados), de forma que você absolutamente não pode ter alguns dados separados dos dados associados (por exemplo, Transform + Physics, Transform + Renderer), poderá optar por replicar os dados do Transform nas matrizes Physics e Renderer , assegurando que todos os dados pertinentes se ajustem à largura da linha de cache para cada operação crítica ao desempenho.

Lembre-se também de que o cache L2 e L3 (se você pode assumi-los na sua plataforma de destino) faz muito para aliviar os problemas que o cache L1 pode sofrer, como uma largura de linha restritiva. Portanto, mesmo com uma falha de L1, essas são redes de segurança que geralmente impedem chamadas para a memória principal, que é de magnitude mais lenta que as chamadas para qualquer nível de cache.

Nota sobre a gravação de dados A gravação não chama a memória principal. Por padrão, os sistemas atuais têm o cache de write-back ativado: a gravação de um valor apenas o grava no cache (inicialmente), não na memória principal, para que você não seja prejudicado por isso. Somente quando os dados são solicitados da memória principal (não ocorrerá enquanto estiver no cache) e estiver obsoleto, a memória principal será atualizada do cache.

Engenheiro
fonte
11
Apenas uma observação para quem pode ser novo no C ++: std::vectoré basicamente uma matriz redimensionável dinamicamente e, portanto, também é contígua (de fato nas versões mais antigas do C ++ e de jure nas versões mais recentes do C ++). Algumas implementações de std::dequetambém são "suficientemente contíguas" (embora não sejam da Microsoft).
Sean Middleditch
2
@ Johnmph Simplesmente: se você não tem localidade de referência, você não tem nada. Se dois dados estão intimamente relacionados (como informações espaciais e físicas), ou seja, são processados ​​juntos, é possível que seja necessário compactá-los como um único componente, intercalados. Mas tenha em mente, então, que qualquer outra lógica (digamos, AI) que aproveita esses dados espaciais podem então sofrer como resultado dos dados espaciais não ser incluído ao lado ele . Portanto, depende do que requer mais desempenho (talvez física no seu caso). Isso faz sentido?
Engineer
11
@ Johnmph sim, eu concordo totalmente com Nick, é sobre como eles são armazenados na memória, se você tem entidade com ponteiros para dois componentes que estão distantes na memória, você não tem localidade, eles precisam caber em uma linha de cache.
usar o seguinte
2
@ Johnmph: De fato, o artigo de Mick West assume interdependências mínimas. Então: Minimize dependências; Replicar dados ao longo de linhas de cache onde você não pode minimizar essas dependências ... por exemplo, incluem Transform ao lado de tanto corpo rígido e renderização; e para ajustar as linhas de cache, pode ser necessário reduzir o máximo possível seus átomos de dados ... isso pode ser conseguido, em parte, passando do ponto flutuante para o ponto fixo (4 bytes vs 2 bytes) por valor decimal. Mas, de um jeito ou de outro, não importa como você o faça, seus dados devem ajustar-se à largura da linha de cache, conforme o concept3d observou, para obter o máximo desempenho.
Engineer
2
@Johnmph. Não. Sempre que você escreve dados do Transform, basta gravá-los nas duas matrizes. Não é com essas gravações que você precisa se preocupar. Depois de enviar uma gravação, ela é tão boa quanto feita. São as leituras , posteriormente na atualização, quando você executa o Physics and Renderer, que devem ter acesso a todos os dados pertinentes, imediatamente, em uma única linha de cache, próxima e pessoal da CPU. Além disso, se você realmente precisar de tudo isso junto, faça repetições adicionais ou verifique se a física, a transformação e a renderização se encaixam em uma única linha de cache ... 64 bytes são comuns e, na verdade, são muitos dados! ...
Engenheiro