Optimiser les performances du processeur avec Instruments

Bonjour, je m’appelle Matt et je suis ingénieur noyau OS. Je vais vous apprendre à utiliser Instruments pour optimiser le code pour les CPU à puce Apple. Une utilisation efficace des ressources du CPU évite des temps d’attente notoires lorsque l’app doit traiter beaucoup de données ou réagir vite à une interaction. Mais prédire les performances des logiciels est difficile pour deux raisons. Les couches d’abstraction entre le code source Swift et ce qui finit par s’exécuter est la première raison. Le code source écrit pour l’app est compilé dans des instructions machine qui finissent par s’exécuter sur un CPU. Mais le code ne s’exécute pas de manière isolée : il est complété par du code généré par le compilateur, le runtime Swift et d’autres system frameworks, qui peuvent invoquer des appels système du noyau pour gérer des opérations privilégiées pour l’app.

Il est donc difficile de connaître le coût des abstractions logicielles liées au code. La deuxième raison est la façon dont le CPU exécute les instructions qui lui sont données. Dans un CPU, les unités fonctionnelles agissent en parallèle pour exécuter efficacement les instructions. Même si elles semblent être exécutées dans l’ordre, les instructions sont exécutées dans le désordre. Les CPU bénéficient aussi de plusieurs couches de caches mémoire assurant un accès rapide aux données. Tout cela accélère grandement les modèles de codage courants, tels que les balayages linéaires de la mémoire ou les contrôles défensifs comme les sorties précoces pour les conditions rares. Sans une optimisation minutieuse ou une restructuration massive, le CPU a du mal à exécuter des structures de données, algorithmes ou approches d’implémentation particuliers. Nous allons détailler comment optimiser le code pour le CPU. D’abord, nous verrons comment analyser les performances en exploitant les données pour cibler les principales accélérations potentielles. Puis, nous examinerons les approches de profilage classiques qui permettent d’identifier l’utilisation excessive du CPU dans le code. Pour combler les lacunes du profilage, nous utiliserons Processor Trace pour enregistrer chaque instruction et mesurer le coût des abstractions logicielles. Enfin, nous utiliserons l’instrument amélioré CPU Counters pour analyser les goulots d’étranglement du CPU et comprendre comment micro-optimiser l’algorithme. Commençons par nous préparer mentalement à l’examen des performances. Premièrement, gardons l’esprit ouvert : les sources de ralentissement peuvent sortir de l’ordinaire. Collectez des données pour tester les hypothèses et vérifier que la façon dont vous percevez l’exécution du code est correcte.

Par exemple, envisagez d’autres causes de ralentissement en plus des performances du CPU monothread. En plus de s’exécuter sur un CPU, les threads et les tâches peuvent avoir à attendre des ressources telles que des fichiers ou l’accès à l’état muable partagé. La session « Visualize and optimize Swift concurrency » couvre les outils permettant de comprendre pourquoi les tâches peuvent être hors du CPU.

Une fois les threads débloqués et sur le CPU, une API peut être utilisée à mauvais escient et, par exemple, appliquer la classe de qualité de service inappropriée au code ou créer implicitement trop de threads. Lisez la documentation sur le réglage des performances du code pour plus de détails. Si le problème est l’efficacité, vous devez modifier l’algorithme et ses structures de données associées ou l’implémentation, qui est la façon dont l’algorithme est exprimé dans le langage de programmation. Utilisez des outils pour déterminer les branches de cette arborescence à cibler. Essayez la jauge de CPU intégrée de Xcode pour détecter si les CPU sont fortement sollicités lors des interactions avec l’app. Pour analyser les comportements de blocage entre les threads, ainsi que les threads qui les débloqueront, utilisez l’instrument System Trace.

Pour les problèmes affectant l’interface utilisateur ou le thread principal de l’app, utilisez l’instrument spécialisé Hangs. La session « Analyzing hangs with Instruments » explique comment confirmer la nécessité d’optimiser l’utilisation du CPU d’une app. Même avec l’aide des outils, faites attention aux types d’optimisations que vous mettez en œuvre. Une micro-optimisation à outrance peut rendre le code plus difficile à étendre et à comprendre. Et elle s’appuie souvent sur des optimisations de compilateur parfois fragiles, comme l’auto-vectorisation ou l’élision du nombre de références. Avant d’effectuer des micro-optimisations intrusives, recherchez des alternatives susceptibles d’éviter complètement les ralentissements. Demandez-vous d’abord pourquoi le code s’exécute. Peut-être pourriez-vous éviter tous ces efforts et juste supprimer le code. Merci d’avoir regardé cette session et... Je plaisante ! Cela est généralement impossible, mais il est utile de vérifier que vos efforts sont justifiés par rapport à l’importance des résultats.

