Optimiser les recherches récursives avec xargs

Publié par cpb
Avr 08 2013

Find Xargs GrepLors de l’écriture d’un script shell on est souvent amené à rechercher une chaîne de caractères ou une expression régulière dans un ensemble de fichiers. Un exemple typique consiste à rechercher les utilisations d’une fonction dans une arborescence de fichiers sources. Plusieurs possibilités s’offrent à nous mais elles ne sont pas équivalentes en terme d’efficacité.

Prenons à titre d’exemple les sources du noyau Linux (version 3.5.7) fraîchement décompressées à partir de l’archive .tar.bz2. Nous souhaitons retrouver les occurrences d’une certaine chaîne de caractères.

On descend l’arborescence des fichiers avec find, en filtrant éventuellement les fichiers en fonction de leurs extensions. Ici, nous rechercherons par exemple tous les fichiers dont l’extension est .c ou .h.

[linux-3.5.7]$ find . -name '*.[ch]'
./mm/kmemcheck.c
./mm/mmzone.c
./mm/swapfile.c
  [...]
./include/pcmcia/cistpl.h
./include/pcmcia/cisreg.h
./include/pcmcia/ciscode.h
[linux-3.5.7]$

L’utilitaire wc (Word Count) nous permet de compter le nombre de lignes de sortie.

[linux-3.5.7]$ find . -name '*.[ch]' | wc -l
31384
[linux-3.5.7]$

Nous désirons à présent rechercher dans ces 31384 fichiers les occurrences d’une chaîne de caractères, prenons par exemple “task_group“.

Évidemment la recherche

[linux-3.5.7]$ find . -name '*.[ch]' | grep task_group

ne donne aucun résultat, car grep agit en recherchant la chaîne dans la liste des fichiers, dans leurs noms, sans examiner leurs contenus.

La solution la plus connue pour résoudre ce problème est d’utiliser l’option -exec de find. Cette approche fonctionne bien.

