Como os sistemas de entidades são eficientes em cache?

Ultimamente, tenho lido muito sobre sistemas de entidades para implementar no meu mecanismo de jogo C ++ / OpenGL. Os dois principais benefícios que ouço constantemente elogiados sobre sistemas de entidades são:

1. a fácil construção de novos tipos de entidades, por não ter que se envolver com hierarquias complexas de herança, e
2. eficiência de cache, que estou tendo problemas para entender.

A teoria é simples, é claro; cada componente é armazenado de forma contígua em um bloco de memória, para que o sistema que se preocupa com esse componente possa iterar a lista inteira, sem precisar pular a memória e eliminar o cache. O problema é que não consigo realmente pensar em uma situação em que isso seja realmente prático.

Primeiro, vamos ver como os componentes são armazenados e como eles se referem. Os sistemas precisam poder trabalhar com mais de um componente, ou seja, o sistema de renderização e a física precisam acessar o componente de transformação. Eu já vi várias implementações possíveis que abordam isso, e nenhuma delas faz isso bem.

Você pode fazer com que os componentes armazenem ponteiros para outros componentes ou ponteiros para entidades que armazenam ponteiros em componentes. No entanto, assim que você coloca ponteiros na mistura, você já está matando a eficiência do cache. Você pode garantir que cada matriz de componentes seja 'n' grande, onde 'n' é o número de entidades ativas no sistema, mas essa abordagem desperdiça terrivelmente memória; isso torna muito difícil adicionar novos tipos de componentes ao mecanismo, mas ainda diminui a eficiência do cache, porque você está pulando de uma matriz para a seguinte. Você pode intercalar sua matriz de entidades, em vez de manter matrizes separadas, mas ainda está desperdiçando memória; tornando proibitivamente caro adicionar novos componentes ou sistemas, mas agora com o benefício adicional de invalidar todos os seus níveis antigos e salvar arquivos.

Isso tudo pressupõe que as entidades sejam processadas linearmente em uma lista, todos os quadros ou marcações. Na realidade, esse não é frequentemente o caso. Digamos que você use um renderizador de setor / portal, ou uma octree, para realizar a seleção da oclusão. Você pode armazenar entidades de forma contígua em um setor / nó, mas você estará pulando, gostando ou não. Então você tem outros sistemas, que podem preferir entidades armazenadas em outra ordem. A IA pode ser boa para armazenar entidades em uma grande lista, até você começar a trabalhar com a AI LOD; então, você deseja dividir essa lista de acordo com a distância do jogador ou com alguma outra métrica do LOD. A física vai querer usar esse octree. Os scripts não se importam, eles precisam executar, não importa o quê.

Eu pude ver a divisão de componentes entre "lógica" (por exemplo, ai, scripts, etc) e "mundo" (por exemplo, renderização, física, áudio, etc.) e gerenciando cada lista separadamente, mas essas listas ainda precisam interagir entre si. A IA não faz sentido, se não puder afetar o estado de transformação ou animação usado para a renderização de uma entidade.

Como os sistemas de entidade são "eficientes em cache" em um mecanismo de jogo do mundo real? Talvez exista uma abordagem híbrida que todos estejam usando, mas não falando, como armazenar entidades em uma matriz globalmente e fazer referência a ela dentro da octree?

Os dois principais benefícios que ouço constantemente elogiados sobre sistemas de entidades são: 1) a fácil construção de novos tipos de entidades, por não ter que se envolver com hierarquias complexas de herança e 2) eficiência do cache.

Observe que (1) é um benefício do design baseado em componentes , não apenas ES / ECS. Você pode usar componentes de várias maneiras que não possuem a parte "sistemas" e eles funcionam muito bem (e muitos jogos independentes e AAA usam essas arquiteturas).

O modelo de objeto padrão do Unity (usando GameObjecte MonoBehaviourobjetos) não é um ECS, mas é um design baseado em componente. O recurso mais recente do Unity ECS é um ECS real, é claro.

Os sistemas precisam ser capazes de trabalhar com mais de um componente, ou seja, o sistema de renderização e a física precisam acessar o componente de transformação.

Alguns ECS classificam seus contêineres de componentes pelo ID da entidade, o que significa que os componentes correspondentes em cada grupo estarão na mesma ordem.

Isso significa que, se você estiver iterando linearmente sobre o componente gráfico, também estará iterando linearmente sobre os componentes de transformação correspondentes. Você pode estar pulando algumas das transformações (já que você pode ter volumes de trigger de física que não são renderizados ou similares), mas como você está sempre avançando na memória (e não por grandes distâncias, em geral), você ainda está indo ter ganhos de eficiência.

Isso é semelhante ao modo como a Estrutura de matrizes (SOA) é a abordagem recomendada para HPC. A CPU e o cache podem lidar com várias matrizes lineares quase tão bem quanto com uma única matriz linear e muito melhor do que com o acesso aleatório à memória.

