[couverture de Linux Magazine 91]

Perles de Mongueurs (29)

Article publié dans Linux Magazine 91, février 2007.

[+ del.icio.us] [+ Developers Zone] [+ Bookmarks.fr] [Digg this] [+ My Yahoo!]

La perle de ce mois-ci a été rédigée par Philippe "BooK" Bruhat (book@mongueurs.net), de Lyon.pm et Paris.pm.

Expressions régulières : ce n'est pas la taille qui compte

À 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.

Améliorer les performances de grep

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).

Comparaison de grep avec n et 1 regexp

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.

Comparaison de grep et 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.

Comparaison de grep et de Regexp::Assemble

Quelques conclusions sur ce graphique :

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

Et ce n'est pas tout !

Regexp::Assemble comporte de nombreuses options supplémentaires qui permettent :

Enfin, le fichier README contenu dans la distribution explique l'algorithme utilisé par Regexp::Assemble.

Références

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 :

À vous !

Envoyez vos perles à perles@mongueurs.net, elles seront peut-être publiées dans un prochain numéro de Linux Magazine.

[IE7, par Dean Edwards] [Validation du HTML] [Validation du CSS]