My photo

Mildred's Website

Tags:
My avatar

GoogleTalk, Jabber, XMPP address:
mildred@jabber.fr


GPG Public Key
(Fingerprint 197C A7E6 645B 4299 6D37 684B 6F9D A8D6 9A7D 2E2B)

Aliasing Strings in Lisaac

Mon 06 Sep 2010, 09:13 AM comp dev fr lisaac

En Lisaac, il y a trois types de chaînes de caractères: ABSTRACT_STRING qui sert de parent à STRING et STRING_CONSTANT.

Quelle conclusion peut on en tirer quant à la comparaison entre chaînes ?

  1. Il est nécessaire de comparer les chaînes caractère à caractère pour s'assurer de leur égalité

  2. Dans le cas des STRING_CONSTANT, il est possible de ne faire qu'une comparaison de pointeurs.

Bien sûr, la méthode n°2 est beaucoup plus rapide, Si possible, on aimerait pouvoir l'utiliser tout le temps. Dans le cas du compilateur Lisaac, les performances étant tellement critiques (nous avons affaire à un algorithme exponentiel) que Benoît s'est arrangé pour toujours faire une comparaison de pointeurs. Comment ?

Tout simplement en transformant les chaînes classiques en STRING_CONSTANT. Cela est fait en construisant de toute pièces l'objet STRING_CONSTANT en copiant les données contenues dans n'importe quelle autre chaîne. Et pour s'assurer de l'unicité de la chaîne, il est nécesaire au préalable de vérifier que la chaîne STRING_CONSTANT n'existe pas déjà.

Pour cela, toutes les chaînes utiles dans le compilateur à tout instant se trouvent dans un prototype ALIAS_STR. Pour les utiliser, on fait juste référence au nom du slot dans ALIAS_STR. Ces chaînes sont de plus insérées au démarrage du compilateur dans l'ensemble SET(ABSTRACT_STRING) qui contient toutes les chaînes constantes.

Cela reste une manipulation lourde (il est nécessaire d'insérer à la main toutes les chaînes constantes qu'on utilise quelque part dans le compilateur dans cet ensemble de chaînes) réservée au compilateur Lisaac. La conversion entre ABSTRACT_STRING et STRING_CONSTANT reste explicite et alourdit le code. J'ai eu donc envie de généraliser cela en l'implémentant en bibliothèque.

Avec les systèmes d'auto-import et auto-export, la conversion peut être très facile. Il restait cependant le problème délicat de référencer toutes les STRING_CONSTANT du segment DATA et de les insérer dans l'ensemble des chaînes. Pour cela il faut ajouter un système d'introspection qui permet au programme de parcourir toutes les chaînes constantes compilées. J'ai pensé à plusieurs solutions:

Une fois le compilateur modifié, il faut modifier la bibliothèque standard. Au début, j'ai eu pour approche d'utiliser la liste chaînée comme ensemble de chaînes uniques au lieu d'un HASHED_SET. Mais les performances ont été tellement déplorables que j'en suis revenu à l'ensemble de hash.

Les modifications sont presque prêtes, et il va être nécessaire d'introduire deux commits de bootstrap (un commit pour introduire la fonctionnalité dans le compilateur, l'autre avec une bibliothèque standard modifiée et le compilateur qui délègue l'aliasing à la bibliothèque).

Il reste quelques problèmes à corriger, et ce sera prêt.

Mildred.