Outra estratégia usada em algumas implementações do ECS - incluindo o Unity ECS - é alocar componentes com base no arquétipo de sua entidade correspondente. Ou seja, todas as entidades com precisamente o conjunto de componentes ( PhysicsBody, Transform) será alocado separadamente das entidades com diferentes componentes (por exemplo PhysicsBody, Transform, e Renderable ).

Os sistemas em tais projetos funcionam encontrando primeiro todos os arquétipos que atendem aos seus requisitos (que possuem o conjunto necessário de componentes), iterando essa lista de arquétipos e iterando os componentes armazenados em cada arquétipo correspondente. Isso permite acesso totalmente linear e verdadeiro ao componente O (1) dentro de um arquétipo e permite que os sistemas encontrem entidades compatíveis com sobrecarga muito baixa (pesquisando uma pequena lista de arquétipos em vez de pesquisar centenas de milhares de entidades).

Você pode fazer com que os componentes armazenem ponteiros para outros componentes ou ponteiros para entidades que armazenam ponteiros em componentes.

Os componentes que fazem referência a outros componentes na mesma entidade não precisam armazenar nada. Para referenciar componentes em outras entidades, basta armazenar o ID da entidade.

Se um componente puder existir mais de uma vez para uma única entidade e você precisar fazer referência a uma instância específica, armazene o ID da outra entidade e um índice de componente para essa entidade. Muitas implementações do ECS não permitem esse caso, no entanto, especificamente porque torna essas operações menos eficientes.

Você pode garantir que cada matriz de componentes seja 'n' grande, onde 'n' é o número de entidades ativas no sistema

Use alças (por exemplo, índices + marcadores de geração) e não ponteiros e, em seguida, você pode redimensionar as matrizes sem medo de quebrar as referências de objetos.

Você também pode usar uma abordagem de "array em partes" (uma matriz de matrizes) semelhante a muitas std::dequeimplementações comuns (embora sem o tamanho de bloco lamentávelmente pequeno das referidas implementações) se desejar permitir ponteiros por algum motivo ou se tiver medido problemas com matriz redimensionar o desempenho.

Em segundo lugar, tudo isso pressupõe que as entidades são processadas linearmente em uma lista a cada quadro / tick, mas, na realidade, esse não é frequentemente o caso

Depende da entidade. Sim, para muitos casos de uso, isso não é verdade. De fato, é por isso que enfatizo tanto a diferença entre o design baseado em componentes (bom) e o sistema de entidades (uma forma específica de CBD).

Alguns de seus componentes certamente serão fáceis de processar linearmente. Mesmo em casos de uso normalmente "pesados ​​em árvores", vimos definitivamente aumentos de desempenho ao usar matrizes compactadas (principalmente nos casos que envolvem um N de algumas centenas, no máximo, como agentes de IA em um jogo típico).

Alguns desenvolvedores também descobriram que as vantagens de desempenho do uso de estruturas de dados alocadas linearmente orientadas a dados superam a vantagem de desempenho do uso de estruturas baseadas em árvore "mais inteligentes". Tudo depende do jogo e casos de uso específicos, é claro.

Digamos que você use um renderizador de setor / portal ou uma octree para realizar a seleção da oclusão. Você pode armazenar entidades de forma contígua em um setor / nó, mas você estará pulando, gostando ou não.

Você ficaria surpreso com o quanto a matriz ainda ajuda. Você está pulando em uma região muito menor da memória do que em "qualquer lugar" e, mesmo com todo esse salto, ainda é muito mais provável que acabe em algo no cache. Com uma árvore de um determinado tamanho ou menos, você pode até conseguir pré-buscar a coisa toda no cache e nunca ter uma falta de cache nessa árvore.

Também existem estruturas de árvores que são construídas para viver em matrizes compactadas. Por exemplo, com o seu octree, você pode usar uma estrutura semelhante a uma pilha (pais antes dos filhos, irmãos próximos um do outro) e garantir que, mesmo quando você "detalha" a árvore, você está sempre iterando para frente na matriz, o que ajuda a CPU otimiza os acessos à memória / pesquisas em cache.

Qual é um ponto importante a destacar. Uma CPU x86 é uma fera complexa. A CPU está efetivamente executando um otimizador de microcódigo no código da sua máquina, dividindo-o em instruções menores de microcódigo e reordenação, prevendo padrões de acesso à memória, etc. Os padrões de acesso aos dados são mais importantes do que podem ser facilmente aparentes se tudo o que você tem é uma compreensão de alto nível como a CPU ou o cache funcionam.

Então você tem outros sistemas, que podem preferir entidades armazenadas em outra ordem.

Você pode armazená-los várias vezes. Depois de reduzir as matrizes para os mínimos detalhes, é possível que você economize memória (pois removeu os ponteiros de 64 bits e pode usar índices menores) com essa abordagem.

Você pode intercalar sua matriz de entidades em vez de manter matrizes separadas, mas ainda está desperdiçando memória

Isso é antitético ao bom uso do cache. Se tudo o que importa são os dados de transformações e gráficos, por que fazer com que a máquina gaste tempo extraindo todos os outros dados para física e IA, entrada e depuração e assim por diante?

