écrire un file grep optimisé

Version imprimable

Voir 40 message(s) de cette discussion en une page

11/05/2007, 17h49
kreesD

Citation:

Envoyé par djibril

moi je ne pense pas que concatener tout ton fichier en une ligne soit une bonne solution, car en fonction de la taille, ça peut etre long. De plus, tu verifies pleins de caracteres dont tu n'aurais peut etre pas besoin.

Je ferais plutot une boucle.
Pour chacun de tes motif à trouver :
- tu ouvres le fichier
- parcour ligne à ligne
- s'il trouve l'occurence => print et sort du while via un last.
- ferme ton fichier

Ce sera déjà beaucoup plus rapide s'il y a des match.

Je pensais ça aussi à l'origine, d'ailleurs mon premier code fonctionnait comme ça. Et c'était... encore plus lent que le fgrep ! J'ai divisé par 100 le temps d'exec en faisant ça (la concaténation se fait en bien moins d'une seconde sur un fichier énorme)... en y réfléchissant bien il est logique que ça marche plus vite avec une seule ligne, en asm c'est du "rep scasb" (code 80x86) sur le premier car. de chaque chaîne, puis du "rep cmpsb".
11/05/2007, 18h31
GnuVince

Citation:

Envoyé par kreesD

C'est une solution que nous avons considérée. Mais elle est difficilement reproductible à la demande, en logique one-shot c'est bien, mais je me place dans une optique de réutilisabilité plus grande... sinon je ferai peut-être un montage NFS accessible depuis une machine séparée. PS: on n'a aucune machine Linux, damned.

VMware ferait l'affaire au pire.

Je suis entrain de fignoler un script pour ton problème (belle utilisation de mon heure de dîner ;)), mais c'est pas très rapide, j'attends encore que mon script termine...
11/05/2007, 18h35
kreesD

Citation:

Envoyé par GnuVince

VMware ferait l'affaire au pire.

Je suis entrain de fignoler un script pour ton problème (belle utilisation de mon heure de dîner ;)), mais c'est pas très rapide, j'attends encore que mon script termine...

Très sympa, merci bcp ! Compare avec ce que donne le mien pour que ce soit significatif (car mon fgrep natif de tout à l'heure est tjs en train de tourner, ça fait quoi, deux heures...)
11/05/2007, 18h36
Jedai

Je crois que tu ne m'as pas bien compris... D'une part je ne suis pas sûr du tout que find soit plus rapide que l'équivalent en Perl (la doc de find2perl dit bien : "The resulting code is typically faster than running find itself.", bien sûr ce n'est pas parole d'évangile, néanmoins... ça peut valoir le coup d'y réfléchir).
D'autre part tu as l'air de croire que Regexp::Assemble ne fait qu'une énorme alternative. Or ce n'est pas du tout le cas, Regexp::Assemble fait une optimisation dite de "trie" (ou arbre à lettre), autrement dit il factorise les préfixes communs à tes alternatives, ce qui réduit énormément, je dirais même de façon colossale le temps d'exécution de la regex par rapport à une grosse alternative.

En fait je ne vois pas que tu puisses faire plus rapide, théoriquement parlant, à part utiliser du C et construire toi-même ton DFA en espérant qu'il ne soit pas trop gros.

--
Jedaï
11/05/2007, 18h43
Jedai

Citation:

Envoyé par kreesD

Code:

while( <IN> ) { $s.=$_; }

Tu dis que tu veux faire rapide et tu utilises ce genre d'abomination pour slurper tes fichiers ? Soit tu utilises l'idiome standard :

Code:

my $s = do {local $/; <IN>};

Soit tu utilises un module qui optimise ça pour toi (Perl6::Slurp ou File::Slurp)
Mais jamais au grand jamais tu n'utilises ton code lorsque tu as besoin de performance !!

--
Jedaï
11/05/2007, 19h13
GnuVince

Après 45 minutes, mon script avait toujours pas fini (avec un fichier data de 164,000 lignes et un fichier test de 869,230 lignes), donc je l'ai arrêté. Back to the drawing board.
11/05/2007, 19h30
Jedai

Encore un truc aberrant dans ton bifteak : tu ne compiles pas tes regexs !! 8O
Il faudrait au moins que tu utilises qr// pour les compiler une bonne fois pour toute plutôt que de les recompiler à chaque fois que tu les utilises... Regexp::Assemble au moins renvoie une regex compilé.

--
Jedaï

