:: wikimiki.org ::
| Allocation De Mémoire |
Allocation de mémoireLes algorithmes sous-jacents à tout programme informatique consomment essentiellement deux ressources : du temps et de l'espace. En machine, l'espace peut être la mémoire vive volatile ou la mémoire de masse persistante. Cet article discute de l'allocation de mémoire vive.
Trois stratégies d'allocation peuvent être employées : allocation statique, allocation dynamique sur la pile, et allocation dynamique sur le tas. L'allocation statique est principalement le fait des langages de programmation compilés. Les langages interprétés ne peuvent, par définition, qu'allouer la mémoire à la demande, lors de l'exécution.
A chacune des stratégies correspond une région mémoire du programme, ou segment. Ces segments sont nommés text (statique), stack (pile) et heap (tas).
L'opération symétrique de l'allocation est couramment appelée libération de la mémoire (on peut parler également de désallocation ou de restitution).
Les trois modes d'allocation
Allocation statique
Allouer statiquement de la mémoire pour un programme signifie :
- prévoir l'espace mémoire nécessaire avant l'exécution du programme, en spécifiant la quantité nécessaire dans le code source,
- réserver cet espace au moment de la compilation, dans le fichier binaire produit,
- au chargement du programme en mémoire, juste avant l'exécution, l'espace réservé devient alors accessible.
Lors de l'exécution, aucune allocation n'a lieu.
L'avantage de l'allocation statique se situe essentiellement au niveau des performances, puisqu'on évite les coûts de l'allocation dynamique à l'exécution : la mémoire statique est immédiatement utilisable.
Sur les systèmes d'exploitation communs, la mémoire allouée statiquement est placée dans le segment text, le segment data ou le segment bss du programme, selon le destin de cette zone mémoire ( reservée , initialisée , read only... ).
Allocation sur la pile
L'exécution d'un programme est généralement structurée autour d'une pile contenant les cadres d'appels à des fonctions (ou procédures) du langage de programmation source. Schématiquement, les variable lexicales, c'est à dire les variables définies dans la portée textuelle d'une fonction, sont donc allouée lors de l'entrée dans la fonction, et désallouées automatiquement lors de la sortie (du retour) de la fonction.
Un segment mémoire, dit segment de pile, est utilisé pour ces allocation/désallocations. Aucun mot clef n'est nécessaire dans le code source d'un langage supportant la notion de variable lexicale : celles-ci sont allouées et libérées selon la discipline de pile par définition.
Certains langages, comme C ou C++, parlent de variables locales ou automatiques au lieu de variables lexicales, mais il s'agit de la même chose.
Allocation sur le tas
La plupart des programmes ayant des besoins en mémoire dépendant de l'usage qu'on en fait, il est nécessaire de pouvoir, à des moments arbitraires de l'exécution, demander au système l'allocation de nouvelles zones de mémoire, et de pouvoir restituer au système ces zones (désallouer la mémoire). Dans ce cas, l'allocation et la libération de la mémoire sont sous la responsabilité du programmeur. Les fuites de mémoire, ainsi que d'autres erreurs fréquentes dans les programmes à gestion manuelle de la mémoire, ont leur source dans les erreurs d'allocation mémoire sur le tas.
Classiquement, les fonctions de la libc malloc et free, les primitives du langage c++ new et delete permettent, respectivement, d'allouer et désallouer la mémoire sur le tas.
Les langages de programmation dotés de ramasse-miettes utilisent, mais de façon transparente pour le programmeur, l'allocation sur la pile et les primitives alloc/free. Dans ce dernier cas, le ramasse-miette permet d'éviter les erreurs liées à l'allocation sur le tas, à l'exception de certaines fuites de mémoire...
Comparaison
L'allocation statique est la méthode la plus sûre dans le sens où :
- la quantité consommée est constante et complètement connue avant l'exécution,
- elle est généralement accessible exclusivement en lecture seule (non modifiable).
C'est toutefois une méthode très inflexible et insuffisante pour les programmes dont les besoins peuvent varier de façon imprévisible : pour un programme ayant des besoins potentiels de mémoire importants, l'allocation statique conduirait à un gaspillage. Elle est finalement essentiellement utilisée pour stocker des constantes ou des valeurs calculées et disponibles au moment de la compilation.
L'allocation sur la pile représente un bon compromis :
- la quantité consommée est proportionnelle aux paramètres d'entrées du programme, qui déterminent la profondeur de la pile et donc la quantité allouée ; elle peut être connue avant l'exécution par une analyse de la complexité algorithmique,
- il n'y a pas de fuite de mémoire, du fait de la libération implicite (respectant la discipline de pile).
L'allocation sur la pile doit être choisie en priorité lorsque les besoins mémoires sont connus à l'avance et sont proportionnels à certains paramètres d'entrée du programme. L'allocation et la libération consécutives, selon une discipline de pile, de grosses quantités de mémoire peuvent toutefois poser des problèmes de performance et de lisibilité du source (explosion du nombre de paramètres passés aux fonctions) ; ces problèmes sont à mettre dans la balance contre l'assurance d'une libération correcte des ressources mémoire.
L'allocation sur le tas, puisqu'elle permet le contrôle complètement arbitraire de l'allocation et de la libération, offre le plus de possibilités. Les ressources allouées manuellement ont cependant une durée de vie indéfinie, c'est à dire que le programmeur a la responsabilité de la libération (et doit éviter de tomber dans les pièges de la double libération, etc.). La mémoire allouée sur le tas peut également être référencée par des variables globales (de préférence confinées dans un espace de nom), ce qui peut aider à délester un groupe de fonctions de paramètres communs.
En pratique, on préfèrera le mode d'allocation le plus simple. La plupart du temps, l'allocation sur la pile est suffisante. On n'utilise l'allocation sur le tas qu'en dernier recours, pour manipuler des structures de données complexes et/ou dont l'évolution ne suit pas la discipline de pile.
Dans les langages à ramasse-miettes, le choix du mode d'allocation est réalisé par le compilateur, en fonction d'une analyse des patterns d'utilisation des variables dans le code source.
catégorie:développement logiciel
Programme informatique
Un programme informatique indique à un ordinateur ce qu'il devrait faire faire. Il s'agit d'un ensemble d'instructions qui doivent être exécutées dans un certain ordre par un processus.
Un ordinateur sans programme ne fait absolument rien. En fait, la capacité à suivre un programme enregistré sert même souvent, d'un point de vue historique, à distinguer un ordinateur d'une simple machine à calculer. Avec cette définition, le premier ordinateur est le Manchester Mark I, premier calculateur à programme enregistré.
À l'origine d'un programme, il y a un code source écrit par un programmeur dans un langage de programmation compréhensible par l'homme. Selon le langage utilisé, ce code est ensuite traduit avec un jeu d'instructions spécifique à un microprocesseur par un compilateur, le programme obtenu peut alors être exécuté directement par l'ordinateur, ou bien est pris en charge par un interpréteur qui décode les instructions et les exécute. Parfois le langage de programmation se réduit à un ensemble de symboles correspondant aux instructions en code machine. C'est du langage assembleur et dans ce cas, un programme appelé assembleur est utilisé pour faire la traduction en langage machine.
Le terme programme informatique est souvent utilisé comme synonyme de logiciel ; bien que la majeure partie de tout logiciel soit composée de programmes, les logiciels incluent souvent les fichiers de ressources qui contiennent des données de toutes sortes ; elles ne font pas partie du programme en elles-mêmes. Un programme abstrait est souvent appelé algorithme.
Les programmes d'ordinateur sont aujourd'hui souvent les sujets des mathématiques : voir les méthodes formelles, la sémantique des langages de programmation, etc.
Voir aussi
[ langage de programmation | machine de Turing | lisibilité | génie logiciel ]
Catégorie:Programmation informatique
ja:プログラム
ko:프로그램
simple:Computer program
zh-cn:程序
Mémoire de masseEn informatique, le terme de mémoire de masse regroupe tous les systèmes de stockage d'informations (données et programmes) auxquels a accès un ordinateur.
- Disque dur
- Disquette
- Bande magnétique
- Disque Zip de la société Iomega
- CD
- DVD
- Clé USB
- Dans une optique moins "locale" mais plûtot orientée réseau : utilisation de système de fichiers distribués tels que Nfs ou Coda, connexion à un serveur Ftp ou à une base de données externe.
La disquette 3"1/2 à longtemps été le moyen de stockage et d'échange traditionnel entre PCs, l'arrivée successive du disque Zip de Iomega et des graveurs de CD ne remis pas, ou très peu, en question cette suprématie, nottamment à cause du coût excessifs de ces derniers à l'époque.
La Clé USB semble être la candidate idéale, en raison de son faible cout ( le modèle de base pouvant s'acheter autour de 30 €), de sa capacité bien plus importante ( de 128 Mo à 1 Go contre 1,44 Mo pour la disquette) et de son encombrement ridicule, sa taille approchant le plus souvent celle d'un briquet.
Catégorie:Matériel informatique
Code source
Définition et usages du code source
Le code source est un ensemble d'instructions écrites dans un langage de programmation informatique de haut niveau, c'est à dire humainement compréhensible, permettant d'obtenir un programme pour un ordinateur.
Les systèmes d'exploitation ne peuvent pas directement exploiter le code source ; ils ne peuvent que lancer des exécutables. Le code source doit donc être :
- Transformé en code comprehensible par la machine , la compilation ;
- Ou être exécuté tel quel par un interpréteur.
Hormis dans le cas des logiciels Open Source, le code source d'un programme n'est généralement pas public.
Analogie de la recette culinaire
L'analogie du code source et de la recette culinaire est souvent employée dans une volonté de vulgarisation. La recette est une liste organisée d'ingrédients en quantités et fonctions définies, dont le but est d'obtenir un résultat visé par le cuisinier, selon une technique déterminée..
Ainsi le code source peut être apparenté à une recette culinaire.
Par exemple, si on mange un plat, il est fort probable que l'on puisse deviner les éléments principaux de sa composition et imaginer dans les grandes lignes comment le faire. Néanmoins, pour un plat très raffiné et subtil (comme l'est un programme) on ne pourra pas savoir comment le chef a procédé. Il faut la recette détaillée (pour un programme la recette peut compter plusieurs millions de lignes de code !) pour pouvoir reproduire le plat... ou bien on est obligé d'acheter les plats préparés.
Catégorie:Programmation informatique
ja:ソースコード
ms:Kod sumber
Ramasse-miettes
Un ramasse-miettes, ou récupérateur de mémoire, ou glaneur de cellules (en anglais garbage collector, abrégé en GC) est un sous-système informatique de gestion automatique de la mémoire. Il est responsable du recyclage de la mémoire préalablement allouée puis inutilisée.
Lorsqu'un système dispose d'un ramasse-miette, ce dernier fait généralement partie de l'environnement d'exécution associé à un langage de programmation particulier. Le ramassage des miettes a été inventé par John McCarthy comme faisant partie du premier système Lisp.
Définition et fonctionnement
Le principe de base de la récupération automatique de la mémoire est simple :
- déterminer quels objets dans le programme ne peuvent pas être utilisés,
- récupérer le stockage utilisé par ces objets.
Bien qu'en général il soit impossible de déterminer à l'avance à quel moment un objet ne sera plus utilisé, il est possible de le découvrir à l'exécution : un objet sur lequel le programme ne maintient plus de référence, donc devenu inaccessible, ne sera plus utilisé.
Principe d'accessibilité d'un objet
Les ramasse-miettes utilisent un critère d'accessibilité pour déterminer si un objet peut être potentiellement utilisé.
Les principes sont :
- un ensemble distinct d'objets qui sont supposés atteignables, ce sont les racines. Dans un système typique ces objets sont les registres machine, la pile, le pointeur d'instruction, les variables globales. En d'autres termes tout ce qu'un programme peut atteindre directement.
- tout objet référencé depuis un objet atteignable est lui-même atteignable.
Dit autrement : un objet atteignable peut être obtenu en suivant une chaîne de pointeurs ou de références.
Bien évidemment, un tel algorithme est une approximation conservatrice de l'objectif idéal de destruction des valeurs ne servant plus : certaines valeurs peuvent fort bien être accessibles depuis les racines mais ne plus jamais être utilisées. Cet objectif idéal est cependant inaccessible algorithmiquement : déterminer quelles valeurs serviront dans le futur est équivalent au problème de l'arrêt.
Cette approximation conservatrice est la raison de la possibilité de fuites de mémoire, c'est-à-dire de l'accumulation de blocs de mémoire qui ne seront jamais réutilisés, mais jamais libérés non plus. Par exemple, un programme peut conserver un pointeur sur une structure de donnée qui ne sera jamais réutilisée. Il est pour cette raison recommandé d'écraser les pointeurs vers des structures inutilisées, afin d'éviter de conserver des références inutiles.
Algorithme de base
L'algorithme du ramasse-miettes est dû à Schorr et Waite. Les ramasse-miettes effectuent des cycles de ramassage. Un cycle est démarré lorsque le récupérateur décide (ou est notifié) qu'il doit récupérer de l'espace de stockage. Un cycle est constitué des étapes suivantes :
- Créer des ensembles dit noir, gris et blanc. Initialement, l'ensemble noir est vide, l'ensemble gris contient les objets « racines » et éventuellement certains objets supplémentaires choisis en fonction de l'algorithme particulier employé, et l'ensemble blanc contient tout le reste. À tout moment dans l'exécution de l'algorithme, un objet ne peut être que dans un seul des trois ensembles. L'ensemble blanc peut être vu comme l'ensemble des objets dont nous essayons de récupérer l'espace mémoire ; au cours du cycle, l'algorithme ôtera des objets de l'ensemble blanc, y laissant les objets dont il peut réclamer l'espace mémoire.
- Choisir un objet de l'ensemble gris, déplacer cet objet vers l'ensemble noir, déplacer tous les objets blancs référencés directement par cet objet vers l'ensemble gris. Cette étape est répétée jusqu'à ce qu'il n'y ait plus d'objets dans l'ensemble gris.
- Quand il n'y a plus d'objets dans l'ensemble gris, alors tous les objets restant dans l'ensemble blanc ne sont pas atteignables, et l'espace mémoire qu'ils utilisent peut être réclamé.
L'invariant des trois couleurs peut être traduit comme ceci : aucun objet noir ne pointe directement sur un objet blanc.
Observons que l'algorithme ci-dessus préserve l'invariant des trois couleurs.
La partition initiale n'a pas d'objet noir, de sorte que l'invariant est trivialement respecté. Par la suite, si un objet devient noir, tous ses fils directs (les objets qu'il référence) deviennent gris, ceci préservant l'invariant. Lorsque la dernière étape de l'algorithme est réalisée, parce que l'invariant est préservé, aucun des objets de l'ensemble noir ne pointe vers un objet de l'ensemble blanc (et il n'y a plus d'objet gris) ce qui signifie que les objets blancs résiduels sont inatteignables depuis les racines. Le système peut alors appeler leurs destructeurs et libérer leur espace mémoire.
Certaines variantes de l'algorithme ne respectent pas l'invariant des trois couleurs, mais ils utilisent un principe différent par lequel toutes les propriétés importantes sont respectées.
Variantes
L'algorithme de base a plusieurs variantes.
- Les ramasse-miettes qui déplacent les objets en mémoire (qui changent leur adresse), dits stop and copy.
- Certains récupérateurs peuvent correctement identifier toutes les références à un objet : ils sont appelés des récupérateurs « exacts », par opposition avec des récupérateurs « conservateurs » ou « partiellement conservateurs ». Les ramasse-miettes « conservateurs » doivent présumer que n'importe quel suite de bits en mémoire est un pointeur si (lorsqu'ils sont interprétées comme un pointeur) il pointe sur un quelconque objet instancié. Ainsi, les récupérateurs conservateurs peuvent avoir des faux négatifs, où l'espace mémoire n'est pas réclamé à cause des faux pointeurs accidentels. En pratique ceci est rarement un gros inconvénient.
- Le ramasse-miettes peut s'exécuter en alternance ou en parallèle avec le reste du système ; les récupérateurs les plus simples suspendent l'exécution du système lorsqu'ils exécutent un cycle ; ils ne sont pas incrémentaux ; les récupérateurs incrémentaux entrelacent leur travail pour s'exécuter pendant les temps d'inactivité du reste du système. Certains récupérateurs incrémentaux peuvent s'exécuter complètement en parallèle dans un thread séparé ; ils peuvent en théorie s'exécuter sur un processeur différent, mais le coût de la mise en cohérence des caches rend cette approche moins pratique qu'il n'y paraît.
Classification des ramasse-miettes
Les récupérateurs peuvent être classés en considérant la façon dont ils implémentent les trois ensembles d'objets blancs, gris et noirs.
Marquage et nettoyage
Ou mark and sweep en anglais.
Un ramasse-miettes de ce type maintient un bit (ou deux) associé à chaque objet pour indiquer s'il est blanc ou noir ; l'ensemble gris est maintenu soit comme une liste séparée ou en utilisant un autre bit. Un récupérateur copieur distingue les objets gris et noirs en les copiant vers d'autres zones mémoire (l'espace de copie) et souvent différencie les objets noirs des objets gris en bi-partitionnant l'espace de copie (dans le cas le plus simple en maintenant un unique pointeur qui indique la séparation entre les objets noirs et gris).
Récupérateur à générations
Ou generational GC en anglais.
Toutes les données d'un programme n'ont pas la même durée de vie. Certaines sont éliminables très peu de temps après leur création (par exemple, une structure de donnée créée uniquement pour retourner une valeur d'une fonction, et démantelée dès que les données en ont été extraites). D'autres persistent pendant toute la durée d'exécution du programme (par exemple, des tables globales créées pendant l'initialisation). Un ramasse-miette traitant toutes ces données de la même façon n'est pas forcément des plus efficaces.
Une solution serait de demander au programmeur d'étiqueter les données créées selon leur durée de vie probable. Cependant, cette solution serait lourde à utiliser ; par exemple, il est courant que les données soient créées dans des fonctions de bibliothèque (par exemple, une fonction créant une table de hachage), il faudrait leur fournir les durées de vie en paramètre.
Une méthode moins invasive est le système des générations. Le ramasse-miette opère alors sur une hiérarchie de 2 ou plus générations, étagées de la plus « jeune » à la plus « âgée ». Les données nouvellement créées sont (en général) placées dans la génération la plus jeune. On ramasse assez fréquemment les miettes dans cette génération jeune ; les données encore présentes à l'issue de la destruction des données inaccessibles de cette génération sont placées dans la génération d'âge supérieur, et ainsi de suite. L'idée est que les données de plus courte durée de vie n'atteignent, pour la plupart, pas la génération supérieure (elle peuvent l'atteindre si elles viennent d'être allouées quand le ramassage de miettes les repère dans la génération jeune, mais c'est un cas rare).
On utilise généralement 2 ou 3 générations, de tailles croissantes. Généralement, on n'utilise pas le même algorithme de ramasse-miette pour les diverses générations. Il est ainsi courant d'utiliser un algorithme non incrémental pour la génération la plus jeune : en raison de sa faible taille, le temps de ramasse-miette est faible et l'interruption momentanée de l'exécution de l'application n'est pas gênante, même pour une application interactive. Les générations plus anciennes sont plutôt ramassées avec des algorithmes incrémentaux.
Le réglage des paramètres d'un ramasse-miettes à génération peut être délicat. Ainsi, la taille de la génération la plus jeune peut influencer de façon importante le temps de calcul (un surcoût de 25%, par exemple, pour une valeur mal choisie) : temps de ramasse-miette, impact sur la localité du cache... Par ailleurs, le meilleur choix dépend de l'application, du type de processeur et d'architecture mémoire.
Comptage de références
Une solution qui vient vite à l'esprit pour la libération automatique de zones de mémoire est d'associer à chacune un compteur donnant le nombre de références qui pointent sur elle. Ces compteurs doivent être mis à jour à chaque fois qu'une référence est créée, alterée ou détruite. Lorsque le compteur associé à une zone mémoire atteint zéro, la zone peut être libérée.
Cette technique souffre d'un inconvénient certain lors de l'usage de structures cycliques : si une structure A pointe sur une structure B qui pointe sur A (ou, plus généralement, s'il existe un cycle dans le graphe des références), mais qu'aucun pointeur extérieur ne pointe ni sur A ni sur B, les structures A et B ne sont jamais libérées : leurs compteurs de références sont strictement supérieurs à zéro (et comme il est impossible que le programme accèdent à A ou B, ces compteurs ne peuvent jamais repasser à zéro).
En raison de ces limites, certains considèrent que le comptage de références n'est pas une technique de récupération de mémoire à proprement parler ; ils restreignent le terme de récupération de mémoire à des techniques basées sur l'accessibilité.
Le comptage de références souffre de certains problèmes sérieux, comme son coût élevé en temps de calcul et aussi en espace mémoire et, comme on l'a vu, l'impossibilité de gérer les références circulaires. D'un autre côté, il récupère les « miettes » plutôt vite, ce qui présente des avantages s'il y a des destructeurs à exécuter pour libérer les ressources rares autres (sockets...) que le tas (mémoire).
Des systèmes hybrides utilisant le comptage de références pour obtenir la libération quasi immédiate des ressources, et appelant à l'occasion un récupérateur de type Mark and Sweep pour libérer les objets contenant des cycles de références, ont été proposés et parfois implémentés. Cela donne le meilleur des deux mondes, mais toujours au prix d'un coût élevé en termes de performances.
Langages dotés de ramasse-miettes
- Common Lisp, Scheme, Smalltalk, Caml, Haskell, Prolog, Oz
- interpréteurs de commandes et langages de scripts comme Bash, Csh, Korn shell, etc.
- Java, C#, Eiffel
- Perl, Javascript, Ruby
- Le langage de programmation Python utilise un mécanisme de comptage de références doublé depuis la version 2.2 d'un garbage collector pour la destruction des cycles.
Avantages et inconvénients des ramasse-miettes
Les langages utilisant un ramasse-miettes permettent d'écrire des programmes plus simples et plus sûrs. La mémoire étant gérée automatiquement par l'environnement d'exécution, le programmeur est libéré de cette tâche, source de nombreuses erreurs difficiles à débusquer. La gestion manuelle de la mémoire est l'une des sources les plus courantes d'erreur.
Trois types principaux d'erreurs peuvent se produire :
- l'accès à une zone non allouée, ou qui a été libérée,
- la libération d'une zone déjà libérée,
- la non-libération de la mémoire inutilisée (fuites mémoire).
L'utilisation d'outils et de méthodologie appropriés permet d'en réduire l'impact, tandis que l'utilisation d'un ramasse-miettes permet de les éliminer presque complétement – les fuites de mémoire restent possibles, bien que plus rares. Cette simplification du travail de programmation peut présenter quelques inconvénients, principalement au niveau des performances des programmes les utilisant.
Des mesures montrent que dans certain cas l'implémentation d'un ramasse-miettes augmente les performances d'un programme, dans d'autre cas le contraire se produit. Le choix des paramètres du ramasse-miette peut aussi altérer ou améliorer significativement les performances d'un programme. Lorsque le ramasse-miette effectue de nombreuses opérations de copies en tâche de fond (cas de l'algorithme stop-and-copy), il tend à défragmenter la mémoire. Le ramasse-miettes peut ainsi se révéler plus rapide qu'un codage ad-hoc de l'allocation/désallocation. Les meilleures implémentations peuvent aussi optimiser l'utilisation des caches mémoires, accélérant ainsi l'accès aux données. À contrario, l'opération de collection est souvent coûteuse.
Il est difficile de borner le temps d'exécution de la phase de collection des objets non atteignables. L'utilisation d'un ramasse-miettes standard peut donc rendre difficile l'écriture de programmes temps réel ; un ramasse-miettes spécialisé (temps-réel) doit être utilisé pour cela.
Sans intervention du programmeur, un programme utilisant un ramasse-miettes a tendance à utiliser plus de mémoire qu'un programme où la gestion est manuelle (en admettant que, dans ce cas, il n'y a pas de fuites, d'erreur d'accès ou de libération). Toutefois, rien n'interdit d'employer des stratégies de pré-allocation des objets utilisés, dans des pools, lorsqu'on veut minimiser le taux d'allocation/désallocation. Dans ce cas, le ramasse-miettes fournit toujours le bénéfice d'une programmation sans erreur grave de gestion de la mémoire (une assurance).
Bien que ce ne soit pas le but d'un ramasse-miettes son implémentation peut aussi faciliter l'implémentation de la persistance d'objet (certains algorithmes sont partagés).
Citations
« Il est dit que les programmeurs Lisp savent que la gestion de la mémoire est si importante qu'elle ne peut être laissée aux programmeurs, et que les programmeurs C savent que la gestion de la mémoire est si importante qu'elle ne peut être laissée au système » -- Bjarne Stroustrup peut-être tiré d'une source antérieure.
Voir aussi
Liens externes
- [http://www.dotnetguru.org/articles/GC/GC.html Les Ramasses-Miettes .NET et Java ]
- http://www.memorymanagement.org/ (textes en anglais)
- [http://www.cs.utexas.edu/users/oops/papers.html Publications du groupe OOPS de l'Université du Texas] (textes en anglais)
- [http://www.cs.kent.ac.uk/people/staff/rej/gc.html Resources sur les ramasses-miettes] (textes en anglais)
Références
H. Schorr, W.M. Waite, An Efficient Machine-Independent Procedure for Garbage Collection in Various List Structures. CACM Août 1967
Catégorie:Algorithmique
ja:ガベージコレクション
Complexité algorithmique ja:計算複雑性理論 th:ทฤษฎีความซับซ้อนในการคำนวณ
Catégorie:Algorithmique
La théorie de la complexité algorithmique s'intéresse à la bonne utilisation des algorithmes.
Elle s'attache à la question : entre différents algorithmes réalisant une même tâche, quel est le plus rapide et dans quelles conditions ?
Dans les années 1960 et au début des années 1970, alors qu'on en était à découvrir des algorithmes fondamentaux (quicksort, Boyer-Moore...), on ne mesurait pas leur efficacité. On se contentait de dire : « cet algorithme (de tri) se déroule en 6 secondes avec un tableau de 50 000 entiers choisis au hasard en entrée, sur un ordinateur IBM 360/91. Le langage de programmation PL/I a été utilisé avec les optimisations standard ». (cet exemple est imaginaire)
Une telle démarche rendait difficile la comparaison des algorithmes entre eux. La mesure publiée était dépendante du processeur utilisé, des temps d'accès à la mémoire vive et de masse, du langage de programmation/compilateur utilisé, etc.
Une approche indépendante des facteurs matériels était nécessaire pour évaluer l'efficacité des algorithmes. Donald Knuth fut un des premiers à l'appliquer systématiquement dès les premiers volumes de sa série The art of computer programming. Il complétait cette analyse de considérations propres à la théorie de l'information : celle-ci par exemple, combinée à la formule de Stirling, montre qu'il ne sera pas possible d'effectuer un tri général par comparaisons de N élements en un temps croissant moins rapidement avec N que N ln N sur une machine algorithmique (à la différence peut-être d'un ordinateur quantique).
Détails
Si l'on élimine de l'analyse de la complexité la question de la vitesse d'exécution de la machine et la qualité du code produit par le compilateur, il ne reste comme paramètre significatif que « la taille des données sur lesquelles il s'exécute ».
On exprime donc le temps d'exécution en nombre d'opérations élémentaires. Le temps d'exécution d'une opération élémentaire ne dépend pas de la taille de la donnée (par exemple, l'addition de deux entiers codés sur 32 bits prend un même temps, quels que soient les entiers considérés).
Exemples d'opérations élémentaires : accès à une cellule mémoire, comparaison de valeurs, opérations arithmétiques (sur valeurs à codage de taille fixe), opérations sur des pointeurs.
Pour la taille de la donnée, on se limite à un ou plusieurs entiers liés au nombre d'éléments de la donnée. Par exemple, le nombre d'éléments dans un algorithme de tri, dans un ensemble, le nombre de sommets et d'arcs dans un graphe orienté.
On évalue le nombre d'opérations élémentaires en fonction de la taille de la donnée : si 'n' est la taille, on calcule une fonction .
Les critères d'analyse : le nombre d'opérations élémentaires peut varier substantiellement pour deux données de même taille. On retiendra deux critères :
- analyse au sens du plus mauvais cas : est le temps d'exécution du plus mauvais cas et le maximum sur toutes les données de taille n. Par exemple, le tri par insertion simple avec des entiers présents en ordre décroissants.
- analyse au sens de la moyenne : tm(n) est l'espérance sur l'ensemble des temps d'exécution muni d'une distribution des probabilités des temps d'exécution. L'analyse mathématique de la complexité moyenne est souvent très délicate. De plus, la signification de la distribution des probabilité par rapport à l'exécution réelle (sur un problème réel) est à considérer.
On a donc introduit des notations asymptotiques ou notations de Landau.
- idée 1 : évaluer l'algorithme sur des données de grande taille. Par exemple, lorsque n est 'grand', + devient indiscernable de .
- idée 2 : on élimine les constantes multiplicatrices, car deux ordinateurs de puissances différentes diffèrent en temps d'exécution par une constante multiplicatrice. À partir de là, devient
L'algorithme est dit en .
L'idée de base est donc qu'un algorithme en est « meilleur » qu'un algorithme en si |
|
|
| :: RELATED NEWS :: |
Category:Politics of Switzerland
This category focuses on political issues and the quest for political office in Switzerland. For articles about the work of national and local governments in Sweden see :category:Government of Switzerland.
Category:Switzerland
Switz
Switz
|
Robert Dale Owen
Robert Dale Owen (November 7, 1801–June 24, 1877) was a longtime exponent in his adopted United States of the socialist doctrines of his father, the Welshman Robert Owen, as well as a politician in the
The Bijeljina Region is one of the seven regions of Republika Srpska in Bosnia and Herzegovina. Its administrative center is the town of Bijeljina.
It includes the historical/geographic region of Semberija and it is located in the northeast of the count
|
Eliyahu Goldratt
Eliyahu M. Goldratt (1948 - ) is an Israel-born physicist turned business consultant, the originator of the theory of constraints (abbreviation: TOC). He claims that he applied the scientific method to resolving some permanent problems of organizations.
He is the author of several business novels. The Goal introduces TOC's a
|
Kumaso
The Kumaso (熊襲) were a peoples of ancient Japan, believed to have lived in the south of Kyushu until at least the Nara period. Their name, Japanese for "bear people", is most likely a description resulting from embellished tales of their physical features (similar to the Tsuchigumo, whose name means "ground spider"). As the Yamato pushed south
|
Bapsi Sidhwa
Bapsi Sidhwa (1938 - ) is an important author of Pakistani origin who writes in English. She is of Parsi Zoroastrian background, and has depicted Parsi life, customs, and the Zoroastrian religion in great detail in most of her works.
She is also the recipient of many awards, including the Sitara-e-Imtiaz, Pakistan's highest honor.
Sidhwa was born in Karachi,
|
Vlasenica Region
The Vlasenica Region is one of the seven regions of Republika Srpska in Bosnia and Herzegovina. Its administrative center is the town of Zvornik (?) and it is located in the northeast of the country.
Category:Republika Srpska
|
Erzerum
Erzurum (or Erzerum, Arzen in antiquity, Karin in ancient Armenian, Theodosiupolis or Theodosiopolis during Byzantine rule) is one of the Provinces of Turkey, in the Eastern Anatolia Region, to the east of the country. It is surrounded by
|
|
|
