{"id":3512,"date":"2013-04-08T08:00:46","date_gmt":"2013-04-08T07:00:46","guid":{"rendered":"http:\/\/www.blaess.fr\/christophe\/?p=3512"},"modified":"2013-04-07T16:33:10","modified_gmt":"2013-04-07T15:33:10","slug":"optimiser-les-recherches-recursives-avec-xargs","status":"publish","type":"post","link":"https:\/\/www.blaess.fr\/christophe\/2013\/04\/08\/optimiser-les-recherches-recursives-avec-xargs\/","title":{"rendered":"Optimiser les recherches r\u00e9cursives avec xargs"},"content":{"rendered":"

\"Find<\/a>Lors de l’\u00e9criture d’un script shell on est souvent amen\u00e9 \u00e0 rechercher une cha\u00eene de caract\u00e8res ou une expression r\u00e9guli\u00e8re dans un ensemble de fichiers. Un exemple typique consiste \u00e0 rechercher les utilisations d’une fonction dans une arborescence de fichiers sources. Plusieurs possibilit\u00e9s s’offrent \u00e0 nous mais elles ne sont pas \u00e9quivalentes en terme d’efficacit\u00e9.<\/p>\n

\n\n<\/p>\n

Prenons \u00e0 titre d’exemple les sources du noyau Linux (version 3.5.7) fra\u00eechement d\u00e9compress\u00e9es \u00e0 partir de l’archive .tar.bz2<\/code>. Nous souhaitons retrouver les occurrences d’une certaine cha\u00eene de caract\u00e8res.<\/p>\n

On descend l’arborescence des fichiers avec find<\/code>, en filtrant \u00e9ventuellement les fichiers en fonction de leurs extensions. Ici, nous rechercherons par exemple tous les fichiers dont l’extension est .c<\/code> ou .h<\/code>.<\/p>\n

[linux-3.5.7]$ find . -name '*.[ch]'<\/strong>\n.\/mm\/kmemcheck.c\n.\/mm\/mmzone.c\n.\/mm\/swapfile.c\n  [...]\n.\/include\/pcmcia\/cistpl.h\n.\/include\/pcmcia\/cisreg.h\n.\/include\/pcmcia\/ciscode.h\n[linux-3.5.7]$<\/pre>\n
L’utilitaire wc<\/code> (Word Count<\/i>) nous permet de compter le nombre de lignes de sortie.<\/p>\n
[linux-3.5.7]$ find . -name '*.[ch]' | wc -l<\/strong>\n31384\n[linux-3.5.7]$<\/pre>\n
Nous d\u00e9sirons \u00e0 pr\u00e9sent rechercher dans ces 31384 fichiers les occurrences d’une cha\u00eene de caract\u00e8res, prenons par exemple \u00ab\u00a0task_group<\/code>\u00ab\u00a0.<\/p>\n
\u00c9videmment la recherche<\/p>\n
[linux-3.5.7]$ find . -name '*.[ch]' | grep task_group<\/strong><\/pre>\n
ne donne aucun r\u00e9sultat, car grep<\/code> agit en recherchant la cha\u00eene dans la liste des fichiers, dans leurs noms, sans examiner leurs contenus.<\/p>\n
La solution la plus connue pour r\u00e9soudre ce probl\u00e8me est d’utiliser l’option -exec<\/code> de find<\/code>. Cette approche fonctionne bien.<\/p>\n
[linux-3.5.7]$ find . -name '*.[ch]' -exec grep task_group {} \\;<\/strong>\nstatic void print_cfs_group_stats(struct seq_file *m, int cpu, struct task_group *tg)\nstatic char *task_group_path(struct task_group *tg)\n[...]\nextern int sched_group_set_rt_period(struct task_group *tg,\nextern long sched_group_rt_period(struct task_group *tg);\nextern int sched_rt_can_attach(struct task_group *tg, struct task_struct *tsk);\n[linux-3.5.7]$<\/pre>\n
La syntaxe de l’option -exec<\/code> de find<\/code> est un peu curieuse : elle ex\u00e9cute pour chaque fichier s\u00e9lectionn\u00e9 pendant la descente de l’arborescence la commande indiqu\u00e9e en argument (ici grep task_group<\/code>) apr\u00e8s avoir remplac\u00e9 le motif {}<\/code> par le nom du fichier consid\u00e9r\u00e9. Un point-virgule final est n\u00e9cessaire pour que find<\/code> trouve la d\u00e9limitation de la commande \u00e0 ex\u00e9cuter. Il faut prot\u00e9ger ce point-virgule de l’interpr\u00e9tation du shell par un backslash \\<\/code>.<\/p>\n
Comme je l’ai dit plus haut, cette commande fonctionne correctement. Toutefois je trouve son efficacit\u00e9 m\u00e9diocre. Relan\u00e7ons-l\u00e0 \u00e0 plusieurs reprises afin de se d\u00e9barrasser des effets de remplissage initial du cache disque et chronom\u00e9trons son temps d’ex\u00e9cution avec la commande time<\/code> du shell. En outre, le r\u00e9sultat du grep<\/code> ne m’int\u00e9ressant pas r\u00e9ellement ici, je l’ai redirig\u00e9 vers \/dev\/null<\/code> pour limiter le temps d\u00fb \u00e0 la gestion du terminal.<\/p>\n
[linux-3.5.7]$ time  find . -name '*.[ch]' -exec grep task_group {} \\; > \/dev\/null <\/strong>\nreal\t0m42.712s<\/strong>\nuser\t0m0.540s\nsys\t0m3.796s\n[linux-3.5.7]$<\/pre>\n
42 secondes. Continuons…<\/p>\n
[linux-3.5.7]$ time  find . -name '*.[ch]' -exec grep task_group {} \\; > \/dev\/null <\/strong>\nreal\t0m42.999s<\/strong>\nuser\t0m0.496s\nsys\t0m3.868s\n[linux-3.5.7]$ time  find . -name '*.[ch]' -exec grep task_group {} \\; > \/dev\/null <\/strong>\nreal\t0m43.015s\nuser\t0m0.504s\nsys\t0m3.880s\n[linux-3.5.7]$ time  find . -name '*.[ch]' -exec grep task_group {} \\; > \/dev\/null<\/strong> \nreal\t0m42.776s\nuser\t0m0.476s\nsys\t0m3.820s\n[linux-3.5.7]$<\/pre>\n
Nous avons donc un temps d’ex\u00e9cution assez homog\u00e8ne de 42 \u00e0 43 secondes. Ce qui me g\u00eane c’est que la commande grep<\/code> est ex\u00e9cut\u00e9e de mani\u00e8re ind\u00e9pendante pour chaque fichier s\u00e9lectionn\u00e9. Il y a plus de 31000 fichiers, et nous lancerons donc plus de 31000 processus grep<\/code> successifs, avec pour chacun d’eux un appel-syst\u00e8me fork()<\/code> pour cr\u00e9er une m\u00e9moire virtuelle, un execve()<\/code> pour charger le code ex\u00e9cutable, etc.<\/p>\n
Essayons une autre approche : la commande xargs<\/code>. Elle prend une commande en argument et l’ex\u00e9cute apr\u00e8s avoir d\u00e9ploy\u00e9 tout ce qu’elle a re\u00e7u sur son entr\u00e9e standard sur la ligne d’arguments de la commande.<\/p>\n
Ici, xargs<\/code> recevra toute la liste des fichiers s\u00e9lectionn\u00e9s par find<\/code>, et les \u00e9num\u00e9rera en arguments sur la ligne de commande de grep<\/code> avant de le lancer. Bien entendu, si le syst\u00e8me impose des limites sur la longueur maximale d’une ligne, xargs<\/code> relancera la commande aussi souvent qu’il le faudra pour analyser ses 31000 fichiers d’entr\u00e9e. Mais il ne devrait au final n’y avoir qu’un (ou quelques-uns) processus grep<\/code> cr\u00e9\u00e9.<\/p>\n
V\u00e9rifions :<\/p>\n
[linux-3.5.7]$ time  find . -name '*.[ch]' | xargs grep task_group  > \/dev\/null <\/strong> \nreal\t0m0.560s<\/strong>\nuser\t0m0.256s\nsys\t0m0.400s\n[linux-3.5.7]$ time  find . -name '*.[ch]' | xargs grep task_group  > \/dev\/null<\/strong> \nreal\t0m0.551s<\/strong>\nuser\t0m0.292s\nsys\t0m0.360s\n[linux-3.5.7]$ time  find . -name '*.[ch]' | xargs grep task_group  > \/dev\/null<\/strong> \nreal\t0m0.557s<\/strong>\nuser\t0m0.272s\nsys\t0m0.376s\n[linux-3.5.7]$<\/pre>\n
Surprenant non ? Nous passons d’un temps d’ex\u00e9cution de 42 secondes \u00e0 0,56 secondes, soit un facteur 75 ! C’est simplement le co\u00fbt de cr\u00e9ation de plus de 31000 processus qui a disparu au profit de la cr\u00e9ation d’un seul processus.<\/p>\n
Voici une bonne piste d’optimisation pour vos scripts qui parcourent des arborescences avec find<\/code> pour r\u00e9aliser un traitement : essayez autant que possible de cumuler les appels \u00e0 la commande de traitement dans un xargs<\/code> plut\u00f4t que des les invoquer en s\u00e9quence avec -exec<\/code>.<\/p>","protected":false},"excerpt":{"rendered":"
Lors 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é.<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8,13],"tags":[],"class_list":["post-3512","post","type-post","status-publish","format-standard","hentry","category-linux-2","category-shell"],"_links":{"self":[{"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/posts\/3512","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/comments?post=3512"}],"version-history":[{"count":11,"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/posts\/3512\/revisions"}],"predecessor-version":[{"id":3515,"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/posts\/3512\/revisions\/3515"}],"wp:attachment":[{"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/media?parent=3512"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/categories?post=3512"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/tags?post=3512"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}