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

Question

J'ai un arbre de décision binaire dont les performances sont critiques, et j'aimerais concentrer cette question sur une seule ligne de code. Le code de l'itérateur d'arbre binaire est présenté ci-dessous avec les résultats de l'analyse des performances.

        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é. Je l'ai fait pour éviter le risque qu'il ne soit pas inlined.

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 constater, la boucle while et la vérification des nullités ont un impact considérable sur les performances. L'arbre est massif, donc je m'attendrais à ce que la recherche d'une feuille prenne un certain temps, mais j'aimerais comprendre la quantité disproportionnée de temps passé sur cette seule ligne.

J'ai essayé :

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

Est-ce un problème de prédiction de branche ? Si oui, que puis-je y faire ? Le cas échéant ?

Je ne vais pas prétendre comprendre le CIL mais je vais le poster pour ceux qui le font afin qu'ils puissent essayer d'en tirer quelques 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

Edita: J'ai décidé de faire un test de prédiction de branche, j'ai ajouté un if identique dans le while, donc nous avons

while (node.BranchData != null)

y

if (node.BranchData != null)

à l'intérieur de ça. J'ai ensuite effectué une analyse des performances et j'ai constaté que l'exécution de la première comparaison prenait six fois plus de temps que l'exécution de la deuxième comparaison qui retournait toujours vrai. Il semble donc qu'il s'agisse bien d'un problème de prédiction de branche - et je suppose que je ne peux rien y faire !

Une autre édition

Le résultat ci-dessus se produirait également si node.BranchData devait être chargé depuis la RAM pour la vérification du 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 sur ce sujet sont :

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

Answer 1

L'arbre est massif

La chose de loin la plus coûteuse qu'un processeur fasse n'est pas d'exécuter des instructions, mais d'accéder à la mémoire. Le noyau d'exécution d'un processeur moderne CPU es beaucoup de fois plus rapide que le bus mémoire. Un problème lié à distance Plus un signal électrique doit parcourir de distance, plus il est difficile de le faire parvenir à l'autre bout du fil sans qu'il soit corrompu. Le seul remède à ce problème est de le faire aller plus lentement. Un gros problème avec les fils qui relient le CPU à la RAM dans votre machine, vous pouvez ouvrir le boîtier et voir les fils.

Les processeurs ont une contre-mesure pour ce problème, ils utilisent caches les tampons qui stockent une copie des octets en RAM. L'un des plus importants est le Cache L1 En général, 16 kilo-octets pour les données et 16 kilo-octets pour les instructions. De petite taille, elle permet d'être proche du moteur d'exécution. La lecture d'octets dans le cache L1 prend généralement 2 ou 3 cycles CPU. Vient ensuite le cache L2, plus grand et plus lent. Les processeurs haut de gamme possèdent également un cache L3, plus grand et plus lent encore. Avec l'amélioration de la technologie des processus, ces caches prennent moins de place et deviennent automatiquement plus rapides à mesure qu'ils se rapprochent du cœur, ce qui explique en grande partie pourquoi 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 se bloquera toujours lors d'un accès à la mémoire si les données ne sont pas disponibles dans l'un des caches. Il ne peut pas continuer jusqu'à ce que le bus mémoire très lent lui fournisse les données. La perte d'une centaine de cycles CPU est possible sur une seule instruction.

Les structures arborescentes sont un problème, elles sont no facile à mettre en cachette. Leurs nœuds ont tendance à être dispersés dans l'espace d'adressage. Le moyen le plus rapide d'accéder à la mémoire est de lire des 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 qu'un tableau de loin la structure de données la plus efficace. C'est aussi la raison pour laquelle la classe List<> de .NET n'est pas du tout une liste, elle utilise un tableau pour le stockage. Il en va de même pour d'autres types de collections, comme les dictionnaires, dont la structure ne ressemble pas du tout à celle d'un tableau, mais qui sont implémentés en interne avec des tableaux.

Il est donc très probable que votre instruction while() souffre 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 en récupérant la valeur en mémoire. L'affectation de la variable locale est bon marché, un processeur utilise un tampon pour les écritures.

Le fait d'aplatir votre arbre en tableaux n'est pas un problème simple à résoudre et risque fort d'être peu pratique. Notamment parce que vous ne pouvez généralement pas prévoir dans quel ordre les nœuds de l'arbre seront visités. Un arbre rouge-noir pourrait être utile, mais la question n'est pas claire. Une conclusion simple à tirer est donc qu'il fonctionne déjà aussi vite que vous pouvez l'espérer. Et si vous avez besoin qu'il aille plus vite, vous aurez besoin d'un meilleur matériel avec un bus mémoire plus rapide. DDR4 devient grand public cette année.

