Lisp at 2.1. Le Lisp est lent - Historique

Home
Up
Previous
Next

2.1.    Le Lisp est lent - Historique

Le Lisp a été inventé à la fin des années cinquante par John McCarthy, comme un formalisme mathématique de raisonnement sur certains types d'expressions logiques. Lisp est l'acronyme de LISt Processing : dans ce formalisme, les programmes comme les données sont représentés sous la forme de listes. La représentation analogue des programmes et des données est une caractéristique quasi unique parmi les langages de programmation; comme on l'a vu dans le chapitre précédent, cette caractéristique est de la plus haute importance.

Au début des années 60, McCarthy et ses collègues du MIT Computation Center développèrent le premier interpréteur Lisp sur un IBM 704. Dans les années 60, le Lisp servait principalement à des applications non numériques comme la dérivation symbolique, la linguistique et la démonstration de théorèmes; il était avant tout un langage de recherche, et l'aspect performance n'avait que peu d'importance. A la suite de ses succès dans ces domaines théoriques, les praticiens de l'informatique accordèrent au Lisp un intérêt grandissant. Alors seulement se posa la question des compilateurs Lisp et de leur efficacité. Bien que ceci soit de l'histoire ancienne, la réputation d'inefficacité du Lisp a la vie dure.

Les implantations actuelles du Lisp sont basées sur des compilateurs capables d'exploiter au mieux les caractéristiques de l'architecture du processeur hôte, tout comme les compilateurs de n'importe quel langage.

Voici le résultat de tests effectués sur une station Unix SUN3 (voir [GABR90]); le tableau ci-dessous donne les rapports de Lisp au C pour le temps d'exécution et pour la taille du code généré par le compilateur, dans le cas de trois tests standard :

 

Rapports du Lisp au C (Lisp/C) pour:

  le temps d'exécution la taille du code généré
Tak 0.9 1.21
Traverse 0.98 1.35
Lexer 1.07 1.48

Tak est un test mesurant l'efficacité de l'appel de fonctions (procédures) et des opérations sur les nombres entiers. Traverse mesure l'efficacité de la construction et de l'accès à des structures (structures de données). Lexer concerne la manipulation de caractères.

Dans le cas du Lisp, les tests ont été effectués sans tenir compte de la charge de la gestion automatique de la mémoire (par le ramasse-miettes, garbage collector en anglais); cela représente environ 2% du temps d'exécution (actuellement, ces ramasse-miettes sont non-intrusifs : ce processus passe inaperçu pour l'utilisateur).

Il existe d'autres comparaisons de ce genre, voir par exemple [FATE91] où il est montré que le Lisp se compare favorablement au C pour un test d'addition et de multiplication polynomiales.

Concernant le calcul avec des nombres réels, les meilleurs compilateurs Lisp approchent les meilleurs compilateurs Fortran (sans doute la référence en la matière). Voici le résultat d'un test de multiplication de matrices (100*100, single float) effectué sur une station Sun Sparc1+ (Allegro CL, Fortran Sun):

 

Lisp

F77

F77 -fast

C/Assembleur

0.73s

4.9s

0.48s

0.2s

A remarquer le facteur 10 entre le Fortran optimisé (F77 -fast) et le Fortran non optimisé (F77). Si un facteur 2 est réellement important, quelque soit le langage utilisé, il est sans doute préférable d'utiliser des librairies spécialisées (comme LAPACK, linear algebra package) qui donneront des résultats du genre de la dernière colonne du tableau (celle-ci correspond à un programme très optimisé où les 2 matrices initiales sont partagées en matrices de 2*3, la multiplication étant faite sur ces sous-matrices; ce programme tient compte de l'architecture du processeur).

Remarques

  1. Etant donné l'augmentation rapide de la puissance des processeurs, il convient de minimiser l'importance de l'efficacité d'un compilateur en comparaison de la richesse de l'environnement de développement et de la puissance du langage.
  2. Outre le fait que le Lisp n'a rien à envier aux autres langages quant à ses performances, il dispose de caractéristiques intéressantes pour des applications purement numériques:

    Nombres entiers

    Contrairement au C et au Fortran, le Lisp permet une précision arbitraire sur les opérations en arithmétique des nombres entiers : il n'y a pas de limites quant à la grandeur d'un nombre entier; la mémoire est automatiquement allouée en fonction des besoins de la représentation.

    Tableaux

    Les tableaux sont dynamiques; le nombre de dimensions et la taille de chacune des dimensions ne doivent pas être fixés à la compilation (le nombre maximum de dimensions est d'au moins 7, selon le standard Common Lisp).

    Un tableau peut être ajustable : une fois créé, la taille de chacune de ses dimensions peut être augmentée (par exemple, ceci se révèle très utile dans certaines applications de la théorie des graphes).

    Un tableau peut être défini comme le sous-tableau physique d'un autre; cela se fait simplement, en une étape, à la création du tableau.

    Types et fonctions arithmétiques prédéfinis

    Le Common Lisp possède un grand nombre de types prédéfinis (integer, rational, complex rational, complex integer, short float, single float, double float, long float, complex, ...). De plus y sont disponibles nombre de fonctions arithmétiques (élémentaires, trigonométriques, hyperboliques, logiques, etc.).

Home    Previous    Up    Next
contact
site map
Last update : 27/11/2001