Pourquoi le wc est-il si lent?

Pourquoi l'utilitaire wc est-il si lent?

Lorsque je l'exécute sur un fichier volumineux, cela prend environ 20 fois plus longtemps que md5sum:

MyDesktop:/tmp$ dd if=/dev/zero bs=1024k count=1024 of=/tmp/bigfile
1024+0 records in
1024+0 records out
1073741824 bytes (1.1 GB) copied, 0.687094 s, 1.6 GB/s

MyDesktop:/tmp$ time wc /tmp/bigfile 
         0          0 1073741824 /tmp/bigfile

real    0m45.969s
user    0m45.424s
sys     0m0.424s

MyDesktop:/tmp$ time md5sum /tmp/bigfile 
cd573cfaace07e7949bc0c46028904ff  /tmp/bigfile

real    0m2.520s
user    0m2.196s
sys     0m0.316s

Ce n'est pas seulement une condition de bord étrange causée par le fichier plein de valeurs nulles, je vois la même différence de performances même si le fichier est rempli de données aléatoires ou est un fichier texte.

(c'est sur Ubuntu 13.04, 64 bits)

performance wc Johnny
la source

Remarque pour ceux qui ne se soucient que du nombre de lignes: wc -l <nom de fichier> est beaucoup plus rapide sur les très gros fichiers.

Réponses:

Je suis donc allé à la source, et il semble que la lenteur réside dans la gestion des caractères à deux octets. Essentiellement, pour chaque caractère lu, il doit appeler mbrtowc()pour essayer de le convertir en caractère large, puis ce caractère large est testé pour voir s'il s'agit d'un séparateur de mots, d'un séparateur de lignes, etc.

En effet, si je change ma LANGvariable locale par défaut en_US.UTF-8(UTF-8 est un jeu de caractères multi-octets) et que je la mets à " C" (jeu de caractères simple à un octet), je peux wcutiliser des optimisations à un octet, ce qui l'accélère considérablement, en prenant seulement environ un quart aussi longtemps qu'avant.

De plus, il n'a qu'à vérifier chaque caractère s'il compte les mots ( -w), la longueur de ligne ( -L) ou le caractère ( -m). S'il ne fait que compter les octets et / ou les lignes, il peut ignorer la gestion des caractères larges, puis il s'exécute extrêmement rapidement - plus rapidement quemd5sum .

Je l' ai couru à travers gprof, et les fonctions qui sont utilisées pour gérer les caractères multi - octets ( mymbsinit(), mymbrtowc(), myiswprint(), etc.) prenez environ 30% du temps d'exécution seul, et le code qui étapes à travers la mémoire tampon est beaucoup plus complexe parce qu'il doit gérer les étapes de taille variable dans le tampon pour les caractères de taille variable, ainsi que rembourrer tous les caractères partiellement complétés qui s'étendent sur le tampon jusqu'au début du tampon afin qu'il puisse être géré la prochaine fois.

Maintenant que je sais quoi chercher, j'ai trouvé quelques articles mentionnant la lenteur de l'utf-8 avec certains utilitaires:

/programming/13913014/grepping-a-huge-file-80gb-any-way-to-speed-it-up http://dtrace.org/blogs/brendan/2011/12/08 / 2000x-performance-win /

Johnny
la source

Oh, je viens de réaliser que vous êtes OP. : p

Ivan Chau

Bien que ce soit la réponse la plus votée, elle n'est pas pertinente. md5sumne vous permettra jamais de compter le nombre de mots et wcne calculera pas le hachage md5 du fichier! C'est comme demander pourquoi ma voiture est si lente par rapport à ma machine à écrire lors de l'écriture de texte.

user49468

@ user49468: Il est raisonnable de supposer que les deux sont liés aux E / S, car les deux doivent lire chaque octet du fichier d'entrée. Cette réponse prouve qu'en wcfait est liée au CPU, lors du traitement de caractères multi-octets.

MSalters

@ user49468: wc et md5sum peuvent faire des choses différentes, mais à la fois lire un fichier et faire un calcul relativement simple, on calcule une somme de contrôle, on compte des octets, des séparateurs de mots et des sauts de ligne. Eh bien, je pensais que c'était simple, mais je n'avais pas pris en compte la complexité supplémentaire des jeux de caractères multi-octets. C'est plus comme demander "Pourquoi ma voiture va-t-elle 20 fois plus vite au magasin que ma mini-fourgonnette?" Vous vous attendez à une différence entre les deux, mais pas à une différence de 20X.

Johnny

@Johnny votre comparaison voiture / monospace n'a pas l'aspect que les deux sont conçus pour vous transporter au magasin. Une comparaison de vitesse est donc en place. Comparer votre voiture au véhicule de peinture à rayures est plus approprié. Tout simplement parce que les deux utilisent les rues, leur vitesse n'est pas pertinente car le peintre à rayures n'est pas adapté pour faire du shopping et vice-versa.

user49468

Juste une supposition, mais vous comparez en quelque sorte les pommes aux oranges en ce qui concerne ce qui wcfait vs ce qui md5sumest en train de faire.

La tâche de md5sum

Lorsque md5sumtraite un fichier, il ouvre simplement le fichier en tant que flux, puis commence à exécuter le flux via la fonction de somme de contrôle MD5 qui nécessite très peu de mémoire. Il est essentiellement lié aux E / S du processeur et du disque.

tâche de wc

Lorsqu'il wcs'exécute, il en fait beaucoup plus que d'analyser le fichier un caractère à la fois. Il doit en fait analyser la structure du fichier, les lignes à la fois déterminant où se trouvent les limites entre les caractères et s'il s'agit d'une limite de mot ou non.

Exemple

Pensez aux chaînes suivantes et à la façon dont chacun des algorithmes devrait les parcourir lors de leur analyse:

“Hello! Greg”
“Hello!Greg”
“Hello\nGreg”
“A.D.D.”
“Wow, how great!”
“wow     \n\n\n    great”
“it was a man-eating shark.”

Pour MD5, il se déplace trivialement à travers ces chaînes un caractère à la fois. Car wcil doit décider ce qu'est une limite de mots et de lignes et garder une trace du nombre d'occurrences qu'il voit.

Discussions supplémentaires sur les WC

J'ai trouvé ce défi de codage de 2006 qui traite de la mise wcen œuvre dans .NET. Les difficultés sont assez évidentes lorsque vous examinez une partie du pseudo-code, cela pourrait donc aider à faire la lumière sur les raisons pour lesquelles il wcsemble être beaucoup plus lent que d'autres opérations.

slm
la source

Vous décrivez quelque chose de différent de la commande wc Unix standard (du moins, pas celle fournie avec Ubuntu). Ce wc ne compte pas des mots uniques , juste des mots, donc "hello hello world" est 3 mots, pas 2.

Johnny

Sur la base de cette théorie, il semble qu'une tâche plus simple, comme compter les lignes, irait plus rapidement. La modification de «wc» pour spécifier un nombre de lignes modifie-t-elle considérablement les résultats? 'wc -l'

Joshua Miller

@Johnny - Je n'ai jamais dit que ça comptait des mots uniques que tu avais dit. wccompte plusieurs choses lors de l'analyse du fichier. Il compte le nombre de mots, de lignes et d'octets lors de l'analyse du fichier. Lisez la page de manuel!

slm

@JoshuaMiller - On ne sait pas si dire wcde ne compter que les lignes limite son analyse interne afin qu'il ne compte que ces choses ou ne signale que les résultats des lignes, même s'il comptait toujours tout.

slm

@slm Vous avez dit que cela comptait des mots uniques, votre exemple dit "Bonjour! Greg ”donne Hello 1, Greg 1 , c'est-à-dire compte pour chaque mot. Et le projet .Net auquel vous avez lié dit "L'une de ses tâches principales est de parcourir un ensemble de données et de compter le nombre de répétitions d'un mot donné. Par exemple, étant donné la phrase" Bonjour, oui bonjour ", cela vous dirait que le mot Bonjour a été utilisé deux fois et le mot oui a été utilisé une fois. " Alors qu'en réalité le résultat de l' écho "Bonjour, oui bonjour" | wc --words , est "3", pas "Hello: 2, Yes: 1"

Johnny