(Statique) Sélection de conteneurs optimaux dans les programmes C ++

Bonjour Aujourd'hui, je voudrais reparler de l'analyse statique. Et encore une fois à propos de C ++. Seulement, contrairement à PVS-Studio, nous ne rechercherons aucune erreur dans nos programmes (bien qu'ils ne recherchent pas seulement des erreurs), mais des endroits qui ne sont pas écrits de manière optimale. Et l'un de ces endroits est de choisir un conteneur pour les données du programme. Si je vous intéresse, alors bienvenue au chat!

Le problème

Au CoreHard 2018 Autumn (une très bonne conférence, venez), j'ai parlé de la façon dont les compilateurs C ++ n'optimisent pas bien pour le moment. Et l' une de mes plaintes était que les compilateurs ne peuvent pas optimiser l'utilisation des conteneurs dans nos programmes. Regardons quelques exemples de code.

void foo() { std::vector<int> v(42); } 

Il semblerait que dans un cas aussi simple, le compilateur devrait être en mesure d'optimiser cette fonction et de simplement jeter une déclaration de variable de type std :: vector, car à partir de C ++ 14, le compilateur est autorisé à supprimer les allocations de mémoire dynamique, mais pas le compilateur. La raison en est qu'à l'heure actuelle, un seul compilateur C ++ implémente l'optimisation pour supprimer les allocations dynamiques - Clang. Jusqu'à présent, tous les autres compilateurs ne savent pas comment procéder. Mais même Clang peut le faire dans un nombre limité de cas.

Dans ce cas, nous pourrions remplacer std :: vector par std :: array, à condition que la taille du vecteur sélectionné ne soit pas trop grande, car nous pourrions ne pas avoir assez de pile pour un tel remplacement. Un tel remplacement supprimera une allocation de mémoire assez chère au tas, et le plus est que lors de l'utilisation de std :: array, le compilateur peut déjà lancer std :: array de la fonction!

Si nous parlons d'optimisation des performances, nous proposons de considérer l'exemple suivant:

 void foo() { std::vector<int> v; for(int i = 0; i < 42; ++i) { v.insert(v.begin(), 42); } for(const auto val : v) { std::cout << val << ' '; } } 

Dans ce cas, nous voyons l'utilisation d'une opération extrêmement inefficace dans le cas de std :: vector - insertion au début du conteneur. Tous les programmeurs C ++ savent que c'est extrêmement mauvais à faire, car cela fait que tous les éléments se déplacent à chaque fois, ce qui entraîne des coûts importants pour la copie / le déplacement. Il serait beaucoup plus agréable dans ce cas de le remplacer par std :: list, qui ne se soucie pas de l'endroit où l'insertion a lieu, ou std :: deque (bien que dans ce cas, vous puissiez clairement voir que vous n'avez pas seulement besoin d'utiliser insert. Mais ce n'est qu'un exemple, pas plus :)

Regardons un autre exemple de code:

 void foo() { std::list<int> v; for(int i = 0; i < 3; ++i) { v.push_front(i); } for(const auto val : v) { std::cout << val << ' '; } } 

Dans ce cas, nous pouvons remarquer que nous pouvons remplacer sans douleur std :: list (oui, je sais que peu de gens l'utilisent) par std :: forward_list. Dans ce cas, dans ce cas, nous ne perdrons absolument rien, mais nous obtiendrons des économies de mémoire. Naturellement, le compilateur ne fait pas une telle optimisation maintenant.

Une astuce similaire peut être effectuée dans l'exemple suivant:

 void foo() { std::deque<int> v; for(int i = 0; i < 3; ++i) { v.push_back(i); } for(int i = 0; i < 3; ++i) { std::cout << v.back() << ' '; v.pop_back(); } } 

Ici, nous pouvons voir que ce dont nous avons vraiment besoin n'est pas std :: deque, mais std :: stack. Cela ne peut pas être appelé optimisation, car std :: stack est un adaptateur et, par défaut, il utilise std :: deque inside (sauf si l'utilisateur spécifie le contraire). Ici, nous pouvons parler davantage de l'optimisation sémantique, c'est-à-dire simplifier le code pour comprendre. De mon point de vue, c'est également important. Si vous demandez: «Peut-être qu'un tel remplacement donne également un gain de performances?», Je répondrai «Peut-être. Consultez les détails de l'implémentation dans votre version de la bibliothèque standard. »

Eh bien, je pense qu'il y a suffisamment d'exemples. Chacun d'entre vous peut également en proposer plusieurs.

Moyens utilisés

Pour implémenter l'analyseur statique, j'ai utilisé Clang Static Analzyer (CSA) et Clang Tidy, qui font partie du package LLVM. J'ai choisi ces outils, car je les considère comme les plus prometteurs parmi les outils ouverts pour l'analyse statique. De plus, Clang fournit l'un des analyseurs C ++ de la plus haute qualité que les autres analyseurs statiques ne peuvent pas se vanter (à moins bien sûr qu'ils utilisent libclang).