Vous pouvez aussi essayer de procéder plus tard en dehors du chemin critique, ou lorsque les résultats seront visibles. Dans le même ordre d’idées, le précalcul de valeurs peut masquer la durée totale du travail. Vous pourriez même avoir à incorporer des valeurs lors de la compilation. Mais ces approches peuvent consommer inutilement de l’énergie ou augmenter la taille de téléchargement de l’app. Pour les opérations répétées avec les mêmes entrées, la mise en cache est une autre solution, mais elle implique souvent des problèmes, comme l’invalidation du cache ou la gestion de l’utilisation accrue de la mémoire. Une fois que vous avez confirmé que vous ne pouvez pas tout simplement supprimer le code, il vous faut que le CPU effectue ce travail plus rapidement. Concentrons-nous donc sur cet aspect. Ciblez vos efforts d’optimisation sur le code ayant le plus d’impact sur l’expérience utilisateur. En général, il se situe sur le chemin critique d’un utilisateur interagissant avec l’app, où des problèmes de performances surviennent, mais il peut aussi s’agir d’opérations de longue durée qui consomment de l’énergie. Nous passerons ici au crible des listes préparées d’entiers, car elles se trouvent sur le chemin critique de mon app.

Mon app utilise la recherche binaire, un algorithme classique qui utilise un tableau trié pour trouver un élément en divisant successivement l’espace de recherche par deux. Dans cet exemple, le tableau contient 16 éléments, et nous recherchons celui qui contient le nombre 5. 5 est inférieur à l’élément du milieu du tableau, 20. Il doit donc être dans la première moitié. 5 est également inférieur à l’élément du milieu de la première moitié, 9. Il doit donc être dans le premier quart du tableau. Nous identifions l’élément correspondant après une comparaison avec 3, en juste 4 étapes. Voilà comment fonctionne la recherche binaire à partir d’un framework utilisé par mon app. Le nom des paramètres de cette fonction autonome s’apparente à la recherche d’une aiguille dans une botte de foin. Elle permet de rechercher une aiguille Comparable dans la botte de foin Collection. L’algorithme suit deux variables : le début de la zone de recherche actuelle et le nombre d’éléments restants à rechercher. La valeur du milieu de l’espace de recherche est identifiée tant qu’il reste des éléments à rechercher. Si l’aiguille est inférieure à cette valeur, l’espace de recherche est réduit de moitié, sans changer le début. Si l’aiguille est égale, l’élément a été trouvé et l’indice du milieu est renvoyé. Sinon, la position de départ devient la valeur située juste après l’élément du milieu et l’espace de recherche est réduit de moitié.

Nous nous préparerons à optimiser cet algorithme de manière incrémentielle, en confirmant à chaque étape que nous progressons en comparant le débit de recherche ou le nombre de recherches que l’algorithme peut effectuer chaque seconde. Ne vous sentez pas obligé de faire d’énormes modifications à chaque fois : certaines optimisations peuvent être difficiles à quantifier, mais les petites améliorations s’additionnent au fil du temps.

