Besoin de quelque chose de plus rapide que «wc -l»

12

Pour un très gros fichier comme 1 Go, wc -lil s'avère être lent. Avons-nous un moyen plus rapide de calculer le nombre de sauts de ligne pour un fichier particulier?

prosti
la source
25
Acheter des disques plus rapides? Étant donné que chaque octet de l'entrée doit être inspecté pour son 0x0Ainess, les E / S sont sans aucun doute le goulot d'étranglement.
thrig
2
Si vous pensez wcavoir trop de frais généraux, vous pouvez essayer d'implémenter le vôtre foreach byte in file: if byte == '\n': linecount++. S'il est implémenté en C ou en assembleur, je ne pense pas que cela va être plus rapide, sauf peut-être dans l'espace du noyau sur un RTOS avec la plus haute priorité (ou même utiliser une interruption pour cela - vous ne pouvez tout simplement rien faire d'autre avec le système. .. d'accord, je m'égare ;-))
Murphy
3
Et juste pour avoir une idée de l'échelle, j'ai fait un rapide time wc -l some_movie.avisur un fichier non mis en cache, ce qui a entraîné 5172672 some_movie.avi -- real 0m57.768s -- user 0m0.255s -- sys 0m0.863s. Ce qui prouve que @thrig a raison, les E / S anéantissent vos performances dans ce cas.
Murphy
10
Le meilleur moyen de montrer qu'il s'agit d'un goulot d'étranglement d'E / S sur disque, de faire time wc -l some_large_file_smaller_than_cachedeux fois de suite rapidement et de voir à quelle vitesse la deuxième opération est, puis de time wc -l some_large_file_larger_than_cachevoir comment le temps ne change pas entre les exécutions. Pour un fichier de ~ 280 Mo ici, le temps passe de 1,7 seconde à 0,2 seconde, mais pour un fichier de 2 Go, c'est 14 secondes les deux fois.
EightBitTony
1
Comment lent est trop lent pour vous? Que /usr/bin/time wc -l <file>dit-on, quel est votre matériel? Est-ce plus rapide si vous exécutez la commande à plusieurs reprises? Nous avons vraiment besoin de plus d'informations;)
marcelm

Réponses:

21

Vous pouvez essayer d' écrire en C:

#include <unistd.h>
#include <stdio.h>
#include <string.h>
int main(){
  char buf[BUFSIZ];
  int nread;
  size_t nfound=0;
  while((nread=read(0, buf, BUFSIZ))>0){
    char const* p;
    for(p=buf; p=memchr(p,'\n',nread-(p-buf)); nfound++,p++) {;}
  }
  if(nread<0) { perror("Error"); return 1; }
  printf("%lu\n", nfound);
  return 0;
}

Enregistrer par exemple, wcl.ccompiler par exemple avec gcc wcl.c -O2 -o wclet exécuter avec

<yourFile ./wcl

