:: wikimiki.org ::
| Optimisation Du Code |
Optimisation du code
En programmation informatique, l'optimisation est la pratique qui consiste généralement à réduire le temps d'exécution d'une fonction, l'espace occupé par les données et le programme, ou la consommation d'énergie.
La règle numéro un de l'optimisation est quelle ne doit intervenir qu'une fois que le programme fonctionne et répond aux spécifications fonctionnelles.
L'expérience montre qu'optimiser du code avant que ces deux conditions ne soient réalisées revient le plus souvent à une perte de temps et s'avère néfaste à la clarté du code et au bon fonctionnement du programme :
:« L'optimisation prématurée est la source de tous les maux. », Donald Knuth citant Dijkstra
La plupart des compilateurs récents pratiquent de façon automatique un certain nombre d'optimisations qu'il serait fastidieux d'effectuer manuellement et qui rendraient le code source moins lisible.
L'optimisation manuelle peut s'avérer nécessaire dans des cas très spécifiques, mais les mesures montrent que sur des machines RISC qui possèdent un nombre élevé de registres et où l'efficacité demande le regroupement des instructions identiques pour bénéficier de l'effet pipeline, l'optimiseur d'un compilateur C fournit souvent un code plus efficace que celui qui serait écrit en assembleur par un programmeur expérimenté (ce qui n'était jamais le cas sur les machines CISC). Et de surcroit ce code est bien plus facile à maintenir, car les instructions en C restent dans un ordre lié à la seule intelligibilité du code et non aux spécificités de la machine : dans les optimiseurs actuels, en effet, les ordres machines associés à une instruction ne se trouvent plus nécessairement en position contiguë, pour des raisons d'efficacité d'exécution. Cela rend le code assembleur généré particulièrement indéchiffrable.
Pratique de l'optimisation
Première approche
Avant de commencer l'optimisation, il faut savoir mesurer la vitesse du code. Pour cela il faut choisir un paramètre, de préférence simple, mesurable. Ceci peut-être par exemple le temps de traitement sur un jeu de donnée précis, ou le nombre d'images affichées par seconde, ou encore le nombre de requêtes traitées par minute.
Une fois le paramètre de mesure déterminé, il faut mesurer le temps passé dans chacune des parties du programme. Il n'est pas rare que 80% à 90% du temps soit consacré à l'exécution de 10% du code (les boucles critiques). Les chiffres varient en fonction de la taille et de la complexité des projets. Il faut localiser ces 10% de code pour être le plus rentable dans ses optimisations. Cette étape de localisation peut être réalisée à l'aide d'outils spécialisés d'instrumentation du code nommés profilers. Ils sont chargés de compter le nombre d'exécutions de chaque fonction et de cycles du microprocesseur correspondants au cours de l'exécution.
Ensuite on itère sur la section la plus consommatrice de ressource autant de fois que nécessaire cette boucle :
- optimisation d'une partie du code
- mesure du gain de performances
Seconde approche
On peut optimiser à plusieurs niveaux un programme:
- au niveau algorithmique, en choisissant un algorithme de complexité inférieure (au sens mathématique) et des structures de données adaptées,
- au niveau du langage de développement, en ordonnant au mieux les instructions et en utilisant les bibliothèques disponibles,
- en utilisant localement un langage de bas niveau, qui peut être le langage C ou, pour les besoins les plus critiques, le langage assembleur.
On ne passe au niveau supérieur d'optimisation qu'une fois qu'on a épuisé les possibilités d'un niveau. L'utilisation d'un langage de bas niveau sur l'ensemble d'un projet pour des raisons de rapidité est l'une des erreurs les plus communes et les plus coûteuses que puisse faire un projet industriel.
L'optimisation de code est considéré par beaucoup de développeurs amateurs comme un art un peu magique et, pour cette raison, comme l'une des parties les plus excitantes de la programmation. Ceci les conduit à croire qu'un bon programmeur est une personne qui optimise d'emblée le programme. Cependant l'expérience montre qu'elle ne peut pallier une mauvaise conception initiale. C'est dans la conception que l'expérience du développeur joue le plus. Par ailleurs, dans un nombre majoritaire et grandissant de cas, le « bon programmeur » est moins celui qui écrit du code astucieux (l'optimiseur s'en chargera le plus souvent mieux que lui) que celui qui écrit du code lisible et aisé à maintenir.
Une bonne connaissance des techniques de structures de données ainsi que des algorithmes (même sans aller jusqu'aux considérations théoriques poussées de la complexité algorithmique) se montre bien plus féconde que celle d'un langage d'assemblage. Lorsqu'on a déterminé l'algorithme le plus adéquat, les optimisations les plus efficaces peuvent être obtenues en utilisant le chemin suivant :
- écriture du code critique dans un langage de haut niveau (comme Scheme ou Common Lisp),
- application de transformations mathématiques successives qui préservent la spécification du programme tout en réduisant la consommation des ressources,
- traduction du code transformé dans un langage de bas niveau (langage C).
Dans la pratique, les performances des machines actuelles font que des applications comportant beaucoup d'entrées-sorties peuvent faire l'économie de ces trois étapes et se rédiger directement dans un langage comme Haskell. L'application bien connue nget, qui moissonne systématiquement les images publiées dans les forums Usenet, avait dans sa première implémentation été écrite en Haskell. La version en C n'en a été qu'une traduction qui ne se révèle pas plus performante pour ce type d'application.
Optimisation automatique
Les compilateurs sont souvent capable de faire des optimisations locales, auxquelles aucun développeur ne penserait en première approche.
Pour le langage C, cela peut considérer :
- les variables locales et les registres
- les fonctions non implémentées en assembleur en tant que fonction
- les switch, qui sont optimum.
Exemples
Une spécificité du binaire : le décalage
Une des toutes premières optimisations a été celle de la division et de la multiplication par une puissance de 2.
En effet, l'informatique actuelle repose sur le binaire, puisqu'elle utilise comme élément de base le transistor (et historiquement, auparavant le relais) qui n'autorise que deux valeurs différentes.
On a donc logiquement implémenté en langage machine les opérations de décalage à gauche et décalage à droite.
En effet, en binaire, le décalage d'un nombre d'un cran vers la gauche le multiplie par 2.
:Ainsi, 2 (102) décalé de 1 bit donne 4 (1002).
:5 (1012) décalé de 2 bits donne 20 (101002) : .
Ceci marche aussi pour la division, en décalant les bits vers la droite.
:100 (11001002) décalé de 3 bits vers la droite donne donc 12 (11002) car nous travaillons sur des nombres entiers.
La division (en dehors de ce cas et des cas pathologiques) est une instruction coûteuse en temps machine, et n'est d'ailleurs toujours pas disponible sur la grande majorité des processeurs de type RISC.
Le mot clef inline du C
Le code C suivant:
inline int f(int a, int b)
int g (int a)
Une compilation avec gcc -O4 -S donne:
.file "opt.c"
.text
.p2align 4,,15
.globl g
.type g, @function
g:
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %edx
cmpl $12, %edx
jg .L14
leal -2(%edx), %eax
cmpl $11, %edx
jge .L15
movl $100, %eax
cmpl $10, %edx
.L17:
je .L2
movl %edx, %eax
.L15:
imull %edx, %eax
.L2:
popl %ebp
ret
.p2align 4,,7
.L14:
movl $1437600, %eax
cmpl $1200, %edx
jmp .L17
.size g, .-g
.section .note.GNU-stack,"",@progbits
.ident "GCC: (GNU) 3.3.2 (Mandrake Linux 10.0 3.3.2-6mdk)"
Ce qui pourrait se traduire, pour une compréhension plus aisée, par le code C suivant:
int g(int a)
On peut remarquer par exemple que la fonction 'f' n'a pas été générée, mais que son code a directement été incorporé dans la fonction 'g' (le mot clef 'inline' permet de forcer ce type d'optimisation en C )
Catégorie:Programmation informatique
Programmation ko:프로그래밍 ja:プログラミング
La programmation dans le domaine informatique est l'ensemble des activités qui permettent l'écriture des programmes informatiques. C'est une étape importante de la conception de logiciel (voire de matériel, cf. VHDL).
Pratiques
- Algorithmique
- Codage
- Contrôle de version
- Optimisation du code
- Programmation système
- Refactoring
- Test unitaisre
Techniques de programmation
- Programmation impérative
- Programmation orientée objet
- Programmation par contrat
- Programmation déclarative
- Programmation fonctionnelle
- Programmation logique
- Programmation par contraintes
- Programmation orientée composant
- Programmation orientée aspect
- Programmation concurrente
Langages de programmation
Les langages de programmation permettent de définir les ensembles d'instructions effectuées par l'ordinateur lors de l'exécution d'un programme. Il existe des milliers de langages de programmation, la plupart d'entre eux étant réservés à des domaines spécialisés. Ils font l'objet de recherches constantes dans les universités et dans l'industrie.
Les langages de programmation peuvent être classifiés de nombreuses manières : généraliste/spécialisé, haut niveau/bas niveau, interprété/compilé, avec ou sans gestion de mémoire automatisée, système de gestion d'exceptions, typage fort/typage faible, typage statique/typage dynamique, syntaxe fixe/extensible ; non objet/orienté objet/purement objet, impératif/fonctionnel/déclaratif, fonctionnel pur/impur, etc.
Nous incluons ci-dessous une classification sommaire des langages de programmation les plus connus. Il faut garder à l'esprit que de nombreux langages appartiennent simultanément à plusieurs catégories - ils sont dits « multi-paradigmes ».
Par exemple, C++ permet la programmation impérative, orientée objet et la programmation générique (à base de classes et de fonctions paramétrées nommées templates). Common Lisp est à la fois impératif, fonctionnel, orienté objet -- et de par son caractère « programmable » (un langage de programmation programmable...), il peut intégrer d'autres « paradigmes » de programmation en son sein (par exemple la programmation logique, ou par contraintes).
Ci-dessous, nous listons les langages les plus connus (nous mettons entre parenthèses certains langages dérivés ou les extensions requises).
Langages déclaratifs
- Oz
- Mercury
- Prolog pour PROgrammation LOGique
- Clips
Ci-dessous, nous listons les langages spécialisés, c'est-à-dire dont l'utilisation est réservée à des domaines bien spécifiques ; les plus connus sont :
Langages de définition de données
- ASN.1
- DTD SGML
- DTD XML
- XML Schéma
- Relax NG
Langages spécialisés pour la communication avec une base de données
- 4GL
Langages de manipulation de chaînes de caractères
- SNOBOL StriNg Oriented symBOlic Language (Langage Symbolique Orienté Chaînes de Caractères)
- awk
- Perl
- sed
Langages spécialisés Web
- Exécution par le serveur HTTP (côté serveur) :
- ASP
- JSP (issu de Java, basé sur des Servlets)
- PHP
- XSP (issu de XML, soutenu par Apache)
- D'une manière générale, les langages non spécialisés (notamment Perl et C) peuvent également être utilisés via Common Gateway Interface
- Exécution par le navigateur Web (côté client) :
- JavaScript ou ECMAScript
- VBScript
- applets écrites en Java
- ActionScript de Macromedia Flash
Langages de description de page
voir Langage de balisage
Langages de programmation théorique
- Lambda-calcul
- Pi-calcul
- Join-Calcul
- Récursion Primitive
- Système T de Kurt Gödel
- BNF
Langages de programmation de Commande Numérique (C.N.)
Une machine-outil automatisée, ou Commande Numérique (C.N.), a besoin d'un langage de programmation pour réaliser les opérations de tournage, ou de fraisage…
- Programmation de Commande Numérique
Pour rendre la programmation plus difficile
- Brainfuck (ou encore F
- ckF
- ck, Ook ou spoon)
- Intercal
- Malbolge
- Unlambda
Non classés
- Nosica
- SAS
- Langage K
- GOTO++
Langages spécialisés
- ABEL : langage pour la programmation électronique des PLD
- R : langage pour l'outil de statistiques du même nom
- VHDL : langage de description matérielle, permettant de synthétiser de l'électronique numérique (descriptions de portes logiques)
- VRML : description de scènes en trois dimensions
- Allegro - multi-plateforme, Multimédia, Jeux
- DirectX - 3D, Multimédia
- GTK+ - multi-plateforme, Environnement graphique
- JFC - Environnement graphique, 2D
- OpenGL - 3D
- Qt - multi-plateforme, Interface utilisateur
- Quartz - Environnement graphique
- SDL - Video
- SWT - multi-plateforme, Interface utilisateur
- Tk - multi-plateforme - Interface graphique associée à Tcl
- wxWidgets - multi-plateforme - Environnement graphique
- Xlib - 2D
Voir aussi
Liens internes
- Chronologie des langages de programmation
- [http://fr.wikibooks.org/wiki/Programmation Wikilivre sur la programmation]
- ABAP
- RIP
Liens externes
- [http://www.codes-sources.com/ CodeS-SourceS ] : site de passionnés qui partagent leurs connaissances
- [http://www.developpez.com/ Developpez.com, le club des développeurs] (de nombreux forums, cours et tutoriels de programmation)
- [http://www.levenez.com/lang/ Computer Languages History]
- [http://www.techbooksforfree.com/perlpython.shtml Free Python Books]
- [http://www.a525g.com/programmation/index-fr.htm A525G - Programmation]
- [http://www.99-bottles-of-beer.net/ 99 Bouteilles de Bière - Un même programme en plus de 780 langages]
- [http://coding.romainl.com Programmation Network Security]
- [http://rmdiscala.developpez.com/cours/ Package pédagogique multimédia V4.1]
Catégorie:Programmation informatique
Fonction (informatique) ja:関数 (プログラミング)
En informatique, une fonction est un ensemble d'instructions réalisant une certaine tâche.
Une fonction prend zéro ou plusieurs paramètres et renvoie éventuellement un résultat. Une fonction qui modifie ses paramètres est appelée procédure. Une fonction propre à un objet est plutôt désignée par le terme de méthode.
Les fonctions réalisant des tâches similaires et dont l'objectif est d'être réutilisées par plusieurs programmes sont regroupées dans des bibliothèques.
Un paradigme de programmation dans lequel toute l'application est vue comme un ensemble de fonctions qui s'enchaînent et s'appellent mutuellement est dit fonctionnel.
Une fonction en informatique se distingue principalement de la fonction mathématique par le fait qu'en plus de calculer un résultat à partir de paramètres, la fonction informatique peut avoir des effets de bord : par exemple afficher un message à l'écran, jouer un son, ou bien piloter une imprimante.
Catégorie:Programmation informatique
Donald Knuth
Donald Ervin Knuth (né le 10 janvier 1938 à Milwaukee, Wisconsin) est un informaticien de renom et professeur émérite en informatique à l'Université de Stanford.
Knuth est mieux connu en tant qu'auteur de l'ouvrage The Art of Computer Programming (couramment appelé TAOCP), une des références dans le domaine de l'informatique,
pour ne pas dire la bible (un mot cher à Knuth...) des informaticiens.
Ce livre a créé un domaine : l'analyse d'algorithmes (i.e. comprendre via une analyse mathématique rigoureuse pourquoi telle méthode est plus efficace [temps, mémoire] qu'une autre,
en moyenne ou en pire des cas).
Knuth consacre désormais presque toute son énergie à achever les 7 volumes de TAOCP (la première édition du premier volume remonte à 1968 et seuls trois volumes ont paru). Il est le pionnier de l'algorithmique, et a fait de nombreuses contributions dans plusieurs branches de l'informatique théorique. Il est le créateur du système de composition de documents TEX et du système de création de polices Metafont, et a inauguré le concept de programmation littérale.
Knuth est une figure de l'informatique, connue pour son humour geek : il offre par exemple une prime de $2,56 pour chaque typo ou erreur découverte dans ses livres sous prétexte que « 256 pennies font un dollar hexadécimal ». (Sa prime pour les erreurs de 3:16 Bible Texts Illuminated est cependant de $3,16). Les numéros de version de TEX convergent vers pi, c'est-à-dire que les versions se suivent de la sorte: 3, 3.1, 3.14, etc, les numéros de version de Metafont convergent eux vers e. Il a également mis en garde les utilisateurs d'un de ses logiciels ainsi: « Faites attention aux bugs dans ce code ; je n'ai fait que le prouver, je ne l'ai pas essayé » ([http://www-cs-faculty.stanford.edu/~knuth/faq.html source]).
Knuth est également l'auteur de 3:16 Bible Texts Illuminated (1991), ISBN 0895792524, dans lequel il tente d'examiner la Bible par une analyse du chapitre 3, verset 16 de chaque livre. Chaque verset est accompagné d'une calligraphie contribuée par un groupe de calligraphistes dirigés par Hermann Zapf. L'ouvrage n'a pas été traduit en français.
Il a reçu son bachelor's degree en mathématiques à la Case Western Reserve University. Il obtient ensuite son doctorat en mathématiques au California Institute of Technology en 1963. En 1968, il devient membre de la faculté de l'Université de Stanford, où il a préalablement reçu un curieux titre académique créé à son intention: Professor Emeritus of the Art of Computer Programming. En 1971, Knuth fut le premier à recevoir le prix ACM Grace Murray Hopper Award. Il a reçu de nombreuses autres distinctions honorifiques, entre autres le prix Turing, la National Medal of Science, la médaille John von Neumann (États-Unis) ainsi que le prix de Kyoto et la Médaille Franklin. Il est élu membre associé de l'Académie des sciences française en 1992 et membre de la Royal Society en 2003.
Knuth apprécie la musique et aime en particulier jouer de l'orgue. Il dispose d'un orgue dans sa propre maison qu'il a construit lui-même. Knuth nie cependant tout talent particulier pour jouer de cet instrument. Il a cessé d'utiliser le courrier électronique en prétendant qu'il s'en était servi entre 1975 et le 1 janvier 1990, et que cela suffisait pour toute une vie. Il trouve plus efficace de tenir une correspondance en « mode batch », et y consacrer une journée tous les trois mois, en répondant par courrier « classique ».
Il est marié à Jill Knuth, qui a publié un livre sur la liturgie. Ils ont deux enfants.
Knuth a publié son premier article dans un magazine scolaire en 1957. À forte teneur humoristique, celui-ci a été publié dans le numéro de juin 1957 du magazine américain MAD.
Sa [http://algo.inria.fr/AofA/Research/11-97.html première analyse d'algorithme]
remonte à l'été 1962, il s'agissait d'étudier l'efficacité d'un algorithme de hachage, grande fut sa surprise de voir que ceci était relié à de très jolies mathématiques remontant à Ramanujan.
Liens externes
- [http://en.wikiquote.org/wiki/Donald_Knuth Wikiquote - Citations de Donald Knuth]
- [http://www-cs-faculty.stanford.edu/~knuth/ La page web de Donald Knuth à l'université de Stanford]
- [http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Knuth.html Une longue biographie de Knuth]
- [http://scpd.stanford.edu/knuth/ Vidéos de présentations avec Donald Knuth]
Knuth, Donald
Knuth, Donald
Knuth, Donald
Knuth, Donald
ja:ドナルド・クヌース
ko:도널드 카누스
Edsger DijkstraEdsger Dijkstra (Rotterdam, 11 mai 1930 - 6 août 2002) était un mathématicien et informaticien néerlandais du
Après des études de physique théorique, il s'engagea dès 1955 dans le domaine de l'informatique alors naissante dont il fut l'un des pionniers les plus éclairés.
Parmi ses contributions se trouve un algorithme de plus court chemin dans les graphes, connu sous le nom d'algorithme de Dijkstra. Enseignant à l'université d'Eindhoven, il commença à se faire connaître en matière de systèmes avec The THE operating system, un système construit en couches d'abstractions successives, et idéal pour l'enseignement (« THE » signifiant Technische Hochschule Eindhoven). Fort de l'expérience d'écriture de ce système, il formalisa la notion, avant lui diffuse, de sémaphore puis introduisit la notion de section critique avec deux exemples devenus des classiques :
- Le problème des lecteurs et des rédacteurs
- Le dîner des philosophes
Constatant les dégâts provoqués par l'usage incontrôlé de l'instruction GOTO en programmation, il rédigea en 1968 dans les Communications of the ACM l'article fondateur On the Go To Statement Considered Harmful, considéré comme l'article qui décida nombre de programmeurs à passer à la programmation structurée (contenant des structures de contrôle plus policées comme if ... then ... else ... fi, do...while, repeat...until).
Il avait eu un rôle important dans le développement du langage Algol à la fin des années 1950, et développa ensuite « la science et l'art des langages de programmation en général, contribuant grandement à notre compréhension de leur structure, de leur représentation et de leur implémentation » (citation de l'ACM, Association for Computer Machinery). Toutefois Niklaus Wirth (créateur d'Algol W et de Pascal) alla plus loin que lui dans le domaine en considérant de pair la structuration des programmes et celles des données.
Le discours qu'il prononça en 1972 lorsqu'il reçut le prix Turing, The Humble Programer, est resté célèbre. Il est disponible [http://www.adrahon.org/classiques/le_programmeur_modeste.php en traduction française] (lien externe).
Anecdotes
Il est né dans le même village que Vincent Van Gogh et son ambition était de devenir plus célèbre que lui. Parmi les informaticiens c'est réussi, mais pour le grand public ce n'est pas certain.
Il avait une très belle écriture manuscripte et a toujours refusé d'utiliser un traitement de textes, préfèrant la lettre manuscripte photocopiée. Luca Cardelli a créé une fonte Dijkstra en son honneur, elle imite son écriturer régulière. Dijkstra référençait toutes ses lettres par EWD suivi d'un nombre.
Il adorait BB King.
Citations
L'informatique n'est pas plus la science de l'ordinateur que l'astronomie est celle du téléscope.
À propos de l'intelligence artificielle : Déterminer si un ordinateur saurait penser n'est pas plus intéressant que de tenter de savoir si un sous-marin sait nager.
Voir aussi
Krzysztof Apt: Edsger Wybe Dijkstra (1930-2002): A Portrait of a Genius in Formal Aspects of Computing(2002) 14:92-08 [http://homepages.cwi.nl/~apt/ps/dijkstra.pdf]
Autostabilisation
Dijkstra, Edsger
Dijkstra, Edsger
Dijkstra, Edsger
Dijkstra
Dijkstra
ja:エドガー・ダイクストラ
ko:에드스거 다익스트라
Compilateur
Un compilateur est un programme informatique qui traduit un langage, le langage source, en un autre, appelé le langage cible, en préservant la signification du texte source. Ce schéma général décrit un grand nombre de programmes différents ; et ce que l'on entend par « signification du texte source » dépend du rôle du compilateur. Lorsque l'on parle de compilateur, on suppose aussi en général que le langage source est, pour l'application envisagée, de plus haut niveau que le langage cible, c'est-à-dire qu'il présente un niveau d'abstraction supérieur.
En pratique, un compilateur sert le plus souvent à traduire un code source écrit dans un langage de programmation en un autre langage, habituellement un langage d'assemblage ou un langage machine. Le programme en langage machine produit par un compilateur est appelé code objet.
Le premier compilateur a été écrit par Grace Hopper.
Structure d'un compilateur
La tâche principale d'un compilateur est de produire du code objet correct. La plupart des compilateurs permettent d'optimiser le code (le code objet optimisé s'exécutera plus rapidement, ou aura une occupation mémoire moindre).
Un compilateur fonctionne par analyse-synthèse, c'est-à-dire qu'au lieu de remplacer chaque construction du langage source par une suite équivalente de constructions du langage cible, il commence par analyser le texte source pour en construire une représentation intermédiaire qu'il traduit à son tour en langage cible.
Il est donc naturel de séparer — au moins conceptuellement, mais aussi en
pratique — le compilateur en une partie avant (ou frontale), parfois appelée « souche », qui lit le texte source et produit la représentation intermédiaire, et une partie arrière (ou finale), qui parcourt cette représentation pour produire le texte cible. Dans un compilateur idéal, la partie avant est indépendante du langage cible, tandis que la partie arrière est indépendante du langage source. Certains compilateurs effectuent de plus sur la forme intermédiaire des traitements substantiels, que l'on peut regrouper en une partie centrale, indépendante à la fois du langage source et de la machine cible. On peut ainsi écrire des compilateurs pour toute une gamme de langages et d'architectures en partageant la partie centrale, à laquelle on attache une partie avant par langage et une partie arrière par architecture.
Les étapes de la compilation incluent
- le découpage du programme en lexèmes (analyse lexicale) ;
- la vérification de la correction de la syntaxe du programme (analyse syntaxique) ;
- l'analyse des structures de données (analyse sémantique) ;
- la transformation du code source en code intermédiaire ;
- l'application de techniques d'optimisation sur le code intermédiaire ;
- l'allocation de registres et la traduction du code intermédiaire en code objet, avec éventuellement l'insertion de données de débogage et d'analyse de l'exécution ;
- enfin vient la phase d'édition des liens.
Ces différentes étapes expliquent que les compilateurs fassent toujours l'objet de recherches, particulièrement dans le domaine de l'optimisation du code produit.
Compilateurs particuliers
Compilateur croisé
Un compilateur croisé (en anglais cross compiler) est un programme capable de traduire un code source en code objet ayant un environnement d'exécution (architecture matérielle, système d'exploitation) différent de celui où la compilation est effectuée. Ces compilateurs sont principalement utilisés en informatique industrielle.
Byte code
Certains compilateurs traduisent un langage source en langage machine virtuel, c'est-à-dire en un code exécuté par une machine virtuelle : un programme émulant les principales fonctionnalités d'un ordinateur. Le portage d'un programme ne requiert ainsi que le portage de la machine virtuelle. C'est le cas du compilateur Java, qui traduit du code Java en bytecode Java (code objet). Une machine virtuelle DotNet peut exécuter du bytecode MSIL produit par les langages de Microsoft C#, Visual Basic ou autres.
Autres compilateurs
Si la plupart des compilateurs traduisent un code d'un langage de programmation vers un autre, ce n'est pas le cas de tous les compilateurs. Par exemple, le logiciel LaTeX compile un code écrit dans le langage de formatage de texte LaTeX, pour le convertir en un autre langage, par exemple DVI, HTML, PostScript...
Le problème de l'amorçage (bootstrap)
Les premiers compilateurs étaient écrits directement en langage assembleur, un langage symbolique élémentaire correspondant aux instructions du processeur cible et quelques structures de contrôle légèrement plus évoluées. Ce langage symbolique doit être assemblé (et non compilé) et lié pour obtenir une version exécutable. En raison de sa simplicité, un programme simple suffit à le convertir en instructions machines.
Les compilateurs actuels sont généralement écrits dans le langage qu'ils doivent compiler ; par exemple un compilateur C est écrit en C, SmallTalk en SmallTalk, Lisp en Lisp, etc. Dans la réalisation d'un compilateur, une étape décisive est franchie lorsque le compilateur pour le langage X est suffisamment complet pour se compiler lui-même : il ne dépend alors plus d'un autre langage (fut-ce de l'assembleur) pour être produit.
Les bugs des compilateurs sont parfois très complexes à détecter. Si un compilateur de langage C comporte un bug, les programmeurs en langage C auront naturellement tendance à mettre en cause leur propre code source, non pas le compilateur.
Pire, si ce compilateur bogué (version V1) compile un compilateur (version V2) non bogué, l'exécutable compilé (par V1) du compilateur V2 sera bogué. Pourtant son code source est bon. Le bootstrap oblige donc les programmeurs de compilateurs à contourner les bugs des compilateurs existants.
Articles connexes
- Interpréteur
- Informatique
- compilateur de compilateur
Lien externe
- [http://perso.club-internet.fr/cdridi Exemple d'interpréteur et de partie-avant d'un compilateur].
- [http://www.idiom.com/free-compilers Liste de compilateurs gratuits et/ou libres]
Catégorie:Compilateur
ja:コンパイラ
ko:컴파일러
simple:Compiler
th:ตัวแปลโปรแกรม
RISCReduced instruction set computer Catégorie:Acronyme
Pipeline (informatique)
En architecture des ordinateurs, un pipeline est une technique de conception des processeurs où l'exécution de plusieurs instructions se chevauchent à l'intérieur même du processeur. Le premier ordinateur à utiliser cette technique est l'IBM Stretch, conçu en 1958.
Définition
Soit un microprocesseur où 5 cycles sont nécessaires pour accomplir une instruction :
# IF (Instruction Fetch) charge l'instruction à exécuter depuis la mémoire.
# ID (Instruction Decode) décode l'instruction et adresse les registres.
# EX (Execute) exécute l'instruction (par la ou les unités arithmétiques et logiques).
# MEM (Memory), dénote un transfert depuis un registre vers la mémoire dans le cas d'une instruction du type STORE (accès en écriture) et de la mémoire vers un registre dans le cas d'un LOAD (accès en lecture).
# W.B (Write Back) stocke le résultat dans un registre. La source peut être la mémoire ou bien un registre.
En supposant que chaque étape met 1 cycle d'horloge pour s'exécuter, il faut normalement 5 cycles pour exécuter une instruction, 15 pour 3 instructions :
registre
Si l'on insère des registres tampons (pipeline registers) entre chaque unité à l'intérieur du processeur, celui ci peut alors contenir plusieurs instructions, chacune à une étape différente.
Les 5 instructions s'exécuteront en 9 cycles, et le processeur sera capable de produire une instruction par cycle à partir de la cinquième, malgré le fait que chacune d'entre elles nécessite 5 cycles pour s'exécuter complètement.
registre
Au 5ème cycle, tous les étages sont en cours d'exécution.
Architecture superscalaire
Si l'on multiplie le nombre d'unités dans le processeur, il est possible d'exécuter plusieurs instructions simultanément. Sur un processeur superscalaire de degré 2, deux instructions sont chargés depuis la mémoire simultanément. C'est le cas des processeurs DEC Alpha, et de quelques autres.
quelques autres
Architecture superpipeline
Certaines architectures ont découplé le nombre d'étapes, celui-ci pouvant aller de 8 à 31 pour l'Intel Prescott. Une telle architecture sera appelée superpipelinée. Voici par exemple le pipeline du Pentium 4, à 20 étages :
quelques autres
Architecture vectorielle
Sur de tels processeurs, une instruction va s'appliquer à un ensemble de données, appelé vecteur. Une seule instruction va donc exécuter la même opération de façon répétitive sur tout le vecteur.
vecteur
Architecture VLIW
Dans les architectures VLIW (Very Long Instruction Word, ou Mot d'instruction très long), l'instruction va contenir les opérations pour chaque unité de calcul disponible dans le processeur. De ce fait chaque instruction peut être définie sur 256 bits, voire plus (512, 1024,...).
bit
Quelques profondeurs de pipeline
Aujourd'hui tous les microprocesseurs sont pipelinés :
Problèmes
Les pipelines provoquent de nouveaux problèmes, en particulier d'interdépendance, ils ne sont pas tous listés ci dessous, juste deux cas simples sont abordés.
Interdépendance des données
Une instruction ne peut récupérer le résultat de la précédente car celui-ci n'est pas encore disponible. Ainsi, la séquence :
ADD R1, R2, R3 // R1 = R2 + R3
STORE R1, 1000 // C(1000) = R1
Ne stocke pas à l'emplacement mémoire 1000 la valeur de R1 contenant la somme R2 + R3, mais la valeur de R1 contenue avant l'instruction ADD. Pour résoudre ce problème particulier, il est parfois possible de créer des courts-circuits pour amener le résultat de l'étape précédente vers l'unité qui en a besoin directement, sans passer par les registres de pipeline.
Interdépendance procédurale
Se pose le même problème avec les sauts :
MOV R1, #1000 // R1 = 1000
JUMP R1 // Saut inconditionnel
R1 ne contient pas encore la valeur 1000 au moment où l'instruction de saut va s'exécuter.
Une solution possible à ces deux problèmes est d'insérer une instruction entre les deux qui sont interdépendantes. Prenons par exemple la séquence suivante :
1: A = B + C
2: D = A + C
3: E = F + B
qui comporte une dépendance directe simple, A ne pouvant être disponible pour la partie droite de la seconde instruction.
- la première solution, triviale, est d'insérer des NOP (No Operation), c'est ce que font les compilateurs quand on ne précise pas d'option d'optimisation du code :
1: A = B + C
1b: NOP
2: D = A + C
3: E = F + B
- la seconde solution consiste à réarranger les instructions. Dans cet exemple, l'opération de la ligne n'a aucune interdépendance avec les deux précédentes. Le code modifié sera :
1: A = B + C
2: E = F + B
3: D = A + C
Références
Liens internes
- Processeur superscalaire
- Processeur vectoriel
- Processeur VLIW
Langage Assembleur ja:アセンブリ言語
Catégorie:Langage de programmation
Catégorie:Langage impératif
Cet article parle du langage assembleur, voyez aussi Programme assembleur
Présentation
Le langage assembleur ou langage d'assemblage, dit aussi assembleur tout court, est le langage de programmation lisible pour un humain le plus proche du langage machine utilisé par le microprocesseur de la machine. Le langage machine est une combinaison de bits, il est rendu lisible en remplaçant les valeurs brutes par des symboles appelés mnémoniques (grec mnêmonikos, relatif à la mémoire), simples et plus faciles à retenir.
Par exemple, alors qu'un processeur de la famille x86 reconnaîtra ce que l'instruction machine
10110000 01100001
signifie, pour le programmeur c'est plus simple de se souvenir de son équivalent en langage assembleur :
mov $0x61, %al
(cela signifie de mettre la valeur hexadécimale 61 (97 en décimal) dans le registre 'AL'.)
Contrairement à un langage de haut niveau, il y a une correspondance 1-1 entre le code assembleur et le langage machine, ainsi il est possible de traduire le code dans les deux sens sans perdre d'information. La transformation du code assembleur en langage machine est accomplie par un programme nommé assembleur, dans l'autre sens par un programme désassembleur. Les opérations s'appellent respectivement assemblage et désassemblage. Dans un programme réel en assembleur, c'est un peu plus complexe que cela (on peut donner des noms aux routines, aux variables), et on n'a plus cette correspondance. Sur les premiers ordinateurs, la tâche d'assemblage était accomplie manuellement par le programmeur.
Chaque architecture d'ordinateurs a son propre langage machine, et donc son propre langage d'assemblage (l'exemple ci-dessus est pour le x86).
Ces différents langages diffèrent par le nombre et le type d'opérations qu'ils ont à supporter. Ils peuvent avoir des tailles et des nombres de registres différents, et différentes représentations de type de données en mémoire. Tous les ordinateurs sont capables de faire les mêmes choses, ils peuvent les faire de manière différente.
De plus, plusieurs groupes de mnémoniques ou de syntaxe de langage assembleur peuvent exister pour un seul ensemble d'instructions.
Le sens des transferts
Une polémique, dans la communauté des programmeurs, consiste dans le "sens" des transferts.
Notre exemple ci-dessus est donné en syntaxe AT&T. En syntaxe Intel, cela donnerait :
MOV AL,61h
C'est vraiment histoire de goût - les opérandes sont inversés - et des possibilités du programme d'assemblage (certains gèrent les deux syntaxes, d'autres une seule). Néanmoins cela ne facilite pas la maintenance des programmes !
Remarquons quand même que cette instruction se traduisant, dans la plupart des langages évolués, par (ici en pseudo-C) :
Al = 0x61 ;
La syntaxe "Intel" semble la plus logique.
Remarquons aussi que en français on dirait :
mettre 0x61 dans AL
La syntaxe "AT&T" semble alors la plus logique.
Ou alors :
AL reçoit 0x61
Ce qui semble tout aussi logique.
Instructions machine
Des opérations de base sont disponibles dans la plupart des jeux d'instructions
- déplacement
- chargement d'une valeur dans un registre
- déplacement d'une valeur depuis un emplacement mémoire dans un registre, et inversement
- calcul
- addition, soustraction, multiplication ou division des valeurs de deux registres et chargement du résultat dans un registre
- combinaison de valeurs de deux registres avec un et/ou logique
- rendre négative la valeur d'un registre arithmétiquement (complément à 2) ou par un non logique (complément à 1)
- modification du déroulement du programme
- saut à un autre emplacement dans le programme (normalement, les instructions sont exécutées séquentiellement, les unes après les autres)
- saut à un autre emplacement, mais après avoir sauvegardé l'instruction suivante afin de pouvoir y revenir (point de retour)
- retour au dernier point de retour
- comparaison
- comparer les valeurs de deux registres
Et on trouve des instructions spécifiques avec une ou quelques instructions pour des opérations qui auraient dû en prendre beaucoup. Exemples :
- déplacement de grands blocs de mémoire
- arithmétique lourde (sinus, cosinus, racine carrée, etc.)
- application d'une opération simple (par exemple, une addition) à un ensemble de données
Exemples simples
Voici quelques exemples simples :
- en syntaxe AT&T (écrits pour l'assembleur GNU)
- utilisant le jeu d'instructions i386
- à utiliser comme suit :
$ as truc.s -o truc.o
$ ld truc.o -o truc
$ ./truc
Afficher Bonjour
.global _start
BONJ: .ascii "Bonjour\n"
_start: mov $4 , %eax
mov $1 , %ebx
mov $BONJ , %ecx
mov $8 , %edx
int $128
mov $1 , %eax
mov $0 , %ebx
int $128
Lire le clavier (16 caractères max) puis l'afficher
# define N 16
.global _start
.comm BUFF , N
_start: mov $3 , %eax
mov $0 , %ebx
mov $BUFF , %ecx
mov $N , %edx
int $128
mov %eax , %edx
mov $4 , %eax
mov $1 , %ebx
mov $BUFF , %ecx
int $128
mov $1 , %eax
mov $0 , %ebx
int $128
Directives du langage assembleur
En plus de coder les instructions machine, les langages assembleur ont des directives supplémentaires pour assembler des blocs de données et assigner des adresses aux instructions en définissant des étiquettes ou labels.
Ils sont capables de définir des expressions symboliques qui sont évaluées à chaque assemblage, rendant le code encore plus facile à lire et à comprendre.
Ils ont habituellement un langage macro intégré pour faciliter la génération de codes ou de blocs de données complexes.
Usage du langage Assembleur
Il y a des débats sur l'utilité du langage assembleur. Dans beaucoup de cas, des compilateurs-optimiseurs peuvent transformer du langage de haut niveau dans un code qui tourne de façon plus efficace qu'un code assembleur écrit à la main, tout en restant beaucoup plus facile à lire et à "maintenir".
Cependant,
#quelques calculs complexes écrits directement en assembleur, en particulier sur des machines massivement parallèles, seront plus rapides,
#certaines routines (drivers) sont parfois plus simples à écrire en langage de bas niveau.
#des tâches très dépendantes du système, exécutées dans l'espace mémoire du système d'exploitation sont parfois difficiles à écrire dans un langage de haut niveau.
Certains compilateurs transforment, lorsque leur option d'optimisation la plus haute n'est pas activée, des programmes écrits en langage de haut niveau en code assembleur, chaque instruction de haut niveau se traduisant en une série d'instructions assembleur rigoureusement équivalentes et utilisant les mêmes symboles; cela permet de voir le code dans une optique de débogage et de profilage, ce qui permet de gagner parfois beaucoup plus de temps en remaniant un algorithme. En aucun cas ces techniques ne peuvent être conservées pour l'optimisation finale.
Beaucoup de systèmes embarqués sont aussi programmés en assembleur pour bénéficier du maximum des possibilités de ces systèmes, souvent limités en ressources, bien que progressivement les composants de ces systèmes soient de plus en plus puissants pour un coût identique.
Macro-assembleur
Beaucoup d'assembleurs gèrent un langage de macros. Il s'agit de regrouper plusieurs instructions afin d'avoir un enchaînement plus logique et moins fastidieux.
Par exemple (en assembleur Microsoft MASM) :
putchar Macro car ; Prototype de la macro
ifdef car ; si car est défini
mov dl,car ; le mettre dans dl
endif
mov ah,2 ; ah=2 : fonction "putchar" en DOS
int 21h ; appel au DOS
endm ; fin macro
est une macro qui affiche un caractère sous MS-DOS. On l'utilisera par exemple ainsi :
putchar "X"
Et cela générera :
mov dl,"X"
mov ah,2
int 21h
----
Références
Article connexe
Voir Programme assembleur
Liens externes
- [http://sourceforge.net/projects/nasm/ NASM - Netwide Assembler]
- [http://www.asmfr.com/ AsmFR ] : site de passionnés qui mettent en commun leurs connaissances - [http://www.codes-sources.com/ CodeS-SourceS]
CISCComplex_instruction_set_computer Catégorie:Acronyme
Langage de programmation ko:프로그래밍 ja:プログラミング
La programmation dans le domaine informatique est l'ensemble des activités qui permettent l'écriture des programmes informatiques. C'est une étape importante de la conception de logiciel (voire de matériel, cf. VHDL).
Pratiques
- Algorithmique
- Codage
- Contrôle de version
- Optimisation du code
- Programmation système
- Refactoring
- Test unitaisre
Techniques de programmation
- Programmation impérative
- Programmation orientée objet
- Programmation par contrat
- Programmation déclarative
- Programmation fonctionnelle
- Programmation logique
- Programmation par contraintes
- Programmation orientée composant
- Programmation orientée aspect
- Programmation concurrente
Langages de programmation
Les langages de programmation permettent de définir les ensembles d'instructions effectuées par l'ordinateur lors de l'exécution d'un programme. Il existe des milliers de langages de programmation, la plupart d'entre eux étant réservés à des domaines spécialisés. Ils font l'objet de recherches constantes dans les universités et dans l'industrie.
Les langages de programmation peuvent être classifiés de nombreuses manières : généraliste/spécialisé, haut niveau/bas niveau, interprété/compilé, avec ou sans gestion de mémoire automatisée, système de gestion d'exceptions, typage fort/typage faible, typage statique/typage dynamique, syntaxe fixe/extensible ; non objet/orienté objet/purement objet, impératif/fonctionnel/déclaratif, fonctionnel pur/impur, etc.
Nous incluons ci-dessous une classification sommaire des langages de programmation les plus connus. Il faut garder à l'esprit que de nombreux langages appartiennent simultanément à plusieurs catégories - ils sont dits « multi-paradigmes ».
Par exemple, C++ permet la programmation impérative, orientée objet et la programmation générique (à base de classes et de fonctions paramétrées nommées templates). Common Lisp est à la fois impératif, fonctionnel, orienté objet -- et de par son caractère « programmable » (un langage de programmation programmable...), il peut intégrer d'autres « paradigmes » de programmation en son sein (par exemple la programmation logique, ou par contraintes).
Ci-dessous, nous listons les langages les plus connus (nous mettons entre parenthèses certains langages dérivés ou les extensions requises).
Langages déclaratifs
- Oz
- Mercury
- Prolog pour PROgrammation LOGique
- Clips
Ci-dessous, nous listons les langages spécialisés, c'est-à-dire dont l'utilisation est réservée à des domaines bien spécifiques ; les plus connus sont :
Langages de définition de données
- ASN.1
- DTD SGML
- DTD XML
- XML Schéma
- Relax NG
Langages spécialisés pour la communication avec une base de données
- 4GL
Langages de manipulation de chaînes de caractères
- SNOBOL StriNg Oriented symBOlic Language (Langage Symbolique Orienté Chaînes de Caractères)
- awk
- Perl
- sed
Langages spécialisés Web
- Exécution par le serveur HTTP (côté serveur) :
- ASP
- JSP (issu de Java, basé sur des Servlets)
- PHP
- XSP (issu de XML, soutenu par Apache)
- D'une manière générale, les langages non spécialisés (notamment Perl et C) peuvent également être utilisés via Common Gateway Interface
- Exécution par le navigateur Web (côté client) :
- JavaScript ou ECMAScript
- VBScript
- applets écrites en Java
- ActionScript de Macromedia Flash
Langages de description de page
voir Langage de balisage
Langages de programmation théorique
- Lambda-calcul
- Pi-calcul
- Join-Calcul
- Récursion Primitive
- Système T de Kurt Gödel
- BNF
Langages de programmation de Commande Numérique (C.N.)
Une machine-outil automatisée, ou Commande Numérique (C.N.), a besoin d'un langage de programmation pour réaliser les opérations de tournage, ou de fraisage…
- Programmation de Commande Numérique
Pour rendre la programmation plus difficile
- Brainfuck (ou encore F
- ckF
- ck, Ook ou spoon)
- Intercal
- Malbolge
- Unlambda
Non classés
- Nosica
- SAS
- Langage K
- GOTO++
Langages spécialisés
- ABEL : langage pour la programmation électronique des PLD
- R : langage pour l'outil de statistiques du même nom
- VHDL : langage de description matérielle, permettant de synthétiser de l'électronique numérique (descriptions de portes logiques)
- VRML : description de scènes en trois dimensions
- Allegro - multi-plateforme, Multimédia, Jeux
- DirectX - 3D, Multimédia
- GTK+ - multi-plateforme, Environnement graphique
- JFC - Environnement graphique, 2D
- OpenGL - 3D
- Qt - multi-plateforme, Interface utilisateur
- Quartz - Environnement graphique
- SDL - Video
- SWT - multi-plateforme, Interface utilisateur
- Tk - multi-plateforme - Interface graphique associée à Tcl
- wxWidgets - multi-plateforme - Environnement graphique
- Xlib - 2D
Voir aussi
Liens internes
- Chronologie des langages de programmation
- [http://fr.wikibooks.org/wiki/Programmation Wikilivre sur la programmation]
- ABAP
- RIP
Liens externes
- [http://www.codes-sources.com/ CodeS-SourceS ] : site de passionnés qui partagent leurs connaissances
- [http://www.developpez.com/ Developpez.com, le club des développeurs] (de nombreux forums, cours et tutoriels de programmation)
- [http://www.levenez.com/lang/ Computer Languages History]
- [http://www.techbooksforfree.com/perlpython.shtml Free Python Books]
- [http://www.a525g.com/programmation/index-fr.htm A525G - Programmation]
- [http://www.99-bottles-of-beer.net/ 99 Bouteilles de Bière - Un même programme en plus de 780 langages]
- [http://coding.romainl.com Programmation Network Security]
- [http://rmdiscala.developpez.com/cours/ Package pédagogique multimédia V4.1]
Catégorie:Programmation informatique
C (langage)
En informatique, C est un langage de programmation impératif.
C’est un des langages les plus utilisés pour trois raisons :
- il est très facile à porter d’une machine à une autre (le compilateur est écrit en C : il y a juste à changer les routines de génération de code et à le faire se compiler lui-même pour une machine cible),
- il est relativement facile à comprendre à première vue, étant plus pauvre en concepts que le C++, par exemple,
- il n’est pas très éloigné de la machine.
Ses principaux inconvénients sont :
- il encourage le programmeur négligent à produire du code non portable ,
- il nécessite beaucoup d'attention du programmeur pour ne pas introduire de bugs, notamment via les manipulations de pointeurs ,
- il y a un certain nombre de points subtils et mal connus du langage.
Histoire
Le langage C est apparu au cours de l’année 1972 dans les Laboratoires Bell. Il était développé en même temps qu’UNIX par Dennis Ritchie et Ken Thompson. Ken Thompson avait développé un prédécesseur de C, le langage B. Dennis Ritchie a fait évoluer le langage B dans une nouvelle version suffisamment différente pour qu’elle soit appelée C. Par la suite, Brian Kernighan aida à populariser le langage. Il procéda aussi à quelques modifications de dernière minute. En 1978, il fut notamment le principal auteur du livre The C Programming Language décrivant le langage enfin fixé ; Ritchie s’était occupé des appendices et des exemples avec UNIX. On parle encore de K&R C (pour Kernighan and Ritchie C) lorsqu’on se réfère au langage tel qu’il existait à cette époque.
En 1983, l’institut national américain de normalisation (ANSI) a formé un comité de normalisation du langage qui a abouti en 1989 à l’approbation de la norme dite ANSI C ou C89 (formellement ANSI X3.159-1989). En 1990, cette norme a également été adoptée par l’ISO (formellement ISO/CEI 9899:1990). ANSI C est une évolution du K&R C qui reste extrêmement compatible. Elle reprend quelques idées de C++.
En 1999, une nouvelle évolution du langage est normalisée par l’ISO : C99 (ISO 9899). Parmi les ajouts, on notera des fonctionnalités déjà présentes dans certains compilateurs comme gcc, ainsi que des fonctionnalités (types complexes, mot-clef « restrict », directives agissant sur la simplification des instructions arithmétiques) souhaitables pour les calculs numériques intensifs, domaine habituel de FORTRAN.
Description
Le langage C peut être qualifié de bas niveau ou peu typé dans le sens où le langage manipule les mêmes sortes d’objets que la plupart des ordinateurs : des mots machine (pouvant contenir une donnée interprétée comme un nombre, un caractère ou une adresse). Le langage ne propose aucune opération qui traite directement des objets de plus haut niveau (fichier, chaîne de caractères, liste...) et il faut donc faire appel à des fonctions de la bibliothèque standard pour manipuler ce type d’objet.
Le langage C a été utilisé pour rendre le système d’exploitation UNIX plus portable. Il a conservé de cela une très grande efficacité pour tout ce qui concerne le développement système. Ainsi depuis la majorité des grands systèmes d’exploitation ont été développés en C.
De même, le langage ne propose pas en standard la gestion de la programmation orientée objet, ni de mécanisme d’exception, ou de traitement multitâche. Il existe des fonctions standards pour gérer les entrées-sorties et les chaînes de caractères, mais contrairement à d'autres langages, aucun opérateur spécifique pour améliorer l'ergonomie. Ceci rend aisé le remplacement des fonctions standards par des fonctions spécifiquement conçues pour un programme donné. En autorisant la surcharge des opérateurs, C++ permet de mélanger la souplesse de C à l'ergonomie des opérateurs spécifiques.
Ces caractéristiques en font néanmoins un langage à privilégier quand on cherche à maîtriser les ressources utilisées, le code assembleur généré par les compilateurs étant relativement prévisible et parfois même optimal sur les machines d’architecture RISC à grand nombre de registres.
Ce langage est donc extrêmement utilisé dans des domaines comme :
la programmation embarquée sur microcontrôleurs, les calculs intensifs, l’écriture de systèmes d’exploitation et tous les modules où la rapidité de traitement est importante. Il est en effet une bonne alternative aux langages assembleurs dans ces domaines avec les avantages d’une syntaxe plus lisible et de la portabilité du code.
En contrepartie, la mise au point de programmes en C, surtout s’ils utilisent des structures de données complexes, est plus difficile qu’avec des langages de plus haut niveau. En effet, dans un souci de performance le langage C impose à l’utilisateur de programmer certains traitements (libération de la mémoire, vérification de la validité des index sur les tableaux...) qui sont pris en charge automatiquement par les langages de haut niveau.
Le C étant un langage simple, son compilateur est assez simple. Sur un nouveau microprocesseur, un compilateur C peut être écrit en deux mois. C’est pour cela qu’il est souvent choisi comme premier langage sur une nouvelle architecture. Le compilateur GNU GCC est d’ailleurs écrit en C : seule la partie de génération de code est à modifier quand on porte le compilateur sur une autre machine, par compilation croisée.
Beaucoup de limitations du langage C ont été levées dans le langage C++ qui est, à l'origine, un C avec la notion d’objet.
Beaucoup d’autres langages de programmation ont adopté une syntaxe (notation) ressemblant à celle du langage C, notamment C++, Java, JavaScript, PHP ou C#.
Exemples
Hello world
Voici l’exemple de programme Hello world donné dans The C Programming Language de Brian W. Kernighan et Dennis M. Ritchie :
#include
main()
Le même programme, conformément à la norme ANSI :
#include
int main(void)
- #include <stdio.h> inclut le fichier d'en-tête stdio.h, contenant les déclarations relatifs aux entrées-sorties de la bibliothèque C ANSI.
- main() indique le début de la fonction principale du programme.
- Les accolades
- printf est la fonction standard d'écriture formatée dans la sortie standard (la console par défaut).
- Les caractères " délimitent la chaîne de caractères à afficher.
- Le \n désigne le saut de ligne.
- Le point-virgule ; termine toute instruction.
- La norme ANSI exige qu'un code retour soit explicitement renvoyé.
Quelques instructions C
Instructions du pré-compilateur
#include,
#define,
#pragma (C89),
#if,
#ifdef,
#ifndef,
#elif (C89),
#else,
#endif,
#undef,
#line,
#error.
Mots clés
auto,
break,
case,
const (C89),
continue,
do,
else,
enum (C89),
extern,
for,
goto,
if,
inline (C99),
register,
restrict (C99),
return,
sizeof,
static,
struct,
switch,
typedef,
union,
void (C89),
volatile (C89),
while,
signed (C89),
unsigned,
char,
short,
int,
long,
float,
double,
_Bool (C99),
_Complex (C99),
_Imaginary (C99)
Types
- Types entiers (mot machine) : int, unsigned int
- Types entiers >= 8 bits : char, signed char, unsigned char
- Types entiers >= 16 bits : short, unsigned short
- Types entiers >= 32 bits : long, unsigned long
- Types entiers >= 64 bits (C-99) : long long, unsigned long long
- Types à virgule flottante : float, double, long double (C89)
- Types énumérés : enum
- Types élaborés : struct, union
Quelques défauts du C
- Le C étant dépouillé volontairement de toute fonctionnalité non rudimentaire, même les opérations les plus simples (opérations sur chaînes de caractères, ordres d’entrée-sortie) se font par des fonctions qui ne peuvent se livrer à aucune vérification syntaxique approfondie au moment de la compilation (hormis une vérification élémentaire du type des arguments). Un programme nommé lint tentait de remédier à ce défaut du langage; quelques fonctionnalités de lint furent par la suite intégrées au compilateur lui-même, et splint fut créé pour remplacer lint.
- Chaque programmeur C a au moins une fois écrit par mégarde = au lieu de dans un if()... avec des résultats hautement inattendus, vu qu’une affectation est exécutée au lieu d’un test ! Toutefois, cette erreur classique est signalée par un message d'avertissement par de nombreux compilateurs. Il est généralement recommandé de compiler C en activant les messages d'avertissement.
- Le débordement de tampon peut passer inaperçu et avoir des conséquences dramatiques.
- Les erreurs d’allocation mémoire comme un oubli d’allocation, une double désallocation, ou un accès à une zone non allouée sont très difficiles à éviter. Il faut noter qu'un ramasse-miettes conservateur pour le C existe (le collecteur Böhm-Weiser), sous la forme d'une bibliothèque, mais son utilisation peut être parfois délicate.
Références
Ressources Internet
- [http://cm.bell-labs.com/cm/cs/who/dmr/chist.html The Development of the C Language] par Dennis Ritchie
- [http://www-rocq.inria.fr/codes/Anne.Canteaut/COURS_C/ Cours de C]
- [http://www.isty-info.uvsq.fr/~rumeau/fclc/ FAQ du groupe fr.comp.lang.c]
- [http://www.eskimo.com/~scs/C-faq/top.html comp.lang.c Frequently Asked Questions], très technique, très haute qualité
- Le livre de programmation C sur Wikilivres
- [http://www.cppfrance.com/ CPPFrance ] : site de passionnés qui mettent en commun leurs connaissances - [http://www.codes-sources.com/ CodeS-SourceS]
- [http://c.developpez.com/ Rubrique C] de [http://www.developpez.com/ Developpez.com], premier site francophone d'entraide entre développeurs.
Bibliographie
- B.W.Kernighan D.M.Ritchie, Le langage C, ISBN 2-225-82070-8
Quelques programmes célèbres écrits en C
- UNIX
- La suite de compilateurs GNU Compiler Collection (GCC)
- Le noyau Linux
- Le noyau de Microsoft Windows
- GNOME
Compilateurs C
- [http://gcc.gnu.org/ GCC] (multiples plateformes)
- [http://www.cs.princeton.edu/software/lcc/ LCC] (multiples plateformes)
- [http://www.cs.virginia.edu/~lcc-win32/ LCC Win32] (Windows)
- [http://www.tendra.org/ TenDRA]
- [http://www.ten15.org/ Ten15], un fork de TenDRA
Catégorie:Langage de programmation
Catégorie:Langage impératif
Catégorie:Norme ISO
ja:C言語
ko:C 프로그래밍 언어
ms:Bahasa pengaturcaraan C
th:ภาษาซี
Algorithme ko:알고리즘 ja:アルゴリズム th:อัลกอริทึม
Catégorie:Algorithmique
On nomme algorithmique la science des algorithmes, visant à étudier les opérations nécessaires à la réalisation d'un calcul. On parle également de procédé ou de procédure. Une recette de cuisine constitue par exemple un algorithme parfaitement défini.
Historique
Antiquité
Les algorithmes dont on a retrouvé des descriptions exhaustives ont été utilisés dès l'époque des Babyloniens, pour des calculs concernant le commerce et les impôts.
L'algorithme le plus célèbre est celui attribué à Euclide permettant de trouver le plus grand commun diviseur de deux nombres.
Etude systématique
L'algorithmique a été systématisée par le mathématicien persan Al Kwarizmi (780-850), auteur d'un ouvrage décrivant des méthodes de calculs algébriques (ainsi que d'un autre introduisant le zéro des Indiens). Son nom donna au moyen-âge le nom "algorisme" qui devint algorithme avec lady Ada Lovelace, fille de lord Byron et assistante de Charles Babbage (1792-1871).
On peut voir une allusion à la méthode algorithmique chez René Descartes dans le Discours de la méthode : « diviser chacune des difficultés que j'examinerois, en autant de parcelles qu'il se pourroit, et qu'il seroit requis pour les mieux résoudre. » Néanmoins, cette approche ne parle ni de boucles, ni d'itérations.
Le substantif algorithmique désigne la méthode utilisant des algorithmes. Le terme est également employé comme adjectif.
Un algorithme énonce une résolution sous la forme d'une série d'opérations à effectuer. La mise en œuvre de l'algorithme consiste en l'écriture de ces opérations dans un langage de programmation et constitue alors la brique de base d'un programme informatique.
Les informaticiens utilisent fréquemment l'anglicisme implémentation pour désigner cette mise en œuvre. L'écriture en langage informatique est aussi fréquemment désignée par le terme « codage », qui n'a ici aucun rapport avec la cryptographie, mais qui se réfère au terme « code source » pour désigner le texte, en langage de programmation, constituant le programme. L'algorithme devra être plus ou moins détaillé selon le niveau d'abstraction du langage utilisé ; autrement dit, une recette de cuisine doit être plus ou moins détaillée en fonction de l'expérience du cuisinier.
Exemples d'algorithme
Il existe un certain nombres d'algorithmes classiques, utilisés pour résoudre des problèmes ou plus simplement pour illustrer des méthodes de programmation. On se réfèrera aux articles suivants pour de plus amples détails :
- Tours de Hanoï, problème célèbre illustrant la programmation récursive.
- Problème du tri, ou comment trier un ensemble de nombres le plus rapidement possible.
- Problème des huit dames, placer huit dames sur un échiquier sans qu'elles puissent se prendre entre elles.
La principale notion mathématique dans le calcul du coût d'un algorithme précis sont les notions de négligeabilité (notée o(f(n)), « petit o ») et de domination (notée O(f(n)), « grand o »), où f est une fonction mathématique de n, variable désignant la quantité d'informations (en bits, en nombre d'enregistrements…) manipulée dans l'algorithme. Les fonctions mathématiques relèvent de l'analyse. En algorithmique on trouve souvent des complexités du type :
- indépendant de la taille de la donnée
- , complexité logarithmique
- , complexité linéaire
- , complexité quasi-linéaire
- , complexité quadratique
- , complexité cubique
- , complexité polynômiale
- , complexité quasi-polynômiale
- , complexité exponentielle
- , complexité factorielle
Sans entrer dans les détails mathématiques, on peut dire que lorsque l'on calcule l'efficacité d'un algorithme (sa complexité algorithmique), on cherche davantage à connaître l'évolution du nombre d'instructions de base en fonction de la quantité de données à traiter (par exemple, dans un
algorithme de tri, le nombre de lignes à trier), que le coût exact en secondes et en quantité de mémoire. Baser le calcul de la complexité d'un algorithme sur le temps qu'un ordinateur particulier prend pour effectuer le-dit algorithme ne permet pas de prendre en compte la structure interne de l'algorithme ni la particularité de l'ordinateur : selon sa charge de travail, la vitesse de son processeur, la vitesse d'accès aux données ou même l'exécution de l'algorithme (qui peut faire intervenir le hasard) le temps d'exécution ne sera pas le même.
Quelques indications sur l'efficacité des algorithmes
Souvent, l'efficacité d'un algorithme n'est connue que de manière asymptotique, c'est-à-dire pour de grandes valeurs du paramètre n.
Lorsque ce paramètre est suffisamment petit, un algorithme de complexité supérieure peut en pratique être plus efficace.
Ainsi, pour trier un tableau de 30 lignes (c'est un paramètre de petite taille), il est inutile d'utiliser un algorithme évolué comme
Quicksort (l'un des algorithmes de tri les plus efficaces en moyenne) : l'algorithme de tri le plus trivial sera suffisamment efficace.
À noter aussi : entre deux algorithmes dont la complexité est identique, on cherchera à utiliser celui dont l'occupation mémoire est la plus faible. L'analyse de la complexité algorithmique peut également servir à évaluer l'occupation mémoire d'un algorithme. Enfin, le choix d'un algorithme plutôt qu'un autre doit se faire en fonction des données que l'on s'attend à lui fournir en entrée. Ainsi, le Quicksort (ou tri rapide), lorsque l'on choisit le premier élément comme pivot, se comporte de façon désastreuse si on l'applique à une liste de valeur ... déjà triée ! Il n'est donc pas judicieux de l'utiliser si on prévoit que le programme recevra en entrée des listes à peu près triées.
Un autre paramètre à prendre en compte est la localité de l'algorithme. Par exemple pour un système à mémoire virtuelle qui dispose de peu de mémoire (par rapport au nombre de données à traiter), le Tri rapide sera normalement plus efficace que le Tri par tas car le premier ne passe qu'une seule fois sur chaque élément de la mémoire tandis que le second accède à la mémoire de manière discontinue (ce qui augmente le risque de "swapping").
Les heuristiques
Pour certains problèmes, les algorithmes ont une complexité beaucoup trop grande pour obtenir un résultat en temps raisonnable, même si l'on pouvait utiliser une puissance de calcul phénoménale. On est donc amené à rechercher une solution la plus proche possible d'une solution optimale en procédant par essais successifs. Puisque toutes les combinaisons ne peuvent être essayées, certains choix stratégiques doivent être faits. Ces choix, généralement très dépendants du problème traité, constituent ce qu'on appelle une heuristique. Le but d'une heuristique est donc de ne pas essayer toutes les combinaisons possibles avant de trouver celle qui répond au problème, afin de trouver une solution approchée convenable (qui peut être exacte dans certains cas) dans un temps raisonnable.
C'est ainsi que les programmes de jeu d'échecs, de jeu de go (pour ne citer que ceux-là) font appel de manière très fréquente à des heuristiques qui modélisent l'expérience d'un joueur. Certains logiciels antivirus se basent également sur des heuristiques pour reconnaître des virus non répertoriés dans leur base, en s'appuyant sur des ressemblances avec des virus connus.
Applications
- Cryptologie et Compression de données
- Structure de données, Algorithmes de tri et Recherche dichotomique
- Allocation de mémoire et ramasse-miettes
- Informatique musicale
- Algorithme génétique en informatique décisionnelle
Voir aussi
- Al-Khuwarizmi
- Algorithme récursif
- Algorithme réparti
- Langage K
- Métaheuristique
- Structure de contrôle
Liens externes
- [http://www-ipst.u-strasbg.fr/pat/program/algo.htm Introduction à l'algorithmique, avec des exemples en langage C]
- [http://www.pise.info/algo/codage.htm Initiation à l'algorithmique]
- [http://www.myalgorithm.com Algorithmes de base dans plusieurs langages de programmation]
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 | | |