Pour faciliter l’optimisation continue, j’ai créé un test automatisé pour mesurer le débit de recherche. Nous n’avons pas besoin d’une configuration particulièrement robuste : nous voulons juste une estimation des performances. Cette boucle repeat-while appelle la fermeture de la recherche à la fin de la durée spécifiée. J’utilise un intervalle de signpost du système d’exploitation pour les appels de fermeture de la recherche afin que les outils ciblent la partie du test à optimiser. J’ai choisi la catégorie des points d’intérêt, car Instruments l’inclut par défaut. Le chronométrage utilise une ContinuousClock, qui, contrairement à la date, ne peut pas revenir en arrière et a une faible surcharge. C’est une approche simple, mais efficace, pour recueillir des données approximatives sur les performances de l’algorithme. Mon test s’appelle searchCollection et simule la façon dont mon app utilise la recherche binaire. Nous lancerons les recherches pendant une seconde avec un nom descriptif pour les signposts, en cas d’exécution de plusieurs tests dans un enregistrement. À la fermeture, une boucle appellera la fonction de recherche binaire pour amortir le coût de vérification de la durée. Exécutons ce test sous un profileur Instruments pour analyser les performances CPU de la recherche binaire. Vous avez le choix entre deux profileurs axés sur le CPU : Time Profiler et CPU Profiler. L’instrument Time Profiler classique échantillonne régulièrement ce qui s’exécute sur les CPU du système, en fonction d’un minuteur. Dans cet exemple, des tâches sont exécutées sur deux CPU. À chaque point d’échantillonnage, Time Profiler capture les piles d’appels de l’espace utilisateur de chaque thread exécuté sur le CPU.

Instruments visualise ensuite ces échantillons sous forme d’arborescence d’appels ou de graphique de flamme dans sa vue détaillée pour estimer le code à optimiser pour les performances du CPU. Cela est utile pour analyser la répartition du travail dans le temps ou les threads actifs en même temps. Mais l’utilisation d’un minuteur pour échantillonner les piles d’appels entraîne un problème d’aliasing. L’aliasing a lieu lorsqu’un travail périodique sur le système se produit à la même cadence que le minuteur d’échantillonnage. Ici, les régions bleues sont responsables de la majeure partie du temps CPU, mais les fonctions orange s’exécutent chaque fois que l’échantillonneur collecte une pile d’appels. L’orange est donc injustement surreprésenté dans l’arborescence d’appels Instruments.

Pour éviter ce problème, nous pouvons passer à CPU Profiler. Il échantillonne les CPU indépendamment, en fonction de leur fréquence d’horloge spécifique. Vous devriez préférer CPU Profiler à Time Profiler pour l’optimisation des CPU, car il est plus précis et pondère plus équitablement les logiciels consommant des ressources de CPU.

Ces cloches illustrent le moment où le compteur de cycles d’un CPU échantillonne la pile d’appels en cours. Les CPU à puce Apple sont asymétriques. Certains s’exécutent à une fréquence d’horloge plus lente, mais plus économe en énergie que d’autres. Les CPU individuels qui augmentent leur fréquence sont échantillonnés plus souvent, sans le biais de Time Profiler contre les CPU plus rapides. Nous utiliserons CPU Profiler pour savoir quelles parties de ma fonction de recherche binaire consomment le plus de cycles de CPU. Avec le navigateur de test de Xcode, vous pouvez lancer rapidement Instruments à partir d’un test unitaire avec un clic secondaire sur le nom du test et la sélection de son élément de profil. Dans ce cas, sélectionnons Profile searchCollection.

Instruments s’ouvre et présente le sélecteur de modèles. Je choisis CPU Profiler. Dans les paramètres de l’enregistreur, passons en mode différé pour réduire la surcharge et commençons l’enregistrement. Le mode Immédiat par défaut des profileurs permet de confirmer que vos interactions avec une app sont capturées. Pour un test automatisé sur la même machine qu’Instruments, nous voulons minimiser toute surcharge potentielle de nos outils en attendant que l’enregistrement s’arrête pour l’analyser. Les nouveaux documents dans Instruments sont souvent intimidants. La fenêtre est divisée en deux moitiés. La partie supérieure contient les pistes affichant l’activité sur la chronologie. Chaque piste peut contenir plusieurs voies avec des graphiques indiquant des niveaux ou régions.

