Tinypy

L'autre jour en feuilletant freshmeat je suis tombé sur tinypy. ça a juste l'air excellent, du python embarquable en 64k avec la vm et l'interpreteur, tout ça sous license MIT.. ça fait un bout de temps que j'ai envie d'embarquer un petit langage de scripting dans une appli pour faire des choses hyper-puissantes mais le problème c'est que je n'en ai pas besoin, et que je n'ai pas d'idées de choses hyper-puissantes :'(

Les regexp

Ken Thompson et Dennis RitchieComme j'avais besoin d'un petit code portable et pas trop lourd en dépendances pour matcher des regexp j'ai perdu un peu (beaucoup trop en fait) de temps à regarder comment ça marche et si je pouvais en écrire un qui soit minimal et rapide.

En gros il y a deux approches:

  • l'approche historique, qui est celle employée par Ken Thompson il y a plus de 40 ans, qui consiste à construire un automate a partir de l'expression regulière, et ensuite de lui balancer les chaines qu'on cherche à matcher et regarder ce qui en sort.
  • l'approche populaire, qui consiste a explorer de façon recursive l'arboresence de toutes les possibilités.

L'approche recursive est celle employée maintenant dans quasiment tous les moteurs de regexp. Et pourtant si on lit ce texte de Russ Cox , c'est un très mauvais choix: contrairement au NFA de Thompson, le temps de test d'une regexp un peu pathologique va exploser exponentiellement avec l'approche récursive, alors qu'avec le NFA la complexité maximale est garantie (linéaire par rapport au nombre de caractères dans l'expression regulière et dans la chaine à matcher).

The regular expression implementations used by today's popular tools are significantly slower than the ones used in many of those thirty-year-old Unix tools.



L'argumentaire de Russ Cox est très convainquant, du coup j'ai fait un petit code de regexp utilisant le NFA, en me disant que les quelques sacrifices à faire pour loger tout ça dans un automate valaient bien ces performances annoncées. Les sacrifices sont:

  • pas de backreferences du genre "(coin|pan)\1" pour matcher "coincoin" ou "panpan"
  • coût supplémentaire matcher les sous-expressions entre parenthèses (il faut ajouter des "tags" à chaque etat actif dans l'automate pour chaque groupe de parentheses)
  • coût supplementaire pour gerer les répétitions comptées "(coin){2,5}" (il faut remplacer ça par (coin)(coin)(coin)?(coin)?(coin)? dans l'automate)

Pour finir j'ai quand même voulu vérifier que mon code allait vraiment aussi vite qu'annoncé en le comparant à une version de réference: PCRE (perl-compatible regular expressions). Et là grosse deception.. D'accord PCRE explose sur des expressions débiles du genre matcher "a?a?a?a?a?a?a?a?a" avec "a", mais sur des regexp bien basiques il est généralement 3x à 10x plus rapide que mon implémentation :'(

OWNED