Erros de cache e usabilidade nos sistemas de entidades

Ultimamente, tenho pesquisado e implementado um Sistema de Entidades para minha estrutura. Acho que li a maioria dos artigos, reddits e perguntas sobre o assunto que pude encontrar, e até agora acho que estou entendendo bem a ideia.

No entanto, ele levantou algumas questões sobre o comportamento geral do C ++, a linguagem na qual implemento o sistema de entidades e alguns problemas de usabilidade.

Portanto, uma abordagem seria armazenar diretamente uma matriz de componentes na entidade, o que eu não fiz porque destrói a localidade do cache ao iterar pelos dados. Por isso, decidi ter uma matriz por tipo de componente, para que todos os componentes do mesmo tipo sejam contíguos na memória, o que deve ser a solução ideal para iteração rápida.

Mas, quando eu iterar matrizes de componentes para fazer algo com elas de um sistema em uma implementação de jogo real, percebo que quase sempre estou trabalhando com dois ou mais tipos de componentes de uma só vez. Por exemplo, o sistema de renderização usa o componente Transform e o modelo juntos para realmente fazer uma chamada de renderização. Minha pergunta é: como não estou repetindo linearmente uma matriz contígua por vez nesses casos, estou imediatamente sacrificando os ganhos de desempenho ao alocar componentes dessa maneira? É um problema quando eu itero, em C ++, duas matrizes contíguas diferentes e uso dados de ambos em cada ciclo?

Outra coisa que eu queria perguntar é como se deve manter referências a componentes ou entidades, já que, devido à natureza de como os componentes são armazenados na memória, eles podem facilmente mudar de posição na matriz ou a matriz pode ser realocada para expansão ou expansão. encolhendo, deixando meus ponteiros de componentes ou manipuladores inválidos. Como você recomenda lidar com esses casos, já que muitas vezes me vejo querendo operar em transformações e outros componentes a cada quadro e se minhas alças ou ponteiros são inválidos, é muito complicado fazer pesquisas em todos os quadros.

Primeiro, eu não diria que, neste caso, você está otimizando muito cedo, dependendo do seu caso de uso. De qualquer forma, você fez uma pergunta interessante e, como eu mesmo tenho experiência com isso, vou me aprofundar. Vou tentar explicar como acabei fazendo as coisas e o que encontrei no caminho.

• Cada entidade possui um vetor de identificadores de componentes genéricos que podem representar qualquer tipo.
• Cada identificador de componente pode ser desreferenciado para gerar um ponteiro T * bruto. *Ver abaixo.
• Cada tipo de componente tem seu próprio pool, um bloco contínuo de memória (tamanho fixo no meu caso).

Deve-se observar que não, você não poderá atravessar sempre um pool de componentes e fazer a coisa ideal e limpa. Existem, como você disse, links inevitáveis ​​entre componentes, nos quais você realmente precisa processar as coisas de uma entidade por vez.

No entanto, existem casos (como eu descobri) em que, de fato, você pode literalmente escrever um loop for para um tipo de componente específico e fazer bom uso das linhas de cache da CPU. Para aqueles que desconhecem ou desejam saber mais, dê uma olhada em https://en.wikipedia.org/wiki/Locality_of_reference . Na mesma nota, quando possível, tente manter o tamanho do componente menor ou igual ao tamanho da linha de cache da CPU. O tamanho da minha linha era de 64 bytes, o que acredito ser comum.

No meu caso, valeu a pena fazer o esforço de implementar o sistema. Vi ganhos visíveis de desempenho (perfilados, é claro). Você precisará decidir por si mesmo se é uma boa ideia. Os maiores ganhos de desempenho que vi em mais de 1000 entidades.

Outra coisa que eu queria perguntar é como se deve manter referências a componentes ou entidades, já que, devido à natureza de como os componentes são armazenados na memória, eles podem facilmente mudar de posição na matriz ou a matriz pode ser realocada para expansão ou expansão. encolhendo, deixando meus ponteiros de componentes ou manipuladores inválidos. Como você recomenda lidar com esses casos, já que muitas vezes me vejo querendo operar em transformações e outros componentes a cada quadro e se minhas alças ou ponteiros são inválidos, é muito complicado fazer pesquisas em todos os quadros.

Eu também resolvi esse problema pessoalmente. Acabei tendo um sistema em que:

• Cada identificador de componente mantém uma referência a um índice de pool
• Quando um componente é 'excluído' ou 'removido' de um pool, o último componente dentro desse pool é movido (literalmente com std :: move) para o local agora livre ou nenhum se você acabou de excluir o último componente.
• Quando ocorre uma troca, eu tenho um retorno de chamada que notifica qualquer ouvinte, para que ele possa atualizar qualquer ponteiro concreto (por exemplo, T *).

* Descobri que tentar sempre desreferenciar identificadores de componentes em tempo de execução em determinadas seções do código de alto uso com o número de entidades com as quais eu estava lidando era um problema de desempenho. Por causa disso, agora mantenho alguns ponteiros T brutos em partes críticas de desempenho do meu projeto, mas, caso contrário, uso os identificadores genéricos de componentes, que devem ser usados ​​sempre que possível. Eu os mantenho válidos como mencionado acima, com o sistema de retorno de chamada. Você pode não precisar ir tão longe quanto isso.

Acima de tudo, basta tentar as coisas. Até você ter um cenário do mundo real, qualquer coisa que alguém disser aqui é apenas uma maneira de fazer as coisas, que pode não ser apropriado para você.

Isso ajuda? Vou tentar esclarecer qualquer coisa que não esteja clara. Também são apreciadas quaisquer correções.

Para responder exatamente isso:

Minha pergunta é: como não estou repetindo linearmente uma matriz contígua por vez nesses casos, estou imediatamente sacrificando os ganhos de desempenho ao alocar componentes dessa maneira? É um problema quando eu itero, em C ++, duas matrizes contíguas diferentes e uso dados de ambos em cada ciclo?

Não (pelo menos não necessariamente). O controlador de cache deve, na maioria dos casos, ser capaz de lidar com a leitura de mais de uma matriz contígua com eficiência. A parte importante é tentar, sempre que possível, acessar cada matriz linearmente.

Para demonstrar isso, escrevi uma pequena referência (aplicam-se as ressalvas usuais).

Começando com uma estrutura vetorial simples:

struct float3 { float x, y, z; };

Descobri que um loop que somava cada elemento de duas matrizes separadas e armazenava o resultado em um terceiro era exatamente igual a uma versão em que os dados de origem eram intercalados em uma única matriz e o resultado armazenado em uma terceira. Eu encontrei, no entanto, se intercalasse o resultado com a fonte, o desempenho sofrido (em torno de um fator de 2).

Se eu acessasse os dados aleatoriamente, o desempenho sofreria por um fator entre 10 e 20.

Tempos (10.000.000 de elementos)

acesso linear

• matrizes separadas 0.21s
• fonte intercalada 0,21s
• fonte intercalada e resultado 0,48s

acesso aleatório (descomentar random_shuffle)

• matrizes separadas 2.42s
• fonte intercalada 4.43s
• fonte intercalada e resultado 4.00s

Origem (compilada com o Visual Studio 2013):

#include <Windows.h>
#include <vector>
#include <algorithm>
#include <iostream>

struct float3 { float x, y, z; };

float3 operator+( float3 const &a, float3 const &b )
{
    return float3{ a.x + b.x, a.y + b.y, a.z + b.z };
}

struct Both { float3 a, b; };

struct All { float3 a, b, res; };


// A version without any indirection
void sum( float3 *a, float3 *b, float3 *res, int n )
{
    for( int i = 0; i < n; ++i )
        *res++ = *a++ + *b++;
}

void sum( float3 *a, float3 *b, float3 *res, int *index, int n )
{
    for( int i = 0; i < n; ++i, ++index )
        res[*index] = a[*index] + b[*index];
}

void sum( Both *both, float3 *res, int *index, int n )
{
    for( int i = 0; i < n; ++i, ++index )
        res[*index] = both[*index].a + both[*index].b;
}

void sum( All *all, int *index, int n )
{
    for( int i = 0; i < n; ++i, ++index )
        all[*index].res = all[*index].a + all[*index].b;
}

class PerformanceTimer
{
public:
    PerformanceTimer() { QueryPerformanceCounter( &start ); }
    double time()
    {
        LARGE_INTEGER now, freq;
        QueryPerformanceCounter( &now );
        QueryPerformanceFrequency( &freq );
        return double( now.QuadPart - start.QuadPart ) / double( freq.QuadPart );
    }
private:
    LARGE_INTEGER start;
};