Sous la chronologie se trouve la vue détaillée avec des informations récapitulatives sur la plage de dates inspectée. Tous les détails étendus sont affichés sur le côté droit. Pour vous orienter, vous trouverez la région où les recherches ont lieu dans la piste Points of Interest. Un clic secondaire sur la région permet de définir la plage d’inspection, limitant la vue détaillée ci-dessous aux données capturées dans l’intervalle de signpost. Cliquer sur la piste de processus de l’exécuteur de test affiche le profil CPU dans la vue détaillée, sous la chronologie. Cette vue affiche une arborescence d’appels des fonctions échantillonnées par le compteur de cycles de chaque CPU dans le test. Maintenez cette option enfoncée et cliquez sur la flèche à côté de la première fonction pour développer l’arborescence jusqu’au premier point où le nombre d’échantillons diverge significativement, ce qui est proche de la fonction de recherche binaire. Pour cibler la fonction de recherche binaire, cliquons sur la flèche à côté de son nom et sélectionnons l’élément Focus on Subtree. Chaque fonction est pondérée par le nombre d’échantillons multiplié par le nombre de cycles entre chacun d’eux. Cette arborescence d’appels montre de nombreux échantillons tirés des fonctions appelées par la recherche binaire pour traiter le type Collection. Ce témoin de protocole apparaît dans environ un quart de nos échantillons. Il existe des allocations et même des vérifications de tableau pour les types Objective-C. Nous pouvons éviter les surcharges des tableaux et des génériques en passant à un type de conteneur plus adapté au type de données que nous examinons. Testons le nouveau type Span. Span peut être utilisé à la place de Collection en cas de stockage contigu des éléments en mémoire, ce qui est courant pour de nombreux types de structures de données. Il s’agit en fait d’une adresse et d’un nombre de base. Cela empêche aussi la fuite de la référence mémoire en dehors des fonctions dans lesquelles elle est utilisée. Pour plus de détails sur Span, regardez « Improve memory usage and performance with Swift session ». L’adoption de Span ne nécessite que de changer les types du haystack en Span. L’algorithme ne change pas.

Cette petite modification rend la recherche quatre fois plus rapide. Mais cette version de la recherche binaire a toujours un impact sur mon app. J’aimerais voir si la vérification des limites de Span contribue à la surcharge. Pour approfondir notre analyse, passons à un nouvel outil, Processor Trace. À partir d’Instruments 16.3, Processor Trace collecte une trace complète de toutes les instructions exécutées par le processus de votre app dans l’espace utilisateur. Il révolutionne la façon dont vous pouvez mesurer les performances logicielles : il n’y a pas de biais d’échantillonnage et seulement 1 % d’impact sur les performances de votre app. Processor Trace nécessite des fonctionnalités CPU spécialisées qui ne sont disponibles que sur Mac et iPad Pro avec M4 ou sur iPhone avec A18. Avant d’aller plus loin, configurons l’appareil pour la traçabilité du processeur. Sur Mac, activez le réglage sous Confidentialité et sécurité et Outils de développement. Sur iPhone ou iPad, ce réglage se trouve dans la section Développeur. Pour une expérience optimale avec Processor Trace, essayez de limiter la traçabilité à quelques secondes. Contrairement à l’échantillonnage avec CPU Profiler, vous n’avez pas besoin de tout regrouper : une seule instance du code que vous souhaitez optimiser peut suffire. Exécutons Processor Trace sur la version Span de la recherche binaire. Notre test ne nécessite plus que quelques itérations. Pour profiler ce test, effectuons un clic secondaire sur l’icône de test dans la marge des numéros de ligne. Cela affiche le menu que nous avons déjà utilisé, mais cela peut être plus pratique que de changer de navigateur. Je sélectionne le modèle Processor Trace et lance l’enregistrement.

Comme Processor Trace doit traiter de nombreuses données, leur capture et leur analyse peuvent prendre du temps. Processor Trace configure le CPU pour enregistrer chaque décision de branchement. Le nombre de cycles et l’heure actuelle sont également enregistrés pour suivre le temps passé par le CPU dans chaque fonction. Instruments utilise ensuite les fichiers binaires exécutables de l’app et du system framework pour recréer un chemin d’exécution et annoter les appels de fonction avec les cycles écoulés et les durées. Nous limitons le temps de traçage, car même si le CPU enregistre le moins d’informations possible, cela peut se monter à des gigaoctets de données par seconde pour une application multithread. Maintenant que le document est prêt, zoomons pour inspecter les appels de fonction de la recherche binaire. La recherche n’occupe désormais qu’une infime partie de l’enregistrement. Elle se trouve donc dans la liste Regions of Interest de la vue détaillée sous la chronologie. Effectuons un clic secondaire sur sa ligne et sélectionnons Set Inspection Range and Zoom. Pour localiser le thread qui exécute la recherche binaire, effectuons un clic secondaire sur la cellule Start Thread et sélectionnons Pin Thread in Timeline.

