Por que meu aplicativo gasta 24% de sua vida fazendo uma verificação de nulos?

Eu tenho uma árvore de decisão binária crítica de desempenho e gostaria de focar esta questão em uma única linha de código. O código para o iterador da árvore binária está abaixo com os resultados da execução da análise de desempenho em relação a ele.

        public ScTreeNode GetNodeForState(int rootIndex, float[] inputs)
        {
0.2%        ScTreeNode node = RootNodes[rootIndex].TreeNode;

24.6%       while (node.BranchData != null)
            {
0.2%            BranchNodeData b = node.BranchData;
0.5%            node = b.Child2;
12.8%           if (inputs[b.SplitInputIndex] <= b.SplitValue)
0.8%                node = b.Child1;
            }

0.4%        return node;
        }

BranchData é um campo, não uma propriedade. Fiz isso para evitar o risco de não ficar inline.

A classe BranchNodeData é a seguinte:

public sealed class BranchNodeData
{
    /// <summary>
    /// The index of the data item in the input array on which we need to split
    /// </summary>
    internal int SplitInputIndex = 0;

    /// <summary>
    /// The value that we should split on
    /// </summary>
    internal float SplitValue = 0;

    /// <summary>
    /// The nodes children
    /// </summary>
    internal ScTreeNode Child1;
    internal ScTreeNode Child2;
}

Como você pode ver, a verificação do loop while / null é um grande impacto no desempenho. A árvore é enorme, então eu esperaria que a busca por uma folha demore um pouco, mas eu gostaria de entender a quantidade desproporcional de tempo gasto naquela linha.

Eu tentei:

• Separando a verificação nula do tempo - é a verificação nula que acerta.
• Adicionar um campo booleano ao objeto e compará-lo não fez diferença. Não importa o que está sendo comparado, o problema é a comparação.

Este é um problema de previsão de branch? Em caso afirmativo, o que posso fazer a respeito? Se alguma coisa?

Não vou fingir que entendo o CIL , mas vou postá-lo para qualquer pessoa, para que possam tentar extrair algumas informações dele.

.method public hidebysig
instance class OptimalTreeSearch.ScTreeNode GetNodeForState (
    int32 rootIndex,
    float32[] inputs
) cil managed
{
    // Method begins at RVA 0x2dc8
    // Code size 67 (0x43)
    .maxstack 2
    .locals init (
        [0] class OptimalTreeSearch.ScTreeNode node,
        [1] class OptimalTreeSearch.BranchNodeData b
    )

    IL_0000: ldarg.0
    IL_0001: ldfld class [mscorlib]System.Collections.Generic.List`1<class OptimalTreeSearch.ScRootNode> OptimalTreeSearch.ScSearchTree::RootNodes
    IL_0006: ldarg.1
    IL_0007: callvirt instance !0 class [mscorlib]System.Collections.Generic.List`1<class OptimalTreeSearch.ScRootNode>::get_Item(int32)
    IL_000c: ldfld class OptimalTreeSearch.ScTreeNode OptimalTreeSearch.ScRootNode::TreeNode
    IL_0011: stloc.0
    IL_0012: br.s IL_0039
    // loop start (head: IL_0039)
        IL_0014: ldloc.0
        IL_0015: ldfld class OptimalTreeSearch.BranchNodeData OptimalTreeSearch.ScTreeNode::BranchData
        IL_001a: stloc.1
        IL_001b: ldloc.1
        IL_001c: ldfld class OptimalTreeSearch.ScTreeNode OptimalTreeSearch.BranchNodeData::Child2
        IL_0021: stloc.0
        IL_0022: ldarg.2
        IL_0023: ldloc.1
        IL_0024: ldfld int32 OptimalTreeSearch.BranchNodeData::SplitInputIndex
        IL_0029: ldelem.r4
        IL_002a: ldloc.1
        IL_002b: ldfld float32 OptimalTreeSearch.BranchNodeData::SplitValue
        IL_0030: bgt.un.s IL_0039

        IL_0032: ldloc.1
        IL_0033: ldfld class OptimalTreeSearch.ScTreeNode OptimalTreeSearch.BranchNodeData::Child1
        IL_0038: stloc.0

        IL_0039: ldloc.0
        IL_003a: ldfld class OptimalTreeSearch.BranchNodeData OptimalTreeSearch.ScTreeNode::BranchData
        IL_003f: brtrue.s IL_0014
    // end loop

    IL_0041: ldloc.0
    IL_0042: ret
} // end of method ScSearchTree::GetNodeForState