CSA et Clang Tidy sont des analyseurs statiques, qui font tous deux partie de LLVM. Quelle est la différence? La différence est que Clang Tidy est conçu pour écrire des vérifications simples, qui consistent essentiellement à trouver une sorte de modèle sur l'arbre de syntaxe abstraite, à afficher une sorte d'avertissement, et éventuellement à le remplacer automatiquement par une autre. Vous pouvez en savoir plus sur Clang Tidy ici .

CSA est conçu pour écrire des vérifications plus «sérieuses» et gourmandes en ressources (tant du point de vue de l'implémentation que du temps d'exécution / mémoire dépensée). Là, par exemple, un mécanisme d'exécution symbolique est disponible.

J'ai décidé de mettre en place le chèque en CSA, car cela ne me semble pas banal, d'ailleurs, à l'avenir ça va devenir de plus en plus dur. Et il a été décidé de passer par Clang Tidy, car cet analyseur statique a de nombreuses intégrations avec divers IDE.

Comment nous allons (essayer) de résoudre les problèmes

Pour commencer, cela vaut la peine d'introduire quelques restrictions assez fortes, qui sont principalement liées au fait qu'il ne s'agit pour l'instant que d'un prototype:

• Analyse uniquement au niveau des fonctions; Cette limitation signifie qu'il n'y aura pas d'analyse entre les fonctions, ainsi qu'entre les unités de traduction. La restriction de l'analyse entre les fonctions a été imposée pour simplifier la mise en œuvre de cette analyse et, à l'avenir, elle peut être relativement facilement corrigée en exécutant une analyse statique pour l'ensemble de l'unité de traduction, et pas seulement pour chaque fonction. La restriction à l'analyse entre les unités de traduction est imposée par les restrictions existantes dans le CSA, qui seront bientôt fixées (les commits se déversent déjà en amont);
• Prise en charge d'un nombre limité de conteneurs uniquement. Ceci est relativement facilement résolu à l'avenir en ajoutant de nouvelles règles pour les nouveaux conteneurs.
• Utilisez pour l'analyse uniquement un arbre de syntaxe abstraite. Étant donné que pour le prototypage, il s'agit du type d'analyse le plus simple. Pour des résultats plus précis, bien sûr, vous pouvez essayer d'utiliser au moins une exécution symbolique, mais cette méthode a ses inconvénients. Vous pouvez en savoir plus sur les méthodes ici .

Maintenant, le prototype implémente l'algorithme simple suivant:

• Tout d'abord, sur l'arbre de syntaxe abstraite, nous trouvons les sommets qui sont responsables de la déclaration des variables de type conteneur que nous prenons en charge.
• Ensuite, nous trouvons les opérations liées à ces conteneurs, les classons et enregistrons ces informations dans un cache temporaire.
• Après avoir atteint la fin de la fonction, nous analysons les statistiques collectées et, sur la base de règles prédéfinies, émettons une recommandation sur l'utilisation d'un conteneur.

