Benötigen Sie etwas, das schneller ist als "wc -l"

12

Denn eine wirklich große Datei wie 1 GB wc -list langsam. Haben wir eine schnellere Möglichkeit, die Anzahl der Zeilenumbrüche für eine bestimmte Datei zu berechnen?

Prosti
quelle
25
Schnellere Festplatten kaufen? Da jedes Byte der Eingabe auf seine 0x0AUnversehrtheit überprüft werden muss, ist E / A zweifellos der Engpass.
Thrig
2
Wenn Sie den Verdacht wchaben, zu viel Overhead zu haben, können Sie versuchen, Ihren eigenen zu implementieren foreach byte in file: if byte == '\n': linecount++. Wenn es in C oder Assembler implementiert ist, wird es meiner Meinung nach nicht schneller, außer vielleicht im Kernelbereich eines RTOS mit höchster Priorität (oder verwenden Sie dafür sogar einen Interrupt - Sie können einfach nichts anderes mit dem System tun. .. in Ordnung, ich schweife ab ;-))
Murphy
3
Und nur um ein Gefühl für die Skalierung zu bekommen, habe ich time wc -l some_movie.avieine nicht zwischengespeicherte Datei schnell bearbeitet, was dazu führte 5172672 some_movie.avi -- real 0m57.768s -- user 0m0.255s -- sys 0m0.863s. Was @thrig im Grunde als richtig erweist, erschüttert I / O in diesem Fall Ihre Leistung.
Murphy
10
Der beste Weg, um zu zeigen, dass es sich um einen Festplatten-E / A-Engpass handelt, time wc -l some_large_file_smaller_than_cachezweimal hintereinander durchzuführen und zu sehen, wie schnell der zweite Vorgang ist, time wc -l some_large_file_larger_than_cacheund dann zu sehen, wie sich die Zeit zwischen den Läufen nicht ändert. Bei einer Datei mit ~ 280 MB beträgt die Zeit zwischen 1,7 Sekunden und 0,2 Sekunden, bei einer Datei mit 2 GB jedoch beide Male 14 Sekunden.
EightBitTony
1
Wie langsam ist dir zu langsam? Was /usr/bin/time wc -l <file>sagt das aus? Was ist Ihre Hardware? Ist es schneller, wenn Sie den Befehl wiederholt ausführen? Wir brauchen wirklich mehr Informationen;)
marcelm

Antworten:

21

Sie können versuchen , in C zu schreiben:

#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;
}

Speichern Sie zB, wcl.ckompilieren Sie zB mit gcc wcl.c -O2 -o wclund führen Sie mit aus

<yourFile ./wcl

Dadurch werden in etwa 370 ms (wiederholte Durchläufe) Zeilenumbrüche in einer 1-GB-Datei auf meinem System angezeigt . (Durch Erhöhen der Puffergröße wird die zu erwartende Zeit geringfügig verlängert - BUFSIZ sollte nahezu optimal sein.) Dies ist sehr vergleichbar mit den ~ 380 ms , von denen ich komme wc -l.

Mmaping gibt mir eine bessere Zeit von ungefähr 280 ms , aber es hat natürlich die Einschränkung, auf echte Dateien beschränkt zu sein (kein FIFOS, keine Terminaleingabe usw.):

#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;
}

Ich habe meine Testdatei erstellt mit:

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

und fügte einige Test-Zeilenumbrüche hinzu mit:

 $ echo >> 1GB 

und ein Hex-Editor.

