Il y a quelques années, je faisais partie d’un panel qui interviewait des candidats à un poste relativement senior de programmeur C intégré.
L’une des questions standard que j’ai posées concernait les techniques d’optimisation. J’ai été assez surpris que certains des candidats n’aient pas eu de réponses.
Donc, dans l’intérêt de dresser une liste pour la postérité – quelles techniques et quelles constructions utilisez-vous habituellement pour optimiser les programmes C?
Réponses à l’optimisation de la vitesse et de la taille acceptées.
Tout d’abord, n’optimisez pas trop tôt. Il n’est pas rare de passer du temps à optimiser soigneusement une partie du code pour constater que ce n’était pas le goulot d’étranglement que vous pensiez devoir être. Ou, pour le dire autrement “Avant de faire vite, faites le fonctionner”
Vérifiez s’il existe une option d’optimisation de l’algorithme avant d’optimiser le code. Il sera plus facile de trouver une amélioration des performances en optimisant un algorithme médiocre qu’en optimisant le code, pour ensuite le jeter à la poubelle lorsque vous le modifiez.
Et déterminez pourquoi vous devez optimiser au départ. Qu’essayez-vous de réaliser? Si vous essayez, par exemple, d’améliorer le temps de réponse à certains événements, déterminez s’il est possible de modifier l’ordre d’exécution afin de minimiser les durées critiques. Par exemple, lorsque vous essayez d’améliorer la réponse à une interruption externe, pouvez-vous effectuer une préparation dans le temps mort entre les événements?
Une fois que vous avez décidé d’optimiser le code, quel bit optimisez-vous? Utilisez un profileur. Concentrez d’abord votre attention sur les domaines les plus utilisés.
Alors, que pouvez-vous faire à propos de ces domaines?
La plupart des options énumérées ci-dessus peuvent être utilisées dans le cadre d’une pratique normale sans aucun effet néfaste. Toutefois, si vous essayez vraiment d’obtenir les meilleures performances: – Recherchez où vous pouvez (en toute sécurité) désactiver la vérification des erreurs. Ce n’est pas recommandé, mais cela vous fera économiser de l’espace et des cycles. – Fabriquez à la main des parties de votre code dans l’assembleur. Bien entendu, cela signifie que votre code n’est plus portable, mais là où ce n’est pas un problème, vous pouvez réaliser des économies. Sachez cependant qu’il est potentiellement temps de transférer des données dans les registres que vous avez à votre disposition (par exemple, pour satisfaire l’utilisation des registres par votre compilateur). Sachez également que votre compilateur devrait faire assez bien par lui-même. (bien sûr il y a des exceptions)
Comme tout le monde l’a dit: profil, profil profil.
En ce qui concerne les techniques actuelles, une technique qui, à mon avis, n’a pas encore été mentionnée:
Séparation des données à chaud et à froid : il est extrêmement important de restr dans le cache de la CPU . Pour ce faire, vous pouvez fractionner vos structures de données en sections fréquemment consultées (“chaudes”) et rarement consultées (“froides”).
Un exemple: supposons que vous ayez une structure pour un client qui ressemble à ceci:
struct Customer { int ID; int AccountNumber; char Name[128]; char Address[256]; }; Customer customers[1000];
Supposons maintenant que vous souhaitiez beaucoup accéder à l’ID et au numéro de compte, mais pas tant au nom ni à l’adresse. Ce que vous feriez, c’est de le scinder en deux:
struct CustomerAccount { int ID; int AccountNumber; CustomerData *pData; }; struct CustomerData { char Name[128]; char Address[256]; }; CustomerAccount customers[1000];
De cette manière, lorsque vous parcourez votre tableau “clients”, chaque entrée ne contient que 12 octets. Vous pouvez ainsi insérer de nombreuses autres entrées dans le cache. Cela peut être un gain énorme si vous pouvez l’appliquer à des situations telles que la boucle interne d’un moteur de rendu.
Ma technique préférée consiste à utiliser un bon profileur. Sans un bon profil vous indiquant où se situe le goulot d’étranglement, aucune astuce ni technique ne vous aidera.
Les techniques les plus courantes rencontrées sont:
En ce qui concerne les recommandations générales, la plupart d’entre elles sont déjà retenties:
Pour une optimisation de bas niveau:
Évitez d’utiliser le tas. Utilisez des obstacles ou un pool-allocateur pour des objects de taille identique. Mettez de petites choses de courte durée sur la stack. alloca existe toujours.
L’optimisation prématurée est la racine de tout Mal! 😉
Étant donné que mes applications ne nécessitent généralement pas beaucoup de temps processeur, je me concentre sur la taille de mes fichiers binarys sur disque et en mémoire. Ce que je fais principalement consiste à rechercher des tableaux de taille statique et à les remplacer par de la mémoire allouée dynamicment, où il vaut la peine de déployer des efforts supplémentaires pour libérer la mémoire ultérieurement. Pour réduire la taille du binary, je recherche les grands tableaux initialisés au moment de la compilation et mets l’initialisation en exécution.
char buf[1024] = { 0, }; /* becomes: */ char buf[1024]; memset(buf, 0, sizeof(buf));
Cela supprimera les 1024 octets de zéro de la section binary .DATA et créera le tampon sur la stack lors de l’exécution et le remplira de zéros.
EDIT: Oh oui, et j’aime bien cacher des choses. Ce n’est pas spécifique au C, mais selon ce que vous mettez en cache, cela peut vous donner un énorme gain de performances.
PS: S’il vous plaît laissez-nous savoir quand votre liste est terminée, je suis très curieux. 😉
Si possible, comparez avec 0, et non avec des nombres arbitraires, en particulier dans les boucles, car la comparaison avec 0 est souvent implémentée avec des commandes d’assembleur distinctes et plus rapides.
Par exemple, si possible, écrivez
for (i=n; i!=0; --i) { ... }
au lieu de
for (i=0; i!=n; ++i) { ... }
Une autre chose qui n’a pas été mentionnée:
bases / général:
certaines choses qui ont réellement aidé:
Optez pour la taille / mémoire:
Optez pour la vitesse (soyez prudent):
Difficile à résumer …
Structures de données:
Algorithmes:
Niveau faible:
Le plus important de tous: mesurez tôt, mesurez souvent et ne faites jamais d’hypothèses, basez votre reflection et vos optimisations sur les données récupérées par un profileur (veuillez utiliser PTU ).
Autre indice, les performances sont la clé du succès d’une application. Elles doivent être sockets en compte au moment de la conception et vous devez définir des objectives de performances clairs.
Ceci est loin d’être exhaustif mais devrait fournir une base intéressante.
De nos jours, les choses les plus importantes dans l’optimisation sont:
Ne vous embêtez pas avec les optimisations impliquant le copier-coller de votre code (comme le déroulement d’une boucle) ou la réorganisation manuelle des boucles. Le compilateur fait généralement un meilleur travail que vous, mais la plupart d’entre eux ne sont pas assez intelligents pour l’annuler.
La collecte de profils d’exécution de code vous rapporte 50% du chemin. L’autre 50% traite de l’parsing de ces rapports.
De plus, si vous utilisez GCC ou VisualC ++, vous pouvez utiliser “l’optimisation guidée par le profil” où le compilateur prendra les informations des exécutions précédentes et des instructions de replanification pour rendre le processeur plus heureux.
Fonctions en ligne! Inspiré par les fans de profilage ici, j’ai profilé une de mes applications et trouvé une petite fonction qui effectue quelques bitshifting sur les trames MP3. Il effectue environ 90% de tous les appels de fonctions dans mon application. Je l’ai donc faite en ligne et le tour est joué – le programme utilise maintenant la moitié du temps CPU qu’il utilisait auparavant.
Sur la plupart des systèmes embarqués, j’ai travaillé, il n’existait pas d’outil de profilage, c’est donc bien de dire utiliser profileur mais pas très pratique.
La première règle en matière d’optimisation de la vitesse est la suivante: trouvez votre chemin critique .
Habituellement, vous constaterez que ce chemin n’est ni long ni complexe. Il est difficile de dire de manière générique comment l’optimiser dépend de ce que vous faites et de ce que vous êtes en mesure de faire. Par exemple, vous voulez généralement éviter la mémoire sur le chemin critique. Vous devez donc toujours utiliser DMA ou optimiser, mais que se passe-t-il si vous n’avez pas de DMA? vérifie si la mise en oeuvre de memcpy est la meilleure sinon la réécrit.
N’utilisez pas du tout l’allocation dynamic dans Embedded, mais si vous le faites pour une raison quelconque, ne le faites pas dans un chemin critique.
Organisez vos priorités de threads correctement, ce qui est correct est une vraie question et est clairement spécifique au système.
Nous utilisons des outils très simples pour parsingr les goulots d’étranglement, une macro simple qui stocke l’horodatage et l’index. Peu (2-3) courses dans 90% des cas trouveront où vous passez votre temps.
Et le dernier est la révision de code, une tâche très importante. Dans la plupart des cas, nous évitons les problèmes de performances lors de la révision du code de manière très efficace 🙂
En outre, vous devez mesurer les performances.
Parfois, vous devez décider si vous recherchez plus d’espace ou de vitesse, ce qui entraînera des optimisations presque opposées. Par exemple, pour tirer le meilleur parti de votre espace, vous conditionnez des structures, par exemple #pragma pack (1), et utilisez des champs de bits dans les structures. Pour plus de rapidité, vous comstackz avec les préférences du processeur et évitez les champs de bits.
Une autre astuce consiste à choisir les algorithmes de redimensionnement appropriés pour la croissance de tableaux via realloc ou, mieux encore, à écrire votre propre gestionnaire de tas en fonction de votre application particulière. Ne supposez pas que celui fourni avec le compilateur est la meilleure solution possible pour chaque application.
Si quelqu’un n’a pas de réponse à cette question, il se peut qu’il ne sache pas grand chose.
Il se pourrait aussi qu’ils en savent beaucoup. J’en connais beaucoup (IMHO :-), et si on me posait cette question, je vous le demanderais de nouveau: pourquoi pensez-vous que c’est important?
Le problème est que toute notion a priori sur les performances, si elles ne sont pas informées par une situation spécifique, est supposée par définition.
Je pense qu’il est important de connaître les techniques de codage pour la performance, mais je pense qu’il est encore plus important de ne pas les utiliser , jusqu’à ce que le diagnostic révèle qu’il existe un problème et en quoi il consiste.
Maintenant, je vais me contredire et dire que si vous faites cela, vous apprendrez à reconnaître les approches de conception qui conduisent à des problèmes afin de les éviter, et à un novice, cela ressemble à une optimisation prématurée.
Pour vous donner un exemple concret, il s’agit d’une application C qui a été optimisée .
Grandes listes. J’appendai simplement un conseil que je n’ai pas vu dans les listes ci-dessus et qui, dans certains cas, peut générer une optimisation considérable à un coût minimal.
contourner l’éditeur de liens
si vous avez une application divisée en deux fichiers, par exemple main.c et lib.c, dans de nombreux cas, vous pouvez simplement append un \#include "lib.c"
dans votre \#include "lib.c"
optimisation efficace pour le compilateur.
Le même effet peut être obtenu en optimisant les dépendances entre les fichiers, mais le coût des modifications est généralement plus élevé.
Parfois, Google est le meilleur outil d’optimisation d’algorithme. Lorsque j’ai un problème complexe, un peu de recherche révèle que certains détenteurs d’un doctorat ont trouvé une correspondance entre ce problème et un problème bien connu et ont déjà effectué l’essentiel du travail.
Je recommanderais d’optimiser en utilisant des algorithmes plus efficaces et de ne pas le faire après coup, mais de le coder ainsi dès le début. Laissez le compilateur traiter les détails des petites choses car il en sait plus sur le processeur cible que vous.
D’une part, j’utilise rarement des boucles pour rechercher des éléments, j’ajoute des éléments à une table de hachage, puis je l’utilise pour rechercher les résultats.
Par exemple, vous devez rechercher une chaîne, puis 50 valeurs possibles. Ainsi, au lieu de faire 50 strcmps, vous ajoutez les 50 chaînes à une table de hachage et leur atsortingbuez un numéro unique (vous ne devez le faire qu’une seule fois). Ensuite, vous recherchez la chaîne cible dans la table de hachage et disposez d’un grand commutateur avec les 50 observations (ou avez des pointeurs de fonctions).
Lorsque je recherche des éléments avec des ensembles d’entrées communs (comme les règles css), j’utilise un code rapide pour garder la trace des seules solitions possibles, puis itérer pour rechercher une correspondance. Une fois que j’ai obtenu une correspondance, j’enregistre les résultats dans une table de hachage (en tant que cache), puis j’utilise les résultats du cache si je reçois ce même jeu d’entrée plus tard.
Mes principaux outils pour un code plus rapide sont:
hashtable – pour des recherches rapides et pour la mise en cache des résultats
qsort – c’est le seul type que j’utilise
bsp – pour rechercher des éléments en fonction de la région (rendu de carte, etc.)