La classification des opérations de conteneurs pour le moment est la suivante (sera élargie à l'avenir):

• Ajoutez un élément en haut du conteneur.
• Ajout d'un élément au milieu du conteneur.
• Ajout d'un élément à la fin du conteneur.
• Suppression d'un élément au début du conteneur.
• Retrait d'un élément du milieu du conteneur.
• Retrait d'un élément de la fin du conteneur.

Le classement pour le moment est incomplet et même sur cette liste ne fonctionne pas correctement. Par exemple, l'opération d'insertion, même si elle est effectuée au début, l'analyseur se classe comme une insertion au milieu, bien qu'en fait elle ne l'est pas du tout.

Lutter contre les faux positifs

Dans toute analyse statique, les faux positifs sont le principal casse-tête. S'il y en a trop, les messages utiles sont perdus à la poubelle. Par conséquent, dans ce cas, vous devez agir de manière très conservatrice et émettre des avertissements uniquement dans les cas où nous sommes vraiment confiants dans nos diagnostics et pouvons tout à fait dire que quelque chose ne va vraiment pas à un endroit du code.

Si nous parlons des optimisations du compilateur, c'est encore plus triste là-bas - les optimisations appropriées ne peuvent pas changer le comportement d'un programme selon la norme C ++ (sinon, un tel optimiseur ne vaut rien). Et l'optimisation ne doit pas non plus introduire de pessimisation :) Donc, ici, vous devez être beaucoup plus prudent dans vos décisions.

Dans cet analyseur, cette lutte a entraîné le fait que si l'analyseur constate qu'une opération non prise en charge est en cours, l'analyse de ce conteneur est désactivée.

Inconvénients et solutions possibles

Il y a plusieurs problèmes avec cette méthode.

Le premier problème est que pour l'analyseur pour le moment, toutes les branches du code sont également probables. Plus précisément, il ne connaît même pas les différentes branches de l'exécution du code.
Cela se traduit par des problèmes d'analyse pour quelque chose comme ce code:

 void foo(int* ptr, std::vector<int>& v) { if(ptr == nullptr) { v.insert(v.begin(), 42); } else { v.push_back(84); } } 

Très probablement, dans notre application, ces branches de code n'ont pas des probabilités égales d'exécution, car dans le monde réel, un pointeur indique généralement quelque chose de normal, et non nullptr. Dans le même LLVM, il existe des heuristiques statiques sur ce score. Par exemple, il prend en compte le cas ci-dessus en comparant les pointeurs avec nullptr, et en comparant entre eux l'égalité des valeurs de deux variables avec une virgule flottante, et quelques autres cas intéressants. Mais cela ressemble de plus en plus à des béquilles, et de mon point de vue, la vraie solution à ce problème est d'ajouter une analyse dynamique ou une instrumentation.

Le deuxième problème est le manque de prise en charge des conteneurs personnalisés. Nous vivons dans le monde du C ++, ils aiment rouler ici (laissons les discussions sur les raisons de ce phénomène pas toujours mauvais en dehors du cadre de cet article) tout, y compris nos conteneurs. Les exemples incluent le même LLVM, LibreOffice et bien d'autres. À cet égard, la question se pose - comment analyser les conteneurs ne provenant pas de la bibliothèque STL? Après tout, je voudrais inclure une analyse pour autant de conteneurs que possible.

Il existe différentes manières de résoudre le problème.

La première est que l'utilisateur annote ses conteneurs d'une manière ou d'une autre (un type spécial de commentaire, des attributs C ++, autre chose). Le problème avec cette méthode est que nous devons comprendre comment annoter en général, quelles informations nous avons besoin pour une analyse qualitative. Un autre problème peut être la modification du code des conteneurs eux-mêmes, ce qui n'est pas toujours possible.

La deuxième méthode offre à l'utilisateur un mécanisme pour écrire ses propres règles. Pour le moment, les règles de l'analyseur sont cousues dans le code source de l'analyseur lui-même, et si l'utilisateur veut ajouter ses propres règles, il devra alors télécharger le code source de l'analyseur, l'assembler, comprendre comment écrire des chèques, écrire, reconstruire, etc. Vous pouvez fournir à l'utilisateur un moyen de définir ses contrôles sur certains DSL, où l'utilisateur écrit uniquement des contrôles pour ses conteneurs, et l'analyseur est engagé dans l'ensemble de la routine. Je considère cette méthode comme plus prometteuse que la précédente.

De plus, le remplacement automatique de conteneur n'est pas pris en charge, car cette fonctionnalité n'est pas dans CSA (mais elle est dans Clang Tidy). Mais dans les cas difficiles, l'exécution de la correction automatique n'est pas toujours une tâche triviale et l'analyseur fonctionne plus probablement en mode semi-manuel.

Applications possibles

Je vois plusieurs applications pour ce type d'analyse:

1. Comme un analyseur statique. Tout est simple ici - un autre test d'analyse statique, que vous exécutez à votre guise (avec vos mains, dans l'EDI automatiquement pendant le développement, sur CI, etc.), où vous recevrez probablement un indice que quelque part vous pourriez ramasser un conteneur et mieux.
2. Comme l'optimisation dans le compilateur. Dans certains cas, nous pouvons garantir que le remplacement du conteneur n'affectera certainement pas les performances. Par exemple, remplacer std :: vector pour les petites tailles connues au moment de la compilation par std :: array ou remplacer std :: list par std :: forward_list lorsque nous n'avons pas besoin de connexion binaire et que nous ne prenons pas la taille de la liste. Le compilateur pourrait remplacer les conteneurs par des conteneurs plus optimaux à notre insu, comme il le fait déjà pour un très grand nombre de choses.
3. Comme un analyseur dynamique. C'est la direction qui me semble la plus prometteuse pour ce type d'analyse. En effet, à l'aide de connaissances sur le profil d'exécution du programme, nous pouvons, par exemple, obtenir pour nous des informations aussi importantes que les probabilités d'exécution de chaque branche de code. Et cela est nécessaire pour une évaluation plus précise. Et avec une telle analyse, vous pouvez déjà penser dans le sens de l'intégration avec PGO ...

