Pourquoi mon application passe-t-elle 24% de sa vie à effectuer une vérification nulle?

J'ai un arbre de décision binaire critique pour les performances, et j'aimerais concentrer cette question sur une seule ligne de code. Le code de l'itérateur d'arborescence binaire est ci-dessous avec les résultats de l'exécution de l'analyse des performances par rapport à celui-ci.

        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 est un champ, pas une propriété. J'ai fait cela pour éviter le risque de ne pas être intégré.

La classe BranchNodeData est la suivante:

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;
}

Comme vous pouvez le voir, la vérification de la boucle while / null est un énorme impact sur les performances. L'arbre est énorme, donc je m'attendrais à ce que la recherche d'une feuille prenne un certain temps, mais j'aimerais comprendre le temps disproportionné passé sur cette ligne.

J'ai essayé:

• Séparer la vérification Null du while - c'est la vérification Null qui est le coup.
• L'ajout d'un champ booléen à l'objet et la vérification par rapport à cela n'a fait aucune différence. Peu importe ce qui est comparé, c'est la comparaison qui est le problème.

S'agit-il d'un problème de prédiction de branche? Si oui, que puis-je y faire? Si quelque chose?

Je ne prétendrai pas comprendre le CIL , mais je le posterai pour que n'importe qui le fasse afin qu'il puisse essayer d'en extraire des informations.

.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: J'ai décidé de faire un test de prédiction de branche, j'ai ajouté un même si dans le temps, donc nous avons

while (node.BranchData != null)

et

if (node.BranchData != null)

à l'intérieur. J'ai ensuite effectué une analyse des performances par rapport à cela, et il a fallu six fois plus de temps pour exécuter la première comparaison que pour exécuter la deuxième comparaison qui retournait toujours vrai. Il semble donc que ce soit effectivement un problème de prédiction de branche - et je suppose que je ne peux rien y faire?!

Une autre modification

Le résultat ci-dessus se produirait également si node.BranchData devait être chargé à partir de la RAM pendant le contrôle while - il serait alors mis en cache pour l'instruction if.

C'est ma troisième question sur un sujet similaire. Cette fois, je me concentre sur une seule ligne de code. Mes autres questions à ce sujet sont:

• Puis-je utiliser une structure de données plus rapide qu'un arbre pour cela?
• Micro optimisations itérant dans un arbre en C #

L'arbre est massif

De loin, la chose la plus coûteuse qu'un processeur fasse est de ne pas exécuter d'instructions, c'est d'accéder à la mémoire. Le cœur d'exécution d'un processeur moderne est plusieurs fois plus rapide que le bus mémoire. Un problème lié à la distance , plus un signal électrique doit voyager loin, plus il est difficile d'obtenir ce signal délivré à l'autre extrémité du fil sans qu'il soit corrompu. Le seul remède à ce problème est de le ralentir. Un gros problème avec les fils qui relient le CPU à la RAM de votre machine, vous pouvez faire sauter le boîtier et voir les fils.

Les processeurs ont une contre-mesure pour ce problème, ils utilisent des caches , des tampons qui stockent une copie des octets dans la RAM. Un élément important est le cache L1 , généralement 16 kilo-octets pour les données et 16 kilo-octets pour les instructions. Petit, lui permettant d'être proche du moteur d'exécution. La lecture d'octets à partir du cache L1 prend généralement 2 ou 3 cycles CPU. Ensuite, le cache L2, plus grand et plus lent. Les processeurs haut de gamme ont également un cache L3, plus gros et plus lent encore. Au fur et à mesure que la technologie des processus s'améliore, ces tampons prennent moins de place et deviennent automatiquement plus rapides à mesure qu'ils se rapprochent du cœur, une grande raison pour laquelle les nouveaux processeurs sont meilleurs et comment ils parviennent à utiliser un nombre toujours croissant de transistors.

Ces caches ne sont cependant pas une solution parfaite. Le processeur bloquera toujours sur un accès mémoire si les données ne sont pas disponibles dans l'un des caches. Il ne peut pas continuer tant que le bus mémoire très lent n'a pas fourni les données. Perdre une centaine de cycles CPU est possible sur une seule instruction.

Les arborescences sont un problème, elles ne sont pas compatibles avec le cache. Leurs nœuds ont tendance à être dispersés dans tout l'espace d'adressage. Le moyen le plus rapide d'accéder à la mémoire est de lire à partir d'adresses séquentielles. L'unité de stockage du cache L1 est de 64 octets. Ou en d'autres termes, une fois que le processeur lit un octet, les 63 suivants sont très rapides puisqu'ils seront présents dans le cache.

Ce qui fait d'un tableau de loin la structure de données la plus efficace. Aussi la raison pour laquelle la classe .NET List <> n'est pas du tout une liste, elle utilise un tableau pour le stockage. La même chose pour les autres types de collection, comme Dictionary, structurellement non similaire à un tableau, mais implémentée en interne avec des tableaux.

Ainsi, votre instruction while () est très susceptible de souffrir de blocages du processeur car elle déréférence un pointeur pour accéder au champ BranchData. L'instruction suivante est très bon marché car l'instruction while () a déjà fait le gros du travail de récupération de la valeur de la mémoire. L'affectation de la variable locale est peu coûteuse, un processeur utilise un tampon pour les écritures.

Ce n'est pas un problème simple à résoudre autrement, l'aplatissement de votre arbre en tableaux ne sera probablement pas pratique. Pas du tout car vous ne pouvez généralement pas prédire dans quel ordre les nœuds de l'arbre seront visités. Un arbre rouge-noir pourrait aider, ce n'est pas clair d'après la question. Donc, une conclusion simple à tirer est qu'il fonctionne déjà aussi vite que vous pouvez l'espérer. Et si vous en avez besoin pour aller plus vite, vous aurez besoin d'un meilleur matériel avec un bus mémoire plus rapide. La DDR4 se généralise cette année.