Voici une version avec Regexp::Assemble, elle ne te permet pas de savoir quelle clé a matché, est-ce important ?
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #!/usr/bin/perl -w # COG May 2007 # # use strict; use warnings; # read and hash grep file $ARGV[0] || die "Specify a grepfile and optionnally a file to search into (otherwise stdin, pipe)\n"; use Regexp::Assemble; my $re = Regexp::Assemble->new ->add_file( $ARGV[0] ) ->anchor_word ->re; # read and concat input file $ARGV[1] && ( open( IN, $ARGV[1] ) || die "$!\n" ) || ( open( IN, "-" ) || die "$!\n" ); my $content = do { local $/; <IN> }; # analyse; if it matches if ( $content =~ m/$re/ ) { print "It matched !\n"; exit 0; } exit 1; __END__
EDIT : Ce script est très mauvais, en effet tout le bénéfice de la compilation est perdu par le fait qu'on ne le fait agir que sur un seul fichier. Une autre bonne raison de faire le Find en interne.

--
Jedaï

11/05/2007, 20h42
Jedai

Une mesure de temps sur le script précédent avec un dictionnaire de 160000 lignes donne une compilation de 130 secondes (2 minutes 10 s) mais un slurp et match en 0 secondes (sur un fichier de 23 Mo où le match est à la fin)... De quoi peut-être faire réviser son opinion à notre posteur ? Un find en interne évite la recompilation, ce qui signifie que cette solution serait rapide comme l'éclair pour son problème semble-t-il.

--
Jedaï
12/05/2007, 11h37
kreesD

Citation:

Envoyé par Jedai

Une mesure de temps sur le script précédent avec un dictionnaire de 160000 lignes donne une compilation de 130 secondes (2 minutes 10 s) mais un slurp et match en 0 secondes (sur un fichier de 23 Mo où le match est à la fin)... De quoi peut-être faire réviser son opinion à notre posteur ? Un find en interne évite la recompilation, ce qui signifie que cette solution serait rapide comme l'éclair pour son problème semble-t-il.

--
Jedaï

