les databases et plus: Perl 5.10 optimise le moteur d'expressions régulières

dimanche 19 avril 2009

Perl 5.10 optimise le moteur d'expressions régulières

Une des nouvelles fonctionnalités de la 5.10 est l'utilisation d'algorithmes tels que Aho-Corasick et Trie (prefix tree) dans le moteur d'expressions régulières. Ainsi la recherche d'alternatives comme le pattern alt1|alt2|alt3|alt4|altN aura une complexité en 0(1) et non plus en 0(N) avec N le nombre d'alternatives. Pour s'en convaincre, rien de mieux qu'un benchmarck entre les versions 5.8 et 5.10. Pour cela j'ai écrit un petit bout de code que vous pouvez récupérer ici.
J'utilise le module Regexp::Trie de Dan Kogai qui permet d'optimiser la recherche d'alternatives ayant un suffixe (ou une partie) en commun

Les résultats obtenus sont les suivants :

a -> sans utilisation du module Regexp::Trie
b -> avec utilisation du module Regexp::Trie

Perl 5.8 :

perl bench_with_tries.pl
Rate a b
a 552/s -- -98%
b 26050/s 4620% --

Perl 5.10 :

perl bench_with_tries.pl
Rate a b
a 20177/s -- -65%
b 57777/s 186% --

On voit bien qu'en version 5.8 l'utilisation du module de Dan Kogai permet de multiplier par plus de 40 les performances, contrairement en 5.10 où les performances de base sont déjà satisfaisantes avec plus de 20 000 exécutions par seconde. Cependant, il est toujours utile d'utiliser ce module en 5.10 puisqu'on obtient près de 3 fois plus de performance.

Blogged with the Flock Browser

2 commentaires:

Jeff a dit…: ca serait pas plutôt en o(m) où m est le nombre de caractère de ta pattern ?; 19 avril 2009 à 12:20
Cyril Scetbon a dit…: En fait, les accès à un Trie se font en 0(m) mais il est possible de représenter un Trie avec des connexions entre des noeuds qui stockent le même caractère par exemple, ce qui permet d'effectuer les comparaisons de N alternatives dans un temps constant, soit en 0(1). Pour plus d'informations sur les optimisations internes, et peut être plus de clarté tu peux jeter un oeil sur http://perldoc.perl.org/perldelta.html#Trie-optimisation-of-literal-string-alternations et http://conferences.mongueurs.net/fpw2009/slides/perl-5.10-2.html; 20 avril 2009 à 12:22