Processor Trace ajoute un graphique de flamme d’appels de fonction à chaque piste de thread. Je fais donc glisser ce séparateur vers le haut pour lui faire de la place.

Processor Trace affiche visuellement l’exécution sous forme de graphique de flamme. Un graphique de flamme représente graphiquement le coût et les relations des fonctions : la largeur des barres représente le temps d’exécution de la fonction, et les lignes les piles d’appels imbriquées. Mais la plupart de ces graphiques montrent des données d’échantillonnage et le coût n’est qu’une estimation basée sur un nombre d’échantillons. Le graphique de flamme de la chronologie de Processor Trace est différent : il montre les appels effectués au fil du temps tels qu’ils auraient été exécutés sur le CPU. Les couleurs de chaque barre représentent les types de binaires dont ils proviennent : marron pour les system frameworks, magenta pour le runtime Swift et la bibliothèque standard, et bleu pour le code compilé dans le fichier binaire de l’app ou tout framework personnalisé. La première partie de cette trace montre la surcharge liée à l’émission de l’intervalle de signalisation. Zoomons sur le code de la recherche binaire vers la fin de la plage. Je maintiens la touche Option enfoncée, je clique et je fais glisser le curseur sur la chronologie pour zoomer.

Je peux sélectionner n’importe quel appel de fonction de la recherche binaire parmi les 10 itérations et définir la plage d’inspection et le zoom avec un clic secondaire. Voilà tout l’intérêt de Processor Trace. On peut voir tous les appels effectués par une seule fonction même si elle n’a duré que quelques centaines de nanosecondes. Nous pouvons zoomer encore plus, mais voyons le résumé Function Call sous la chronologie. Il montre les mêmes informations que la chronologie sous forme de tableau, avec le nom complet des fonctions appelées pendant de courtes périodes. Je vais trier ce tableau par cycles.

Mon hypothèse initiale selon laquelle la vérification des limites causait des ralentissements était fausse. Cette implémentation de la recherche binaire reste confrontée à des surcharges de métadonnées de protocole et ne peut pas inclure les comparaisons de nombres, ce qui représente un gros pourcentage du nombre total de cycles de la recherche. En effet, le paramètre générique Comparable n’est pas spécialisé pour le type d’éléments utilisés.

Comme mon code se trouve dans un framework lié par l’app, le compilateur Swift ne peut générer une version spécialisée de la recherche binaire que pour les types transmis par les appelants.

Lorsque cela entraîne des surcharges dans le code d’un framework, ajoutez l’annotation inlinable à la fonction de ce framework pour générer des implémentations spécialisées dans les exécutables binaires du client du framework.

Mais cette annotation peut compliquer l’analyse du code, car elle s’entremêle avec les appelants. Je préfère éviter de l’utiliser dans le cadre de test. Je vais donc spécialiser manuellement cette fonction pour le type Int utilisé par l’app et la tester, avec un nouveau nom. Le code perd beaucoup de généralité tout en devenant environ 1,7 fois plus rapide. L’optimisation doit se poursuivre, car la recherche binaire contribue toujours aux ralentissements de l’app. Il est plutôt étrange de passer tant de temps à optimiser une fonction que vous réévaluerez régulièrement et de collecter plus de données pour vous rendre compte qu’une autre partie du code affecte l’inefficacité. La recherche binaire spécialisée Span ne montre pas non plus d’appels de fonction inattendus dans Processor Trace. Nous devons donc déterminer comment s’exécute le code sur le CPU pour avancer. L’instrument CPU Counters permet d’identifier les goulots d’étranglement subis par le code exécuté sur un CPU. Avant d’utiliser à nouveau Instruments, visualisons mentalement le mode de fonctionnement d’un CPU. À la base, un CPU ne fait que suivre une liste d’instructions, modifie les registres et la mémoire, et interagit avec les périphériques.