Edit: Decidi fazer um teste de predição de branch, adicionei um idêntico if dentro do tempo, então temos

while (node.BranchData != null)

e

if (node.BranchData != null)

dentro disso. Em seguida, executei a análise de desempenho em relação a isso e demorou seis vezes mais para executar a primeira comparação do que levou para executar a segunda comparação, que sempre retornou verdadeiro. Portanto, parece que é realmente um problema de previsão de ramificação - e estou supondo que não há nada que eu possa fazer sobre isso ?!

Outra Edição

O resultado acima também ocorreria se node.BranchData tivesse que ser carregado da RAM para a verificação while - ele seria então armazenado em cache para a instrução if.

Esta é minha terceira pergunta sobre um tópico semelhante. Desta vez, estou focando em uma única linha de código. Minhas outras perguntas sobre este assunto são:

• Posso usar uma estrutura de dados mais rápida do que uma árvore para isso?
• Micro otimizações iterando através de uma árvore em C #

A árvore é enorme

De longe, a coisa mais cara que um processador faz é não executar instruções, é acessar a memória. O núcleo de execução de uma CPU moderna é muitas vezes mais rápido que o barramento de memória. Um problema relacionado à distância , quanto mais longe um sinal elétrico tem que viajar, mais difícil fica para que o sinal seja entregue à outra extremidade do fio sem que seja corrompido. A única solução para esse problema é torná-lo mais lento. Um grande problema com os fios que conectam a CPU à RAM da sua máquina, você pode abrir o gabinete e ver os fios.

Os processadores têm uma contra-medida para esse problema, eles usam caches , buffers que armazenam uma cópia dos bytes na RAM. Um importante é o cache L1 , normalmente 16 kilobytes para dados e 16 kilobytes para instruções. Pequeno, permitindo que fique próximo ao mecanismo de execução. Ler bytes do cache L1 normalmente leva 2 ou 3 ciclos de CPU. O próximo é o cache L2, maior e mais lento. Os processadores de luxo também têm um cache L3, maior e mais lento ainda. Conforme a tecnologia de processo melhora, esses buffers ocupam menos espaço e automaticamente se tornam mais rápidos à medida que se aproximam do núcleo, um grande motivo pelo qual os processadores mais novos são melhores e como eles conseguem usar um número cada vez maior de transistores.

No entanto, esses caches não são uma solução perfeita. O processador ainda travará no acesso à memória se os dados não estiverem disponíveis em um dos caches. Não pode continuar até que o barramento de memória muito lento forneça os dados. É possível perder centenas de ciclos de CPU com uma única instrução.

Estruturas de árvore são um problema, eles são não cache de amigável. Seus nós tendem a estar espalhados por todo o espaço de endereço. A maneira mais rápida de acessar a memória é lendo os endereços sequenciais. A unidade de armazenamento para o cache L1 é de 64 bytes. Ou seja, uma vez que o processador lê um byte, os próximos 63 são muito rápidos, pois estarão presentes no cache.

O que torna uma matriz de longe a estrutura de dados mais eficiente. Além disso, a razão pela qual a classe .NET List <> não é uma lista, ela usa um array para armazenamento. O mesmo para outros tipos de coleção, como Dicionário, estruturalmente não remotamente semelhante a um array, mas implementado internamente com arrays.

Portanto, é muito provável que sua instrução while () esteja sofrendo de paralisações da CPU porque está desreferenciando um ponteiro para acessar o campo BranchData. A próxima instrução é muito barata porque a instrução while () já fazia o trabalho pesado de recuperar o valor da memória. Atribuir a variável local é barato, um processador usa um buffer para gravações.

De outra forma, não é um problema simples de resolver, mas achatar sua árvore em matrizes provavelmente não será prático. Nem um pouco porque você normalmente não pode prever em que ordem os nós da árvore serão visitados. Uma árvore vermelho-preta pode ajudar, não fica claro com a pergunta. Portanto, uma conclusão simples é que ele já está funcionando tão rápido quanto você pode esperar. E se você precisa ir mais rápido, então você precisará de um hardware melhor com um barramento de memória mais rápido. O DDR4 está se tornando popular este ano.

Para complementar a excelente resposta de Hans sobre os efeitos do cache de memória, acrescento uma discussão sobre a memória virtual para a tradução da memória física e os efeitos NUMA.