Answer 2

Pour compléter l'excellente réponse de Hans sur les effets du cache mémoire, j'ajoute une discussion sur la traduction de la mémoire virtuelle en mémoire physique et les effets NUMA.

Avec les ordinateurs à mémoire virtuelle (tous les ordinateurs actuels), lorsqu'on effectue un accès à la mémoire, chaque adresse de mémoire virtuelle doit être traduite en une adresse de mémoire physique. Cette opération est effectuée 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 mémoire vive. Pour chaque página de la mémoire virtuelle, il existe une entrée dans cette table de traduction qui met en correspondance une page virtuelle et une page physique. Rappelez-vous la discussion de Hans sur les accès à la mémoire qui sont coûteux : si chaque traduction virtuelle vers physique nécessite une consultation de la mémoire, tous les accès à la mémoire coûteraient deux fois plus cher. La solution consiste à disposer d'un cache pour la table de traduction, appelé le "cache". Translation Lookaside buffer (TLB en abrégé). La TLB n'est pas grande (12 à 4096 entrées), et la taille typique des pages sur l'architecture x86-64 n'est que de 4 KB, ce qui signifie que il y a au maximum 16 MB directement accessible avec des hits TLB (c'est probablement encore moins que cela, la Sandy Bridge a une taille de TLB de 512 éléments. ). Pour réduire le nombre de ratés de la TLB, vous pouvez demander au système d'exploitation et à l'application de travailler ensemble pour utiliser une taille de page plus grande, comme 2 Mo, ce qui permet d'obtenir un espace mémoire beaucoup plus grand accessible avec des ratés de la TLB. Cette page explique comment pour utiliser de grandes pages avec Java ce qui peut accélérer considérablement les accès à la mémoire .

Si votre ordinateur possède de nombreuses prises, il s'agit probablement d'une NUMA l'architecture. NUMA signifie Non-Uniform Memory Access (accès mémoire non uniforme). Dans ces architectures, certains accès à la mémoire coût plus que d'autres . Par exemple, dans le cas d'un ordinateur à deux sockets avec 32 Go de RAM, chaque socket dispose probablement de 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 distants sont 20 à 100% plus lents, peut-être même plus). Si sur cet ordinateur, votre arbre utilise 20 Go de RAM, au moins 4 Go de vos données se trouvent 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 à la mémoire de 10%. De plus, si vous n'avez de la mémoire libre que sur un seul nœud NUMA, tous les processus ayant besoin de 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 coûteux. 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 à la mémoire encore plus coûteux . Ceci est expliqué plus en détail dans Le problème de "swap insanity" de MySQL et les effets de l'architecture NUMA où certaines solutions sont données pour Linux (répartir les accès à la mémoire sur tous les nœuds NUMA, mordre la poussière sur les accès NUMA distants pour éviter le swapping). Je peux aussi penser à allouer plus de RAM à un socket (24 et 8 Go au lieu de 16 et 16 Go) et faire en sorte que votre programme soit planifié sur le plus gros nœud NUMA, mais cela nécessite un accès physique à l'ordinateur et un tournevis ;-).

Answer 3

Il ne s'agit pas d'une réponse en soi, mais plutôt d'une mise en évidence de 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 vidéo, ne sont pas seulement écrits pour mettre en œuvre le jeu lui-même, ils sont également adaptés de telle sorte que le code et les structures de données tirent le meilleur parti des systèmes de cache et de mémoire, c'est-à-dire qu'ils les traitent comme une ressource limitée. Lorsque je m'occupe de problèmes de cache, je pars généralement du principe que la mémoire L1 délivrera les données en 3 cycles si elles s'y trouvent. Si elles ne le sont pas et que je dois passer à L2, je suppose 10 cycles. Pour L3 30 cycles et pour la mémoire RAM 100.

Il existe une action supplémentaire liée à la mémoire qui - si vous devez l'utiliser - impose une pénalité encore plus importante : il s'agit du verrouillage du bus. Les verrous de bus sont appelés sections critiques si vous utilisez la fonctionnalité Windows NT. Si vous utilisez une variété maison, vous pouvez l'appeler spinlock. Quel que soit son nom, il se synchronise jusqu'au périphérique le plus lent du système avant que le verrou ne soit en place. Le périphérique le plus lent peut être une carte PCI 32 bits classique connectée à 33 MHz. 33MHz est un centième de la fréquence d'un CPU x86 typique (@ 3.3 GHz). Je suppose qu'il faut au moins 300 cycles pour compléter un verrouillage de bus mais je sais qu'ils peuvent prendre plusieurs fois ce temps donc si je vois 3000 cycles je ne serai pas surpris.

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