Qualquer programador se beneficiará da compreensão das várias
estruturas de dados e de como analisar seu desempenho. Mas, na prática, nunca fui útil para
árvores AVL ,
árvores preto-vermelho, árvores de prefixo ,
listas de pulos etc. Uso algumas estruturas de dados para apenas um algoritmo específico e para nada mais (por exemplo,
pilhas para implementar uma
fila de prioridade no
algoritmo de pesquisa de caminho A * ).
No trabalho diário, costumo fazer com surpreendentemente poucas estruturas de dados. Na maioria das vezes, eles são úteis para mim:
- Matrizes de dados compartilhados (dados em massa) - uma maneira de armazenar efetivamente um grande número de objetos.
- Referências fracas (ou identificadores ) - uma maneira de acessar objetos em dados em massa sem falhas no programa se o objeto for excluído.
- Os índices são uma maneira de acessar rapidamente subconjuntos individuais em dados em massa.
- Matrizes de matrizes são uma maneira de armazenar objetos de dados em massa com tamanhos dinâmicos.
Vou dedicar vários artigos a como geralmente implemento todas essas estruturas. Vamos começar com os dados em massa mais simples e úteis.
Dados em massa
Não existe um termo comum para este conceito (ou não o conheço). Eu chamo de "
dados em massa " qualquer coleção grande de objetos semelhantes. Por exemplo, poderia ser:
- Todas as balas no jogo.
- Todas as árvores do jogo.
- Todas as moedas do jogo.
Ou, se você estiver escrevendo código em um nível mais alto de abstração, pode ser:
- Todas as entidades no jogo.
- Todas as malhas do jogo.
- Todos os sons do jogo.
Normalmente, cada sistema (renderização, som, animação, física etc.) em um jogo tem alguns tipos diferentes de objetos que ele precisa rastrear. Por exemplo, para um sistema de som, poderia ser:
- Todos os recursos sonoros que podem ser reproduzidos.
- Todos os sons atualmente sendo reproduzidos.
- Todos os efeitos (atenuação, alterações de tom etc.) aplicados aos sons.
No caso de dados em massa, assumirei o seguinte:
- A ordem de armazenamento dos objetos não é importante. I.e. nós percebemos a matriz como muitos objetos.
- Cada objeto é representado como uma estrutura de dados simples (POD-struct) de tamanho fixo que pode ser movido ou duplicado usando
memcpy() .
Obviamente, você pode criar situações em que a ordem é
importante . Por exemplo, se os objetos denotarem elementos para renderização, antes da renderização, podemos precisar classificá-los da frente para trás para reduzir a quantidade de
redesenho .
No entanto, acredito que, na maioria dos casos, é preferível classificar os dados à
medida que são usados , em vez de armazená-
los em um contêiner classificado, como
árvores preto-vermelho ou
árvores B. Por exemplo, podemos classificar os objetos renderizados da frente para trás antes de passá-los para o renderizador ou classificar os arquivos em ordem alfabética antes de exibi-los na tela como uma lista. A classificação dos dados em cada quadro pode parecer dispendiosa, mas em muitos casos isso é feito em
O (n) usando a
classificação radix .
Como uso apenas estruturas de dados simples, prefiro objetos C ++ a objetos C ++, porque é mais fácil entender o que está acontecendo na memória e avaliar seu desempenho. No entanto, há situações em que você precisa armazenar em massa dados que não possuem um tamanho fixo. por exemplo, o nome ou a lista de objetos filho. Vou falar sobre esses casos em um post separado, onde analisamos "matrizes de matrizes". Por enquanto, vamos supor que todos os objetos sejam estruturas de dados simples e de tamanho fixo.
Por exemplo, aqui está como serão as estruturas de dados em massa do nosso sistema de som hipotético:
typedef struct { resource_t *resource;
Ao considerar maneiras de armazenar dados em massa, precisamos considerar algumas metas:
- Adicionar e remover objetos deve ser rápido.
- Os dados devem estar localizados em um formato conveniente para armazenamento em cache , para que você possa iterar rapidamente para atualizar o sistema.
- Ele deve suportar o mecanismo de link - deve haver uma maneira de transmitir informações sobre objetos específicos em dados em massa. No exemplo acima, o fade deve poder especificar qual som é atenuado. No exemplo, escrevi os links como ponteiros, mas sua implementação depende de como os dados em massa são organizados.
- Os dados devem ser amigáveis ao alocador - devem usar várias alocações de memória grandes e não alocar objetos individuais no heap.
As duas maneiras mais fáceis de representar dados em massa são uma matriz estática ou um vetor C ++:
Trabalhar com uma matriz é extremamente simples e pode funcionar bem se você souber exatamente quantos objetos são necessários no aplicativo. Se você
não sabe disso , desperdice sua memória ou ficará sem objetos.
O vetor
std::vector também é uma solução muito digna e simples, mas aqui você precisa considerar alguns aspectos:
- A implementação padrão do
std::vector do Visual Studio é lenta no modo de depuração devido a iteradores de depuração. Eles devem ser definidos como _ITERATOR_DEBUG_LEVEL = 0 . - Para criar e destruir objetos, o
std::vector usa construtores e destruidores e, em alguns casos, pode ser muito mais lento que o memcpy() . std::vector muito mais difícil de analisar do que implementar um simples "buffer extensível" .
Além disso, sem medidas adicionais, nem matrizes nem vetores regulares suportam referências a objetos individuais. Vamos examinar este tópico, bem como outras decisões importantes de design envolvidas na criação do sistema de dados em massa.
Estratégia de remoção
A primeira decisão importante: o que deve ser feito ao excluir o objeto
a[i] . Aqui estão três opções principais:
- Você pode mudar todos os elementos subsequentes
a[i+1] → a[i] , a[i+2] → a[i+1] etc. para fechar um slot vazio. - Você pode mover o último elemento da matriz para um slot vazio:
a[i] = a[n-1] . - Ou você pode deixar o slot vazio criando um buraco na matriz. Este buraco pode ser usado posteriormente para colocar um novo objeto.
A primeira opção é terrível -
O (n) é gasto no movimento de todos esses elementos. O único benefício do primeiro método é que, se a matriz for classificada, a ordem nela será preservada. Mas, como mencionado acima, o pedido não nos incomoda. Observe que se você usar
a.erase() para remover o elemento
std::vector , é exatamente isso que acontecerá!
A segunda opção é frequentemente chamada de "swap-and-pop". Porque Como se você usar um vetor C ++, essa opção geralmente é implementada substituindo (trocando) o elemento que você deseja excluir pelo último, seguido pela remoção ou popping do último elemento:
std::swap(a[i], a[a.size() - 1]); a.pop_back();
Por que tudo isso é necessário? Em C ++, se
atribuirmos a[i] = a[n-1] , primeiro devemos remover
a[i] chamando seu destruidor e depois chamar o construtor de cópia para criar uma cópia de
a[n-1] na posição
i finalmente, chamamos o destruidor de
a[n-1] ao mudar o vetor. Se o construtor de cópia alocar memória e copiar dados, isso pode ser muito ruim. Se usarmos
std::swap vez de atribuição, podemos fazer apenas com a movimentação dos construtores e não devemos alocar memória.
Novamente, é por isso que C ++ prefiro estruturas de dados simples e operações em C. O C ++ tem muitas armadilhas de desempenho nas quais você pode cair se não souber o que está acontecendo lá dentro. Em C, a operação de troca e apagamento será muito simples:
a.data[i] = a.data[--an];
Ao usar swap e pop, os objetos permanecem compactados. Para colocar um novo objeto, basta anexá-lo ao final da matriz.
Se usarmos a opção “com furos” I, ao colocar um novo objeto, primeiro precisamos verificar se existem “furos” livres que possam ser usados. Vale a pena aumentar o tamanho da matriz somente quando não houver “furos” livres. Caso contrário, no processo de exclusão e criação de objetos, ele crescerá indefinidamente.
Você pode usar um
std::vector<uint32_t> separado
std::vector<uint32_t> para rastrear as posições dos furos, mas há uma solução melhor que não requer memória adicional.
Como os dados do objeto no "furo" não são usados para nada, você pode usá-lo para armazenar um ponteiro para o próximo furo livre. Assim, todos os furos na matriz formam uma
lista simplesmente conectada e, se necessário, podemos adicionar e remover elementos dela.
Esse tipo de estrutura de dados, na qual a memória não utilizada é usada para ligar elementos livres, geralmente é chamada de
lista livre .
Em uma lista vinculada tradicional, um
elemento especial do
cabeçalho da lista aponta para o primeiro nó da lista e o último elemento da lista aponta para NULL, o que significa o fim da lista. Em vez disso, prefiro usar uma
lista vinculada circular , na qual o cabeçalho é apenas um item de lista especial e o último item da lista aponta para um elemento de cabeçalho:
Listas tradicionais e com links para anel.A vantagem dessa abordagem é que o código se torna muito mais simples, reduzindo o número de casos especiais no início e no final da lista.
Observe que se você usar
std::vector para armazenar objetos, os ponteiros para os objetos serão alterados a cada redistribuição do vetor. Isso significa que não podemos usar ponteiros regulares para uma lista vinculada, porque os ponteiros estão constantemente mudando. Para contornar esse problema, você pode usar índices como "ponteiros" para a lista vinculada, pois o índice aponta constantemente para um slot específico, mesmo ao redistribuir a matriz. Falaremos mais sobre realocação na próxima seção.
Você pode alocar espaço para um elemento especial do título da lista, sempre armazenando-o no slot 0 da matriz.
O código será algo como isto:
Qual é a melhor estratégia de remoção? Movendo o último elemento para um slot vazio, garantindo uma compactação apertada da matriz ou mantendo todos os elementos em seus lugares com a criação de “orifícios” na matriz no lugar do elemento excluído?
Ao tomar uma decisão, dois aspectos devem ser levados em consideração:
- A iteração sobre uma matriz densamente compactada é mais rápida, porque ignoramos menos memória e não precisamos gastar muito tempo pulando espaços vazios.
- Se usarmos uma matriz compactada, os elementos se moverão. Isso significa que não podemos usar o índice de um elemento como um identificador constante para referências externas a elementos. Teremos que atribuir um identificador diferente para cada elemento e usar a tabela de pesquisa para corresponder esses IDs constantes aos índices de objetos atuais. Essa tabela de pesquisa pode ser uma tabela de hash ou um
std::vector com orifícios, conforme descrito acima (a segunda opção é mais rápida). Seja como for, precisaremos de memória adicional para esta tabela e uma etapa indireta extra para identificadores.
A escolha da melhor opção depende do seu projeto.
Você pode dizer que armazenar uma matriz densamente compactada é melhor, porque as iterações sobre todos os elementos (para atualizar o sistema) ocorrem com mais frequência do que os links externos correspondentes. Por outro lado, podemos dizer que o desempenho de uma “matriz com furos” é pior apenas no caso de um grande número de furos, e no desenvolvimento de jogos geralmente nos preocupamos com o desempenho nos
piores casos (queremos ter uma taxa de quadros de 60 Hz, mesmo quando as operações máximas são realizadas no jogo) . Na pior das hipóteses, temos o número máximo de objetos reais e, nesse caso,
não haverá furos na matriz. Os furos ocorrem apenas quando o número de objetos diminui, quando excluímos alguns desses objetos.
Também existem estratégias que podem ser usadas para acelerar o processamento de matrizes com muitos furos. Por exemplo, podemos rastrear os comprimentos das seqüências contínuas de furos para pular seqüências inteiras de furos por vez, em vez de elemento por elemento. Como esses dados são necessários apenas para "furos" e não para elementos comuns, você pode armazená-los junto com o ponteiro da lista de liberação na memória não alocada de objetos e não desperdiçar memória extra.
Na minha opinião, se você não precisa otimizar o código para iterações rápidas, provavelmente é melhor usar a opção "array with holes". É mais simples, não requer estruturas de pesquisa adicionais e você pode usar o índice do objeto como seu ID, o que é muito conveniente. Além disso, a falta de objetos em movimento elimina possíveis erros.
Estratégias de remoção de dados em massa.Ponteiros fracos
Como observação, direi que é fácil implementar o suporte a "indicadores fracos" ou "descritores" para objetos de dados em massa.
Um ponteiro fraco é uma referência a um objeto que, de alguma forma, pode determinar que o objeto ao qual se refere foi excluído. O conveniente em indicadores fracos é que eles permitem excluir objetos sem se preocupar com quem pode fazer referência a eles. Sem ponteiros fracos para remover um objeto, precisaríamos procurar cada link individual e declará-lo inválido. Isso pode ser especialmente difícil se os links estiverem armazenados no código de script, em outros computadores na rede etc.
Lembre-se de que já temos um ID que identifica exclusivamente objetos
existentes . Na opção "com furos", esse ID é simplesmente o índice do elemento (porque os elementos nunca se movem). No caso de matrizes densamente compactadas, esse índice de objeto é um registro na
matriz de pesquisa .
O próprio ID não pode ser usado como um ponteiro fraco, porque os IDs podem ser reutilizados. Se um elemento for excluído e um novo elemento for criado no mesmo espaço, não poderemos descobrir isso apenas pelo ID. Para obter um ponteiro fraco, você precisa combinar o ID com o campo de
generation :
typedef struct { uint32_t id; uint32_t generation; } weak_pointer_t;
O campo de
generation é um campo na estrutura do objeto que rastreia quantas vezes o slot na matriz de dados em massa foi reutilizado. (No caso de embalagem apertada, ele controla quantas vezes o slot foi reutilizado na matriz de
pesquisa .)
Quando você exclui um item, aumentamos o número de geração em seu slot. Para verificar se o ponteiro fraco ainda é válido, verificamos se a
generation na estrutura do ponteiro fraco corresponde à geração do slot indicado por seu
id . Se eles corresponderem, o objeto de origem que estamos referenciando ainda existe. Caso contrário, significa que foi excluído e o slot está na lista de liberação ou foi reutilizado.
Lembre-se de que, como o campo de
generation é necessário para os furos e para os objetos existentes, é necessário armazená-lo fora da união:
typedef struct { uint32_t generation; union { object_t; freelist_item_t; }; } item_t;
Estratégia de distribuição
Se você usar
std::vector para armazenar dados do elemento, quando a matriz estiver cheia e precisar ser aumentada, toda a matriz de elementos será redistribuída. Os itens existentes são copiados para a nova matriz.
std::vector cresce
geometricamente . Isso significa que toda vez que um vetor precisa aumentar, o número de elementos distribuídos é multiplicado por algum fator (geralmente por × 2). O crescimento geométrico (exponencial) é importante porque mantém os custos de aumentar a matriz constantes.
Ao redistribuir a matriz, precisamos mover todos os elementos, o que requer
O (n) . No entanto, à medida que a matriz cresce, adicionamos espaço para outros
n elementos, porque dobramos o tamanho. Isso significa que não precisaremos aumentar o array novamente até adicionarmos mais
n elementos a ele. Ou seja, os custos de aumento são iguais a
O (n) , mas apenas os executamos * O (n) * pela enésima vez que escrevemos no array, ou seja, em média, o custo de escrever um elemento é
O (n) / O (n) = O (1)O custo de registrar um item é chamado de
constante amortizada , porque se você calcular a média de todos os registros que estão sendo executados, os custos serão fixos. No entanto, não devemos esquecer que, antes da média, os custos acabam sendo muito espasmódicos. Após todos os registros de
O (n) , obtemos um pico de altura
O (n) :
O custo de escrever para std::vector .Vamos ver também o que acontece se não usarmos crescimento geométrico. Suponha que, em vez de dobrar a memória durante o crescimento, simplesmente adicionaremos mais 128 slots. Mover dados antigos ainda nos custa
O (n) , mas agora precisamos fazê-lo a cada 128 itens adicionados, ou seja, os custos médios agora serão
O (n) / O (128) = O (n) . O custo de escrever um elemento em uma matriz é proporcional ao tamanho da matriz; portanto, quando a matriz se torna grande, ela começa a trabalhar à velocidade da tartaruga. Opa!
A estratégia de distribuição
std::vector é uma boa opção padrão, funcionando bem na maioria dos casos, mas tem alguns problemas:
- Constante amortizada não é adequada para software em tempo real. Se você possui uma matriz muito grande, digamos, centenas de milhões de elementos, o aumento dessa matriz e a movimentação de todos os elementos podem causar um abrandamento perceptível na taxa de quadros. Isso é problemático pelo mesmo motivo que a coleta de lixo é problemática nos jogos. Não importa quão baixos sejam os custos médios, se em alguns quadros os custos puderem subir, causando falhas no jogo.
- Da mesma forma, essa estratégia de alocação no caso de matrizes grandes pode desperdiçar muita memória. Digamos que temos um conjunto de 16 milhões de elementos e precisamos escrever outro. Isso fará com que a matriz cresça para 32 milhões. Agora, temos 16 milhões de elementos na matriz que não estamos usando. Para uma plataforma com pouca memória, isso é muito.
- Por fim, a realocação move objetos na memória, invalidando todos os ponteiros para objetos. Isso pode ser uma fonte de erros difíceis de rastrear.
O código abaixo é um exemplo de bugs que podem ocorrer ao mover objetos:
O problema aqui é que a função
item_2 allocate_slot() pode precisar redistribuir a matriz para criar espaço para o
item_2 . Nesse caso, o
item_1 será movido para a memória e o ponteiro para o
item_1 deixará de ser válido. Nesse caso em particular, podemos eliminar o erro movendo o
item_1 atribuição_1, mas erros semelhantes podem parecer mais imperceptíveis. Pessoalmente, eles me morderam muitas vezes.
Essa situação é perversa pelo fato de que o bug será lançado apenas quando a matriz for redistribuída exatamente no momento em que o
slot_2 . O programa pode funcionar corretamente por um longo tempo até que algo mude o padrão de distribuição, após o qual o bug funcionará.
Todos esses problemas podem ser resolvidos usando uma estratégia de distribuição diferente. Aqui estão algumas das opções:
- : 16, 32, 64, …, . , 16 , 32 , .… ,
std::vector . - , . , . . , O(n)
push() , . - , , , , .
Repito, cada método tem suas próprias vantagens e desvantagens. O último é bom porque os elementos ainda estão armazenados na memória um ao lado do outro, e precisamos rastrear um único buffer, para que vetores ou listas adicionais não sejam necessários. Requer a configuração do tamanho máximo da matriz, mas o espaço dos endereços virtuais é tão grande que você geralmente pode especificar qualquer número enorme sem o menor problema.Se você não pode usar uma solução com memória virtual, qual abordagem seria melhor - tamanho fixo ou blocos com crescimento geométrico? Se a matriz for muito pequena, um tamanho fixo gasta muita memória extra. Por exemplo, se um bloco tiver um tamanho de 16 mil elementos, use todos esses 16 mil elementos, mesmo que haja apenas um elemento na matriz. Por outro lado, com o crescimento geométrico, você estará desperdiçando memória com uma matriz muito grande, porque, em média, o último bloco distribuído estará 50% cheio. Para uma grande variedade, isso pode ter muitos megabytes.Mais uma vez direi que no desenvolvimento de jogos é mais importante otimizar o código para o pior caso, então não estou realmente preocupado em perder memória em matrizes pequenas, se matrizes grandes sempre mostrarem bom desempenho. A quantidade total de memória desperdiçada nunca será superior a * 16 K * n *, em que n é o número de matrizes de dados em massa separadas no projeto e não acho que teremos muitas matrizes diferentes (apenas algumas peças para cada sistema).Blocos de tamanho fixo têm duas outras vantagens. Em primeiro lugar, os cálculos para encontrar um elemento por seu índice são mais simples, é apenas blocks\[i / elements_per_block\][i % elements_per_block]. Em segundo lugar, alocar memória diretamente da memória virtual é muito mais eficiente do que acessar um alocador dinâmico (alocador de heap), devido à falta de fragmentação.Concluindo, quero dizer que, se você usar a opção “with holes” para armazenamento de dados, acho que vale a pena sair da estratégia de distribuição std::vectorpara que os objetos obtenham indicadores constantes que nunca mudam. Provavelmente, uma grande variedade de memória virtual será a melhor solução, mas se você não puder implementá-la, a segunda melhor opção será uma sequência de blocos de tamanho fixo.Observe que, como essa abordagem torna os ponteiros para objetos permanentes, agora, além dos IDs, podemos usar ponteiros para objetos para se referir a objetos. A vantagem disso é que podemos acessar objetos diretamente, sem realizar pesquisas de índice. Por outro lado, um ponteiro precisa de 64 bits de memória e 32 bits geralmente são suficientes para um índice (4 bilhões de objetos são muitos).Estratégias de distribuiçãoMatriz de estruturas e estrutura de matrizes
Outra decisão importante do projeto é escolher entre uma matriz de estruturas (Matriz de estruturas, AoS) e uma estrutura de matriz (Estrutura de matrizes, SoA). A diferença é melhor mostrada pelo exemplo. Suponha que tenhamos um sistema de partículas no qual as partículas tenham vida útil, posição, velocidade e cor: typedef struct { float t; vec3_t pos; vec3_t vel; vec3_t col; } particle_t;
A maneira usual de armazenar seria colocar muitas dessas estruturas em uma matriz. É por isso que chamamos de "conjunto de estruturas". Isto é: uint32_t num_particles; particle_t *particles;
Obviamente, em vez da matriz usual, você pode usar qualquer uma das estratégias acima.Na variante da estrutura da matriz (SoA), usamos uma matriz separada para cada campo da estrutura: uint32_t num_particles; typedef struct { float *t; vec3_t *pos; vec3_t *vel; vec3_t *col; } particles;
De fato, podemos ir ainda mais longe, porque vec3_tem si é uma estrutura: uint32_t num_particles; typedef struct { float *t; float *pos_x; float *pos_y; float *pos_z; float *vel_x; float *vel_y; float *vel_z; float *col_r; float *col_g; float *col_b; } particles;
Isso parece muito mais complicado do que o nosso esquema AoS original, por que é realmente necessário? Existem dois argumentos para apoiar essa abordagem:- Alguns algoritmos funcionam apenas com um subconjunto de campos. Por exemplo, um algoritmo
tick()afeta apenas um campo t. O algoritmo simulate_physics()afeta apenas os campos pose vel. Em um esquema SoA, apenas certas partes de uma estrutura são carregadas na memória. Se estamos limitados pela memória (o que geralmente acontece com os processadores modernos), isso pode ter um grande impacto. Por exemplo, uma função tick()afeta apenas 1/10 da memória, o que significa que ela recebe aceleração 10 vezes. - O esquema SoA permite carregar dados diretamente nos registros SIMD para processamento. Isso pode ter um grande impacto se estivermos limitados às FPUs . Usando o AVX, podemos processar oito números flutuantes por vez, o que fornece uma aceleração de 8 vezes.
Isso significa que, com essas acelerações, ele tick()se tornará 80 mais rápido? Não.
Obteremos a primeira aceleração de 10 vezes apenas se estivermos completamente limitados pela memória e se estivermos completamente limitados pela memória, o SIMD não poderá permitir que trabalhemos mais rapidamente.Desvantagens da abordagem SoA:- O código está ficando mais complicado.
- Mais pressão no distribuidor, porque precisamos distribuir, em vez de um ponto, dez matrizes separadas.
particle_t * , . .- ,
- ( ), . , .
Como um exemplo de que tipo de problemas pode surgir com o cache, lembre-se das partículas de estrutura mostradas acima e imagine que alocamos todas as matrizes usando uma VM (ou seja, elas estão alinhadas nas bordas de uma página de quatro kilobytes). Devido a esse alinhamento, todos os 10 campos de partículas struct serão vinculados a um bloco de cache. Se o cache for associativo múltiplo de 8 canais, isso significa que todos os campos da partícula não podem estar no cache ao mesmo tempo. Opa!Uma maneira de resolver esse problema é agrupar as partículas pelo tamanho do vetor SIMD. Por exemplo, podemos fazer o seguinte: uint32_t num_particles; typedef struct { float t[8]; float position_x[8]; float position_y[8]; float position_z[8]; float velocity_x[8]; float velocity_y[8]; float velocity_z[8]; float color_r[8]; float color_g[8]; float color_b[8]; } eight_particles_t; eight_particles_t *particles;
Nesse esquema, ainda podemos usar as instruções SIMD para processar oito partículas por vez, mas os campos de uma partícula estão bem próximos na memória e não temos problemas com colisões de linhas de cache que apareceram anteriormente. Isso é melhor para um sistema de distribuição, porque estamos de volta a uma distribuição por toda a matriz de partículas.Nesse caso, o algoritmo tick()afetará 32 bytes, ignorará 288 bytes, afetará 32 bytes, etc. Isso significa que não obteremos aceleração total de 10x, como no caso de uma matriz separadat. Em primeiro lugar, as linhas de cache geralmente têm um tamanho de 64 bytes e, como usamos apenas metade, não podemos acelerar mais de 5 vezes. Além disso, os custos associados ao ignorar bytes podem ocorrer, mesmo se processarmos as linhas de cache completas, mas não tenho 100% de certeza sobre isso.Para resolver esse problema, você pode experimentar o tamanho do grupo. Por exemplo, você pode redimensionar um grupo [16]para um campo flutuante que preencha toda a linha de cache. Ou, se você usar um método de alocação de bloco, poderá simplesmente definir qualquer tamanho que caiba no bloco para o tamanho do grupo:AoS e SoA.Quanto à estratégia de exclusão, o SoA não é a melhor opção para a opção "com furos", porque se usarmos o SIMD para processar oito elementos ao mesmo tempo, não seremos capazes de perder furos de maneira alguma (a menos que todos os oito elementos sejam "furos") .Como as instruções do SIMD processam “buracos” da mesma maneira que dados reais, precisamos garantir que os buracos contenham dados “seguros”. Por exemplo, não queremos que as operações de furo causem exceções nas operações de ponto flutuante ou criem números subnormais que reduzem o desempenho. Além disso, não devemos mais manter o ponteironextuma lista de liberação usando union porque as operações do SIMD a substituirão. Em vez disso, use o campo struct.Se usarmos a opção densamente compactada, a exclusão será um pouco mais cara, pois é necessário mover cada campo individualmente e não uma estrutura inteira por vez. Mas como a remoção é muito mais difícil que as atualizações, isso não será um grande problema.Comparando AoS e SoA, posso dizer que, na maioria dos casos, melhorar o desempenho não vale o trabalho de escrever códigos mais pesados. Eu o usaria como formato de armazenamento “padrão” para sistemas AoS e mudaria para SoA para sistemas que exigem velocidades de computação SIMD, como sistemas de recorte e partículas. Nesses casos, para velocidade máxima, eu provavelmente escolheria matrizes densamente compactadas.Vale a pena considerar outra opção - armazenar dados no AoS e gerar dados temporários de SoA para processamento por algum algoritmo. Por exemplo, eu daria uma passada nos dados do AoS e os gravaria em um buffer SoA temporário, processaria esse buffer e, em seguida, escreveria os resultados novamente como AoS (se necessário). Como neste caso eu tenho certeza do algoritmo que processará esses dados, posso otimizar o formato de armazenamento para eles.Lembre-se de que essa abordagem funciona bem com a opção "armazenamento em bloco". Você pode processar um milésimo milésimo de cada vez, convertê-lo em SoA, executar o algoritmo e gravar os resultados novamente. Para armazenar dados temporários, você precisa apenas de um buffer temporário com 16 mil elementos.Conclusão
Qualquer abordagem tem suas vantagens e desvantagens, mas "por padrão" eu recomendo armazenar dados em massa para o novo sistema da seguinte maneira:Uma matriz de estruturas com "orifícios" e ponteiros constantes, distribuídos como um grande volume reservado na VM (se possível) ou como uma matriz de blocos de tamanho fixo (16 mil cada ou em um tamanho ideal para seus dados).
Para casos em que você precisa de cálculos muito rápidos de valores para dados:A estrutura de matrizes de objetos compactados, agrupadas por 8 para processamento SIMD e distribuídas como um grande volume reservado em uma VM ou como uma matriz de blocos de tamanho fixo.
Da próxima vez, consideraremos o tópico de indexação desses dados.