En cours d’exécution, il doit suivre une série d’étapes, qui sont globalement classées en deux phases. D’abord, la livraison des instructions s’assure que le CPU a des instructions à exécuter. Puis, le traitement des instructions est responsable de leur exécution. Les instructions livrées sont récupérées et décodées en micro-opérations que le CPU peut exécuter plus facilement. La plupart sont décodées en une seule micro-opération, mais certaines impliquent plusieurs actions, comme l’émission d’une requête mémoire et l’incrémentation d’une valeur d’index. Pour traiter une micro-opération, elle est envoyée aux unités de mappage et de planification, qui l’acheminent et la distribuent. À partir de là, elle est affectée à une unité d’exécution, ou à l’unité de charge/stockage si elle a besoin d’accéder à la mémoire.

Si le CPU exécutait ces phases en série avant de pouvoir recommencer la récupération, le processus serait lent. C’est pourquoi les CPU à puce Apple sont en pipeline. Une fois qu’une unité a terminé son travail, elle passe à l’opération suivante. Chaque unité reste ainsi occupée.

La mise en pipeline et la création de copies supplémentaires des unités d’exécution permettent le parallélisme au niveau des instructions.

Cela diffère du parallélisme au niveau des processus ou des threads auquel vous accéderiez avec Swift Concurrency ou Grand Central Dispatch, où plusieurs CPU exécutent différents threads de système d’exploitation. Le parallélisme au niveau des instructions permet à un CPU de tirer parti des moments où les unités pourraient être inactives et d’utiliser efficacement les ressources matérielles, occupant ainsi toutes les parties du pipeline. Le code source Swift ne contrôle pas directement ce parallélisme, mais doit aider le compilateur à générer une séquence d’instructions adaptée.

Malheureusement, les séquences d’instructions parallélisables ne sont pas immédiatement intuitives en raison de l’interaction entre les unités d’un CPU. Chaque flèche entre les unités indique où les opérations peuvent se bloquer dans le pipeline, limitant le parallélisme disponible. Ce sont des goulots d’étranglement.

Pour déterminer celui qui correspond à une charge de travail, les CPU à puce Apple peuvent compter les événements intéressants dans chaque unité et d’autres caractéristiques des instructions exécutées. L’instrument CPU Counters lit ces compteurs pour en tirer des métriques globales. Cette année, nous avons ajouté des modes prédéfinis aux compteurs pour en faciliter l’utilisation. Instruments les utilise dans une méthodologie guidée itérative, appelée analyse des goulots d’étranglement, pour analyser les performances du code. Utilisons-la pour découvrir pourquoi la recherche binaire reste lente, bien qu’aucun appel de fonction ne subisse de surcharge apparente. L’instrument CPU Counters repose sur l’échantillonnage de la charge de travail. Nous devons donc revenir au cadre de test utilisé avec CPU Profiler pour mesurer à nouveau le débit.

Profilons un test de l’implémentation spécialisée de Span avec Instruments.

Sélectionnons le modèle CPU Counters.

Il existe désormais une configuration guidée avec des modes de mesure spécifiques.

Pour en savoir plus sur ces modes, cliquez sur l’icône d’information à côté de la sélection du mode. Allons-y.

Ce mode initial Goulots d’étranglement du CPU répartit le travail effectué par le CPU en quatre catégories qui représentent toutes les performances potentielles du CPU. Instruments affiche ces catégories sous forme de graphique à barres colorées empilées et de tableau récapitulatif dans la vue détaillée. Pendant l’enregistrement, Instruments collecte les données des compteurs CPU pour les threads utilisés dans le test et les convertit en pourcentages de goulot d’étranglement. Utilisons à nouveau la zone Points of Interest pour nous orienter, zoomer et sélectionner nos recherches.

Épinglons ensuite le thread qui exécute l’implémentation de la recherche binaire à la chronologie.

Le survol de la piste Goulot d’étranglement du CPU montre un pourcentage élevé dans le goulot d’étranglement ignoré. La vue détaillée ci-dessous montre les agrégations de métriques de la plage d’inspection. La sélection de la ligne Discarded Bottleneck affiche une description dans la vue détaillée étendue à droite. Instruments affiche aussi une remarque au-dessus du graphique dans la chronologie. Cliquer sur cette remarque affiche plus de détails en dessous. C’est utile, mais je ne sais toujours pas quelle partie de la recherche est responsable du goulot d’étranglement. Un clic secondaire sur la cellule Discarded Sampling sous la colonne Suggested Next Mode permet de profiler à nouveau la charge de travail avec un mode différent. Essayons. Ce mode diffère un peu du mode Goulots d’étranglement du CPU. Il collecte aussi des données de compteur, mais il configure également les compteurs pour déclencher l’échantillonnage. Les données d’échantillon sont limitées à l’instruction qui génère le travail ignoré. Pour les afficher, orientons-nous avec la région Points of Interest.

