English Version

C'est une question que je me pose depuis des années. LispE n'est pas mon premier langage de programmation, loin de là. J'ai déjà proposé par le passé: Tamgu un langage plutôt riche puisqu'il intègre dans la même syntaxe un Prolog, des listes en compréhension utilisant une syntaxe inspirée de Haskell et un langage proche de Python.

LispE partage de nombreux points communs avec l'implémentation de Tamgu, mais sous une forme plus épurée. Les choix initiaux d'une implémentation ont parfois des effets pernicieux qui finissent par alourdir une approche donnée, mais qui pris dans la nasse du code noyau deviennent indéboulonnables. Parfois, la meilleure solution est de recommencer à zéro.

Le choix que j'ai fait dans le cas de LispE est de projeter sur des classes C++ un fonctionnement quasi fonctionnel. Ainsi, chaque objet dans LispE est une instance d'une classe particulière associée à une méthode eval (voir Interpreter) De plus, chaque instruction du langage est une méthode particulière dans la classe List. Il suffit de quelques minutes pour enrichir le langage avec une nouvelle méthode.

Ainsi chaque objet sait comment s'évaluer, il n'existe donc pas de machine virtuelle pour exécuter les instructions de façon centralisée, ce qui a pour effet de rendre le multi-tâche quasi transparent. En revanche, la question de l'efficacité se pose immédiatement. Cette implémentation est-elle rapide ?

Pour répondre à cette question, nous avons implémenté un algorithme de descente de gradient. Tout d'abord, le choix de cet algorithme n'a rien d'accidentel. Il est aujourd'hui absolument fondamental en Intelligence Artificielle, y compris dans les approches les plus avancées comme Transformer. Evidemment, le code que nous proposons ici n'a que peu de chance d'apparaître dans le moindre code professionnel. Dans Python, l'implémentation ferait appel à PyTorch ou numpy.

En revanche, cet algorithme est suffisamment complexe pour qu'une comparaison entre LispE et Python soit aussi intéressante que significative.

Nous n'allons pas décrire les deux programmes en détail. Leur code est disponible respectivement ici:

Code Python

Code LispE

En revanche, nous avons tenté de conserver un même style de code des deux côtés.

Nous supposerons que nos données ont la structure suivante:

# X et Y ont la même taille
X = [[1, 0.72, 0.32], [1, 0.75, 0.12], [1, 0.53, 0.65] etc.]
Y = [6.93, 5.99, 1.46, 1.44, 4.51, 1.25, 2.53, 6.88 etc.]
a = [0.1, 0.1, 0.1] 

La fonction de perte des moindres carrés:

𝑆 =  ∑(𝑦𝑖 − <𝑎, 𝑥𝑖>)²

est construite de la façon suivante en Python:

def Loss(a, X,Y):
     # sAX contient le calcul de: <a, xi>
     sAX = []
     for x in X:
         sAX.append(sum([w * e for (w,e) in zip(a,x)]))
     return sum([(yy - e)**2 for (yy,e) in zip(Y,sAX)])

Nous utilisons des listes en intention où les listes sont combinées via l'opérateur zip.

En LispE, le code est très proche:

(setq Loss (sum (zipwith (λ(x y) (• (• y - (sum (•  a * x))) ^^ 2)) X Y)))

Notons que le calcul de sAX est implicite en LispE. En effet, le langage sait par défaut multiplier deux listes, élément par élément.

L'opérateur • permet d'écrire une formule mathématique sous sa forme infixée:

(• a * x) correspond en fait à: (* a x)

Lorsque l'on exécute les deux codes sur la même machine, ici un iMac équipé d'un processeur Intel Core i7 quad-core à 4.2 GHz avec 32 Go de mémoire. Nous obtenons les résultats suivants:

LispE:    9ms
Python:  45ms

La différence est particulièrement significative, puisque l'on a un ratio de 1 pour 5.

Pour être honnête, la première version de LispE était loin d'offrir de telles performances. De fait, nous avons suivi le principe bien connu qu'une optimisation prématurée est la racine de tous les maux. Nous nous sommes d'abord concentrés sur l'implémentation du langage avant de nous intéresser aux problèmes de performance. Fort heureusement, les choix d'implémentation se sont révélés plutôt judicieux (le résultat d'années d'errement). Il a suffit de quelques modifications mineures locales pour améliorer les performances.

Le nombre d'itérations dans Python et LispE pour atteindre les mêmes valeurs est un peu différent. Pour certaines raisons, il faut 449 itérations avec Python et 452 avec LispE.

Toujours est-il que Python et LispE utilisent la même représentation flottante de 64 bits, mais les erreurs de calcul ont tendance à s'accumuler au point qu'un petit bit de différence dans la mantisse peut avoir un effet de bord sur les comparaisons des pertes, lequel s'avère légèrement pire dans LispE que dans Python.

Cependant, nous avons également testé avec des flottants 32 bits sur LispE (il suffit de remplacer numbers par floats.)

Dans ce cas, les résultats sont très différents... VRAIMENT TRES différents.

En effet, il ne faut plus que 175 itérations pour converger et ce en 3ms.

Le premier choix a été d'offrir dans LispE des listes spécialisées sous la forme de classes C++ particulières chacune avec ses propres surcharges de méthodes. Ainsi, la classe Numbers offre des méthodes spécifiques pour l'addition ou la multiplication, ce qui minimise le surcoût qu'un accès générique à une liste aurait entrainé.