Esse é o argumento geralmente feito em favor de objetos de jogo ECS x monolíticos (embora não seja realmente aplicável quando comparado a outras arquiteturas baseadas em componentes).

Pelo que vale, a maioria das implementações de ECS de "nível de produção", das quais eu sei, usam armazenamento intercalado. A abordagem popular do arquétipo que mencionei anteriormente (usada no Unity ECS, por exemplo) é muito explicitamente criada para usar o armazenamento intercalado dos componentes associados a um arquétipo.

A IA não faz sentido se não puder afetar o estado de transformação ou animação usado para a renderização de uma entidade.

Só porque a IA não pode acessar com eficiência transformar dados linearmente não significa que nenhum outro sistema possa usar essa otimização de layout de dados com eficiência. Você pode usar uma matriz compactada para transformar dados sem impedir que os sistemas lógicos dos jogos façam as coisas da maneira ad hoc que os sistemas lógicos dos jogos geralmente fazem.

Você também está esquecendo o cache de código . Ao usar a abordagem de sistemas do ECS (ao contrário de uma arquitetura de componentes mais ingênua), você garante que está executando o mesmo pequeno loop de código e não pulando pelas tabelas de funções virtuais para uma variedade de Updatefunções aleatórias espalhadas por todo o lado. seu binário. Portanto, no caso da IA, você realmente deseja manter todos os seus diferentes componentes da IA ​​(porque certamente você tem mais de um para poder compor comportamentos!) Em intervalos separados e processa cada lista separadamente para obter o melhor uso do cache de código.

Com uma fila de eventos atrasados ​​(em que um sistema gera uma lista de eventos, mas não os despacha até que o sistema termine de processar todas as entidades), você pode garantir que seu cache de código seja usado bem enquanto mantém os eventos.

Utilizando uma abordagem em que cada sistema sabe em quais filas de eventos ler para o quadro, você pode até tornar os eventos de leitura mais rápidos. Ou mais rápido que sem, pelo menos.

Lembre-se, o desempenho não é absoluto. Você não precisa eliminar todas as últimas falhas de cache para começar a ver os benefícios de desempenho de um bom design orientado a dados.

Ainda há pesquisas ativas para fazer com que muitos sistemas de jogos funcionem melhor com a arquitetura do ECS e os padrões de design orientados a dados. Da mesma forma que algumas das coisas surpreendentes que vimos fazendo com o SIMD nos últimos anos (por exemplo, analisadores JSON), estamos vendo mais e mais coisas feitas com a arquitetura ECS que não parecem intuitivas para as arquiteturas clássicas de jogos, mas oferecem várias benefícios (velocidade, multiencadeamento, testabilidade etc.).

Ou talvez haja uma abordagem híbrida que todo mundo está usando, mas ninguém está falando

Isso é o que eu advoguei no passado, especialmente para as pessoas que são céticas em relação à arquitetura do ECS: use boas abordagens orientadas a dados para componentes nos quais o desempenho é crítico. Use arquitetura mais simples, onde a simplicidade melhora o tempo de desenvolvimento. Não insira cada componente em uma super definição estrita de componente, como propõe o ECS. Desenvolva sua arquitetura de componentes de forma que você possa usar facilmente abordagens semelhantes a ECS, onde elas façam sentido e usar uma estrutura de componentes mais simples, onde abordagens semelhantes a ECS não fazem sentido (ou fazem menos sentido do que uma estrutura em árvore, etc.) .

Pessoalmente, sou um convertido relativamente recente ao verdadeiro poder da ECS. Embora, para mim, o fator decisivo seja algo raramente mencionado no ECS: torna os testes de escrita para sistemas e lógica de jogos quase triviais em comparação com os projetos baseados em componentes carregados de lógica e fortemente acoplados com os quais trabalhei no passado. Como as arquiteturas do ECS colocam toda a lógica em Sistemas, que consomem apenas Componentes e produzem atualizações de Componentes, criar um conjunto "simulado" de Componentes para testar o comportamento do Sistema é bastante fácil; como a maioria das lógicas dos jogos deve viver apenas dentro dos sistemas, isso significa efetivamente que testar todos os seus sistemas fornecerá uma cobertura de código bastante alta da lógica dos jogos. Os sistemas podem usar dependências simuladas (por exemplo, interfaces de GPU) para testes com muito menos complexidade ou impacto no desempenho do que você '

Como um aparte, você pode notar que muitas pessoas falam sobre ECS sem realmente entender o que é. Vejo o Unity clássico chamado ECS com frequência deprimente, ilustrando que muitos desenvolvedores de jogos equiparam "ECS" a "Componentes" e praticamente ignoram completamente a parte "Sistema de entidades". Você vê muito amor no ECS na Internet quando grande parte das pessoas está realmente defendendo o design baseado em componentes, e não o ECS real. Nesse ponto, é quase inútil argumentar; O ECS foi corrompido de seu significado original para um termo genérico e você também pode aceitar que "ECS" não significa a mesma coisa que "ECS orientado a dados". : /