Sélectionnons ensuite la piste du processus de test et accédons à Instruction Samples sous la chronologie.

Il ne s’agit pas d’une pile d’appels, mais de l’instruction exacte qui cause le problème. Nous pouvons ouvrir la visionneuse de source en cliquant sur la flèche à côté du nom de la fonction pour afficher le code source échantillonné, car le CPU a suivi la mauvaise direction de branche. Ici, les comparaisons effectuées entre l’aiguille et la valeur du milieu sont prédites de manière incorrecte. Pour comprendre pourquoi ces lignes sources sont responsables de tant de mauvaises prédictions, familiarisons-nous davantage avec les CPU.

Les CPU sont sournois et exécutent les instructions dans le désordre. Les instructions semblent uniquement s’exécuter de manière séquentielle grâce à une étape de réorganisation supplémentaire qui a lieu à la fin. Autrement dit, les CPU anticipent et prédisent les instructions qui s’exécuteront par la suite. Les prédicteurs de branche responsables sont généralement précis, mais peuvent prendre des chemins incorrects sans modèle cohérent tiré de l’exécution précédente pour savoir si une branche sera utilisée ou non.

La boucle de l’algorithme de la recherche binaire comporte deux types de branches. La première condition va généralement jusqu’à la fin de la boucle. Elle est donc prédite correctement et n’apparaît pas dans l’échantillonnage. Mais la recherche de l’aiguille est une branche aléatoire. Il n’est donc pas étonnant que les prédicteurs aient du mal à l’identifier.

J’ai réécrit le corps de la boucle pour éviter les branches difficiles à prédire qui affectent le flux de contrôle. Le corps de l’instruction if attribue uniquement une valeur en fonction de la condition. Cela permet au compilateur Swift de générer une instruction de déplacement conditionnelle et d’éviter de créer une branche vers une autre instruction. Le retour d’une fonction ou la rupture d’une boucle basée sur une condition doit être implémenté avec une branche. J’ai donc aussi dû supprimer le retour anticipé. J’ai utilisé l’arithmétique non vérifiée pour éviter les branches qui mettraient fin au programme. C’est l’un des domaines où la micro-optimisation devient fébrile et facile à perturber, voire moins sûre et moins compréhensible. Pour effectuer une modification comme celle-ci, revenons au mode initial Goulots d’étranglement du CPU pour vérifier son impact sur le reste des goulots d’étranglement. J’ai déjà collecté une trace de la nouvelle recherche binaire sans branche, qui est environ deux fois plus rapide que la version avec branches. Elle est maintenant presque complètement bloquée sur Instruction Processing. Instruments indique que nous devons réexécuter la charge de travail avec le mode Instruction Processing.

Dans ce mode, des remarques recommandaient d’exécuter le mode L1D Cache Miss Sampling mode. Les échantillons d’échecs de cache prouvent que l’accès à la mémoire à partir du tableau explique pourquoi le CPU ne parvient pas à exécuter les instructions efficacement. Approfondissons notre connaissance des CPU et de la mémoire pour comprendre pourquoi.

Les CPU accèdent à la mémoire via une hiérarchie de caches qui accélèrent grandement les accès répétés à la même adresse, voire les modèles d’accès prévisibles. Cela commence par les caches L1 situés dans chaque CPU. Ils ne stockent pas beaucoup de données, mais offrent l’accès le plus rapide à la mémoire. Plus lent, le cache L2 se trouve en dehors des CPU et offre beaucoup plus de marge. Les requêtes qui passent à côté des deux caches et qui doivent accéder à la mémoire principale deviennent 50 fois plus lentes que le chemin rapide. Ces caches regroupent la mémoire en segments de 64 ou 128 octets appelés lignes de cache : même si une instruction ne demande que 4 octets, les caches extraient plus de données, car les instructions suivantes peuvent avoir besoin d’accéder à d’autres octets à proximité.

