Article publié dans Linux Magazine 91, février 2007.
La perle de ce mois-ci a été rédigée par Philippe "BooK" Bruhat
(book@mongueurs.net
), de Lyon.pm et Paris.pm.
À moins d'avoir besoin de la puissance des expressions régulières de
Perl, il est légitime de penser que GNU grep sera plus
rapide que perl -ne 'print if /regexp/'
. Après tout, grep est écrit
en C, et Perl est « interprété », n'est-ce pas ?
Tant qu'une affirmation sur la meilleure performance d'un composant par rapport à un autre n'a pas été vérifiée par l'expérience, il est préférable de ne pas trop y croire (sauf si on compare le débit d'un lecteur de cartes perforée à celui d'un disque SATA, peut-être). De plus, toute comparaison a des limites de validité. Nous allons donc vérifier dans quels cas grep est meilleur que Perl.
GNU grep dispose d'une option peu connue, qui permet de faire sa recherche de correspondance sur plusieurs motifs listés dans un fichier :
-f FICHIER, --file=FICHIER Lire les motifs dans le FICHIER indiqué, un motif par ligne. Un fichier vide ne contient aucun motif, si bien qu'aucune concor- dance n'est trouvée.
Cependant, il faut prendre en compte le fait que GNU grep ne réalise aucune optimisation sur ces expressions : il se contente de les tester en boucle sur chacune des lignes en entrée. On peut donc s'attendre à voir les performances diminuer en proportion inverse du nombre d'expressions régulière à tester.
Soit une liste d'expressions simples prises au hasard (à l'aide du module
Acme::MetaSyntactic
et du thème unicode
) pour construire un fichier
d'expressions régulières :
AEGEAN_NUMBER_TWENTY FULLWIDTH_LATIN_CAPITAL_LETTER_S GREEK_ACROPHONIC_ATTIC_FIFTY_THOUSAND LATIN_CAPITAL_LETTER_O_WITH_TILDE_AND_ACUTE MUSICAL_SYMBOL_ORNAMENT_STROKE_5
On peut combiner ces cinq expressions en une seule, avec la magie de
\|
:
AEGEAN_NUMBER_TWENTY\|FULLWIDTH_LATIN_CAPITAL_LETTER_S\|GREEK_ACROPHONIC_ATTIC_FIFTY_THOUSAND\|LATIN_CAPITAL_LETTER_O_WITH_TILDE_AND_ACUTE\|MUSICAL_SYMBOL_ORNAMENT_STROKE_5
Comparons les résultats de grep -f
avec le fichier contenant n expressions
et celui de grep -f
avec un fichier contenant l'expression combinée.
Pour les tests, nous utiliserons une boîte mail de 116 389 octets
(la taille du fichier importe peu) et une liste d'expressions régulières
produites au hasard (ce sont comme précédemment des noms de caractères
Unicode distincts fournis par Acme::MetaSyntactic
).
Lors de mes tests, j'ai constaté que grep avait un comportement assez erratique (ainsi qu'on peut le voir sur la courbe rouge du graphe). Sans pouvoir le prouver avec certitude, je pense qu'il s'agit d'optimisations (ou de bogues) liées à la liste d'expressions passées à grep. Il semble cependant que la courbe est bien comprise entre deux droites, qui correspondraient aux cas le pire (bogue ou absence d'optimisation) et le meilleur (absence de bogue ou optimisation enclenchée). De plus, avec beaucoup d'expressions régulières, j'ai constaté qu'il est assez facile de tomber sur des cas défavorables.
On voit cependant le gain qu'il y a à remplacer une boucle qui passe une liste d'expressions régulière par une seule expression qui combine les expressions de la liste en question : la courbe verte est parfois très en dessous de la courbe rouge (d'un facteur 10 ou 20), ce qui fera une différence lorsqu'on traite de gros fichiers de données.
Regexp::Assemble
Lassé du spam et des virus qui engorgeaient son serveur STMP, et constatant que nombre d'entre eux provenaient d'adresses de connexion ADSL chez des particuliers (probablement infestés de virus et de chevaux de Troie), David Landgren a pris des mesures radicales : il a considéré que les messages venant de connexions personnelles (dialup) pouvaient être directement rejetés.
Les lignes ADSL sont faciles à détecter avec une résolution DNS inverse :
64-80-231-201.fibertel.com.ar host-67-84-230-24.midco.net host-89-229-2-176.torun.mm.pl host-213-213-233-44.brutele.be ppp-58.10.219.243.revip2.asianet.co.th 68-67-200-36.atlaga.adelphia.net
Il est facile d'en déduire quelques expressions régulières pour trouver les utilisateurs du même type :
\d+-\d+-\d+-\d+\.fibertel\.com\.ar host-\d+-\d+-\d+-\d+\.midco\.net host-\d+-\d+-\d+-\d+\.torun\.mm\.pl host-\d+-\d+-\d+-\d+\.brutele\.be ppp-\d+\.\d+\.\d+\.\d+\.revip\d+\.asianet\.co\.th \d+-\d+-\d+-\d+\.atlaga\.adelphia\.net
Postfix (le MTA utilisé par David) peut utiliser la librairie PCRE
(Perl Compatible Regular Expressions) pour faire des correspondances
sur de tels noms de domaine à rejeter automatiquement. La première approche
de David a donc consisté à produire une liste d'expressions régulières
(comme pour grep -f
).
Comme nous l'avons vu précédemment, les performances
se dégradent rapidement quand on a quelques
centaines d'expression à passer sur chaque connexion entrante. David a
donc commencé à écrire un optimiseur d'expressions régulières qui va plus
loin que le simple join '|'
. L'idée est de grouper les parties communes
pour optimiser la recherche. Un exemple valant mieux qu'un long discours,
voici le résultat sur les six expressions précédentes :
(?: host-\d+-\d+-\d+-\d+\. (?: torun\.mm\.pl |brutele\.be |midco\.net ) |\d+-\d+-\d+-\d+\. (?: atlaga\.adelphia\.net |fibertel\.com\.ar ) |ppp-\d+\.\d+\.\d+\.\d+\.revip\d+\.asianet\.co\.th )
Ce travail a donné lieu à une présentation aux premières « Journées Perl » en 2004. La réaction des auditeurs a été unanime : « Il faut en faire un module CPAN ! ».
C'est ainsi qu'est né le module Regexp::Assemble
.
Son utilisation est très simple, comme le montre ce petit script, utilisé
pour comparer les performances d'un programme Perl basé sur Regexp::Assemble
avec grep -f
:
#!/usr/bin/perl use strict; use warnings; use Regexp::Assemble; my $ra = Regexp::Assemble->new(); { local @ARGV = shift; # joli hack # ajout des expressions à la structure $ra->add($_) while <>; } # récupération de l'expression optimisée et compilée my $re = $ra->re(); # utilisation de l'expression dans un traitement while (<>) { print if /$re/; }
Ce script assemble les expressions contenues dans le premier fichier passé
en paramètre (le hack mentionné dans les commentaires) et les applique
au reste des fichiers passés en paramètre, pour produire un résultat
équivalent à grep -f
.
Regexp::Assemble
Revenons à notre exemple de départ. À partir d'une liste de noms de caractères Unicode, nous prenons les n premières pour produire nos listes de test. Ceci nous permet d'éviter les cahots liés aux différences entre les listes de regexps tirées au hasard.
Enfin, le script ci-dessus sera utilisé, ainsi qu'une version modifiée qui se contente de compiler l'expression rationnelle assemblée. Le fichier de test est le même que précédemment.
Quelques conclusions sur ce graphique :
grep -f
avec n regexps peut rapidement faire augmenter le temps
de traitement avec l'ajout d'une expression régulière à la liste. Ce
comportement me fait pencher pour une bogue dans le programme.
Avec une expression optimisée par simple concaténation avec des \|
,
les performances de grep se dégradent beaucoup moins vite qu'avec une
liste et l'option -f
.
Mais au bout d'un certain nombre d'expressions, on rencontre à nouveau des problèmes de dégradation des performances.
Une expression optimisée par Regexp::Assemble
permet à un programme Perl
de devenir plus rapide que grep (pourtant écrit en C et certainement
très optimisé). Ceci dépend des expressions à assembler, mais c'est vrai
dès quelques centaines d'expressions.
Plus il y a d'expressions à assembler, plus le temps d'assemblage par
Regexp::Assemble
augmente. En fait, on constate que le temps de
traitement du fichier de données par Perl à l'aide de l'expression
régulière obtenue est quasiment constant.
Il semblerait que le temps d'assemblage augmente linéairement avec le nombre d'expressions à assembler.
Même s'il faut deux secondes et demie sur ma machine pour assembler 10 000 expressions régulières, ce coût d'initialisation est largement compensé par le gain en performance que procure cette optimisation.
De plus, dans des cas comme celui du Postfix de David, l'expression n'a besoin d'être calculée qu'à chaque fois qu'il rajoute des éléments à sa liste noire, le résultat faisant partie de la configuration de Postfix. C'est tout bénéfice lors de l'exécution de Postfix.
La configuration actuelle de David comporte 4096 expressions régulières, soit 136 467 octets brut et 90 549 octets après assemblage.
Regexp::Assemble
comporte de nombreuses options supplémentaires qui
permettent :
le suivi des regexps, qui permet de savoir quelle expression régulière a déclenché la correspondance.
un affichage enjolivé pour améliorer la visualisation du résultat de l'assemblage.
la réduction des branches, une optimisation réalisée par défaut. Elle est couteuse lors de l'assemblage des expressions, mais peut être désactivée.
Enfin, le fichier README contenu dans la distribution explique
l'algorithme utilisé par Regexp::Assemble
.
Cette perle reprend des éléments de la présentation que David Landgren a faite aux Journées Perl 2006. Voici tous les liens utiles :
La présentation de Regexp::Assemble
aux Journées Perl :
http://conferences.mongueurs.net/fpw2006/slides/regexp-assemble.html
Le site Perl de David : http://www.landgren.net/
Perl Compatible Regular Expressions (PCRE) : http://www.pcre.org/.
Regexp::Assemble
sur CPAN :
http://search.cpan.org/dist/Regexp-Assemble/.
Regex::PreSuf
, un précurseur de Regex::Assemble
par Jarkko
Hietaniemi : http://search.cpan.org/dist/Regex-PreSuf/.
Acme::MetaSyntactic
, le module qui m'a pris deux ans de ma vie :
http://search.cpan.org/dist/Acme-MetaSyntactic/.
Envoyez vos perles à perles@mongueurs.net
, elles seront peut-être
publiées dans un prochain numéro de Linux Magazine.
Copyright © Les Mongueurs de Perl, 2001-2011
pour le site.
Les auteurs conservent le copyright de leurs articles.