¿Por qué mi aplicación pasa el 24% de su vida haciendo una verificación nula?

Tengo un árbol de decisiones binarias de rendimiento crítico y me gustaría centrar esta pregunta en una sola línea de código. El código para el iterador de árbol binario se encuentra a continuación con los resultados de la ejecución del análisis de rendimiento en él.

        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 es un campo, no una propiedad. Hice esto para evitar el riesgo de que no estuviera alineado.

La clase BranchNodeData es la siguiente:

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 puede ver, la comprobación while / null es un gran éxito en el rendimiento. El árbol es enorme, por lo que esperaría que la búsqueda de una hoja lleve un tiempo, pero me gustaría comprender la cantidad desproporcionada de tiempo que se dedica a esa línea.

He intentado:

• Separando el chequeo nulo del while, el cheque nulo es el acierto.
• Agregar un campo booleano al objeto y compararlo, no hizo ninguna diferencia. No importa lo que se esté comparando, el problema es la comparación.

¿Es este un problema de predicción de rama? Si es así, ¿qué puedo hacer al respecto? ¿Si algo?

No pretendo entender el CIL , pero lo publicaré para que cualquiera lo entienda para que puedan intentar extraer información de él.

.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

Editar: Decidí hacer una prueba de predicción de rama, agregué un si idéntico dentro del tiempo, así que tenemos

while (node.BranchData != null)

y

if (node.BranchData != null)

dentro de eso. Luego ejecuté un análisis de rendimiento en contra de eso, y me tomó seis veces más ejecutar la primera comparación que ejecutar la segunda comparación que siempre resultó verdadera. Así que parece que se trata de un problema de predicción de ramas, ¿y supongo que no hay nada que pueda hacer al respecto?

Otra edición

El resultado anterior también ocurriría si node.BranchData tuviera que cargarse desde la RAM para la verificación while; luego se almacenaría en caché para la declaración if.

Esta es mi tercera pregunta sobre un tema similar. Esta vez me estoy enfocando en una sola línea de código. Mis otras preguntas sobre este tema son:

• ¿Podría usar una estructura de datos más rápida que un árbol para esto?
• Micro optimizaciones iterando a través de un árbol en C #

El árbol es masivo

Con mucho, lo más caro que hace un procesador es no ejecutar instrucciones, sino acceder a la memoria. El núcleo de ejecución de una CPU moderna es muchas veces más rápido que el bus de memoria. Un problema relacionado con la distancia , cuanto más lejos tiene que viajar una señal eléctrica, más difícil se vuelve conseguir que la señal llegue al otro extremo del cable sin que se corrompa. La única cura para ese problema es hacerlo más lento. Un gran problema con los cables que conectan la CPU a la RAM en su máquina, puede abrir la carcasa y ver los cables.

Los procesadores tienen una contramedida para este problema, usan cachés , búferes que almacenan una copia de los bytes en la RAM. Uno importante es el caché L1 , normalmente 16 kilobytes para datos y 16 kilobytes para instrucciones. Pequeño, lo que le permite estar cerca del motor de ejecución. La lectura de bytes de la caché L1 generalmente toma 2 o 3 ciclos de CPU. El siguiente es el caché L2, más grande y lento. Los procesadores de lujo también tienen una caché L3, más grande y más lenta aún. A medida que la tecnología de procesos mejora, esos búferes ocupan menos espacio y automáticamente se vuelven más rápidos a medida que se acercan al núcleo, una gran razón por la que los procesadores más nuevos son mejores y cómo se las arreglan para utilizar un número cada vez mayor de transistores.

Sin embargo, esos cachés no son una solución perfecta. El procesador aún se detendrá en un acceso a la memoria si los datos no están disponibles en una de las cachés. No puede continuar hasta que el bus de memoria muy lento haya proporcionado los datos. Es posible perder cien ciclos de CPU con una sola instrucción.

Las estructuras de los árboles son un problema, son no caché de usar. Sus nodos tienden a estar dispersos por todo el espacio de direcciones. La forma más rápida de acceder a la memoria es leyendo direcciones secuenciales. La unidad de almacenamiento de la caché L1 es de 64 bytes. O en otras palabras, una vez que el procesador lee un byte, los siguientes 63 son muy rápidos ya que estarán presentes en la caché.

Lo que hace que una matriz sea, con mucho, la estructura de datos más eficiente. Además, la razón por la que la clase .NET List <> no es una lista en absoluto, usa una matriz para el almacenamiento. Lo mismo para otros tipos de colección, como Dictionary, estructuralmente no es remotamente similar a una matriz, pero implementado internamente con matrices.

Por lo tanto, es muy probable que su declaración while () sufra bloqueos de CPU porque está desreferenciando un puntero para acceder al campo BranchData. La siguiente instrucción es muy barata porque la instrucción while () ya hizo el trabajo pesado de recuperar el valor de la memoria. Asignar la variable local es barato, un procesador usa un búfer para escrituras.

De lo contrario, no sería un problema simple de resolver, es muy probable que aplanar su árbol en matrices no sea práctico. No en lo más mínimo porque normalmente no se puede predecir en qué orden se visitarán los nodos del árbol. Un árbol rojo-negro podría ayudar, no queda claro en la pregunta. Entonces, una conclusión simple es que ya se está ejecutando tan rápido como se puede esperar. Y si necesita que sea más rápido, necesitará un mejor hardware con un bus de memoria más rápido. DDR4 se está generalizando este año.