Com o computador com memória virtual (todos os computadores atuais), ao fazer um acesso à memória, cada endereço de memória virtual deve ser traduzido para um endereço de memória física. Isso é feito pelo hardware de gerenciamento de memória usando uma tabela de tradução. Esta tabela é gerenciada pelo sistema operacional para cada processo e ela mesma é armazenada na RAM. Para cada página de memória virtual, há uma entrada nesta tabela de tradução que mapeia uma página virtual para uma página física. Lembre-se da discussão de Hans sobre os acessos à memória que são caros: se cada tradução virtual para física precisar de uma pesquisa de memória, todo acesso à memória custaria o dobro. A solução é ter um cache para a tabela de tradução, que é chamado de buffer lookaside de tradução(TLB para breve). TLB não são grandes (12 a 4096 entradas) e o tamanho de página típico na arquitetura x86-64 é de apenas 4 KB, o que significa que há no máximo 16 MB diretamente acessíveis com acessos TLB (provavelmente é ainda menos do que isso, o Sandy Bridge com um tamanho TLB de 512 itens ). Para reduzir o número de falhas de TLB, você pode fazer com que o sistema operacional e o aplicativo trabalhem juntos para usar um tamanho de página maior, como 2 MB, levando a um espaço de memória muito maior acessível com acessos de TLB. Esta página explica como usar páginas grandes com Java, que podem acelerar bastante os acessos à memória .

Se o seu computador tiver muitos soquetes, provavelmente é uma arquitetura NUMA . NUMA significa acesso não uniforme à memória. Nessas arquiteturas, alguns acessos à memória custam mais do que outros. Por exemplo, com um computador de 2 soquetes com 32 GB de RAM, cada soquete provavelmente tem 16 GB de RAM. Neste computador de exemplo, os acessos à memória local são mais baratos do que os acessos à memória de outro soquete (o acesso remoto é 20 a 100% mais lento, talvez até mais). Se em tal computador, sua árvore usa 20 GB de RAM, pelo menos 4 GB de seus dados estão no outro nó NUMA, e se os acessos são 50% mais lentos para a memória remota, os acessos NUMA diminuem seus acessos à memória em 10%. Além disso, se você tiver apenas memória livre em um único nó NUMA, todos os processos que precisam de memória no nó faminto terão memória alocada do outro nó, cujos acessos são mais caros. Pior ainda, o sistema operacional pode pensar que é uma boa ideia trocar parte da memória do nó faminto,o que causaria acessos à memória ainda mais caros . Isso é explicado com mais detalhes em O problema de “swap insanity” do MySQL e os efeitos da arquitetura NUMA, onde algumas soluções são fornecidas para Linux (espalhando acessos de memória em todos os nós NUMA, mordendo a bala em acessos NUMA remotos para evitar a troca). Também posso pensar em alocar mais RAM para um soquete (24 e 8 GB em vez de 16 e 16 GB) e garantir que seu programa seja agendado no nó NUMA maior, mas isso precisa de acesso físico ao computador e uma chave de fenda ;-) .

Esta não é uma resposta em si, mas sim uma ênfase no que Hans Passant escreveu sobre atrasos no sistema de memória.

Software realmente de alto desempenho - como jogos de computador - não é apenas escrito para implementar o jogo em si, ele também é adaptado de forma que o código e as estruturas de dados aproveitem ao máximo os sistemas de cache e memória, ou seja, tratem-nos como um recurso limitado. Quando lido com problemas de cache, normalmente presumo que o L1 será entregue em 3 ciclos se os dados estiverem presentes nele. Se não for e eu tiver que ir para L2, presumo 10 ciclos. Para L3 30 ciclos e para memória RAM 100.

Existe uma ação adicional relacionada à memória que - se você precisar usá-la - impõe uma penalidade ainda maior e que é um bloqueio de barramento. Os bloqueios de barramento são chamados de seções críticas se você usar a funcionalidade do Windows NT. Se você usar uma variedade caseira, pode chamá-la de spinlock. Qualquer que seja o nome, ele se sincroniza com o dispositivo de controle de barramento mais lento do sistema antes que a fechadura seja instalada. O dispositivo de masterização de barramento mais lento pode ser uma placa PCI clássica de 32 bits conectada a 33 MHz. 33 MHz é um centésimo da frequência de uma CPU x86 típica (@ 3,3 GHz). Suponho que não menos do que 300 ciclos para completar um bloqueio de barramento, mas sei que eles podem demorar muito mais tempo, então se eu vir 3000 ciclos não ficarei surpreso.

Os desenvolvedores de software multi-threading novatos usam travas de barramento em todo lugar e se perguntam por que seu código é lento. O truque - como tudo que tem a ver com memória - é economizar nos acessos.