par Guillaume Foliard gfoliard@anrtt.inp-fc.fr
Voici un article qui se veut ludique, sans aucune prétention quand aux programmes que je vais vous présenter. En effet, on va tout bêtement réecrire la commande "wc" de plusieurs manières grâce à notre ami FLEX. Je tiens à préciser qu'une grande partie de ce que je vais vous exposer se trouve dans le répertoire /usr/doc/flex/MISC/fastwc de votre distribution Slackware (au moins la 3.0). Je passerai sur la syntaxe de FLEX, tout lecteur linuxien digne de ce nom ayant lu la manpage de FLEX à la simple évocation du titre.
FLEX est ce qu'on appelle un générateur d'analyseur lexical. Pour ne point égarer nos chers lecteurs, un analyseur lexical est un programme qui détecte un ou plusieurs "motifs" (pattern en anglais) de caractères dans un flot de caractères. Pour parvenir à cet objectif, les analyseurs générés par FLEX utilisent un algorithme à base de tables précalculées, cela leur donne la propriétés trés intéressante d'avoir une vitesse d'exécution indépendante du nombre de motifs à rechercher. Sans rentrer dans les détails, du fait de l'algorithme employé, basé sur un automate à pile, plus les motifs à rechercher sont long plus l'analyseur est rapide.
Tout cela va nous permettre d'écrire une nouvelle commande wc presque aussi rapide que le "wc" que l'on trouve dans la distribution Slackware.
Commençons par la version la plus simple, mais la moins rapide:
# la syntaxe employée est celle des
# expressions régulières de grep
# motif correspondant aux espaces vides:
# espace et tabulation
ws [ \t]
# motif correspondant aux lignes vides:
# ^ indique début de ligne
nonws [^ \t\n]
%%
int cc = 0, wc = 0, lc = 0;
# Actions associées à une ou plusieurs
# lignes vides
{nonws}+ cc += yyleng; ++wc;
# Actions associées à un ou plusieurs blancs
{ws}+ cc += yyleng;
# Actions associées lors d'une fin de ligne
\n ++lc; ++cc;
# traitement à effectuer en fin de fichier
<> { printf( "%8d %8d %8d\n", lc, wc, cc );
yyterminate(); }
%%
int yywrap ()
{ return 1; }
main ()
{ yylex(); }
Pour générer un exécutable à partir d'un tel source, il suffit de taper les commandes suivantes:
/* Génération du source en c
# flex
/* Compilation du code c obtenu
# cc -o monwc lex.yy.c
Bon, sur un Pentium 100 avec un fichier ASCII de 1444995 octets nommé test, un ``time monwc test'' me donne:
1.39user 0.03system 0:01.42elapsed 100%CPU
(0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+0minor)pagefaults 0swaps
Avec le wc original un "time wc test" me donne:
0.17user 0.04system 0:00.21elapsed 100%CPUComme on peut le voir, c'est pas terrible.
Première optimisation: on rajoute quelques règles, mais surtout celles-ci sont plus longues:
ws [ \t]
nonws [^ \t\n]
word {ws}*{nonws}+
words {word}{ws}+
%%
int cc = 0, wc = 0, lc = 0;
{word}{ws}* cc += yyleng; ++wc;
{word}{ws}*\n cc += yyleng; ++wc; ++lc;
{words}{word}{ws}* cc += yyleng; wc += 2;
{words}{2}{word}{ws}* cc += yyleng; wc += 3;
{words}{3}{word}{ws}* cc += yyleng; wc += 4;
{ws}+ cc += yyleng;
\n+ cc += yyleng; lc += yyleng;
<> { printf( "%8d %8d %8d\n", lc, wc, cc );
yyterminate(); }
%%
int yywrap ()
{ return 1; }
main ()
{ yylex(); }
Résultat:
1.29user 0.06system 0:01.35elapsed 100%CPU
(0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+0minor)pagefaults 0swaps
Encore décevant. Voyons en rajoutant des règles supplémentaires:
ws [ \t]
nonws [^ \t\n]
word {ws}*{nonws}+
words {word}{ws}+
%%
int cc = 0, wc = 0, lc = 0;
{word}{ws}* ++wc; cc += yyleng;
{word}{ws}*\n ++wc; cc += yyleng; ++lc;
{words}{word}{ws}* wc += 2; cc += yyleng;
{words}{word}{ws}*\n wc += 2; cc += yyleng; ++lc;
{words}{2}{word}{ws}* wc += 3; cc += yyleng;
{words}{2}{word}{ws}*\n wc += 3; cc += yyleng; ++lc;
{words}{3}{word}{ws}* wc += 4; cc += yyleng;
{words}{3}{word}{ws}*\n wc += 4; cc += yyleng; ++lc;
{ws}+ cc += yyleng;
\n+ cc += yyleng; lc += yyleng;
<> { printf( "%8d %8d %8d\n", lc, wc, cc );
yyterminate(); }
%%
int yywrap ()
{ return 1; }
main ()
{ yylex(); }
Avec time j'obtiens le résultat suivant (stable):
1.30user 0.03system 0:01.34elapsed 99%CPU
(0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+0minor)pagefaults 0swaps
Bon, on est loin des performances espérées, heureusement l'ami FLEX a plus d'un tour dans son sac, une option nous permet de préciser que l'on désire générer des tables non compactées pour l'analyseur, avec pour objectif de rendre celui-ci plus efficace.
# flex -Cf
Voyons le résultat pour chacune de nos version précédente (dans l'ordre d'apparition):
0.32user 0.02system 0:00.34elapsed 100%CPU
(0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+0minor)pagefaults 0swaps
0.26user 0.05system 0:00.31elapsed 100%CPU
(0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+0minor)pagefaults 0swaps
0.27user 0.03system 0:00.30elapsed 100%CPU
(0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+0minor)pagefaults 0swaps
C'est déjà beaucoup mieux mais pas encore au niveau du vrai wc. Après une compilation C du dernier exemple avec les options d'optimisation de code -O3 et -m486 on obtient:
0.20user 0.06system 0:00.26elapsed 100%CPU
(0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+0minor)pagefaults 0swaps
Haha, ça devient intéressant !
Après un rapide survol de la manpage de flex, je me suis aperçu que l'on pouvait rajouter une option d'optimisation supplémentaire (-Cfa).
# flex -Cfa
# cc -O3 -m486 -o monwc lex.yy.c
Résultat du time un poil au dessous du vrai wc:
0.18user 0.04system 0:00.22elapsed 100%CPU
(0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+0minor)pagefaults 0swaps
Pour terminer on peut rajouter une dernière option pour la génération du source de l'analyseur. Cette option sert à contraindre l'utilisation des primitives d'entrée/sortie du système au lieu des primitives de la librairies standard.
# flex -Cfar
# cc -O3 -m486 -o monwc lex.yy.c
Les résultats sont encore un peu meilleurs. A titre indicatif la valeur la plus souvent obtenue est la suivante:
0.14user 0.06system 0:00.20elapsed 100%CPU
(0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+0minor)pagefaults 0swaps
Finalement, bien que les performances soient presque équivalentes, on est en droit d'être déçu lorsque l'on compare la taille des binaires obtenus, le binaire issu de FLEX est près de 20 fois plus gros que le wc original livré avec la Slackware ! Cela laisse donc à penser que ce dernier ne doit pas employer le même algorithme que les analyseurs générés par FLEX.
Bon il se fait tard, on étudiera donc le problème une prochaine fois.