Cela trouve des sauts de ligne saupoudrés dans un fichier de 1 Go sur mon système en environ 370 ms ( cycles répétés). (L'augmentation de la taille des tampons augmente légèrement le temps, ce qui est normal - BUFSIZ devrait être presque optimal). C'est très comparable aux ~ 380 ms dont je viens wc -l.

Mmaping me donne un meilleur temps d'environ 280 ms , mais il a bien sûr la limitation d'être limité aux fichiers réels (pas de FIFOS, pas d'entrée de terminal, etc.):

#include <stdio.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>
int main(){
  struct stat sbuf;
  if(fstat(0, &sbuf)<0){ perror("Can't stat stdin"); return 1; }

  char* buf = mmap(NULL, sbuf.st_size, PROT_READ, MAP_PRIVATE, 0/*stdin*/, 0/*offset*/);
  if(buf == MAP_FAILED){ perror("Mmap error"); return 1; } 

  size_t nread = sbuf.st_size, nfound=0;
  char const* p;
  for(p=buf; p=memchr(p,'\n',nread-(p-buf)); nfound++,p++) {;}

  printf("%lu\n", nfound);
  return 0;
}

J'ai créé mon fichier de test avec:

 $ dd if=/dev/zero of=file bs=1M count=1042 

et ajouté quelques nouvelles lignes de test avec:

 $ echo >> 1GB 

et un éditeur hexadécimal.

PSkocik
la source
J'ai été surpris du résultat mmap TBH. Je pensais que le mmaping était plus rapide que la lecture / écriture, mais j'ai ensuite vu des benchmarks Linux qui montraient le contraire. On dirait que c'est très vrai dans ce cas.
PSkocik
4
mmap va obtenir de bien meilleurs résultats sur linux car il sera mappé sur des pages énormes ces jours-ci, et les échecs TLB sont trop lentswwwwww.
jthill
Il peut être avantageux de lire différentes parties du fichier dans des threads séparés (par exemple avec une forboucle OpenMP ) afin que certains progrès puissent être réalisés pendant qu'un thread est bloqué en attente d'entrée. Mais d'un autre côté, cela peut entraver la planification des E / S, donc tout ce que je peux recommander est de l'essayer et de mesurer!
Toby Speight
La read()version peut bénéficier d'une lecture anticipée.
Barmar
1
@TobySpeight Oui, le multithreading pourrait l'accélérer. La recherche de deux octets à la fois via des tables de recherche 2 ^ 16 a également fourni une assez bonne vitesse la dernière fois que j'ai joué avec.
PSkocik
18

Vous pouvez améliorer la solution proposée par @pskocik en réduisant le nombre d'appels vers read. Il y a beaucoup d'appels pour lire des BUFSIZmorceaux à partir d'un fichier 1 Go. L'approche habituelle consiste à augmenter la taille du tampon:

  • juste pour le plaisir, essayez d'augmenter la taille de la mémoire tampon d'un facteur 10. Ou 100. Sur mon Debian 7, BUFSIZc'est 8192. Avec le programme d'origine, c'est 120 000 opérations de lecture. Vous pouvez probablement vous permettre un tampon d'entrée de 1 Mo pour le réduire d'un facteur 100.
  • pour une approche plus optimale, les applications peuvent allouer un tampon aussi grand que le fichier, nécessitant une seule opération de lecture. Cela fonctionne assez bien pour les "petits" fichiers (bien que certains lecteurs aient plus de 1 Go sur leur machine).
  • enfin, vous pouvez expérimenter avec des E / S mappées en mémoire, qui gèrent l'allocation en tant que telle.

Lors de l'analyse comparative des différentes approches, vous pouvez garder à l'esprit que certains systèmes (tels que Linux) utilisent la plupart de la mémoire inutilisée de votre machine comme cache disque. Il y a quelque temps (il y a près de 20 ans, mentionné dans la vile FAQ ), j'étais perplexe devant les bons résultats inattendus d'un algorithme de pagination (pas très bon) que j'avais développé pour gérer les conditions de faible mémoire dans un éditeur de texte. On m'a expliqué qu'il fonctionnait rapidement parce que le programme fonctionnait à partir des tampons de mémoire utilisés pour lire le fichier, et que seulement si le fichier était relu ou écrit, il y aurait une différence de vitesse.

La même chose s'applique à mmap(dans un autre cas toujours sur ma liste de tâches à intégrer dans une FAQ, un développeur a rapporté de très bons résultats dans un scénario où le cache disque était la raison réelle de l'amélioration). L'élaboration de repères nécessite du temps et du soin pour analyser les raisons de la bonne (ou mauvaise) performance.

Lectures complémentaires:

Thomas Dickey
la source
2
Vous surestimez l'influence des tailles de tampons au-dessus d'un certain seuil. En règle générale, l'augmentation de la taille du tampon au-delà de 4KB n'aide pas beaucoup, et peut en fait être préjudiciable car elle peut pousser le tampon hors du cache L1. Sur ma machine, les tests avec dd, en utilisant des tampons de 1 Mo sont plus lents que 8 Ko . La valeur par défaut de 8 Ko pour wc est en fait assez bien choisie, elle sera presque optimale pour une large gamme de systèmes.
marcelm