Merci. Je reprécise car apparemment tu as oublié mon 1er post: ça fait HUIT ans que je n'ai pas touché au perl. Donc tout ce que tu me dis est certainement très pertinent, mais il faut que je m'y remette car la moitié de ton propos ne me parle que théoriquement (je dois voir en pratique commen ça fonctionne et ce que ça peut m'apporter). En revanche "l'aberration" sur ma boucle de lecture du fichier in prend 0,1 sec environ, sur un traitement de 4mn35 (pour un seul gros fichier)... donc aberrant en théorie certes, mais en pratique ça ne pose aucun pb. C'est la suite qui est lente (le matching).

En revanche, je n'avais effectivement pas compris l'intérêt de tes suggestions, si effectivement il y a optimisation sur la façon de matcher n regepx via une structure dédiée (arbre à lettres) alors j'achète bien-sûr !

Et au passage je te remercie encore. Ta contribution va m'être doublement utile: pour mon pb, et pour me remettre à jour, ce sur quoi je compte capitaliser.

A+
12/05/2007, 12h07
Jedai
Citation:

Envoyé par kreesD

En revanche "l'aberration" sur ma boucle de lecture du fichier in prend 0,1 sec environ, sur un traitement de 4mn35 (pour un seul gros fichier)... donc aberrant en théorie certes, mais en pratique ça ne pose aucun pb. C'est la suite qui est lente (le matching).

Ok, j'admets :mrgreen:
Pour des fichiers de tailles raisonnable, et vu combien de temps prenait ton match c'est sûr que c'était tout à fait négligeable ! :aie:
Néanmoins si le match en lui-même prend moins d'une seconde comme avec mon script, ça commence à devenir plus intéressant d'optimiser là-dessus.

Donc je résume mon idée : au lieu d'utiliser le find Unix et d'appeler un script Perl sur chacun des fichiers trouvé, je te propose d'intégrer le find dans un script Perl unique, où l'on compile une regex qui matche si et seulement si l'une de tes regex de ton fichier de mots matche, puis l'on utilise cette regex compilée sur tous les fichiers que notre find intégré nous renvoie.

L'économie se fait sur plusieurs points :
- tu ne crée plus un processus perl par fichier trouvé, il n'y a qu'un seul processus pour l'ensemble de l'opération
- Tu ne charges plus le fichier de regex (163000 lignes à lire ligne par ligne ce n'est pas si économique que ça) à chaque fichier trouvé
- tu ne recompiles plus l'ensemble de tes regexs pour chaque fichier
- le match se fait en une seule étape, bien plus rapide que la succession de match que tu faisais
- le find en Perl sera vraisemblablement plus rapide que le find Unix
Certains de ces points sont des économies minimes, mais ensemble cette nouvelle architecture devrait te permettre un saut énorme de vitesse grâce à la rapidité du match qu'elle autorise. (je dirais même qu'on pourra réduire à moins d'une dizaine de minutes, néanmoins il me manque quelques éléments pour juger, je fais le calcul suivant : disons que mon script prend 3 secondes par fichier là où le tien prend 4 minutes, et sachant que tu mets une demi-journée : (12 * 60) / (4 * 60 / 3) = 9 minutes auxquelles il faut rajouter le temps initial de compil de la regex...)

Trois questions toutefois :
1. Combien as-tu de RAM ? (les grosses Regex sont assez gourmandes)
2. As-tu besoin de savoir quelle alternative a matché, et as-tu besoin de toutes les alternatives qui ont matchés dans un même fichier ?
3. A quoi ressemble ton fichier de regex ? S'agit-il véritablement de regexs ou simplement de chaînes de caractères que tu veux matcher littéralement ?
--
Jedaï
12/05/2007, 20h20
Jedai

Donc résumé de mes dernières investigations : avec un fichier de test moins favorable (mes lignes étaient ininterrompues, maintenant j'ai mis des espaces très régulièrement pour mieux imiter un véritable fichier de texte) de 11 Mo et un "dictionnaire" de 160000 mots aléatoires (de 20 lettres) et 3 mots non aléatoires, dont l'un se trouve à la fin du fichier de test, je trouve une compilation en 130 secondes et un match en 3.5 secondes pour une occupation mémoire de 300 Mo ( 8O d'où la question 1). Avec Regexp::Trie, qui est une variante "simplifiée" de Regexp::Assemble (et qui ne marche que pour des littéraux, d'où ma question 3), la compil prend 30 secondes, et le match 3.5 secondes.
A noter que dans les deux cas, je récupère la première alternative qui matche seulement (c'est déjà mieux que juste de savoir s'il y en a une qui a matché).

--
Jedaï
13/05/2007, 17h45
kreesD

Citation:

Envoyé par Jedai

Donc résumé de mes dernières investigations : avec un fichier de test moins favorable (mes lignes étaient ininterrompues, maintenant j'ai mis des espaces très régulièrement pour mieux imiter un véritable fichier de texte) de 11 Mo et un "dictionnaire" de 160000 mots aléatoires (de 20 lettres) et 3 mots non aléatoires, dont l'un se trouve à la fin du fichier de test, je trouve une compilation en 130 secondes et un match en 3.5 secondes pour une occupation mémoire de 300 Mo ( 8O d'où la question 1). Avec Regexp::Trie, qui est une variante "simplifiée" de Regexp::Assemble (et qui ne marche que pour des littéraux, d'où ma question 3), la compil prend 30 secondes, et le match 3.5 secondes.
A noter que dans les deux cas, je récupère la première alternative qui matche seulement (c'est déjà mieux que juste de savoir s'il y en a une qui a matché).

--
Jedaï

Merci encore. Je vais regarder tout ça en détail lundi, de retour au taf. Ma version lente a fait bosser nos serveurs tout le WE :mrgreen: ...

Pour la mémoire j'y ai déjà répondu auparavant (je ne sais plus là, mais plein d'env // dessus), mais pas de regexp. Ce sont des noms de contreparties financières que l'on recherche "en dur" dans du code sous CVS. Car malheureusement certain(e)s @!#ù%^¨£$*! codent encore des choses en dur... c'est donc très simple. En revanche j'ai impérativement besoin de connaître toutes les occurrences (analyse d'impact au changement de mapping des contreparties externes).

Ce que je retiens, c'est la méthode ciblée sur l'efficacité pour ce pb avec le find natif et la regexp compilée une fois pour toutes et passée ensuite sur tous les fichiers (très intéressant); ce que je vais garder cependant c'est une primitive du style ffgrep.pl (fast file grep) pour la réutiliser ensuite depuis du shell standard. A savoir que le perl n'est pas utilisé chez nous, je l'ai ressorti de mon chapeau car personne n'avais de meilleure solution en terme d'efficacité. Certaines technos sont retenues, les compétences que l'on recherche et qui dirigent nos recrutements sont bien ciblées. Perl n'est pas dans notre panel (à mon grand désarrois d'ailleurs).

[EDIT]
J'ajoute une chose au passage: une bonne méthode consisterait à savoir si ça a matché dans un premier temps (ce n'est pas le cas souvent au final) grâce à la regexp 'assemble' compilé et donc optimisée, et si c'est le cas, de parcourir les hash keys - comme dans mon script - de façon à dire plus précisément ce qui a matché. Ça ça doit être vraiment rapide pour mon cas (match improbable, mais on doit absolument savoir quand c'est le cas).
[/EDIT]

is inutile... s seul en fait, manque le wordonly encore...

Derniers résultats: faire comme je l'avais suggéré une grosse regexp avec pipes. Sur un fichier de test, je passe de 4mn35 à 2mn 35. Après avoir ajouté le qr// (compil de regexp) aucun changement... :(
Code:

1 2 3 4 5 6 7 8 # read keys file into string $regexp my $regexp = do { local $/; <GREPKEYS> }; close( GREPKEYS ); # turn all \n chars into | (make a regexp "ptn1|ptn2|...|ptnN|" from all N keys read) $regexp =~ s/\n/\|/g; # and remove final | chop $regexp; my $re = qr/$regexp/i;
Next: les Regexp::Assemble...

Je crois que tu n'as pas bien compris : la compilation de la regex n'a aucun intérêt si tu ne la réutilises pas plusieurs fois. Voici un petit exemple de script qui réutilises sa regexp, il permet d'utiliser les mêmes arguments que find, mais utilise find2perl en sous-main pour convertir ça en utilisation de File::Find (NB : File::Find et find2perl sont là depuis Perl 5, donc ça devrait aller).
Il trouve toutes les alternatives dans un fichier.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#!/usr/bin/perl 
use strict; use warnings;
use Regexp::Trie;
 
# read and hash grep file
die "Specify a grepfile and then the args for find"
    unless @ARGV > 1;
 
open my($alt_file), '<', shift
    or die "$!\n";
 
my $count;
$| = 1;
my $trie = Regexp::Trie->new;
while( <$alt_file> ) {
    chomp;
    $trie->add($_);
    ++$count % 1000 or print "$count\r";
}
print "$count\n";
close $alt_file;
 
my $rx = $trie->regexp;
undef $trie;
$rx = qr/\b($rx)\b/;
 
defined( my $pid = open my($codegen), '-|' )
  or die "The fork before find2perl invocation has failed : $!\n";
if( $pid ) { # parent
    my $code = do { local $/; <$codegen> };
    eval($code);
    die "The eval failed : $@\n" if $@;
} else { # child
    exec('find2perl', @ARGV, '-eval', <<'CODE' );
open my($in), "<", $_
    or die "Couldn't read $name : $!\n";
my $content = do { local $/; <$in> };
while ( $content =~ m/$rx/g ) { print "$name : $1 !\n"; }
close $in;
CODE
    die "exec failed in the child : $!\n"; 
}
 
__END__

--
Jedaï

Citation:
Envoyé par Jedai
Je crois que tu n'as pas bien compris : la compilation de la regex n'a aucun intérêt si tu ne la réutilises pas plusieurs fois. Voici un petit exemple de script qui réutilises sa regexp, il permet d'utiliser les mêmes arguments que find, mais utilise find2perl en sous-main pour convertir ça en utilisation de File::Find (NB : File::Find et find2perl sont là depuis Perl 5, donc ça devrait aller).
Il trouve toutes les alternatives dans un fichier.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #!/usr/bin/perl use strict; use warnings; use Regexp::Trie; # read and hash grep file die "Specify a grepfile and then the args for find" unless @ARGV > 1; open my($alt_file), '<', shift or die "$!\n"; my $count; $| = 1; my $trie = Regexp::Trie->new; while( <$alt_file> ) { chomp; $trie->add($_); ++$count % 1000 or print "$count\r"; } print "$count\n"; close $alt_file; my $rx = $trie->regexp; undef $trie; $rx = qr/\b($rx)\b/; defined( my $pid = open my($codegen), '-|' ) or die "The fork before find2perl invocation has failed : $!\n"; if( $pid ) { # parent my $code = do { local $/; <$codegen> }; eval($code); die "The eval failed : $@\n" if $@; } else { # child exec('find2perl', @ARGV, '-eval', <<'CODE' ); open my($in), "<", $_ or die "Couldn't read $name : $!\n"; my $content = do { local $/; <$in> }; while ( $content =~ m/$rx/g ) { print "$name : $1 !\n"; } close $in; CODE die "exec failed in the child : $!\n"; } __END__
--
Jedaï
OK merci, je comprends bien ta remarque sur la réutilisation. Tu veux dire qu'en cas de match unique il y a un temps de compilation de regexp et un temps d'utilisation de celle-ci, et qu'en conséquence le bénéfice ne se mesure qu'à la seconde utilisation ou la compil ne sera pas refaite. Fair enough; je vais essayer d'utiliser le find pour ma culture perso. Ta solution est un peu complexe à lire, il y a certaines parties que je ne comprends pas; ok pour le fork ou encore l'eval du CODE <<'here', mais pour ce qui est des var. comme $codegen, je ne vois pas d'où ça sort (la façon dont le fork fonctionne n perl serait de créer un $codegen avec "-|" ??? pour que le fils l'évalue ?)... il faudra que je pousse mon investigation sur Perl pour profiter de ton exemple de Perl "élégant" mais peu lisible pour un novice (or chez nous tout le monde est novice en perl puisqu'on n'en fait pas).

