Quelles techniques de codage utilisez-vous pour optimiser les programmes C?

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?

  • minimiser la vérification de l’état. Les conditions de vérification (par exemple, les conditions de terminaison pour les boucles) représentent du temps qui n’est pas consacré au traitement réel. La vérification des conditions peut être minimisée avec des techniques telles que le déroulage en boucle.
  • Dans certaines circonstances, la vérification des conditions peut également être éliminée à l’aide de pointeurs de fonction. Par exemple, si vous implémentez une machine à états, vous constaterez que l’implémentation des gestionnaires pour des états individuels sous forme de petites fonctions (avec un prototype uniforme) et le stockage du “prochain état” en stockant le pointeur de fonction du prochain gestionnaire sont plus efficaces que d’utiliser un instruction de commutateur volumineuse avec le code de gestionnaire implémenté dans les instructions de cas individuelles. YMMV.
  • minimiser les appels de fonction. Les appels de fonction entraînent généralement une lourde tâche de sauvegarde du contexte (par exemple, l’écriture de variables locales contenues dans des registres dans la stack, la sauvegarde du pointeur de la stack). Ainsi, si vous n’avez pas à passer d’appel, vous gagnez du temps. Une option (si vous optimisez la vitesse et non l’espace) consiste à utiliser des fonctions en ligne.
  • Si les appels de fonction sont inévitables, minimisez les données transmises aux fonctions. Par exemple, le passage de pointeurs sera probablement plus efficace que le passage de structures.
  • Lors de l’optimisation pour la vitesse, choisissez les types de données qui sont la taille native de votre plate-forme. Par exemple, sur un processeur 32 bits, il sera probablement plus efficace de manipuler des valeurs 32 bits que des valeurs de 8 ou 16 bits. (note latérale – il est utile de vérifier que le compilateur fait ce que vous pensez. Il est déjà arrivé que mon compilateur insiste pour faire de l’arithmétique 16 bits sur des valeurs de 8 bits avec toutes les conversions à partir de et vers aller avec eux)
  • Recherchez des données pouvant être précalculées et effectuez le calcul lors de l’initialisation ou (encore mieux) lors de la compilation. Par exemple, lors de la mise en œuvre d’un CRC, vous pouvez calculer vos valeurs de CRC à la volée (en utilisant directement le polynôme), ce qui est excellent pour la taille (mais redoutable pour la performance), ou vous pouvez générer un tableau de toutes les valeurs intermédiaires, qui est une valeur. mise en oeuvre beaucoup plus rapide, au désortingment de la taille.
  • Localisez vos données. Si vous manipulez un bloc de données, votre processeur peut souvent accélérer le processus en le stockant dans le cache. Et votre compilateur pourra peut-être utiliser des instructions plus courtes adaptées à des données plus localisées (par exemple, des instructions qui utilisent des décalages de 8 bits au lieu de 32 bits).
  • Dans le même esprit, localisez vos fonctions. Pour les mêmes raisons.
  • Déterminez les hypothèses que vous pouvez formuler sur les opérations que vous effectuez et trouvez les moyens de les exploiter. Par exemple, sur une plate-forme 8 bits, si la seule opération que vous effectuez sur une valeur 32 bits est un incrément, vous pouvez trouver que vous pouvez faire mieux que le compilateur en ajoutant (ou en créant une macro) spécifiquement à cet effet, plutôt que d’utiliser une opération arithmétique normale.
  • Évitez les instructions coûteuses – la division est un excellent exemple.
  • Le mot clé “register” peut être votre ami (bien que votre compilateur ait une bonne idée de l’utilisation de votre registre). Si vous utilisez “register”, vous devrez probablement déclarer les variables locales que vous souhaitez “enregistrer” en premier.
  • Soyez cohérent avec vos types de données. Si vous effectuez des calculs sur une combinaison de types de données (par exemple, shorts et ints, doubles et float), le compilateur ajoute des conversions de type implicites pour chaque non-concordance. Ce sont des cycles de processeurs gaspillés qui peuvent ne pas être nécessaires.

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:

  • boucle déroulante
  • Optimisation de la boucle pour une meilleure lecture anticipée du cache (c.-à-d. N opérations en M cycles au lieu d’opérations singulières NxM)
  • alignement des données
  • fonctions en ligne
  • extraits asm fabriqués à la main

En ce qui concerne les recommandations générales, la plupart d’entre elles sont déjà retenties:

  • choisir de meilleurs algues
  • utiliser profileur
  • n’optimisez pas si cela n’améliore pas les performances de 20 à 30%

