Início / coding / Perguntas / 79215951
Accepted
SinixND
Asked: 2024-11-23 01:11:18 +0800 CST

Design orientado a dados - preparando dados para iteração amigável ao cache vs acesso direto

  • 772

nas palestras de Mike Actons aqui e aqui (os links têm carimbos de data/hora), bem como nesta postagem do blog, eles preparam/pré-condicionam/pré-buscam/consultam dados não contíguos necessários primeiro para depois iterá-los/fazer cálculos de uma forma amigável ao cache.

Aqui está o código da postagem do blog:

// objects_store.h

struct ObjectsStore
{
    vector<Vector3D> m_Positions;
    vector<Quaternion> m_Orientations;
};

// Runtime solution:

struct TranslationData
{
    Vector3D m_ObjPosition;
    const Quaternion m_ObjOrientation;
    const Vector3D m_ObjTranslation;
};

void PrepareTranslations(const ObjectsStore& inStore,
                         const vector<Vector3D>& inTranslations,
                         vector<TranslationData>& outObjectsToTranslate)
{
    assert(inStore.m_Positions.size() == inStore.m_Orientations.size());
    assert(inStore.m_Positions.size() == inTranslations.size());
    for (size_t i = 0; i < inTranslations.size(); ++i)
    {
        outObjectsToTranslate.push_back
        ({ 
             inStore.m_Positions[i];
             inStore.m_Orientations[i];
             inTranslations[i];
        });
    }
}

void TranslateObject(vector<TranslationData>& ioObjectsToTranslate)
{
    for (TranslationData& data: ioObjectsToTranslate)
        data.m_ObjPosition += data.m_ObjOrientation * data.m_ObjTranslation;
}

void ApplyTranslation(const vector<TranslationData>& inTranslationData
                      ObjectsStore& outStore)
{
    assert(inStore.m_Positions.size() == inTranslationData.size());
    for (size_t i = 0; i < inTranslationData.size(); ++i)
        outStore.m_Positions[i] = inTranslationData[i].m_ObjPosition;
}

void UpdateGame(ObjectsStore& ioStore, vector<Vector3D>& inTranslations)
{
   vector<TranslationData> translation_data;
   PrepareTranslations(ioStore, inTranslations, translation_data);
   TranslateObject(translation_data);
   ApplyTranslation(translation_data, ioStore);
}

Minha pergunta é: para preparar os dados dessa maneira, é preciso acessá-los de qualquer maneira (e também copiá-los), então me pergunto se, mesmo que os dados sejam mais amigáveis ​​ao cache depois , não seria mais eficiente modificá-los diretamente e poupar a etapa de preparação?

Até onde eu entendo, obviamente os cálculos são muito eficientes nos dados preparados, mas com o custo adicional de prepará-los em primeiro lugar.

Alguém pode me dizer o que estou esquecendo aqui? Alguém assume o custo extra para obter outros benefícios (como código mais claro etc.) ou é realmente mais eficiente do que a modificação direta?

desde já, obrigado

c++

1 respostas

  1. Best Answer

    Aqui não vale a pena preparar dados. Na verdade, certamente será mais lento.

    Primeiro de tudo, PrepareTranslationschama push_backmas não reserveé chamado antes, então o vetor será redimensionado O(log n)vezes. Não é ótimo para acessos de memória, especialmente para vetores grandes.

    Os seguintes pontos precisam ser considerados:

    • PrepareTranslationsdeve ser vinculado à memória e não compatível com SIMD ( push_backcertamente evita qualquer otimização de SIMD).
    • TranslateObjectdeve ser bastante limitado à computação (embora possa não se beneficiar muito do AVX2/AVX-512, que operam em 8 e 16 itens, respectivamente, enquanto o Vector3D deve ter 3 atributos e o Quaternion deve ter 4 atributos).
    • ApplyTranslationdeve ser vinculado à memória.

    O problema é que se você mesclar as 3 operações em um loop, a CPU pode esconder a latência da memória com computação, ler/escrever dados enquanto faz computação e mover menos dados na memória no geral. Aqui, preparar dados quase não traz benefícios e introduz custos adicionais, então o resultado é certamente uma execução mais lenta.

    Preparar dados seria uma boa ideia se você pudesse então tornar os cálculos principais mais amigáveis ​​ao SIMD , por exemplo. Também pode ser uma boa ideia reduzir paradas de latência de loops complexos com dependência transportada pelo loop, impedindo que a CPU busque muitos dados da memória simultaneamente. A divisão de loop também pode ajudar a evitar o cache trashing em alguns casos (por exemplo, quando você acessa muitos arrays alinhados em uma grande potência de dois na memória no mesmo loop).

    Aqui está um exemplo prático: você tem uma lista de N posições 2D (por exemplo, jogador) que você quer atualizar com base em uma função que requer 8 arrays de N itens e a computação requer fazer acessos a um grande hash-map. Neste caso, é melhor:

    • use 2 matrizes (uma por coordenada) para a lista de posições (veja AoS vs SoA );
    • busque os valores do mapa de hash com antecedência e coloque o resultado em uma matriz temporária;
    • faça o cálculo de uma forma amigável ao SIMD (possivelmente usando 2 loops em relação à máquina alvo e/ou pedaço por pedaço).

    De fato, o hash-map impedirá qualquer otimização SIMD por compiladores tradicionais. A mesma coisa seria verdadeira para um código com ramificações condicionais que não podem ser vetorizadas.

    No seu caso, usar um array por coordenada certamente acelerará um pouco as coisas, supondo que você não precise converter o SoA para AoS todas as vezes (considere mantê-los como SoA o máximo possível). De fato, isso torna a operação de computação mais amigável ao SIMD. De fato, CPUs x86-64 modernas podem operar em 8 floatitens por vez usando uma única instrução AVX/AVX2 e até mesmo 16 floatcom AVX-512 (então uma Vector3Destrutura de dados não se encaixa bem). Se os arrays contiverem muitos itens, então AoSoA é o melhor layout (já que AoS não é amigável ao SIMD e SoA tende a causar destruição de cache em arrays grandes). No entanto, é uma dor de cabeça escrever (e manter) códigos usando estruturas de dados AoSoA, sem mencionar que alterar o layout também é complicado e frequentemente necessário por causa de bibliotecas externas.

    Por último, mas não menos importante, quando você tem que buscar muitas estruturas de dados por item de um array, os acessos parecerão aleatórios e as CPUs tradicionais não conseguem pré-buscar dados facilmente. Nesse caso, elas apenas iniciarão as cargas de memória o mais cedo possível, mas isso geralmente não é suficiente, pois a latência da memória pode ser realmente enorme (especialmente para dados na RAM) e geralmente não há computação suficiente para escondê-la. A pré-busca manual pode ajudar nesse caso, mas não é uma solução mágica e é frágil (dependendo da arquitetura de destino). Nesse caso, mover dados para arrays (ou seja, alternar de AoS para SoA) pode ajudar um pouco porque os pré-buscadores de hardware podem pré-buscar dados de forma mais eficiente com um pequeno passo constante .

    Nota sobre GPUs

    Se parte da sua computação puder ser portada para GPUs, então esteja ciente de que SoA é geralmente muito mais eficiente nelas do que AoS (por causa da coalescência e também porque GPUs são dispositivos SIMT ). O benefício de AoSoA em GPUs é frequentemente pequeno, então não vale o esforço em tal plataforma.

    • 2

relate perguntas