Para complementar la gran respuesta de Hans sobre los efectos de la memoria caché, agrego una discusión de la memoria virtual a la traducción de la memoria física y los efectos NUMA.

Con la computadora de memoria virtual (todas las computadoras actuales), al hacer un acceso a la memoria, cada dirección de memoria virtual debe traducirse a una dirección de memoria física. Esto lo hace el hardware de administración de memoria mediante una tabla de traducción. Esta tabla es administrada por el sistema operativo para cada proceso y ella misma se almacena en la RAM. Para cada página de la memoria virtual, hay una entrada en esta tabla de traducción que asigna una página virtual a una física. Recuerde la discusión de Hans sobre los accesos a la memoria que son costosos: si cada traducción virtual a física necesita una búsqueda de memoria, todos los accesos a la memoria costarían el doble. La solución es tener un caché para la tabla de traducción que se llama búfer de búsqueda de traducción(TLB para abreviar). Los TLB no son grandes (12 a 4096 entradas), y el tamaño de página típico en la arquitectura x86-64 es de solo 4 KB, lo que significa que hay como máximo 16 MB directamente accesibles con accesos TLB (probablemente sea incluso menor que eso, el Sandy Puente que tiene un tamaño TLB de 512 elementos ). Para reducir la cantidad de errores de TLB, puede hacer que el sistema operativo y la aplicación trabajen juntos para usar un tamaño de página más grande, como 2 MB, lo que genera un espacio de memoria mucho más grande accesible con accesos de TLB. Esta página explica cómo utilizar páginas grandes con Java que pueden acelerar considerablemente los accesos a la memoria .

Si su computadora tiene muchos sockets, probablemente sea una arquitectura NUMA . NUMA significa Acceso a memoria no uniforme. En estas arquitecturas, algunos accesos a memoria cuestan más que otros. Por ejemplo, con una computadora de 2 sockets con 32 GB de RAM, cada socket probablemente tenga 16 GB de RAM. En esta computadora de ejemplo, los accesos a la memoria local son más baratos que los accesos a la memoria de otro socket (el acceso remoto es entre un 20 y un 100% más lento, quizás incluso más). Si en dicha computadora, su árbol usa 20 GB de RAM, al menos 4 GB de sus datos están en el otro nodo NUMA, y si los accesos son 50% más lentos para la memoria remota, los accesos NUMA ralentizan sus accesos a la memoria en un 10%. Además, si solo tiene memoria libre en un solo nodo NUMA, a todos los procesos que necesitan memoria en el nodo hambriento se les asignará memoria del otro nodo cuyos accesos son más costosos. Peor aún, el sistema operativo podría pensar que es una buena idea intercambiar parte de la memoria del nodo hambriento.lo que causaría accesos a memoria aún más costosos . Esto se explica con más detalle en El problema de la “locura de intercambio” de MySQL y los efectos de la arquitectura NUMA donde se dan algunas soluciones para Linux (distribuir los accesos a la memoria en todos los nodos NUMA, morder los accesos NUMA remotos para evitar el intercambio). También puedo pensar en asignar más RAM a un socket (24 y 8 GB en lugar de 16 y 16 GB) y asegurarme de que su programa esté programado en el nodo NUMA más grande, pero esto necesita acceso físico a la computadora y un destornillador ;-) .

Esta no es una respuesta per se, sino más bien un énfasis en lo que escribió Hans Passant sobre los retrasos en el sistema de memoria.

El software de alto rendimiento, como los juegos de computadora, no solo está escrito para implementar el juego en sí, sino que también está adaptado para que el código y las estructuras de datos aprovechen al máximo los sistemas de memoria caché y memoria, es decir, los traten como un recurso limitado. Cuando trato con problemas de caché, generalmente asumo que el L1 se entregará en 3 ciclos si los datos están presentes allí. Si no es así y tengo que pasar a L2, asumo 10 ciclos. Para L3 30 ciclos y para memoria RAM 100.

Hay una acción adicional relacionada con la memoria que, si necesita usarla, impone una penalización aún mayor y es un bloqueo de bus. Los bloqueos de bus se denominan secciones críticas si utiliza la funcionalidad de Windows NT. Si usa una variedad de cosecha propia, podría llamarla spinlock. Cualquiera que sea el nombre, se sincroniza con el dispositivo de masterización de bus más lento del sistema antes de que el bloqueo esté en su lugar. El dispositivo de masterización de bus más lento podría ser una tarjeta PCI clásica de 32 bits conectada a 33MHz. 33MHz es una centésima parte de la frecuencia de una CPU x86 típica (@ 3.3 GHz). Supongo que no menos de 300 ciclos para completar un bloqueo de bus, pero sé que pueden tardar muchas veces ese tiempo, así que si veo 3000 ciclos no me sorprenderá.

Los desarrolladores de software de subprocesos múltiples novatos usarán bloqueos de bus por todas partes y luego se preguntarán por qué su código es lento. El truco -como todo lo que tiene que ver con la memoria- es economizar accesos.