Voyons comment cela affecte l’algorithme de la recherche binaire. Dans cet exemple, les lignes bleues sont les éléments du tableau, tandis que les capsules grises sont les lignes de cache du CPU.

Le tableau commence complètement hors du cache. La première comparaison génère une ligne de cache et plusieurs éléments dans le cache de données L1. Mais la comparaison suivante subit un échec de cache. Et les itérations suivantes manquent également le cache. Cela continue jusqu’à ce que la recherche cible une région de la taille d’une ligne de cache. La recherche binaire se révèle être un cas pathologique pour la hiérarchie de la mémoire du CPU.

Mais si nous tolérons de réorganiser les éléments pour qu’ils soient plus en accord avec le cache, nous pouvons placer les points de recherche sur la même ligne de cache. C’est ce qu’on appelle un agencement Eytzinger, d’après un généalogiste autrichien du 16ème siècle qui organisait les arbres généalogiques de cette façon. Cette optimisation générale implique des conséquences significatives. En améliore la vitesse de recherche au détriment de la vitesse de traversée dans l’ordre, cette opération manque maintenant le cache. Revenons au premier exemple de recherche binaire pour montrer comment réorganiser un tableau trié en un agencement Eytzinger. En commençant par l’élément du milieu comme racine, nous allons modéliser l’opération de recherche binaire sous forme d’arborescence. Les points médians seront des nœuds descendants. Un agencement Eytzinger est organisé comme la traversée en largeur de cette arborescence.

Les éléments proches de la racine de l’arborescence sont agencés de manière plus dense et sont plus susceptibles de partager des lignes de cache. La recherche du nombre 5 passe désormais les trois premières étapes dans la même ligne de cache. Les nœuds terminaux sont triés à la fin du tableau, entraînant un échec de cache inévitable.

J’ai enregistré une trace Goulots d’étranglement du CPU de la recherche binaire Eytzinger, qui montre qu’elle est deux fois plus rapide que la recherche sans branche. Mais cet exemple met en évidence un point intéressant : elle reste techniquement bloquée sur Instruction Processing. Nous avons adapté l’implémentation au cache, mais la charge de travail reste intrinsèquement liée à la mémoire.

Suivez les performances pour savoir quand arrêter et optimiser d’autres parties du code de votre app, car notre recherche n’affecte plus les performances du chemin critique. Au cours de ce processus, nous avons considérablement amélioré le débit de recherche. Tout d’abord, avec CPU Profiler, nous l’avons considérablement accéléré en passant de Collection à Span.

Ensuite, Processor Trace nous a montré les surcharges des génériques non spécialisés. Enfin, nous avons considérablement augmenté les performances avec quelques micro-optimisations, guidées par l’analyse des goulots d’étranglement. Globalement, la fonction de recherche est devenue 25 fois plus rapide avec Instruments. Pour obtenir ces accélérations, nous avons commencé avec le bon état d’esprit, en utilisant des outils pour confirmer nos suppositions et nous faire une idée du coût des abstractions. Nous avons successivement appliqué d’autres outils pour trouver les surcharges inattendues. Elles sont tout aussi faciles à traiter qu’à ignorer si elles ne sont mesurées. Après le traitement des surcharges, nous avons ciblé les optimisations axées sur les goulots d’étranglement du CPU. Nous avons pris davantage conscience des fonctionnalités du CPU qui sont considérées comme acquises. Cet ordre était important : nous devons nous assurer que les outils axés sur le CPU ne sont pas perturbés par d’autres surcharges d’exécution de logiciels.

Pour en faire de même avec vos apps, collectez des données et suivez les pistes avec un état d’esprit axé sur les performances. Écrivez des tests permettant de mesurer les performances de manière répétée avec ces instruments. Donnez votre feedback ou posez des questions sur l’utilisation des outils sur les forums. Regardez les sessions que j’ai mentionnées et la session de la WWDC24 sur les performances de Swift pour vous faire une idée plus précise du coût des abstractions de Swift. Pour mieux comprendre comment les CPU exécutent votre code, lisez le guide d’optimisation des CPU à puce Apple. Merci de votre attention. J’espère que vous vous amuserez à trouver des aiguilles d’optimisation dans les bottes de foin de votre code avec Instruments.