c# - traduccion - voided check español

¿Por qué mi aplicación pasa el 24% de su vida haciendo un cheque nulo?

Question

Tengo un árbol de decisiones binarias de rendimiento crítico, y me gustaría enfocar esta pregunta en una sola línea de código. El código para el iterador de árbol binario está debajo con los resultados de ejecutar el análisis de rendimiento en su contra.

        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 esté en línea.

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 loop / null es un golpe enorme en el rendimiento. El árbol es enorme, por lo que espero que la búsqueda de una hoja me lleve un tiempo, pero me gustaría entender la cantidad desproporcionada de tiempo que pasé en esa línea.

He intentado:

• Separar el cheque nulo del tiempo: es el control nulo el golpe.
• Agregar un campo booleano al objeto y verificarlo, no hizo ninguna diferencia. No importa lo que se compare, la comparación es el problema.

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

No voy a pretender que entiendo el CIL , pero lo publicaré para que lo haga cualquier persona, para que pueda tratar de extraer algo de 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é una idéntica si dentro de un tiempo, así que tenemos

while (node.BranchData != null)

y

if (node.BranchData != null)

dentro de eso. Luego ejecuté el análisis de rendimiento contra eso, y tardé seis veces más en ejecutar la primera comparación que en la segunda comparación que siempre devolvió verdadero. Así que parece que de hecho es un problema de predicción de sucursal, y supongo que no hay nada que pueda hacer al respecto?

Otro Editar

El resultado anterior también ocurriría si hubiése que cargar node.BranchData desde la RAM durante la comprobación while - entonces se almacenaría en caché para la sentencia 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 #

Answer 1

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 mucho más rápido que el bus de memoria. Un problema relacionado con la distancia , cuanto más tenga que viajar una señal eléctrica, más difícil será 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. Una importante es la caché L1 , típicamente 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 desde la caché L1 generalmente toma 2 o 3 ciclos de CPU. El siguiente es el caché L2, más grande y más lento. Los procesadores de alta gama también tienen un caché L3, más grande y más lento todavía. A medida que la tecnología de proceso 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 cual los procesadores más nuevos son mejores y cómo logran utilizar un número cada vez mayor de transistores.

Esos cachés, sin embargo, no son una solución perfecta. El procesador aún se detendrá en un acceso de memoria si los datos no están disponibles en uno de los cachés. No puede continuar hasta que el bus de memoria muy lento haya suministrado los datos. Perder cientos de ciclos de CPU es posible en una sola instrucción.

Las estructuras de árbol son un problema, no son compatibles con la caché. Sus nodos tienden a estar dispersos en todo el espacio de direcciones. La forma más rápida de acceder a la memoria es leyendo direcciones secuenciales. La unidad de almacenamiento para la memoria 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 el caché.

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

Por lo tanto, es probable que su sentencia while () sufra bloqueos de CPU porque está desreferenciando un puntero para acceder al campo BranchData. La siguiente afirmación es muy barata porque la sentencia while () ya hizo el trabajo pesado de recuperar el valor de la memoria. La asignación de la variable local es barata, un procesador utiliza un buffer para escrituras.

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

Answer 2

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

El software de alto rendimiento, como los juegos de computadora, no solo está diseñado 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 caché y memoria, es decir, tratarlos como un recurso limitado. Cuando trato con problemas de caché, normalmente asumo que el L1 se entregará en 3 ciclos si los datos están presentes allí. Si no es así y tengo que ir a L2, asumo 10 ciclos. Para L3 30 ciclos y para la 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 usa la funcionalidad de Windows NT. Si usa una variedad de cosecha propia, puede llamarlo spinlock. Cualquiera que sea el nombre, se sincroniza hasta el dispositivo de control de bus más lento del sistema antes de que el bloqueo esté en su lugar. El dispositivo más lento de masterización de bus podría ser una clásica tarjeta PCI 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 el bloqueo de un bus, pero sé que pueden durar muchas veces, así que si veo 3000 ciclos no me sorprenderá.

Los desarrolladores de software multihilo noveles utilizarán bloqueos de bus por todas partes y luego se preguntarán por qué su código es lento. El truco, al igual que con todo lo que tiene que ver con la memoria, es economizar en los accesos.

Answer 3

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

Con la computadora con memoria virtual (toda la computadora actual), al hacer un acceso a memoria, cada dirección de memoria virtual debe traducirse a una dirección de memoria física. Esto es hecho por el hardware de administración de memoria usando una tabla de traducción. Esta tabla es administrada por el sistema operativo para cada proceso y está almacenada en RAM. Para cada página de memoria virtual, hay una entrada en esta tabla de traducción mapeando una página virtual a una página física. Recuerde la discusión de Hans sobre los accesos de memoria que son caros: si cada traducción virtual a física necesita una búsqueda de memoria, todo acceso a la memoria costaría el doble. La solución es tener un caché para la tabla de traducción que se denomina buffer traducción lookaside (TLB para abreviar). 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 mucho 16 MB directamente accesibles con hits TLB (es probable que sea incluso menor que eso, el Sandy Puente que tiene un tamaño de TLB de 512 elementos ). Para reducir el número de errores de TLB, puede hacer que el sistema operativo y la aplicación funcionen en conjunto para usar un tamaño de página más grande, como 2 MB, lo que lleva a un espacio de memoria mucho más grande, accesible con hits de TLB. Esta página explica cómo usar páginas grandes con Java, lo que puede acelerar considerablemente los accesos a la memoria .

Si su computadora tiene muchos sockets, es probable que sea una arquitectura NUMA . NUMA significa acceso a memoria no uniforme. En estas arquitecturas, algunos accesos a memoria cuestan más que otros . Como ejemplo, con una computadora de 2 zócalos con 32 GB de RAM, cada zócalo probablemente tenga 16 GB de RAM. En esta computadora de ejemplo, los accesos a la memoria local son más económicos que los accesos a la memoria de otro socket (el acceso remoto es entre un 20 y un 100% más lento, tal vez 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 un 50% más lentos para la memoria remota, los accesos NUMA reducen la velocidad de sus accesos de memoria en un 10%. Además, si solo tiene memoria libre en un solo nodo NUMA, todos los procesos que necesiten memoria en el nodo privado de memoria se asignarán a la memoria del otro nodo cuyos accesos son más caros. Incluso peor, el sistema operativo podría pensar que es una buena idea intercambiar parte de la memoria del nodo muerto de hambre, lo que causaría accesos de memoria aún más caros . Esto se explica con más detalle en el problema de "swan crazy" de MySQL y los efectos de la arquitectura NUMA donde se dan algunas soluciones para Linux (expandiendo los accesos de memoria en todos los nodos NUMA, mordiendo la viñeta en accesos NUMA remotos para evitar el intercambio). También puedo pensar en asignar más memoria RAM a un socket (24 y 8 GB en lugar de 16 y 16 GB) y asegurarme de que tu programa esté programado en el nodo NUMA más grande, pero esto necesita acceso físico a la computadora y un destornillador ;-) .