//Une liste de type Numbers possède sa propre méthode d'addition de liste
//On peut de plus détecter le type de e de façon à choisir la méthode la plus 
//efficace.
Element* Numbers::plus_direct(LispE* lisp, Element* e) {
    switch (e->type) {
        case t_numbers: {
	//On "caste" e en un objet du même type
            Numbers* n = (Numbers*)e;
            long szl = liste.size();
            long i = n->liste.size();

           szl = lmin(szl, i);

	//l'addition des deux listes se fait localement
            for (i = 0; i < szl; i++) {
                liste.vecteur[i] += n->liste[i];
            }
            return this;
etc.

Le fait que l'addition ou la multiplication de deux listes sa fassent directement, quasiment sans objets intermédiaires a un impact très significatif sur les performances, de près de 40% par rapport à la version initiale.

Dans Python, cette absence d'objets spécialisés est largement compensée par numpy.

C++ est souvent opposé aux langages de programmation dont la gestion mémoire est effectuée via un ramasse-miette. Comme d'habitude ce n'est qu'en partie vraie. Certes C++ oblige le programmeur à analyser soigneusement son code pour vérifier que tous les objets créées ont bien été nettoyés en fin d'analyse. Les fuites mémoire n'ont rien d'une légende urbaine. Elles sont d'ailleurs l'une des principales raisons qui donne à C++ sa réputation de langage difficile.

Mais il existe un deuxième aspect qui lui est souvent oublié: la fragmentation de la mémoire. En effet, l'allocation et la désallocation des objets peut avoir des aspects désastreux sur la vitesse d'exécution. Les objets n'ayant jamais tout à fait la même taille, leur création et leur destruction peut laisser des trous, ce qui oblige le système à régulièrement réorganiser la mémoire pour éviter de saturer celle-ci trop vite. Ces opérations finissent par avoir un coût extravagant sur l'exécution, divisant les performances par deux ou trois.

La solution est de réutiliser les objets autant que faire se peut.

Au lieu de détruire un objet non utilisé, il est bien plus intéressant de le placer dans un pool d'objets du même type dans lequel on puisera au besoin. Bien sûr, seuls les objets les plus fréquents tels que les nombres, les chaines ou les listes, seront gérés en pools (voir lispe.h).

En fin d'exécution, ces pools d'objets pourront être détruits en une seule fois.

L'utilisation de ces pools dans LispE a permis de diviser le temps de calcul par trois.

Chaque appel d'une fonction ou d'une lambda nécessite l'enregistrement dans la pile d'exécution de variables avec leurs valeurs. Nous avons créé un dictionnaire sur mesure dont les clefs sont des uint16_t. En effet, les noms de variables et de fonctions sont tous encodés sous la forme d'un entier sur 16 bits. Cela autorise près de 65536 noms différents, soit la taille d'un bon dictionnaire du français , ce qui à priori est amplement suffisant pour n'importe quelle application.

Ce dictionnaire est composé d'un vecteur dont chaque element est une table de 64 éléments. Ce vecteur a donc une taille maximale de 1024 tables. Notons que ces dictionnaires sont aussi gérés sous la forme d'un pool, ce qui permet de réutiliser ces structures à volonté.

Pour positionner un élément dans un dictionnaire, il suffit de calculer l'index de sa table dans le vecteur puis sa position dans cette table:

//Calcul des indexes et des positions pour "nom":

index = nom >> 6; //soit une division par 64
position = nom & 0x3F; //soit le reste de la division par 64   

Comme on le voit, le calcul d'une clef est quasi immédiat. De plus, comme l'enregistrement d'une variable est forcément unique à un moment t, le fait de ne pas gérer les collisions ne pose aucun problème.

La version initiale était basée sur un std::unordered_map dont le remplacement nous a permis de diviser le temps d'exécution par 2.

Enfin, un autre aspect sur lequel nous avons beaucoup travaillé est la manipulation du compteur de référence (voir status dans la classe Element).

En particulier, lorsqu'une liste A est rangée dans une liste L, seul le status de A est modifié. Nous ne touchons donc pas aux compteurs de référence des éléments de A. Ainsi, l'ajout d'un élément dans un conteneur, qu'il soit atomique ou conteneur; se fait toujours en temps constant. Les compteurs de référence ne sont jamais modifiés récursivement. Il en est de même lorsque l'on range la valeur d'une variable dans la pile d'exécution. Le seul moment où un compteur de référence est décrémenté survient quand le conteneur qui le contient est détruit ou lorsque la pile d'exécution est vidée. En revanche, dans ce cas, la destruction des éléments peut aboutir à une exploration récursive complètes de toutes les sous-structures.

Notons que les listes spécialisées contiennent des valeurs et non des objets, ce qui rend leur destruction immédiate sans la moindre descente en récursion. Par conséquent, leur création et leur destruction est beaucoup plus rapide que celle d'une liste générique. Ce choix permet encore une amélioration notable des performances, là encore de près de 20% par rapport à la version initiale.

La première version de LispE prenait 85ms pour exécuter ce même code de descente de gradient. Il n'en faut plus que 9 aujourd'hui.

Les modifications que nous avons présentées ici ne sont pas les seules à avoir permis une amélioration des performances. D'autres aspects ont aussi été pris en compte, telles que le nombre d'arguments dans les appels de fonction pour réduire la taille de la pile d'exécution de l'interpréteur. Nous avons aussi tenté de réduire le plus possible les if dans le code, pour suivre les conseils de Daniel Lemire pour réduire les effets de bord de l'exécution out of order des processeurs modernes. Mais si ces modifications se sont traduits par une plus grande efficacité, aucune n'a eu l'impact spectaculaire de celles que nous avons décrites ici.

C++ est un langage de programmation dont on sait qu'il permet de produire les binaires parmi les plus efficaces au monde (avec C et Rust). Mais, il n'en reste pas moins qu'il suffit parfois de quelques modifications légères pour obtenir les améliorations les plus surprenantes.