PSkocik
quelle
Ich war überrascht über das mmap-Ergebnis TBH. Früher dachte ich, mmaping sei schneller als Lesen / Schreiben, aber dann sah ich einige Linux-Benchmarks, die das Gegenteil zeigten. Sieht so aus, als ob es in diesem Fall sehr wahr ist.
PSkocik
4
mmap wird unter Linux erheblich bessere Ergebnisse erzielen, da es heutzutage großen Seiten zugeordnet wird und TLB-Fehler nur langsam auftreten.
Bis zum
Das Lesen verschiedener Teile der Datei in separaten Threads (z. B. mit einer OpenMP- forSchleife) kann von Vorteil sein, sodass einige Fortschritte erzielt werden können, während ein Thread auf die Eingabe wartet. Auf der anderen Seite kann dies die E / A-Planung behindern. Ich kann es also nur empfehlen, es auszuprobieren und zu messen!
Toby Speight
Die read()Version kann von Vorauslesen profitieren.
Barmar
1
@TobySpeight Ja, Multithreading könnte es beschleunigen. Auch das Scannen von zwei Bytes gleichzeitig über 2 ^ 16 Nachschlagetabellen lieferte eine ziemlich gute Beschleunigung, als ich das letzte Mal damit spielte.
PSkocik
18

Sie können die von @pskocik vorgeschlagene Lösung verbessern, indem Sie die Anzahl der Anrufe auf reduzieren read. Es gibt viele Aufrufe zum Lesen von BUFSIZChunks aus einer 1-GB-Datei. Der übliche Ansatz hierfür ist das Erhöhen der Puffergröße:

  • Versuchen Sie nur zum Spaß, die Puffergröße um den Faktor 10 oder 100 zu BUFSIZerhöhen . Auf meinem Debian 7 ist es 8192. Mit dem ursprünglichen Programm sind das 120.000 Lesevorgänge. Sie können sich wahrscheinlich einen 1-MB-Eingabepuffer leisten, um diesen um den Faktor 100 zu reduzieren.
  • Für einen optimaleren Ansatz können Anwendungen einen Puffer zuweisen, der so groß wie die Datei ist und einen einzelnen Lesevorgang erfordert. Das funktioniert gut genug für "kleine" Dateien (obwohl einige Leser mehr als 1 GB auf ihrem Computer haben).
  • Schließlich können Sie mit speicherabgebildeten E / A experimentieren, die die Zuordnung als solche behandelt.

Beachten Sie beim Benchmarking der verschiedenen Ansätze möglicherweise, dass einige Systeme (z. B. Linux) den größten Teil des nicht verwendeten Speichers Ihres Computers als Festplatten-Cache verwenden. Vor einiger Zeit (vor fast 20 Jahren, erwähnt in den abscheulichen FAQ ) war ich verwirrt über unerwartet gute Ergebnisse eines (nicht sehr guten) Paging-Algorithmus, den ich entwickelt hatte, um mit Bedingungen mit wenig Speicher in einem Texteditor umzugehen. Mir wurde erklärt, dass es schnell lief, weil das Programm aus den Speicherpuffern arbeitete, die zum Lesen der Datei verwendet wurden, und dass es nur dann einen Geschwindigkeitsunterschied geben würde, wenn die Datei erneut gelesen oder geschrieben würde.

Gleiches gilt für mmap(in einem anderen Fall, der noch auf meiner To-Do-Liste steht, um ihn in eine FAQ aufzunehmen, meldete ein Entwickler sehr gute Ergebnisse in einem Szenario, in dem der Festplatten-Cache der eigentliche Grund für Verbesserungen war). Die Entwicklung von Benchmarks erfordert Zeit und Sorgfalt, um die Gründe für die gute (oder schlechte) Leistung zu analysieren.

Weiterführende Literatur:

Thomas Dickey
quelle
2
Sie überschätzen den Einfluss von Puffergrößen über einem bestimmten Schwellenwert. In der Regel hilft das Erhöhen der Puffergröße über 4 KB hinaus nicht viel und kann sich sogar nachteilig auswirken, da der Puffer möglicherweise aus dem L1-Cache verschoben wird. Auf meinem Computer ist das Testen mit 1- ddMB-Puffern langsamer als 8 KB. Der Standardwert von 8 KB für wc ist eigentlich ziemlich gut gewählt und für eine Vielzahl von Systemen nahezu optimal.
Marcelm