Pour une optimisation de bas niveau:

  1. START_TIMER / STOP_TIMER macros de ffmpeg (précision au niveau de l’horloge pour la mesure d’un code quelconque).
  2. Oprofile, bien sûr, pour le profilage.
  3. D’énormes quantités d’assemblages codés à la main (faites simplement un wc -l dans le répertoire / common / x86 de x264, puis souvenez-vous que la plupart du code est basé sur des modèles).
  4. Codage soigneux en général; Un code plus court est généralement préférable.
  5. Des algorithmes intelligents de bas niveau, comme l’écrivain à stream de bits 64 bits que j’ai écrit, n’utilisent qu’un seul si et aucun autre.
  6. Combinaison explicite d’écriture .
  7. Prise en compte des aspects étranges importants des processeurs, tels que le problème de division du cache d’Intel .
  8. Trouver des cas dans lesquels on peut effectuer une résiliation anticipée sans perte ou presque sans perte, où le contrôle de résiliation anticipée coûte beaucoup moins cher que la rapidité avec laquelle on en gagne.
  9. Assemblage réellement intégré pour les tâches beaucoup mieux adaptées à l’unité SIMD x86, telles que les calculs de médiane (nécessite une vérification au moment de la compilation pour le support MMX).
  • D’abord et avant tout, utilisez un algorithme meilleur / plus rapide. Il ne sert à rien d’optimiser le code qui est lent par conception.
  • Lorsque vous optimisez votre vitesse, échangez votre mémoire contre votre vitesse: tables de recherche de valeurs précalculées, arbres binarys, écriture d’une implémentation personnalisée plus rapide des appels système …
  • Lorsque vous échangez de la vitesse pour de la mémoire: utilisez la compression en mémoire

É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:

  • Connaissez vos besoins: n’optimisez pas les situations improbables ou jamais, concentrez-vous sur le meilleur rapport qualité-prix

bases / général:

  • Ne pas optimiser quand vous n’avez pas de problème.
  • Connaissez votre plateforme / CPU …
  • … le savoir à fond
  • connaissez votre ABI
  • Laissez le compilateur faire l’optimisation, aidez-le simplement avec le travail.

certaines choses qui ont réellement aidé:

Optez pour la taille / mémoire:

  • Utiliser des champs de bits pour stocker des bools
  • réutilisez de grands tableaux globaux en superposant une union (soyez prudent)

Optez pour la vitesse (soyez prudent):

  • utiliser des tables précalculées si possible
  • place des fonctions / données critiques en mémoire rapide
  • Utiliser des registres dédiés pour les globals souvent utilisés
  • compter jusqu’à zéro, l’indicateur zéro est libre

Difficile à résumer …

  • Structures de données:

    • La division d’une structure de données en fonction du cas d’utilisation est extrêmement importante. Il est courant de voir une structure contenant des données auxquelles on accède en fonction d’un contrôle de stream. Cette situation peut réduire considérablement l’utilisation du cache.
    • Prendre en compte la taille de la ligne de cache et les règles de prélecture.
    • Pour réorganiser les membres de la structure afin d’obtenir un access séquentiel à partir de votre code
  • Algorithmes:

    • Prenez le temps de réfléchir à votre problème et de trouver le bon algorithme.
    • Connaissez les limites de l’algorithme que vous choisissez (un sorting rapide / sorting rapide pour 10 éléments à sortinger pourrait ne pas être le meilleur choix).
  • Niveau faible:

    • En ce qui concerne les derniers processeurs, il est déconseillé de dérouler une boucle ayant un petit corps. Le processeur fournit à cet effet son propre mécanisme de détection et court-circuitera toute la section de son pipeline.
    • Faites confiance au préfetcher HW. Bien sûr si vos structures de données sont bien conçues;)
    • Prenez soin de vos oublis de ligne de cache L2.
    • Essayez de réduire autant que possible l’ensemble de travail local de votre application, car les processeurs s’appuient sur des caches plus petits par cœur (C2D bénéficiait d’un maximum de 3 Mo par cœur, où iCore7 fournira un maximum de 256 Ko par cœur + 8 Mo partagés entre tous les cœurs quad core die.).

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:

  • respect du cache – essayez d’accéder à la mémoire de manière simple et ne déroulez pas les boucles rien que pour le plaisir. Utilisez des tableaux au lieu de structures de données avec beaucoup de pointeur et ce sera probablement plus rapide pour de petites quantités de données. Et ne faites rien de trop gros.
  • éviter la latence – essayez d’éviter les divisions et les tâches lentes si d’autres calculs en dépendent immédiatement. Les access mémoire qui dépendent d’autres access mémoire (c’est-à-dire a [b [c]]) sont incorrects.
  • éviter l’imprévisibilité – beaucoup de si / elses avec des conditions imprévisibles, ou des conditions qui introduisent plus de temps de latence, vont vraiment vous gâcher. Il existe de nombreuses astuces mathématiques sans twigs qui sont utiles ici, mais elles augmentent la latence et ne sont utiles que si vous en avez vraiment besoin. Sinon, écrivez simplement du code simple et n’avez pas de conditions de boucle loufoques.

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 🙂

  1. Mesurer les performances.
  2. Utilisez des repères réalistes et non sortingviaux. Rappelez-vous que “tout est rapide pour les petits N” .
  3. Utilisez un profileur pour trouver des points chauds.
  4. Réduisez le nombre d’allocations de mémoire dynamics, d’access au disque, d’access à la firebase database, d’access réseau et de transitions utilisateur / kernel, car il s’agit souvent de points chauds.
  5. Mesurer les performances.

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.)