Je vais donc rester sur du code intelligible pour le commun des mortels-dév :mrgreen:

Merci encore en tout cas.

PS: mes scripts pas parfaits ont tourné (lentement mais sûrement) donc je considère le sujet clos et édite l'entête en conséquence.

Version commentée :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#!/usr/bin/perl 
use strict; use warnings;
use Regexp::Trie;
 
# vérification du nombre d'arguments, ou bref message d'erreur
die "Specify a grepfile and then the args for find"
    unless @ARGV > 1;
 
open my($alt_file), '<', shift
    or die "$!\n";
 
# Construction de l'objet Regexp::Trie
my $count;
$| = 1;
my $trie = Regexp::Trie->new;
while( <$alt_file> ) {
    chomp;
    $trie->add($_);
    ++$count % 1000 or print "$count\r";
}
print "$count\n";
close $alt_file;
 
# on récupère la regexp construite par Regexp::Trie
my $rx = $trie->regexp;
# on détruit explicitement le Regexp::Trie dont on a plus besoin
undef $trie;
# on finalise la regex en rajoutant les limites de mots et la capture
$rx = qr/\b($rx)\b/;
 
# on ouvre un pipe en lecture à partir de la commande find2perl
# $codegen est le handle d'où l'on peut lire le code généré par
# find2perl
open my($codegen), '-|', 'find2perl', @ARGV, '-eval', <<'CODE'
open my($in), "<", $_
    or die "Couldn't read $name : $!\n";