[linux-3.5.7]$ find . -name '*.[ch]' -exec grep task_group {} \;
static void print_cfs_group_stats(struct seq_file *m, int cpu, struct task_group *tg)
static char *task_group_path(struct task_group *tg)
[...]
extern int sched_group_set_rt_period(struct task_group *tg,
extern long sched_group_rt_period(struct task_group *tg);
extern int sched_rt_can_attach(struct task_group *tg, struct task_struct *tsk);
[linux-3.5.7]$

La syntaxe de l’option -exec de find est un peu curieuse : elle exécute pour chaque fichier sélectionné pendant la descente de l’arborescence la commande indiquée en argument (ici grep task_group) après avoir remplacé le motif {} par le nom du fichier considéré. Un point-virgule final est nécessaire pour que find trouve la délimitation de la commande à exécuter. Il faut protéger ce point-virgule de l’interprétation du shell par un backslash \.

Comme je l’ai dit plus haut, cette commande fonctionne correctement. Toutefois je trouve son efficacité médiocre. Relançons-là à plusieurs reprises afin de se débarrasser des effets de remplissage initial du cache disque et chronométrons son temps d’exécution avec la commande time du shell. En outre, le résultat du grep ne m’intéressant pas réellement ici, je l’ai redirigé vers /dev/null pour limiter le temps dû à la gestion du terminal.

[linux-3.5.7]$ time  find . -name '*.[ch]' -exec grep task_group {} \; > /dev/null 
real	0m42.712s
user	0m0.540s
sys	0m3.796s
[linux-3.5.7]$

42 secondes. Continuons…

[linux-3.5.7]$ time  find . -name '*.[ch]' -exec grep task_group {} \; > /dev/null 
real	0m42.999s
user	0m0.496s
sys	0m3.868s
[linux-3.5.7]$ time  find . -name '*.[ch]' -exec grep task_group {} \; > /dev/null 
real	0m43.015s
user	0m0.504s
sys	0m3.880s
[linux-3.5.7]$ time  find . -name '*.[ch]' -exec grep task_group {} \; > /dev/null 
real	0m42.776s
user	0m0.476s
sys	0m3.820s
[linux-3.5.7]$

Nous avons donc un temps d’exécution assez homogène de 42 à 43 secondes. Ce qui me gêne c’est que la commande grep est exécutée de manière indépendante pour chaque fichier sélectionné. Il y a plus de 31000 fichiers, et nous lancerons donc plus de 31000 processus grep successifs, avec pour chacun d’eux un appel-système fork() pour créer une mémoire virtuelle, un execve() pour charger le code exécutable, etc.

Essayons une autre approche : la commande xargs. Elle prend une commande en argument et l’exécute après avoir déployé tout ce qu’elle a reçu sur son entrée standard sur la ligne d’arguments de la commande.

Ici, xargs recevra toute la liste des fichiers sélectionnés par find, et les énumérera en arguments sur la ligne de commande de grep avant de le lancer. Bien entendu, si le système impose des limites sur la longueur maximale d’une ligne, xargs relancera la commande aussi souvent qu’il le faudra pour analyser ses 31000 fichiers d’entrée. Mais il ne devrait au final n’y avoir qu’un (ou quelques-uns) processus grep créé.

Vérifions :

[linux-3.5.7]$ time  find . -name '*.[ch]' | xargs grep task_group  > /dev/null  
real	0m0.560s
user	0m0.256s
sys	0m0.400s
[linux-3.5.7]$ time  find . -name '*.[ch]' | xargs grep task_group  > /dev/null 
real	0m0.551s
user	0m0.292s
sys	0m0.360s
[linux-3.5.7]$ time  find . -name '*.[ch]' | xargs grep task_group  > /dev/null 
real	0m0.557s
user	0m0.272s
sys	0m0.376s
[linux-3.5.7]$

Surprenant non ? Nous passons d’un temps d’exécution de 42 secondes à 0,56 secondes, soit un facteur 75 ! C’est simplement le coût de création de plus de 31000 processus qui a disparu au profit de la création d’un seul processus.

Voici une bonne piste d’optimisation pour vos scripts qui parcourent des arborescences avec find pour réaliser un traitement : essayez autant que possible de cumuler les appels à la commande de traitement dans un xargs plutôt que des les invoquer en séquence avec -exec.

11 Réponses

  1. MisterFreez dit :

    Je ne m’attendais pas à une telle différence…

    Une autre solution consiste à appeler find ainsi :

    find . -name ‘*.[ch]’ -exec grep task_group \{\} \+

    J’en ai profité pour tester avec l’option -F de grep puis avec ack et ag. Ce sont des cas où aucune de ces solutions n’apporte quelque chose. En effet ils cherchent particulièrement à optimiser la recherche de fichier mais ne sont pas fondamentalement plus rapide lors de la recherche de chaine. Il faut à mon avis avoir de très gros fichier pour que -F apporte quelque chose.

    J’ai aussi essayé avec les globbings étendus de mon shell (zsh). zargs a des performances exécrables (c’est entre un find et xargs), mais utiliser directement avec grep (grep task_group **/*[hc](.)) est aussi performant qu’un find+zargs.

    C’est intéressant de savoir ça pour optimiser ses commandes au quotidien je trouve. C’est dommage pour zargs il faudrait que je regarde de plus près ses options.

    • cpb dit :

      Oui, j’ai aussi essayé l’option -F en me disant que grep n’ayant en ce cas pas besoin d’analyser la chaîne fournie comme une expression régulière, irait plus vite. Je n’ai pas remarqué de différence sensible de temps de recherche. Peut-être y en aurait-il sur une expression très complexe (avec des répétitions et des références arrières par exemple), je n’ai pas vérifié.

      L’option -exec commande \+ est en effet maintenant bien implémentée dans la plupart des versions de find. Elle a le même rôle que xargs.

  2. shtouff dit :

    Bon article.

    Attention aux résultats indéterminés avec find / xargs et des noms de fichiers “ésotériques”.

    On peut sécuriser le pipe avec les options -print0 de find et -r0 de xargs

    -r => pas d’exécution si pas d’argument recu dans le pipe,
    -0 => attend que les arguemnts recus dans le pipe soient séparés par ” plutôt que ‘\n’. (Le pendant de -print0 dans find)

    • cpb dit :

      Exact. Si on craint que certains fichiers aient des noms qui puissent être interprétés comme des options de grep (par exemple -v), il est utile de faire suivre le motif recherché par -- (deux tirets successifs). Ceci indique à grep que tout le reste de la ligne de commande est constitué de noms de fichiers et ne contient plus d’option.

      • maison dit :

        Si on veut filtrer ou exclure des fichiers entre le find et le xargs (car find ramène souvent trop de trucs, les .svn par exemple si ça existe encore), les options -print0 et -0 imposent l’utilisation de grep -z -Z.
        Au final la commande est alors robuste, mais du genre pénible à saisir…

  3. MisterFreez dit :

    Encore une dernière chose, si on prend les sources de linux et qu’on les versionne avec git (ou qu’on clone directement depuis le dépôt de linux) on a accès à la commande git-grep sans avoir à filtrer les fichiers elle est aussi rapide que find/xargs.

  4. Fabrice dit :

    Pourquoi ne pas utiliser que grep pour faire la recherche du motif?
    Par exemple:
    $ grep -rn ‘task_group’ –include=*.[ch] .

    Et en plus on a le numéro de ligne avec un peu de couleur 😉

    • cpb dit :

      Bonjour Fabrice

      Il est vrai que si l’on peut utiliser directement grep, la recherche est plus simple, mais l’option -r n’est pas standard (voir http://pubs.opengroup.org/onlinepubs/9699919799/utilities/grep.html), même si elle est reconnue par la plupart des versions de grep actuelles.

      En outre le filtrage avec find permet de sélectionner plus finement (sur le propriétaire, la date de modification, etc).

      PS: alors ? la toolchain pour votre carte marche mieux ? 😉

      • Fabrice dit :

        Salut Christophe,
        Pour la toolchain, j’ai laissé tomber la toolchain de Marvell pour utiliser une de Codesourcery et maintenant U-Boot compile sans erreur…
        Bref, j’ai une solution mas pas d’explication

  5. masao dit :

    À noter qu’il existe aussi ack pour ce genre de trucs : http://beyondgrep.com/

URL de trackback pour cette page