Pour compléter la grande réponse de Hans sur les effets de cache mémoire, j'ajoute une discussion sur la mémoire virtuelle à la traduction de la mémoire physique et aux effets NUMA.

Avec un ordinateur à mémoire virtuelle (tous les ordinateurs actuels), lors d'un accès à la mémoire, chaque adresse de mémoire virtuelle doit être traduite en une adresse de mémoire physique. Ceci est effectué par le matériel de gestion de la mémoire à l'aide d'une table de traduction. Cette table est gérée par le système d'exploitation pour chaque processus et elle est elle-même stockée en RAM. Pour chaque page de mémoire virtuelle, il existe une entrée dans cette table de traduction mappant une page virtuelle à une page physique. Rappelez-vous la discussion de Hans sur les accès mémoire coûteux: si chaque traduction virtuelle-physique nécessite une recherche de mémoire, tous les accès mémoire coûteraient deux fois plus cher. La solution est d'avoir un cache pour la table de traduction qui s'appelle le tampon de recherche de traduction(TLB pour faire court). Les TLB ne sont pas volumineux (12 à 4096 entrées), et la taille de page typique sur l'architecture x86-64 n'est que de 4 Ko, ce qui signifie qu'il y a au plus 16 Mo directement accessibles avec les hits TLB (c'est probablement encore moins que cela, le Sandy Bridge ayant une taille TLB de 512 éléments ). Pour réduire le nombre de ratés TLB, vous pouvez faire en sorte que le système d'exploitation et l'application travaillent ensemble pour utiliser une taille de page plus grande comme 2 Mo, ce qui conduit à un espace mémoire beaucoup plus grand accessible avec les hits TLB. Cette page explique comment utiliser de grandes pages avec Java, ce qui peut considérablement accélérer les accès mémoire .

Si votre ordinateur possède de nombreuses prises, il s'agit probablement d'une architecture NUMA . NUMA signifie accès mémoire non uniforme. Dans ces architectures, certains accès mémoire coûtent plus cher que d'autres. A titre d'exemple, avec un ordinateur à 2 sockets avec 32 Go de RAM, chaque socket a probablement 16 Go de RAM. Sur cet exemple d'ordinateur, les accès à la mémoire locale sont moins chers que les accès à la mémoire d'un autre socket (les accès à distance sont 20 à 100% plus lents, voire plus). Si sur un tel ordinateur, votre arborescence utilise 20 Go de RAM, au moins 4 Go de vos données sont sur l'autre nœud NUMA, et si les accès sont 50% plus lents pour la mémoire distante, les accès NUMA ralentissent vos accès mémoire de 10%. De plus, si vous n'avez de mémoire libre que sur un seul nœud NUMA, tous les processus nécessitant de la mémoire sur le nœud affamé se verront allouer de la mémoire de l'autre nœud dont les accès sont plus chers. Pire encore, le système d'exploitation pourrait penser que c'est une bonne idée d'échanger une partie de la mémoire du nœud affamé,ce qui entraînerait des accès mémoire encore plus coûteux . Ceci est expliqué plus en détail dans Le problème MySQL «swap insanity» et les effets de l'architecture NUMA où certaines solutions sont données pour Linux (étendre les accès mémoire sur tous les nœuds NUMA, mordre la balle sur les accès NUMA distants pour éviter les échanges). Je peux également penser à allouer plus de RAM à un socket (24 et 8 Go au lieu de 16 et 16 Go) et à m'assurer que votre programme est programmé sur le nœud NUMA plus grand, mais cela nécessite un accès physique à l'ordinateur et un tournevis ;-) .

Ce n'est pas une réponse en soi, mais plutôt un accent sur ce que Hans Passant a écrit sur les retards dans le système de mémoire.

Les logiciels très performants - tels que les jeux informatiques - ne sont pas seulement écrits pour implémenter le jeu lui-même, ils sont également adaptés de telle sorte que le code et les structures de données exploitent au maximum les systèmes de cache et de mémoire, c'est-à-dire les traitent comme une ressource limitée. Lorsque je traite des problèmes de cache, je suppose généralement que la L1 livrera en 3 cycles si les données y sont présentes. Si ce n'est pas le cas et que je dois passer en L2, je suppose 10 cycles. Pour L3 30 cycles et pour la mémoire RAM 100.

Il y a une action supplémentaire liée à la mémoire qui - si vous devez l'utiliser - impose une pénalité encore plus grande et c'est un verrouillage de bus. Les verrous de bus sont appelés sections critiques si vous utilisez la fonctionnalité Windows NT. Si vous utilisez une variété cultivée sur place, vous pouvez l'appeler un spinlock. Quel que soit le nom, il se synchronise avec le périphérique de maîtrise de bus le plus lent du système avant la mise en place du verrou. Le périphérique de maîtrise de bus le plus lent peut être une carte PCI 32 bits classique connectée à 33 MHz. 33 MHz est un centième de la fréquence d'un processeur x86 typique (à 3,3 GHz). Je suppose pas moins de 300 cycles pour terminer un verrouillage de bus, mais je sais qu'ils peuvent prendre plusieurs fois plus de temps, donc si je vois 3000 cycles, je ne serai pas surpris.

Les développeurs de logiciels multithreads novices utiliseront des verrous de bus partout et se demanderont ensuite pourquoi leur code est lent. L'astuce - comme pour tout ce qui a à voir avec la mémoire - est d'économiser les accès.