my $content = do { local $/; <$in> };
while ( $content =~ m/$rx/g ) { print "$name : $1 !\n"; }
close $in;
CODE
  or die "The fork and find2perl invocation has failed : $!\n";
 
# find2perl génère un code Perl mimiquant la recherche d'un find avec les 
# mêmes arguments, et appliquant à chacun des fichiers trouvé
# notre regex précompilée, on place ce code dans $code
my $code = do { local $/; <$codegen> };
 
# on évalue le code récupéré, c'est ici que le gros du boulot est 
# effectué
eval($code);
 
# $@ est faux sauf si le eval() a échoué
die "The eval failed : $@\n" if $@;
 
__END__

--
Jedaï

Citation:

Envoyé par Jedai

Version commentée :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#!/usr/bin/perl 
use strict; use warnings;
use Regexp::Trie;
 
# vérification du nombre d'arguments, ou bref message d'erreur
die "Specify a grepfile and then the args for find"
    unless @ARGV > 1;
 
open my($alt_file), '<', shift
    or die "$!\n";
 
# Construction de l'objet Regexp::Trie
my $count;
$| = 1;
my $trie = Regexp::Trie->new;
while( <$alt_file> ) {
    chomp;
    $trie->add($_);
    ++$count % 1000 or print "$count\r";
}
print "$count\n";
close $alt_file;
 
# on récupère la regexp construite par Regexp::Trie
my $rx = $trie->regexp;
# on détruit explicitement le Regexp::Trie dont on a plus besoin
undef $trie;
# on finalise la regex en rajoutant les limites de mots et la capture
$rx = qr/\b($rx)\b/;
 
# on ouvre un pipe en lecture à partir de la commande find2perl
# $codegen est le handle d'où l'on peut lire le code généré par
# find2perl
open my($codegen), '-|', 'find2perl', @ARGV, '-eval', <<'CODE'
open my($in), "<", $_
    or die "Couldn't read $name : $!\n";
my $content = do { local $/; <$in> };
while ( $content =~ m/$rx/g ) { print "$name : $1 !\n"; }
close $in;
CODE
  or die "The fork and find2perl invocation has failed : $!\n";
 
# find2perl génère un code Perl mimiquant la recherche d'un find avec les 
# mêmes arguments, et appliquant à chacun des fichiers trouvé
# notre regex précompilée, on place ce code dans $code
my $code = do { local $/; <$codegen> };
 
# on évalue le code récupéré, c'est ici que le gros du boulot est 
# effectué
eval($code);
 
# $@ est faux sauf si le eval() a échoué
die "The eval failed : $@\n" if $@;
 
__END__

--
Jedaï

OK, vu, merci :)

Voir 40 message(s) de cette discussion en une page