URL: https://linuxfr.org/users/steckdenis/journaux/performances-des-processeurs-intel-et-optimisation Title: Performances des processeurs Intel et optimisation Authors: steckdenis Date: 2013年05月14日T17:11:59+02:00 License: CC By-SA Tags: optimisation, gcc et performance Score: 61 Bonjour, Je préviens d'abord que ce journal aborde des sujets assez pointus et n'intéressant peut-être pas grand-monde. N'étant pas un expert en microprocesseurs et optimisation, ce journal sera très certainement incomplet et incorrect par endroits. Je vais vous parler d'une aventure très spéciale que j'ai vécue avec mon microprocesseur, alors que je voulais améliorer un morceau de code sur lequel je travaille depuis quelques temps. Présentations ============= Je ne pense pas être l'objet central de ce journal, mais pour être complet, je précise tout de même que je suis un étudiant en 2e année de « Sciences Informatiques », comme on appelle ça en Belgique (j'étudie à l'Université Libre de Bruxelles). Le logiciel que je vais décrire est une base de donnée spécifique à un de mes projets personnels, codée en C++. Le processeur ------------- * [Intel Core i5 3230M](http://ark.intel.com/products/72056), 35 W * Double coeur avec hyper threading * 2,6 Ghz de base, 3,2 Ghz turbo sur un coeur, 3,1 Ghz turbo sur les deux coeurs (mon échantillon maintient cette vitesse toute la journée, chargé à 100%, si je le lui demande) * Cache L1 : 128k (je dirais donc 32k instructions, 32k données par coeur) * Cache L2 : 512k (donc 256k par coeur) * Cache L3 : 3 Mio (partagé par les deux coeurs si je me rappelle bien) Le tout épaulé par 6 Gio de RAM DDR3 1600 Mhz double canal dans un portable Dell Inspiron 15R Special Edition que je vous recommande d'ailleurs plus que chaudement : j'ai eu le mien à 610€ (promo saisonnière), c'est un 15 pouces avec écran mat FullHD, le processeur que je viens de décrire, et une carte graphique AMD Radeon HD 7720M qui peut s'utiliser en parallèle de la carte Intel via l'équivalent d'Optimus chez AMD qui a l'avantage d'être supporté sous Linux (mais ça consomme beaucoup et il faut chipoter). Le logiciel ----------- Dans le cadre d'un projet personnel qui n'est pas encore assez avancé pour que j'en parle, j'ai du développer une base de donnée répondant aux critères suivants : * Association de valeurs à des couples (objet, clé) (donc par exemple A.B = C) * Les objets, les attributs et les valeurs sont tous des entiers (donc l'exemple devient 34.128 = 21) * Ça doit être rapide, et par rapide je veux dire capable de lire plusieurs millions de valeurs par seconde (donc toute base de donnée externe, SQL ou non, est disqualifiée) * Scalable (aucun algorithme dont la complexité est non-constante en fonction du nombre d'entrées dans la base n'est accepté) Ça fait déjà deux ans que je travaille sur le volet base de donnée, même si elle ne pèse que 314 SLOC (source lines of code), et tous ces points sont respectés. Je compte publier cette base de donnée sous licence libre quand tout le projet sera terminé, ou avant, suivant les circonstances et l'intérêt que pourrait avoir une publication à son sujet. Quand ralentir accélère ======================= Maintenant que toutes ces présentations sont faites, et j'espère ne pas avoir ennuyé trop de monde, je peux passer aux choses sérieuses : les timings. Jusqu'à il y a peu, la base de donnée était parfaitement fonctionnelle, mais vraiment pensée pour aller le plus vite possible. Par exemple, elle n'était pas thread-safe : si deux threads y accédaient en écriture en même temps, tout pouvait exploser. Dans cet état, la base de donnée lisait 65536*12 = 786432 couples (objet, clé) en **3.7 millisecondes**. Cela fait 213 millions de couples (objet, clé) lus par seconde. En comptant que mon processeur passera en mode turbo entre le début et la fin du benchmark, sa fréquence moyenne se situe donc entre 2,6 Ghz et 3,2 Ghz. Le nombre de cycles d'horloge par lecture est donc compris entre 15,0 et 12,2. Pendant ce temps, 12,6 Mio sont lus depuis un fichier mappé en mémoire et stocké dans un tmpfs (ça fait quand-même 3,5 Gio/s, le contrôleur RAM de mon CPU peut lire jusqu'à 25 Gio/s, et le benchmark lit les données assez séquentiellement). Les valeurs absolues de ces nombres ne sont pas à considérer trop sérieusement, le benchmark étant assez court du fait que la base de donnée doit rester assez petite. L'important sera de voir leur évolution au fil des modifications. Comme le projet en général aura besoin d'accéder à la base de donnée depuis plusieurs threads, il m'a un jour fallu me rendre à l'évidence que cette base de donnée doit être thread-safe. Comme la base de donnée sera beaucoup plus souvent lue que modifiée (grosso-modo, elle sera lue comme de la mémoire, d'ailleurs c'est un fichier mappé en mémoire), j'ai opté pour un [Readers-Writer lock](https://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock), qui permet à plusieurs lecteurs d'accéder en même temps à la base de donnée, mais qu'à un seul thread d'écriture. Quand une écriture est en cours, il faut qu'aucun lecteur ne soit en train d'accéder à la base de donnée. En utilisant l'implémentation Posix Threads (bibliothèque pthreads) de ce lock, j'ai eu des performances vraiment mauvaises, mon benchmark prenait de l'ordre de 80 millisecondes pour se compléter. En utilisant une version personnelle de ces locks, optimisée pour mon cas d'utilisation, j'ai pu ramener ce temps à **38 millisecondes** environ. Notez bien que le benchmark n'utilise qu'un seul thread ! Il mesure donc le temps perdu dans la gestion du lock alors qu'il n'y a aucune contention. La programmation lockless ------------------------- J'ai donc du trouver une autre solution, pour garder ma base de donnée rapide. L'idéal aurait été de faire se compléter le benchmark en entre 3.2 millisecondes et 38 millisecondes, les deux extrémités. J'ai donc passé deux mois à m'intéresser aux algorithmes dits [Lockless](http://preshing.com/20120612/an-introduction-to-lock-free-programming) (c'est assez spartiate). Le code d'algorithmes lockless n'est pas très compliqué. On programme en fait sans utiliser ni mutex, ni condition d'arrêt, ni rien de ce genre. Un thread ne peut jamais bloquer un autre. La seule chose qu'on fait est coder comme si un seul thread exécuterait le code, tout en sachant qu'ils seront plusieurs. À chaque ligne de code, il faut donc se demander ce qui pourrait se passer si deux threads devaient l'exécuter en même temps. Pour nous aider, les microprocesseurs x86, ainsi que d'autres sans doutes, disposent d'instructions dites « atomiques ». Par exemple, pour incrémenter une valeur, il faut lire l'ancienne valeur, lui ajouter 1, puis écrire la nouvelle valeur. Deux threads peuvent lire en même temps l'ancienne valeur, l'incrémenter en même temps (ils obtiennent tous les deux la même nouvelle valeur), et l'écrire tous les deux. Au final, la valeur n'aura été incrémentée que de 1, et non de deux. Il existe néanmoins une instruction d'incrément atomique, qui bloquera l'accès à la variable par les autres threads (ou processeurs dans ce cas-ci) tant que l'incrément n'est pas complet. Ces instructions sont accessibles avec GCC et Clang en utilisant les fonctions de la famille [__sync](http://gcc.gnu.org/onlinedocs/gcc-4.8.0/gcc/_005f_005fsync-Builtins.html#g_t_005f_005fsync-Builtins). Par exemple, pour incrémenter une variable atomiquement, je peux faire ```c int var = 0; int incrementer() { return __sync_fetch_and_add(&var, 1); // Retourne la valeur précédente de var } ``` Si var permet d'indicer un tableau, plein de threads peuvent appeler cette fonction incrementer() en même temps, et ils vont tous recevoir une case différente du tableau, dans laquelle ils pourront écrire ce qu'ils veulent. Base de donnée lockless ----------------------- J'ai donc truffé mon code de fonctions __sync. J'attire bien votre attention sur le fait que je n'ai fait que rajouter du code. J'ai changé des `variable++` en `__sync_fetch_and_add(&variable, 1)`, et j'ai rajouté des boucles (par exemple : exécuter quelque-chose, voir si un autre thread ne nous est pas passé sous le nez, et recommencer si c'est le cas). Après avoir beaucoup réfléchi, noté, transpiré, relu et testé (quand c'était possible), j'ai finalement obtenu une base de donnée qui marche et qui ne plante pas quand on y accède depuis plusieurs threads. Ne va-t-elle jamais planter ? Je ne sais pas, la programmation lockless n'est pas supportée par des choses comme helgrind, et je n'ai pas les compétences pour prouver qu'il n'y aura jamais le moindre problème. Je me suis donc juste assuré que je pouvais laisser tourner mes tests pendant des heures sans qu'ils ne plantent. Les performances ? Et bien, il faut **1.66 millisecondes** pour compléter le benchmark, 474 millions de valeurs lues à la seconde, 6 cycles d'horloge par valeur. Là maintenant, vous comprenez ce qui m'a motivé à écrire ce journal : en rajoutant du code, des instructions lourdes, qui synchronisent les coeurs de mon CPU, j'ai drastiquement accéléré mon benchmark, alors même qu'il n'est que mono-thread et qu'il aurait donc du ralentir à cause de ces nouvelles instructions ! Questions quant à l'optimisation ================================ Cette accélération de ma base de donnée, qui tourne maintenant deux fois plus vite, mais fait quand-même me poser des questions quant à l'optimisation logicielle. J'ai regardé le code assembleur généré par GCC 4.8, et les différences sont minimes (instructions remplacées par d'autres normalement plus lentes, ajout d'instructions). Même l'alignement de mon code est toujours le même. Aucune structure de donnée n'a changé. Je me demande donc comment ça se fait qu'ajouter ces instructions accélère le code à ce point. Surtout que mon benchmark se porte sur la lecture de la base de donnée, c'est à dire quelque-chose auquel je n'ai quasiment pas touché, les synchronisations entre threads ne s'appliquant que quand on écrit. Donc mes modifications, au lieu de ralentir ou de laisser tel quel un code auquel je n'ai quasiment pas touché, l'ont en fait drastiquement accélérer. Les processeurs modernes sont très complexes, d'ailleurs mon i5 a vraiment des performances époustouflantes sur certains points (j'ai indiqué plus haut que mon benchmark nécessite 13 cycles d'horloge par lecture sur ce CPU, alors qu'il en fallait 40 sur un AMD E-350 plus lent), est-il donc encore possible d'optimiser pour eux ? Si ça se trouve, ces instructions permettent au processeur de mieux gérer sa mémoire cache, ou alors on évite des latences, ou alors le processeur exécute des choses en avance (vu que le code gère maintenant tous ces cas bizarres de modifications parallèles). Je n'en sais rien donc rien, et j'invite toute personne ayant une idée de ce qui peut se passer à laisser un commentaire. Je me demande également si les compilateurs ne pourraient pas un jour tirer parti de ces bizarreries, surtout quand on voit les gains obtenus. Notes ===== Tous les tests ont été réalisés avec le gouverneur cpufreq « userspace » et la fréquence du processeur fixée à 2,6 Ghz. La documentation d'Intel indique que cette fréquence, la maximum possible, peut être augmentée vers la fréquence turbo. Cela arrive après un court délai qui semble néanmoins plus long que le temps que met le benchmark pour s'exécuter, car l'utilitaire turbostat n'indique aucun passage en fréquence turbo lors des benchmarks. J'ai également re-fait les tests avec la fréquence calée sur 2,5 Ghz, et les durées sont à peine plus longue, et toujours dans le même rapport. Niveau précision, j'utilise `gettimeofday`, qui retourne des valeurs en microsecondes. Quelques tests montrent que mon ordinateur peut mesurer des temps précis de l'ordre de la milliseconde ou du dixième de milliseconde. Plusieurs itérations du benchmark sont bien entendu exécutées, et la moyenne des résultats est prise. L'écart-type n'est jamais grand, mes tests donnent par exemple 1.666 msec, 1.668 msec, 1.663 msec, 1.699 msec, 1.667 msec, etc. Pour ceux qui se demandent à juste titre comment je peux lire une base de donnée en 10 cycles d'horloge : la base de donnée a été pensée pour que la lecture soit grosso-modo équivalente à cette ligne de C : ```c int get(int **db, int object, int key) { return db[object][key]; } ```

AltStyle によって変換されたページ (->オリジナル) /