int main( int argc, char* argv[] )
{
    const int count = 10000000;

    std::vector< float3 > a( count, float3{ 1.f, 2.f, 3.f } );
    std::vector< float3 > b( count, float3{ 1.f, 2.f, 3.f } );
    std::vector< float3 > res( count );

    std::vector< All > all( count, All{ { 1.f, 2.f, 3.f }, { 1.f, 2.f, 3.f }, { 1.f, 2.f, 3.f } } );
    std::vector< Both > both( count, Both{ { 1.f, 2.f, 3.f }, { 1.f, 2.f, 3.f } } );

    std::vector< int > index( count );
    int n = 0;
    std::generate( index.begin(), index.end(), [&]{ return n++; } );
    //std::random_shuffle( index.begin(), index.end() );

    PerformanceTimer timer;
    // uncomment version to test
    //sum( &a[0], &b[0], &res[0], &index[0], count );
    //sum( &both[0], &res[0], &index[0], count );
    //sum( &all[0], &index[0], count );
    std::cout << timer.time();
    return 0;
}

Resposta curta: o perfil é otimizado.

Resposta longa:

Mas, quando devo iterar matrizes de componentes para fazer algo com elas de um sistema em uma implementação de jogo real, percebo que quase sempre estou trabalhando com dois ou mais tipos de componentes de uma só vez.

É um problema quando eu itero, em C ++, duas matrizes contíguas diferentes e uso dados de ambos em cada ciclo?

O C ++ não é responsável por falhas de cache, pois se aplica a qualquer linguagem de programação. Isso tem a ver com o modo como a arquitetura moderna da CPU funciona.

Seu problema pode ser um bom exemplo do que pode ser chamado de otimização pré-madura .

Na minha opinião, você otimizou muito cedo para a localidade do cache sem observar os padrões de acesso à memória do programa. Mas a questão maior é: você realmente precisa desse tipo (localidade de referência) de otimização?

O Fog da Agner sugere que você não deve otimizar antes de criar um perfil do seu aplicativo e / ou saber com certeza onde estão os gargalos. (Tudo isso é mencionado em seu excelente guia. Link abaixo)

É útil saber como um cache é organizado se você estiver criando programas com estruturas de big data com acesso não sequencial e desejar impedir a contenção do cache. Você pode pular esta seção se estiver satisfeito com mais diretrizes heurísticas.

Infelizmente, o que você fez foi realmente supor que a alocação de um tipo de componente por matriz oferecerá melhor desempenho, enquanto na realidade você pode ter causado mais falhas no cache ou até contenção no cache.

Você definitivamente deve olhar para o seu excelente guia de otimização de C ++ .

Outra coisa que eu queria perguntar é como manter referências a componentes ou entidades, uma vez que a própria natureza de como os componentes são armazenados na memória.

Pessoalmente, alocarei os componentes mais usados ​​juntos em um único bloco de memória, para que eles tenham endereços "próximos". Por exemplo, uma matriz será assim:

[{ID0 Transform Model PhysicsComp }{ID10 Transform Model PhysicsComp }{ID2 Transform Model PhysicsComp }..] e comece a otimizar a partir daí, se o desempenho não for "bom o suficiente".

Minha pergunta é: como não estou repetindo linearmente uma matriz contígua por vez nesses casos, estou imediatamente sacrificando os ganhos de desempenho ao alocar componentes dessa maneira?

As chances são de que você receba menos erros de cache em geral com matrizes "verticais" separadas por tipo de componente do que intercalando os componentes anexados a uma entidade em um bloco de tamanho variável "horizontal", por assim dizer.

O motivo é que, primeiro, a representação "vertical" tenderá a usar menos memória. Você não precisa se preocupar com o alinhamento de matrizes homogêneas alocadas de forma contígua. Com tipos não homogêneos alocados em um conjunto de memórias, você precisa se preocupar com o alinhamento, pois o primeiro elemento da matriz pode ter um tamanho e requisitos de alinhamento totalmente diferentes do segundo. Como resultado, muitas vezes você precisará adicionar preenchimento, como um exemplo simples:

// Assuming 8-bit chars and 64-bit doubles.
struct Foo
{
    // 1 byte
    char a;

    // 1 byte
    char b;
};

struct Bar
{
    // 8 bytes
    double opacity;

    // 8 bytes
    double radius;
};

Digamos que queremos intercalar Fooe Bararmazená-los um ao lado do outro na memória:

// Assuming 8-bit chars and 64-bit doubles.
struct FooBar
{
    // 1 byte
    char a;

