Aujourd’hui, Hugo vous propose de réfléchir au facteur limitant du code.
Un programme, est, à l’exécution, limité par l’utilisation des ressources dont il a besoin pour fonctionner.
Le facteur limitant du programme est alors la ressource dont l’usage tend à freiner le programme dans son temps d’exécution.
Ce billet vise deux objectifs principaux :
– Partager une définition compréhensive des facteurs limitants
– Fournir un mode opératoire afin :
a) de parvenir à le minimiser, dans la mesure du possible.
b) d’identifier le facteur limitant d’un programme.
Définition
On dénombre 3 facteurs limitants :
- CPU-bound, aussi appelé processor-bound, computation-bound ou compute-bound
- Memory-bound aussi appelé RAM-bound, storage-bound ou memory-constrained
- I/O-bound aussi appelé disk-bound, network-bound, ou input/output-constrained
1. CPU-bound
Un programme est dit CPU-bound lorsque sa performance est délimitée par la puissance de calculs du processeur (CPU). Cela signifie que le CPU est le goulet d’étranglement, empêchant le programme de s’exécuter à une cadence maîtrisée. En d’autres termes, le programme exécute des opérations nécessitant une puissance de calculs plus importante que celle dont il est pourvu.
2. Memory-bound
Un programme est dit memory-bound lorsque sa performance est délimitée par la quantité de mémoire vive disponible. Le programme nécessite une quantité de mémoire vive plus importante que celle accessible ; le programme traite un nombre de données qui excèdent la quantité de mémoire disponible.
3. I/O-bound
Un programme est dit I/O-bound lorsque sa performance est délimitée soit par la quantité de données à lire depuis/écrire sur un périphérique de stockage, soit par la vitesse de lecture depuis/d’écriture sur un périphérique de stockage, ou les 2 (ici, un périphérique de stockage peut être un disque dur ou une interface réseau). Cela signifie que le programme doit attendre que les opérations de lecture/écriture s’effectuent, ce qui ralentit les performances.
💡I/O = E/S (Entrées/Sorties)
Identification et minimisation
1. Mode opératoire CPU-bound
1.1. Profiler le code
Utiliser un profiler pour identifier les fonctions ou sections du code qui prennent le plus de temps CPU. Cela aidera à concentrer les efforts d’optimisation sur les zones qui auront le plus d’impact. Il est intéressant ici de mesurer la complexité algorithmique des différents blocs d’instructions afin d’orienter le réflexion.
1.2. Simplifier le code
Chercher des opportunités pour simplifier le code ou éliminer les calculs inutiles. Par exemple, on pourra pré-calculer certaines valeurs ou mettre en cache des résultats pour éviter les calculs redondants.
1.3. Optimiser les algorithmes
Passer en revue les algorithmes utilisés dans le code et rechercher des moyens de les optimiser. Par exemple, on pourra utiliser un algorithme de tri ou une structure de données plus efficace.
1.4. Paralléliser le code
Si possible, paralléliser le code pour profiter de plusieurs cœurs de processeur. Cela peut être fait en utilisant le multithreading, le multiprocessing ou d’autres techniques de parallélisation.
💡 La parallélisation du code consiste à diviser une tâche en morceaux plus petits et indépendants qui peuvent être exécutés simultanément sur plusieurs cœurs de CPU. Cela peut considérablement améliorer les performances, en particulier pour les programmes CPU-bound. Le multithreading est une technique courante utilisée pour paralléliser le code, tandis que le multiprocessing est une autre technique permettant d’exécuter plusieurs processus en parallèle. Cependant, la parallélisation n’est pas toujours simple et peut nécessiter des efforts supplémentaires pour assurer la correction et éviter des problèmes tels que des race conditions ou des blocages.
💡La parallélisation utilise plusieurs coeurs de CPU pour effectuer plusieurs calculs en simultané.
1.5. Utiliser la vectorisation
La vectorisation permet d’optimiser les boucles et autres calculs qui peuvent être effectués sur des tableaux. Cela peut être fait en utilisant des instructions SIMD (Single Instruction Multiple Data).
💡 La vectorisation consiste à utiliser des instructions SIMD pour effectuer simultanément la même opération sur plusieurs éléments de données. Cela peut améliorer les performances en réduisant le nombre d’instructions nécessaires pour effectuer un calcul. La vectorisation permet de bénéficier de l’accélération hardware.
💡La vectorisation optimise l’usage d’un unique coeur de CPU via l’utilisation des instructions SIMD.
1.6. Utiliser l’accélération hardware
L’accélération matérielle, comme les GPU ou les coprocesseurs spécialisés, permet de décharger les calculs intensifs du CPU vers du matériel dédié. En dernier recours, il faudra peut-être envisager d’exécuter le programme dans un environnement disposant de plus de ressources CPU.
1.7. Surveiller les performances
Surveiller les performances du code optimisé pour s’assurer que les modifications apportées améliorent réellement les performances. Utiliser des outils de profilage et des benchmarks pour comparer les performances du code optimisé au code original.
1.8. Itérer
Répéter le processus de profilage, d’optimisation et de surveillance jusqu’à ce que le niveau de performance souhaité soit atteint.
2. Mode opératoire Memory-bound
2.1 Profiler le code
Utiliser un profiler pour identifier les parties du code qui causent un usage mémoire excessif. On pourra alors concentrer l’effort d’analyse et d’optimisation sur ces portions de code les plus limitantes.
2.2. Optimiser les structures de données
Passer en revue les structures de données utilisées dans le code, et rechercher des moyens de les optimiser. Cela peut impliquer l’utilisation de structures de données plus efficaces, telles que des tables de hachage ou des arbres, ou la réduction de la taille des structures de données en utilisant des représentations plus compactes.
S’attacher à choisir les bonnes structures de données est essentiel, car des structures de données inefficaces peuvent rapidement consommer de grandes quantités de mémoire. Par exemple, l’utilisation d’une table de hachage au lieu d’une liste peut réduire l’utilisation de la mémoire pour les recherches, tandis que l’utilisation d’un arbre binaire peut réduire l’utilisation de la mémoire pour les données triées. En choisissant la structure de données la plus appropriée pour la tâche, on peut réduire l’empreinte mémoire globale du programme.
2.3. Optimiser l’allocation mémoire
Passer en revue les modèles d’allocation mémoire utilisés dans le code, et rechercher des moyens de les optimiser. Cela peut impliquer le recours à la pré-allocation de mémoire pour les structures de données, la réutilisation de la mémoire au lieu d’allouer de la nouvelle mémoire, ou l’utilisation de techniques d’allocation de mémoire spécialisées, telles que les pools de mémoire, ou des patterns, comme le singleton et le flyweight.
2.4. Utiliser la mise en cache
Utiliser la mise en cache pour réduire la quantité de mémoire nécessaire pour stocker les données fréquemment consultées. Cela peut être fait en mettant en cache les résultats des calculs ou en utilisant des techniques telles que la mémorisation pour éviter les calculs redondants.
2.5. Réduire la fragmentation mémoire
La fragmentation de la mémoire peut se produire lorsque le programme alloue et libère de la mémoire à plusieurs reprises, ce qui produit de petits espaces de mémoire inutilisée dispersés dans le tas. Cela peut entraîner une utilisation inefficace de la mémoire et réduire les performances. Pour réduire la fragmentation, on peut envisager d’utiliser des allocations de mémoire spécialisées capables de gérer plus efficacement un grand nombre de petites allocations. Par exemple, l’utilisation d’un slab allocator peut réduire la fragmentation en regroupant des allocations de mémoire de tailles similaires ensemble.
2.6. Utiliser la compression
Si le programme traite de grandes quantités de données, on peut envisager d’utiliser la compression pour réduire l’utilisation mémoire. En effet, la compression peut être un moyen efficace de réduire l’utilisation de la mémoire d’un programme, en particulier pour les données qui ont beaucoup de redondance ou qui peuvent être représentées sous une forme plus compacte. Par exemple, la compression des données à l’aide d’une technique telle que gzip ou lz4 peut considérablement réduire la quantité de mémoire nécessaire pour stocker les données. Cependant, la compression s’accompagne également d’un compromis en termes d’utilisation du processeur, elle doit donc être utilisée judicieusement en fonction des exigences spécifiques du programme.
2.7. Surveiller les performances
Surveiller les performances du code optimisé pour s’assurer que les modifications apportées améliorent réellement les performances. Utiliser des outils de profilage et des benchmarks pour comparer les performances du code optimisé au code original.
2.8. Itérer
Répéter le processus de profilage, d’optimisation et de surveillance jusqu’à ce que le niveau de performance souhaité soit atteint.
3. Mode opératoire I/O-bound
3.1. Profiler le code
Utiliser un profiler pour identifier les parties du code qui provoquent une utilisation excessive des I/O. On pourra alors concentrer l’effort d’analyse et d’optimisation sur les zones où les écueils sont les plus importants.
3.2. Optimiser les opérations I/O
Examiner les opérations I/O utilisées dans le code, et rechercher des moyens de les optimiser. Cela peut impliquer de réduire le nombre d’opérations I/O nécessaires, d’augmenter la taille des opérations I/O ou d’utiliser des opérations I/O asynchrones pour chevaucher les I/O et le calcul.
3.3. Utiliser la mise en cache
Utiliser la mise en cache pour réduire la quantité d’I/O nécessaires pour récupérer les données fréquemment consultées. Cela peut être fait en mettant en cache les résultats des opérations d’I/O en mémoire ou en utilisant des techniques telles que la mémorisation pour éviter les opérations d’I/O redondantes.
3.4. Optimiser le data storage
Examiner le stockage des données utilisé dans le code et recherchez des moyens de l’optimiser. Cela peut impliquer l’utilisation de formats de stockage de données plus efficaces, tels que des formats binaires ou compressés, ou l’utilisation de techniques de stockage de données spécialisées telles que l’indexation pour améliorer les performances de récupération des données.
3.5. Utiliser la compression
Si le programme traite de grandes quantités de données, on peut envisager d’utiliser la compression pour réduire les besoins en I/O. Cela peut être particulièrement efficace pour les données qui présentent beaucoup de redondance ou qui peuvent être représentées sous une forme plus compacte.
3.6. Utiliser le parallélisme
Si le programme effectue plusieurs opérations I/O indépendantes les unes des autres, on doit envisager d’utiliser le parallélisme pour chevaucher les opérations I/O et les calculs. Cela peut être fait en utilisant le multithreading ou le multiprocessing pour exécuter des opérations I/O et des calculs simultanément.
3.7. Surveiller les performances
Surveiller les performances du code optimisé pour s’assurer que les modifications apportées améliorent réellement les performances. Utiliser des outils de profilage et des benchmarks pour comparer les performances du code optimisé au code original.
3.8. Itérer
Répéter le processus de profilage, d’optimisation et de surveillance jusqu’à ce que le niveau de performance souhaité soit atteint.
À vous de jouer !
Vous pouvez retrouver aussi un condensé de ce billet ici