Il convient également de noter que cette méthode est bien sûr applicable non seulement aux programmes C ++. J'aimerais vraiment voir ce genre d'analyse / optimisation statique dans le compilateur et pour d'autres langages de programmation. Par exemple, l'analyseur statique SAP pour ABAP sait déjà comment effectuer une analyse d'optimalité statique à un niveau de base, ce qui est une bonne nouvelle. Si vous connaissez des projets similaires pour d'autres langages de programmation - écrivez dans les commentaires et j'ajouterai à l'article!

Travailler dans des directions similaires

Pour le monde C ++, je n'ai trouvé de tels analyseurs nulle part. Pour le monde ABAP, j'ai mentionné l'analyseur ci-dessus, qui peut trouver des opérations inefficaces pour une partie des conteneurs standard, mais à ma connaissance, une analyse statique très simple y est implémentée.

Un travail beaucoup plus intéressant est Chameleon - un analyseur dynamique pour Java, qui est très intelligemment fait. Ils ont légèrement modifié la machine virtuelle Java et, pendant le fonctionnement, ils collectent diverses statistiques sur l'utilisation des conteneurs et, en fonction du profil de charge actuel, ils sélectionnent certains conteneurs et les remplacent automatiquement pendant le fonctionnement. Malheureusement, les sources sont fermées et il n'y a aucune chance de les obtenir (j'ai essayé).

Je recommande également de regarder différents travaux (il y en a beaucoup) sur SETL . Dans ces documents, les auteurs ont également souvent posé des questions sur la sélection automatique du conteneur.

Les références

1. Implémentation actuelle sur github
2. C ++ Russia 2017: Yuri Efimochev, clang-tidy: a journey inside C ++ Abstract Syntax Tree
3. Caméléon: sélection adaptative des collections
4. Guide de l'analyseur statique Clang
5. Discussion en russe sur le développement de compilateurs dans Telegram. Si vous êtes intéressé, entrez, c'est très intéressant là-bas. Faites juste attention au déluge - ils le puniront immédiatement :)

Au lieu d'une conclusion, je voudrais me concentrer sur le fait qu'il ne s'agit pour l'instant que d'un prototype et qu'il a trop de «trous» dans la mise en œuvre. Dans cet article, je veux juste partager avec vous l'idée d'une telle analyse et sa vulgarisation. Eh bien, peut-être que quelqu'un sera intéressé par ce sujet et qu'il y aura un désir de se connecter au projet - je ne serai que heureux! De plus, vous pouvez toujours récupérer cet analyseur à votre place pour l'essayer sur vos exemples de test.

Si vous avez quelque chose à compléter le matériel, avez rencontré une tâche similaire, ou avez simplement des informations qui peuvent être utiles sur ce sujet - n'hésitez pas à partager ces informations dans les commentaires.

Merci de votre attention!