    // 1 byte
    char b;

    // 6 bytes padding for 64-bit alignment of 'opacity'

    // 8 bytes
    double opacity;

    // 8 bytes
    double radius;
};

Agora, em vez de usar 18 bytes para armazenar Foo e Bar em regiões de memória separadas, são necessários 24 bytes para fundi-los. Não importa se você troca o pedido:

// Assuming 8-bit chars and 64-bit doubles.
struct BarFoo
{
    // 8 bytes
    double opacity;

    // 8 bytes
    double radius;

    // 1 byte
    char a;

    // 1 byte
    char b;

    // 6 bytes padding for 64-bit alignment of 'opacity'
};

Se você usar mais memória em um contexto de acesso seqüencial sem melhorar significativamente os padrões de acesso, geralmente ocorrerá mais falhas de cache. Além disso, o passo para passar de uma entidade para a próxima aumenta e para um tamanho variável, fazendo com que você salte de tamanho variável na memória para passar de uma entidade para a próxima apenas para ver quais têm os componentes que você possui. re interessado.

Portanto, é mais provável que o uso de uma representação "vertical", como o armazenamento de tipos de componentes, seja ideal do que as alternativas "horizontais". Dito isto, o problema com falhas de cache na representação vertical pode ser exemplificado aqui:

Onde as setas simplesmente indicam que a entidade "possui" um componente. Podemos ver que, se tentarmos acessar todos os componentes de movimento e renderização de entidades que possuem ambos, acabamos pulando por toda parte na memória. Esse tipo de padrão de acesso esporádico pode fazer com que você carregue dados em uma linha de cache para acessar, digamos, um componente de movimento, acesse mais componentes e tenha esses dados antigos despejados, apenas para carregar novamente a mesma região de memória que já foi despejada para outro movimento componente. Portanto, pode ser um desperdício carregar exatamente as mesmas regiões de memória mais de uma vez em uma linha de cache apenas para percorrer e acessar uma lista de componentes.

Vamos limpar um pouco essa bagunça para que possamos ver mais claramente:

Observe que, se você encontrar esse tipo de cenário, geralmente leva muito tempo depois que o jogo começou a rodar, depois que muitos componentes e entidades foram adicionados e removidos. Em geral, quando o jogo começa, você pode adicionar todas as entidades e componentes relevantes, e nesse ponto eles podem ter um padrão de acesso seqüencial muito ordenado e com boa localidade espacial. Depois de muitas remoções e inserções, você pode acabar tendo algo como a bagunça acima.

Uma maneira muito fácil de melhorar essa situação é simplesmente ordenar rapidamente seus componentes com base no ID / índice da entidade que os possui. Nesse ponto, você obtém algo como isto:

E esse é um padrão de acesso muito mais amigável ao cache. Não é perfeito, pois podemos ver que precisamos pular alguns componentes de renderização e movimento aqui e ali, já que nosso sistema está interessado apenas em entidades que possuem os dois , e algumas entidades têm apenas um componente de movimento e outras apenas um componente de renderização , mas você pelo menos acaba processando alguns componentes contíguos (mais na prática, normalmente, pois muitas vezes você anexa componentes de interesse relevantes, como talvez mais entidades em seu sistema que tenham um componente de movimento tenham um componente de renderização do que não).

Mais importante, depois de classificá-las, você não carregará dados de uma região de memória em uma linha de cache apenas para recarregá-los em um único loop.

E isso não requer um design extremamente complexo, apenas uma passagem de classificação de tempo linear de vez em quando, talvez depois de inserir e remover um monte de componentes para um tipo de componente específico; nesse momento, você pode marcá-lo como precisando ser classificado. Uma classificação de raiz razoavelmente implementada (você pode até paralelizar, o que eu faço) pode classificar um milhão de elementos em cerca de 6ms no meu quad-core i7, como exemplificado aqui:

Sorting 1000000 elements 32 times...
mt_sort_int: {0.203000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
mt_sort: {1.248000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
mt_radix_sort: {0.202000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
std::sort: {1.810000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
qsort: {2.777000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]

A descrição acima é para classificar um milhão de elementos 32 vezes (incluindo o tempo para os memcpyresultados antes e depois da classificação). E eu suponho que na maioria das vezes você não terá mais de um milhão de componentes para classificar, portanto, você poderá facilmente esgueirar-se agora e ali, sem causar interrupções visíveis na taxa de quadros.